2021/02/05 by Roberto Roberti, Mario Ruthmair · 2 citations
Engineering · #Smart Parking Systems Research #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · doi:10.1287/trsc.2020.1017
openalex publication_date 2021/02/05 · crossref created 2021/02/05 · crossref issued 2021/03/01 · crossref published 2021/03/01 · crossref published-print 2021/03/01 · crossref deposited 2023/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01 · crossref indexed 2026/08/01
Efficiently handling last-mile deliveries becomes more and more important nowadays. Using drones to support classical vehicles allows improving delivery schedules as long as efficient solution methods to plan last-mile deliveries with drones are available. We study exact solution approaches for some variants of the traveling salesman problem with drone (TSP-D) in which a truck and a drone are teamed up to serve a set of customers. This combination of truck and drone can exploit the benefits of both vehicle types: the truck has a large capacity but usually low travel speed in urban areas; the drone is faster and not restricted to street networks, but its range and carrying capacity are limited. We propose a compact mixed-integer linear program (MILP) for several TSP-D variants that is based on timely synchronizing truck and drone flows; such an MILP is easy to implement but nevertheless leads to competitive results compared with the state-of-the-art MILPs. Furthermore, we introduce dynamic programming recursions to model several TSP-D variants. We show how these dynamic programming recursions can be exploited in an exact branch-and-price approach based on a set partitioning formulation using ng-route relaxation and a three-level hierarchical branching. The proposed branch-and-price can solve instances with up to 39 customers to optimality outperforming the state-of-the-art by more than doubling the manageable instance size. Finally, we analyze different scenarios and show that even a single drone can significantly reduce a route’s completion time when the drone is sufficiently fast.