Multiple traveling salesman problem with drones: Mathematical model and heuristic approach
By Patchara Kitjacharoenchai, Mario Ventresca, M. Moshref-Javadi, Seokcheon Lee, J. Tanchoco, P. Brunese. Computers & industrial engineering, 2019
343 citations recorded by the source corpus.
Abstract E-commerce and retail companies are seeking ways to cut delivery times and costs by exploring opportunities to use drones for making last mile delivery deliveries. This paper addresses the delivery concept of a truck-drone combination along with the idea of allowing autonomous drones to fly from delivery trucks, make deliveries, and fly to any available delivery truck nearby. We present a mixed integer programming (MIP) formulation that captures this scenario with the objective of minimizing the arrival time of both trucks and drones at the depot after completing the deliveries. A new algorithm based on insertion heuristics is also developed to solve large sized problems containing up to a hundred locations. Experiments are conducted to compare the MIP solutions with those obtained from different models with single truck, multiple truck and a single truck and drone system, as well as test the performance of the proposed algorithm. The numerical results demonstrate the potential operational gain when implementing the proposed drone delivery system compared to the conventional truck alone or single truck/drone delivery system.
Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Industrial and Manufacturing Engineering
View Paper: https://www.semanticscholar.org/paper/ec6dd10e58fce5778efdfae40aadcf4990e91f2a
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Aerospace Engineering
In Computer Vision and Pattern Recognition
In Industrial and Manufacturing Engineering
Citations in the corpus
- A Comprehensive Survey on the Multiple Travelling Salesman Problem: Applications, Approaches and Taxonomy (2021, methodology): “[14] MinMax (time) Formulated as Mixed Integer Programming (MIP) and solver by Cplex solver Trucks and drones parcel delivery for last mile.”
- Applications and Research avenues for drone-based models in logistics: A classification and review (2021, methodology): “Kitjacharoenchai et al. (2019) extend the TSPD model by considering multiple uncapacitated trucks and multiple drones.”