Scientific Program > Talks by Topic

In the last decades e-commerce has boomed and home deliveries have followed the same trend. Moreover, customers began expecting parcels delivery to be performed in a very short time after purchase. One of the proposed methods to deliver parcels to customers in a fast way is the use of unmanned areal vehicles (UAV), also known as drones.

In this work we consider the parallel drone scheduling traveling salesman problem (PDSTSP) defined by Murray and Chu [1], where a set of drones can serve the customers within a certain radius from the depot and deliver parcels in parallel with a vehicle. The authors proposed a MILP formulation and greedy heuristics for the problem. More recently, Mbiadou Saleu et al. [2] proposed an iterative two-step heuristic in which customers are firstly partitioned between the vehicle and the drones and then the routing optimization is performed.

In this work we propose a new formulation for the PDSTSP and we define some effective math-heuristic local searches that can be used to provide good quality solutions in a short computation time. Preliminary results on benchmark instances are very promising, allowing us to provide the optimal solution for most of them.

[1] Murray, C.C. and Chu, A.G.: The flying sidekick traveling salesman problem:
Optimization of drone-assisted parcel delivery. Transportation Research Part C:
Emerging Technologies, 54, 86-109, (2015).
[2] Mbiadou Saleu, R.G., Deroussi, L., Feillet, D., Grangeon, N. and Quilliot, A.:
An iterative twostep heuristic for the parallel drone scheduling traveling salesman
problem. Networks, 72(4), 459-474, (2018).