An efficient branch-and-cut algorithm for the parallel drone scheduling traveling salesman problem

Minh Anh Nguyen, Hai Long Luong, Minh Hoàng Hà () and Ha-Bang Ban
Additional contact information
Minh Anh Nguyen: Phenikaa University
Hai Long Luong: Phenikaa University
Minh Hoàng Hà: Phenikaa University
Ha-Bang Ban: Hanoi University of Science and Technology

4OR, 2023, vol. 21, issue 4, No 3, 609-637

Abstract: Abstract This paper proposes an efficient branch-and-cut algorithm to exactly solve the parallel drone scheduling traveling salesman problem. The problem is first formulated as a mixed integer linear program with truck-flow variables defined on undirected edges, not on directed arcs as in existing models. The formulation is then strengthened by valid inequalities and the branch-and-cut algorithm is developed. The experimental results show that our algorithm can find optimal solutions for all existing instances, but two in a reasonable running time. To make the problem more challenging for future solution methods, we introduce two new sets of 120 larger instances with the number of customers varying from 318 to 783 and test our algorithm and investigate the performance of state-of-the-art metaheuristics on these instances. We show that the proposed algorithm can steadily solve the instances with up to 400 customers to optimality. Optimal solutions of several cases with 600 and 783 customers are also found by our algorithm. This is the first time problems of such a large size are optimally solved.

Keywords: Parallel drone scheduling; Traveling salesman problem; Branch and cut; Benchmark instances; 9010; 90B06; 90C11 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-022-00527-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:aqjoor:v:21:y:2023:i:4:d:10.1007_s10288-022-00527-z

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-022-00527-z

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().