Premium
A b ranch‐and‐cut approach and alternative formulations for the traveling salesman problem with drone
Author(s) -
Schermer Daniel,
Moeini Mahdi,
Wendt Oliver
Publication year - 2020
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21958
Subject(s) - drone , travelling salesman problem , benchmark (surveying) , mathematical optimization , computer science , set (abstract data type) , integer programming , linear programming , integer (computer science) , truck , exponential function , operations research , mathematics , engineering , genetics , geodesy , biology , programming language , geography , mathematical analysis , aerospace engineering
In this paper, we are interested in studying the traveling salesman problem with drone (TSP‐D). Given a set of customers and a truck that is equipped with a single drone, the TSP‐D asks that all customers are served exactly once and minimal delivery time is achieved. We provide two compact mixed integer linear programming formulations that can be used to address instances with up to 10 customer within a few seconds. Notably, we introduce a third formulation for the TSP‐D with an exponential number of constraints. The latter formulation is suitable to be solved by a branch‐and‐cut algorithm. Indeed, this approach can be used to find optimal solutions for several instances with up to 20 customers within 1 hour, thus challenging the current state‐of‐the‐art in solving the TSP‐D. A detailed numerical study provides an in‐depth comparison on the effectiveness of the proposed formulations. Moreover, we reveal further details on the operational characteristics of a drone‐assisted delivery system. By using three different sets of benchmark instances, consideration is given to various assumptions that affect, for example, technological drone parameters and the impact of distance metrics.