A Branch-Cut-and-Price Algorithm for the Travelling Salesman with Drone

The collaboration between a truck and drone with the joint objective to satisfy customer demand under minimisation of the execution time is studied. Leading exact methods approach the problem in the fashion of a set covering problem but have to cope with a large solution space. A framework is introduced that refines the solution space, improving the performance of existing methods. Furthermore, a branch-cut-and-price algorithm is proposed and a branching rule is introduced that is specific for the problem. Despite, the pricing procedure did not yield any computational advantage over the branch-and-cut benchmark. The computational study showed promising results as problems with 34 customers were solved to optimality, whereas the best-known exact methods could handle up to 15 customers under the same conditions. Furthermore, a local search routine within the methods was considered and achieved reductions in the costs of up to 6% for a problem with 70 customers compared to a respectable heuristic (Agatz et al., 2016).