Daniel Schermer, Mahdi Moeini, Oliver Wendt

• In this paper, we are interested in studying thetraveling salesman problem withdrone(TSP-D). Given a set of customers and a truck that is equipped with a singledrone, the TSP-D asks that all customers are served exactly once and minimal deliv-ery time is achieved. We provide two compact mixed integer linear programmingformulations that can be used to address instances with up to 10 customer within afew seconds. Notably, we introduce a third formulation for the TSP-D with an expo-nential number of constraints. The latter formulation is suitable to be solved by abranch-and-cut algorithm. Indeed, this approach can be used to find optimal solu-tions for several instances with up to 20 customers within 1 hour, thus challenging thecurrent state-of-the-art in solving the TSP-D. A detailed numerical study providesan in-depth comparison on the effectiveness of the proposed formulations. More-over, we reveal further details on the operational characteristics of a drone-assisteddelivery system. By using three different sets of benchmark instances, considera-tion is given to various assumptions that affect, for example, technological droneparameters and the impact of distance metrics.