차량과 드론을 혼용한 다목적 일정계획 문제
Multi Objective Vehicle and Drone Routing Problem with Time Window
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (20)
- C. C. Murray, "The flying sidekick traveling salesman problem : Optimization of drone-assisted parcel delivery", Transportation Research Part C : Emerging Technologies, 54, pp.86~109 (2015)
- N. Agatz, "Optimization approaches for the traveling salesman problem with drone" (2016)
- Q. M. Ha, "Heuristic methods for the Traveling Salesman Problem with Drone", arXiv preprint arXiv:1509.08764, ~ (2015)
- Q. M. Ha, "On the Min-cost Traveling Salesman Problem with Drone", arXiv preprint arXiv:1509.08764, ~ (2015)
- 정예림, "배송 네트워크에서 드론의 유용성 검증: 차량과 드론을 혼용한 배송 네트워크의 경로계획", 한국경영과학회지, 41(3), pp.75~96 (2016), 한국경영과학회[DOI]
- T. Back, "Evolutionary algorithms in theory and practice:evolution strategies, evolutionary programming, genetic algorithm" (1996), Oxford university press
- G. Laporte, "Classical and modern heuristics for the vehicle routing problem", International transactions in operational research, 7(4-5), pp.285~300 (2000)
- B. Ombuki, "Multi-objective genetic algorithms for vehicle routing problem with time windows", Applied Intelligence, 24(1), pp.17~30 (2006)
- O. Bräysy, "Evolutionary algorithms for the vehicle routing problem with time windows", Journal of Heuristics, 10(6), pp.587~611 (2004)
- S. C. Hong, "A heuristic for bi-objective vehicle routing with time window constraints", International Journal of Production Economics, 62(3), pp.249~258 (1999)
- K. Deb, "Multi-Objective Optimization Using Evolutionary Algorithms" (2001), John Wiley& Sons. Inc
- SPEA2, Improving the strength Pareto evolutionary algorithm, "E. Zitzler", ~ (2001)
- E. G. Talbi, "Metaheuristics: from design to implementation, Vol. 74" (2009), John Wiley & Sons
- C. A. C. Coello, "Evolutionary algorithms for solving multi-objective problems, (Vol. 5)" (2007), Springer
- J. Berger, "A hybrid genetic algorithm for the capacitated vehicle routing problem", Genetic and evolutionary computation conference, pp.646~656 (2003)
- K. C. Tan, "A multiobjective evolutionary algorithm for solving vehicle routing problem with time windows", Systems, Man and Cybernetics, 2003. IEEE International Conference, 1, pp.361~366 (2003), IEEE
- O. Bräysy, "Fast local searches for the vehicle routing problem with time windows", INFOR : Information Systems and Operational Research, 40(4), pp.319~330 (2002)
- An evolutionary algorithm for multiobjective optimization: The strength pareto approach, "E. Zitzler", ~ (1998)
- W. Chaovalitwongse, "GRASP with a new local search scheme for vehicle routing problems with time windows", Journal of Combinatorial Optimization, 7(2), pp.179~207 (2003)
- F. Glover, "New ejection chain and alternating path methods for traveling salesman problems", Computer science and operations research, 449, pp.491~507 (1992)