Branch‐price‐and‐cut for the truck–drone routing problem with time windows
Authors:
- 1 December 2022
- journal article
- research article
- Published by Wiley in Naval Research Logistics (NRL)
- Vol. 70 (2) , 184-204
Abstract
Considering the important realistic benefits of drones combined with trucks for last‐mile parcel deliveries, we define the truck–drone routing problem with time windows (TDRP‐TW). The TDRP‐TW has the characteristics of time windows, synchronization en route, direct delivery, multiple trucks, and multiple drones carried by each truck. Customers covered by truck routes can be used as drone launch/retrieval locations, which are called satellites in this study. The synchronization en route enables drones to launch from trucks to return to paired trucks at nodes other than departure sites if necessary. We present an effective branch‐price‐and‐cut algorithm, in which a concept named candidate forward‐satellite (CFS) is introduced to manage the labeling challenge caused by the synchronization en route. In addition, the branch‐price‐and‐cut algorithm is combined with an adaptive large neighborhood search to obtain approximation solutions for large‐scale instances. In the computational experiments, instances with up to 50 customers are solved to optimality, and approximation solutions of large‐scale instances with 100 customers are presented.Keywords
Funding Information
- National Natural Science Foundation of China (71972007, 71672005)
This publication has 30 references indexed in Scilit:
- Last-Mile Deliveries by Using Drones and Classical Vehicles2017
- Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windowsComputers & Operations Research, 2017
- The vehicle routing problem with drones: several worst-case resultsOptimization Letters, 2016
- The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel deliveryTransportation Research Part C: Emerging Technologies, 2015
- Branch and Cut and Price for the Pickup and Delivery Problem with Time WindowsTransportation Science, 2009
- Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time WindowsOperations Research, 2008
- Shortest Path Problems with Resource Constraints2006
- Selected Topics in Column GenerationOperations Research, 2005
- Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems1998
- Algorithms for the Vehicle Routing and Scheduling Problems with Time Window ConstraintsOperations Research, 1987