EconPapers    
Economics at your fingertips  
 

The multiple traveling salesman problem in presence of drone- and robot-supported packet stations

Konstantin Kloster, Mahdi Moeini, Daniele Vigo and Oliver Wendt

European Journal of Operational Research, 2023, vol. 305, issue 2, 630-643

Abstract: In this paper, we introduce the multiple Traveling Salesman Problem with Drone Stations (mTSP-DS), which is an extension to the classical multiple Traveling Salesman Problem (mTSP). In the mTSP-DS, we have a depot, a set of trucks, and some packet stations that host a given number of autonomous vehicles (drones or robots). The trucks start their mission from the depot and can supply some packet stations, which can then launch and operate drones/robots to serve customers. The goal is to serve all customers either by truck or by drones/robots while minimizing the makespan. We formulate the mTSP-DS as a mixed integer linear programming (MILP) model to solve small instances. To address larger instances, we first introduce two variants of a decomposition-based matheuristic. Afterwards, we suggest a third approach that is based on populating a solution pool with several restarts of an iterated local search metaheuristic, which is followed by determining the best combination of tours using a set-partitioning model. To verify the performance of our algorithms, we conducted extensive computational experiments. According to the numerical results, we observe that the use of drone stations leads to considerable savings in delivery time compared to traditional mTSP solutions. Furthermore, we investigated the energy consumption of trucks and drones. Indeed, depending on the energy consumption coefficients of trucks and drones as well as on the distance covered by drones, the mTSP-DS can also achieve energy savings in comparison to mTSP solutions.

Keywords: Logistics; Vehicle routing; Drone deliveries; Mixed integer linear programming; Heuristics (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722004593
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:305:y:2023:i:2:p:630-643

DOI: 10.1016/j.ejor.2022.06.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().

 
Page updated 2025-03-19
Handle: RePEc:eee:ejores:v:305:y:2023:i:2:p:630-643