Multi Objective Vehicle and Drone Routing Problem with Time Window = 차량과 드론을 혼용한 다목적 일정계획 문제

다국어 초록 (Multilingual Abstract)

In this paper, we study the multi-objectives vehicle and drone routing problem with time windows, MOVDRPTW for short, which is defined in an urban delivery network. We consider the dual modal delivery system consisting of drones and vehicles. Drones are used as a complement to the vehicle and operate in a point to point manner between the depot and the customer. Customers make various requests. They prefer to receive delivery services within the predetermined time range and some customers require fast delivery. The purpose of this paper is to investigate the effectiveness of the delivery strategy of using drones and vehicles together with a multi-objective measures. As experiment datasets, we use the instances generated based on actual courier delivery data. We propose a hybrid multi-objective evolutionary algorithm for solving MOVDRPTW. Our results confirm that the vehicle-drone mixed strategy has 30% cost advantage over vehicle only strategy.

목차 (Table of Contents)

• Abstract
• I. Introduction
• II. Problem statements and network model
• III. HMOEA : Hybrid Multi-Objective Evolutionary Algorithm
• V. Experiment
• V. Limitation and Discussion
• VI. Conclusions
• REFERENCES

참고문헌 (Reference)

1 정예림, "배송 네트워크에서 드론의 유용성 검증: 차량과 드론을 혼용한 배송 네트워크의 경로계획" 한국경영과학회 41 (41): 75-96, 2016

2 C. C. Murray, "The flying sidekick traveling salesman problem : Optimization of drone-assisted parcel delivery" 54 : 86-109, 2015

3 E. Zitzler, "SPEA2, Improving the strength Pareto evolutionary algorithm" 2001

4 N. Agatz, "Optimization approaches for the traveling salesman problem with drone" 2016

5 Q. M. Ha, "On the Min-cost Traveling Salesman Problem with Drone"

6 F. Glover, "New ejection chain and alternating path methods for traveling salesman problems" 449 : 491-507, 1992

7 B. Ombuki, "Multi-objective genetic algorithms for vehicle routing problem with time windows" 24 (24): 17-30, 2006

8 K. Deb, "Multi-Objective Optimization Using Evolutionary Algorithms" John Wiley& Sons. Inc 2001

9 E. G. Talbi, "Metaheuristics: from design to implementation, Vol. 74" John Wiley & Sons 2009

10 Q. M. Ha, "Heuristic methods for the Traveling Salesman Problem with Drone"

11 W. Chaovalitwongse, "GRASP with a new local search scheme for vehicle routing problems with time windows" 7 (7): 179-207, 2003

12 O. Bräysy, "Fast local searches for the vehicle routing problem with time windows" 40 (40): 319-330, 2002

13 T. Back, "Evolutionary algorithms in theory and practice:evolution strategies, evolutionary programming, genetic algorithm" Oxford university press 1996

14 O. Bräysy, "Evolutionary algorithms for the vehicle routing problem with time windows" 10 (10): 587-611, 2004

15 C. A. C. Coello, "Evolutionary algorithms for solving multi-objective problems, (Vol. 5)" Springer 2007

16 G. Laporte, "Classical and modern heuristics for the vehicle routing problem" 7 (7): 285-300, 2000

17 E. Zitzler, "An evolutionary algorithm for multiobjective optimization: The strength pareto approach" 1998

18 K. C. Tan, "A multiobjective evolutionary algorithm for solving vehicle routing problem with time windows" IEEE 1 : 361-366, 2003

19 J. Berger, "A hybrid genetic algorithm for the capacitated vehicle routing problem" 646-656, 2003

20 S. C. Hong, "A heuristic for bi-objective vehicle routing with time window constraints" 62 (62): 249-258, 1999