An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem

被引：83
作者：
Saleu, Raissa G. Mbiadou [1 ]
Deroussi, Laurent [1 ]
Feillet, Dominique [2 ,3 ]
Grangeon, Nathalie [1 ]
Quilliot, Alain [1 ]
机构：
[1] Univ Clermont Auvergne, LIMOS, UMR 6158, CNRS, F-63178 Aubiere, France
[2] Mines St Etienne, F-13541 Gardanne, France
[3] CMP Georges Charpak, UMR 6158, LIMOS, CNRS, F-13541 Gardanne, France
来源：
NETWORKS | 2018年 / 72卷 / 04期
关键词：
city logistics; drone delivery; dynamic programming; heuristic; PDSTSP; vehicle routing problem; CUT ALGORITHM; DELIVERY;
D O I：
10.1002/net.21846
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
A recent evolution in urban logistics involves the usage of drones. In this article, we address a heuristic solution of the parallel drone scheduling traveling salesman problem, recently introduced by Murray and Chu. In this problem, deliveries are split between a vehicle and drones. The vehicle performs a classical delivery tour, while the drones are constrained to perform back and forth trips. The objective is to minimize completion time. We propose an iterative two-step heuristic, composed of: a coding step that transforms a solution into a customer sequence, and a decoding step that decomposes the customer sequence into a tour for the vehicle and trips for the drones. Decoding is expressed as a bicriteria shortest path problem and is carried out by dynamic programming. Experiments conducted on benchmark instances confirm the efficiency of the approach and give some insights on this drone delivery system.
引用
收藏
页码：459 / 474
页数：16
相关论文
共 26 条
  • [11] Gambella C., 2017, TRANSPORT SCI, V52, P229
  • [12] Traveling-Salesman Problem for a Class of Carrier-Vehicle Systems
    Garone, Emanuele
    Naldi, Roberto
    Casavola, Alessandro
    [J]. JOURNAL OF GUIDANCE CONTROL AND DYNAMICS, 2011, 34 (04) : 1272 - 1276
  • [13] Gendreau M, 1998, NETWORKS, V32, P263, DOI 10.1002/(SICI)1097-0037(199812)32:4<263::AID-NET3>3.0.CO
  • [14] 2-Q
  • [15] Ha Q. M., 2015, ARXIV150908764
  • [16] An effective implementation of the Lin-Kernighan traveling salesman heuristic
    Helsgaun, K
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 126 (01) : 106 - 130
  • [17] A branch-and-cut algorithm for the capacitated profitable tour problem
    Jepsen, Mads Kehlet
    Petersen, Bjorn
    Spoorendonk, Simon
    Pisinger, David
    [J]. DISCRETE OPTIMIZATION, 2014, 14 : 78 - 96
  • [18] Kelion L., 2015, ALIBABA BEGINS DRONE
  • [19] Liptak A., 2016, 7-Eleven just made the first commercial delivery by drone
  • [20] The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery
    Murray, Chase C.
    Chu, Amanda G.
    [J]. TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2015, 54 : 86 - 109
123