VRPSPD 해결을 위한 위치기반의 실시간 재경로 탐색 휴리스틱 = A Location-based Real-time Re-routing Heuristic to Solve the VRPSPD

다국어 초록 (Multilingual Abstract)

The vehicle routing problem with simultaneous pick-up and delivery (VRPSPD) is a variant of the vehicle routing problem (VRP) that customers require simultaneously a pick-up and delivery service. The main objective of VRPSPD is to minimize a cost of routes satisfying many constraints. Traditional VRPSPD have been dealt with a static environment. The static environment means that a routing data and plan cannot be changed. For example, it is difficult to change a vehicle’s routing plan so that a vehicle serves the pick-up demands of new customers during the delivery service. Therefore, traditional approach is not suitable for dynamic environments. To solve this problem, we propose a novel approach for finding efficient routes using a real-time re-routing heuristics based on the Location Based Service (LBS). Our re-routing heuristics can generate a new route for vehicle that satisfies a new customer’s demand considering the current geographic location of a vehicle. Experimental results show that our methodology can reduce the traveling cost of vehicles comparing with other previous methods.

참고문헌 (Reference)

1 조대수, "특허 분석을 통한 LBS 기술현황에 관한 연구" 한국공간정보시스템학회 8 (8): 65-76, 2006

2 진희채, "위치기반 서비스를 위한 모델 분석 및 기술 연구" 438-450, 2003

3 유영훈, "시간 제약을 가지는 차량 경로 스케줄링 문제 해결을 위한 기회시간 반영 하이브리드 휴리스틱" 한국지능정보시스템학회 15 (15): 137-150, 2009

4 문형돈, "국내 LBS 동향 및 활성화 방안 분석" 정보통신연구진흥원 (1133) : 2004

5 "http://en.wikipedia.org/wki/Meshup_"

6 Casco, D. O., "Vehicle Routing with Backhauls : Models Algorithms, and Case Studies" 127-147, 1988

7 Anily, S., "The vehicle routing problem with delivery and back-haul options" 43 : 415-434, 1996

8 Min, H., "The multiple vehicle routing problem with simultaneous delivery and pick- up" 23A (23A): 377-386, 1989

9 Glover, F., "Tabu Search Part II" 2 (2): 4-32, 1990

10 Glover, F., "Tabu Search Part I" 1 (1): 190-206, 1989

11 Baker B. D., "Sovling vehicle routing problems using constraint programming and meta heuristics" 6 : 501-523, 2000

12 Willian P., "Solving the pickup and delivery problem with time windows using reactive tabu search" 34 : 107-121, 2000

13 Clark, G., "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points" 2 (2): 568-581, 1964

14 Yu Y.H, "Recommendation system using location-based ontology on wireless internet: An example of collective intelligence by using ‘mashup’ applications" 36 (36): 11675-11681, 2009

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

16 Tan K.C., "Heuristic methods for vehicle routing problem with time windows" 15 : 281-295, 2001

17 Solomon M.M, "Algorithms for the vehicle routing and scheduling problems with time window constrains" 35 : 254-265, 1987

18 Antoine L., "A tabu search heuristic for the single vehicle pickup and delivery problem with time windows" 12 : 497-508, 2001

19 Brandao, J., "A new tabu search for the vehicle routing problem with back-hauls" 173 (173): 540-555, 2006

20 Quan L., "A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows" 175 : 672-687, 2006

21 Zachariadis E.E, "A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service" 36 (36): 1070-1081, 2009