컨테이너 셔틀 서비스를 위한 차량 경로 문제의 근사적 해법 = An efficient heuristic to solve vehicle routing problem for container shuttle service

다국어 초록 (Multilingual 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.

국문 초록 (Abstract)

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

참고문헌 (Reference)

1 김상현, "환경비용을 고려한 수출입컨테이너 화물의 운송경로 선택에 관한 연구" 한국항해항만학회 27 (27): 155-162, 2003

2 윤항묵, "컨테이너 운송체계 개선을 위한 화물수거-배송계획 시스템 개발" 한국항해항만학회 29 (29): 221-226, 2005

3 윤원영, "내륙 운송 체계 하에서 컨테이너의 최적 운송관리에 관한 연구" 31 (31): 207-209, 2007

4 Mosheiov,G, "Vehicle routing with pick-up and delivery: tour-partitioning heuristics" 34 : 669-684, 1998

5 Dethloff,J, "Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up" 23 : 79-96, 2001

6 Cordeau, J. F, "The dial-a-ride problem: models and algorithms" 153 : 29-46, 2007

7 Cordeau, J. F, "The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms" 1 : 89-101, 2003

8 Gendreau, M, "Heuristics for the traveling salesman problem with pickup and delivery" 26 : 699-714, 1999

9 Bianchessi, N, "Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery" 34 : 578-594, 2007

10 Nagy, G, "Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveri" 162 : 126-141, 2005

11 Chung, K. H, "Development of mathematical models for the container road transportation in Korean trucking industries" 53 : 252-262, 2007

12 신재영, "Combined chassis 트레일러를 이용한 컨테이너 차량 경로 문제" 155-156, 2008

13 Ganesh, K, "CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up" 178 : 699-717, 2007

14 Roberto, W. C, "An effective and fast heuristic for the Dial-a-Ride problem" 5 : 61-73, 2007

15 Kalantari, B, "An algorithm for the traveling salesman problem with pickup and delivery customers" 22 : 377-386, 1985

16 Cordeau, J. F, "A tabu search heuristic for the static multi-vehicle dial-a-ride problem" 37 : 579-594, 2003

17 Fermin, A. T. M, "A tabu search algorithm for the vehicle routing problem with\ simultaneous pick-up and delivery service" 33 : 595-619, 2006

18 Luo, Y, "A rejected-reinsertion heuristic for the static Dial-A-Ride Problem" 41 : 736-755, 2007

19 Healy, P, "A new extension of local search applied to the Dial-A-Ride Problem" 83 : 83-104, 1995

20 Vigo,D, "A heuristic algorithm for the Asymmetric Capacitated Vehicle Routing Problem" 89 : 108-126, 1996