A Branch-and-Cut Algorithm for the Traveling Salesman Problem with Drone

In this thesis, we introduce logical and comb inequalities for the Traveling Salesman Problem with assistance of a Drone, where a truck and drone work together in a coordinated tour that visits all customers. We have solved randomly generated instances with up to 40 customer nodes using a branch-and-cut algorithm implemented by CPLEX and assessed the performance of the proposed inequalities. Moreover, we present an extensive analysis to determine the benefit from the proposed methods by running two versions of the algorithm in parallel in an optimistic environment, where violated cuts are identified immediately.