Journal of Navigation and Port Research (한국항해항만학회지)

Korean Institute of Navigation and Port Research (한국항해항만학회)
권호 표지
DOI QR코드

DOI QR Code

An Efficient Heuristic to Solve Vehicle Routing Problem for Container Shuttle Service

컨테이너 셔틀 서비스를 위한 차량 경로 문제의 근사적 해법

  • Shin, Jae-Young (Department of Logistics Engineering, National Korea Maritime University) ;
  • Oh, Sung-Inn (Graduate school of National Korea Maritime University) ;
  • Park, Jong-Won (Graduate school of National Korea Maritime University)
  • 신재영 (한국해양대학교 물류시스템공학과) ;
  • 오성인 (한국해양대학교 대학원) ;
  • 박종원 (한국해양대학교 대학원)
  • Published : 2009.10.31
Download PDF
⟨ Previous Next ⟩

Abstract

Generally, the container road transportation can be divided into three types; short distance, long distance and shuttle transportation. Specially, the shuttle service occurs several amounts of container which is same as O/D pairs. Also container vehicle can be divided into three types according to the chassis types of vehicle; only 20-feet container, only 40-feet container and combined chassis trailer. Combined chassis trailers can load two 20-feet containers or one 40-feet container. This paper deals with Vehicle Routing Problem (VRP) for delivering containers considering shuttle service. This problem is similar to the previously studied Shin and Oh (2008), but the characteristics of shuttle service must be considered additionally. We formulate the container shuttle transportation planning problem using combined chassis trailers based on VRP with pick-up and delivery which can visit each node more than one time, and propose an efficient solution procedure.

일반적으로 컨테이너 공로 운송은 근거리 운송, 장거리 운송, 셔틀 운송으로 구분되고, 컨테이너 차량은 섀시 형태에 따라 20' 컨테이너 전용, 40' 컨테이너 전용, 콤바인 섀시 차량으로 나눌 수 있다. 셔틀 서비스는 O/D pairs가 같은 물량이 여러 개 발생할 수 있으며, 콤바인 섀시 트레일러는 20ft 컨테이너 2개를 싣거나 한 개의 40ft 컨테이너를 실을 수 있다. 본 논문에서는 셔틀 서비스를 고려한 컨테이너 차량 경로 문제를 다루고자 한다. 문제 정의는 기존의 연구된 신재영, 오성인(2008)의 문제와 유사하지만 셔틀 서비스의 특징을 고려해야 한다. 이에 각 노드를 한 번 이상 방문할 수 있는 pick-up and delivery 제약을 가진 차량경로문제를 근간으로 하여 콤바인 섀시 트레일러를 이용한 컨테이너 셔틀 운송계획 문제를 정의하고, 적합하고 효율적인 해법을 제안하고자 한다.

Keywords

References

  1. 김상현, 고창두(2003), "환경비용을 고려한 수출입컨테이너화물의 운송경로 선택에 관한 연구", 한국항해항만학회, 27권, 2호, pp.155-162 https://doi.org/10.5394/KINPR.2003.27.2.155
  2. 신재영, 오성인(2008), "Combined chassis 트레일러를 이용한 컨테이너 차량 경로 문제", 한국항해항만학회 2008 공동학술대회, 논문집, pp.155-156
  3. 윤원영, 류숙재(2007), "내륙 운송 체계 하에서 컨테이너의 최적 운송관리에 관한 연구", 한국항해항만학회, 31권, 2호, pp.207-209
  4. 윤항묵, 황흥석, 김형보(2005), "컨테이너 운송체계 개선을 위한 화물수거-배송계획 시스템 개발", 한국항해항만학회, 29권, 3호, pp.221-226 https://doi.org/10.5394/KINPR.2005.29.3.221
  5. Bianchessi, N. and Righini, G.(2007), "Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery", Computers & Operational Research, 34, pp.578-594 https://doi.org/10.1016/j.cor.2005.03.014
  6. Chung, K. H., Ko, C. S., Shin, J. Y., Hwang, H., and Kim, K. H.(2007), "Development of mathematical models for the container road transportation in Korean trucking industries", Computers & Industrial Engineering, 53, pp.252-262 https://doi.org/10.1016/j.cie.2007.06.017
  7. Cordeau, J. F. and Laporte, G.(2003a), "A tabu search heuristic for the static multi-vehicle dial-a-ride problem", Transportation Research Part B, 37, pp.579-594 https://doi.org/10.1016/S0191-2615(02)00045-0
  8. Cordeau, J. F. and Laporte, G.(2003b), "The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms", 4OR, 1, pp.89-101
  9. Cordeau, J. F. and Laporte, G.(2007), "The dial-a-ride problem: models and algorithms", Annals of operations research, 153, pp.29-46 https://doi.org/10.1007/s10479-007-0170-8
  10. Dethloff, J.(2001), "Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up", OR Spektrum, 23, pp.79-96 https://doi.org/10.1007/PL00013346
  11. Fermin, A. T. M. and Roberto, D. G.(2006), "A tabusearch algorithm for the vehicle routing problem with simultaneous pick-up and delivery service", Computers & Operations Research, 33, pp.595-619 https://doi.org/10.1016/j.cor.2004.07.009
  12. Ganesh, K. and Narendran, T. T.(2007), "CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up", European Journal of Operational Research, 178, pp.699-717 https://doi.org/10.1016/j.ejor.2006.01.037
  13. Gendreau, M., Laporte, G., and Vigo, D.(1999), "Heuristics for the traveling salesman problem with pickup and delivery", Computers & Operations Research, 26, pp.699-714 https://doi.org/10.1016/S0305-0548(98)00085-9
  14. Healy, P. and Moll, R.(1995), "A new extension of local search applied to the Dial-A-Ride Problem", European Journal of Operational Research, 83, pp.83-104 https://doi.org/10.1016/0377-2217(93)E0292-6
  15. Kalantari, B., Hill, A. V., and Arora, S. R.(1985), "Analgorithm for the traveling salesman problem with pickup and delivery customers", European Journal of Operational Research, 22, pp.377-386 https://doi.org/10.1016/0377-2217(85)90257-7
  16. Luo, Y. and Schonfeld, P.(2007), "A rejected-reinsertion heuristic for the static Dial-A-Ride Problem", Transportation Research Part B, 41, pp.736-755 https://doi.org/10.1016/j.trb.2007.02.003
  17. Mosheiov, G.(1998), "Vehicle routing with pick-up and delivery: tour-partitioning heuristics", Computers & Industrial Engineering, 34, pp.669-684 https://doi.org/10.1016/S0360-8352(97)00275-1
  18. Nagy, G. and Salhi, S.(2005), "Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries", European Journal of Operational Research, 162, pp.126-141 https://doi.org/10.1016/j.ejor.2002.11.003
  19. Roberto, W. C. and Alberto, C.(2007), "An effective and fast heuristic for the Dial-a-Ride problem", 4OR, 5, pp.61-73
  20. Vigo, D.(1996), "A heuristic algorithm for the Asymmetric Capacitated Vehicle Routing Problem", European Journal of Operational Research, 89, pp. 108-126 https://doi.org/10.1016/S0377-2217(96)90060-0

Cited by

  1. An Efficient Heuristic to Solve Vehicle Routing Problem for Container Shuttle Service vol.33, pp.8, 2009, https://doi.org/10.5394/KINPR.2009.33.8.583
  2. Container Transportation Models in Industrial Estate Area vol.38, pp.2, 2014, https://doi.org/10.5394/KINPR.2014.38.2.171