The Parallel Drone Scheduling Traveling Salesman Problem with Collective Drones

Minh Anh Nguyen () and Minh Hoàng Hà ()
Additional contact information
Minh Anh Nguyen: ORLab, Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam
Minh Hoàng Hà: ORLab, Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam

Transportation Science, 2023, vol. 57, issue 4, 866-888

Abstract: In this paper, we study a new variant of the parallel drone scheduling traveling salesman problem that aims to increase the utilization of drones, particularly for heavy item deliveries. The system under consideration adopts a technology that combines multiple drones to form a collective drone (c-drone) capable of transporting heavier items. The innovative concept is expected to add further flexibility in vehicle assignment decisions. An especially difficult challenge to address is the collaboration among drones because it requires temporal synchronization between their delivery tours. To better model the reality, we also consider that drone power consumption is a nonlinear function of both speed and parcel weight. We first develop a two-index mixed integer linear programming (MILP) formulation from which a simple branch and cut is developed to solve small-size instances to optimality. To efficiently handle larger problem instances, we propose a ruin-and-recreate metaheuristic with problem-tailored removal and insertion operators, in which an efficient move evaluation procedure based on the topological sort is designed to deal with the complexity of the synchronization constraints. Computational experiments demonstrate the validity of the developed MILP model and the performance of the proposed metaheuristic. Sensitivity analyses based on the classification and regression tree are performed to investigate the benefits of using c-drones and the important factors affecting the efficiency of the new transportation system.

Keywords: traveling salesman problem; drone parallel scheduling; collective drones; synchronization; mixed integer liner programming; ruin and recreate (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1192 (application/pdf)

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:inm:ortrsc:v:57:y:2023:i:4:p:866-888

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().