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

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.