본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

유전자알고리즘에 의한 시간제한을 가지는 차량경로모델
Heuristic Model for Vehicle Routing Problem with Time Constrained Based on Genetic Algorithm

이상철    (Department of Business Administration, Tongmyong University   ); 류정철    (Dept. of Management Information, Kyungnam College of Information & Technology  );
  • 초록

    시간제한을 가지는 차량경로문제는 배송 및 물류에서 가장 중요한 문제 중의 하나이다. 현실적으로 고객의 서비스를 위하여 정해진 시간 안에 출발해서 배송을 끝마쳐야 한다. 그러므로 본 연구는 개선된 유전자 알고리즘을 이용하여 차량의 용량 및 운행시간을 초과하지 않으면서 고객의 서비스를 제공해주며 비용을 최소화하는 목적이 있다. 그리고 본 연구에서 제안한 개선된 유전자 알고리즘을 이용하면 다른 휴리스틱 기법보다 더욱 효율적인 시간제한을 가지는 차량경로문제에서 훌륭한 해를 도출할 수 있다. 따라서 차량경로문제의 해를 도출할 수 있는 개선된 유전자 알고리즘을 이용한 GUI 방식의 컴퓨터 프로그램을 개발하고 표준문제를 통하여 비교한 결과 본 연구에서 개발된 프로그램이 매우 유용한 결과를 보였다.


    A vehicle routing problem with time constraint is one of the important problems in distribution and transportation. The service of a customer must start and finish within a given time interval. Our method is based on an improved operators of genetic algorithm and the objective is to minimize the cost of servicing the set of customers without being tardy or exceeding the capacity or travel time of the vehicles. This research shows that a proposed method based on the improved genetic search can obtain good solutions to vehicle routing problems with time constrained compared with a high degree of efficiency other heuristics. For the computational purpose, we developed a GUI-type computer program according to the proposed method and the computational results show that the proposed method is very effective on a set of standard test problems, and can be potentially useful in solving the vehicle routing problems.


  • 주제어

    Vehicle Routing Problems .   Genetic Algorithm .   GA-TSP.  

  • 참고문헌 (16)

    1. Yeu-Geun Kim, "Meta Heuristic", Young-ji Co. pp.57-123,September, 1997 
    2. Achim Bachem et al, "An efficient parallel cluster-heuristic for large Traveling Salesman Problems" Universitat zu Koln,1994. 
    3. Chul-Hun Choi, "A Study on the Vehicle Routing of Multi-Supply Center", Dongeui, Univ., Pusan, pp.1-45, 1998. 
    4. D. Whitley, T. Starkweather, and D. Fuquay. "Scheduling Problems and Traveling Salesman: The Genetic Edge Recomvination Operator." In Proc. Third Int. Conf. on Genetic Algrithoms, pp.133-140, 1989. 
    5. D. Whitley, T. Starkweather, and D. Shaner. "Traveling Salesman and Sequence Scheduling: Quality Solutions Using Genetic Edge Recombination." In Handbook of Genetic Algorims, 1990. 
    6. Grefenstette J et al, "Genetic algorithm for the traveling salesman problem", Proc. Intern. Conf. of Genetic algorithm and their applications, pp. 160-165, 1995. 
    7. Nygard, K. E. Greenverg, P., Bolkan, W. E., and Swenson, J.E., "Generalized Assignment Methods for the Deadline Vechile Routing Problem", In Vechile Routing: Methods and Studies, North Holland, Amsterdam, 1988. 
    8. Sam R., H. Osman., Tong Sun., "Algorithms for the Vehicle Routing Problams with Time Deadlines", American J. of Math. & Manag. Sci., 13(3&4), p323-355, 1994. 
    9. Shin, H. W, "Vehicle routing for the delivery using Hybrid Genetic Algorithm", Hanyang University, Seoul, pp.1-75, 1994. 
    10. Solomon, M., Desrosiers, M., Desrosiers, J. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows", Operations Research, Vol. 40, No. 2, pp. 342-354, 1992. 
    11. V. M. Kureichick, A. N. Melihhov et al, "Some new features in genetic solution of the traveling salesman problem" ACEDC, Taganrog State University of Radio-Engineering, Rusia, 1996. 
    12. Victor M. Kureichick, Victor V. Miagkikh, et al, "Genetic Algorithm of The Traveling Salesman Problem with New Features against Premature Convergence", Taganrog State University of adio-Engineering, Rusia, 1995. 
    13. Weilin, "High QualityTour Hybrid Genetic Schemes for TSP Optimization Problems", State University of New York, 1992. 
    14. D. L. Applegate, R. E. Bixby, V. Chvatal and W. J. Cook, "The Traveling Salesman Problem: A Computational Study." Princeton University Press. 2006 
    15. Marco Antonio Cruz-Chavez, Ocotlan Diaz-Parral, et., "Search Algorithm for the Constraint Satisfaction Problem of VRPTW," cerma, Electronics, Robotics and Automotive Mechanics Conference, pp. 746-751, 2007. 
    16. P. Berman, M. Karpinski, "8/7 APProximation Algorithm for(1,2)-TSP", Proc. 17th ACM-SIAM SODA, pp. 641-648, 2006 
  • 이 논문을 인용한 문헌 (1)

    1. Song, Jun-Woo ; Kim, Kyung-Sup ; Jeong, Suk-Jae 2013. "Case Study on the continuous pickup and delivery vehicle routing problem in Multi-level Logistic Network based on S automobile Part Logistics Process" 대한안전경영과학회지 = Journal of the Korea safety management & science, 15(2): 193~204     

 저자의 다른 논문

  • 류정철 (2)

    1. 2007 "금속열처리를 위한 생산정보시스템 구축" 한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society 8 (4): 938~945    
    2. 2007 "복수물류센터에 대한 VRP 및 GA-TSP의 개선모델개발" 한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society 8 (5): 1279~1288    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
  • (사)한국산학기술학회 : 저널
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기