In:
Transportation Science, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 55, No. 2 ( 2021-03), p. 315-335
Kurzfassung:
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.
Materialart:
Online-Ressource
ISSN:
0041-1655
,
1526-5447
DOI:
10.1287/trsc.2020.1017
Sprache:
Englisch
Verlag:
Institute for Operations Research and the Management Sciences (INFORMS)
Publikationsdatum:
2021
ZDB Id:
2015901-8
ZDB Id:
160958-0
SSG:
3,2
