Drone-Assisted Last-Mile Delivery Problem by Covering Salesman Problem with Nodes and Segments

Drones attract increasing attention in the last decades as a means for last mile delivery; they are mainly considered as supplement delivery tools that work jointly with trucks. In this paper, we develop a Covering Salesman Problem with Nodes and Segments Using Drones (CSPNS-D) and formulate three Mixed Integer Linear Programming (MILP) models that minimize delivery time in a drone-assisted truck delivery system. Four types of drone operations are defined to cover different synchronizing modes of the drone and the truck. Performance of the models are tested on randomly generated examples and benchmark datasets. Using CPLEX, all the three models can be solved efficiently to optimality on instances with up to 35 orders. On larger instances, a simple link(node)-removal heuristic is developed to reduce the possible number of branching choices in the solution process. The approach works effectively in reducing computational time. Further insights about the influences of drone flying capability and certain geographic features of the service area are also discussed