Branch-price-and-cut for the truck-drone routing problem with time windows. (English) Zbl 1525.90064
Summary: 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.
{© 2022 Wiley Periodicals LLC.}
{© 2022 Wiley Periodicals LLC.}
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Boysen, N., Fedtke, S., & Schwerdfeger, S. (2020). Last‐mile delivery concepts: A survey from an operational research perspective. OR Spectrum, 43, 1-58. |
| [2] | Chung, S. H., Sah, B., & Lee, J. (2020). Optimization for drone and drone‐truck combined operations: A review of the state of the art and future directions. Computers & Operations Research, 123, 105004. · Zbl 1458.90072 |
| [3] | Coindreau, M. A., Gallay, O., & Zufferey, N. (2021). Parcel delivery cost minimization with time window constraints using trucks and drones. Networks, 2021, 1-21. |
| [4] | Das, D. N., Sewani, R., Wang, J., & Tiwari, M. K. (2020). Synchronized truck and drone routing in package delivery logistics. IEEE Transactions on Intelligent Transportation Systems, 22, 5772-5782. https://doi.org/10.1109/TITS.2020.2992549 · doi:10.1109/TITS.2020.2992549 |
| [5] | Desaulniers, G., Desrosiers, J., & Solomon, M. (2005). Column generation. Springer. · Zbl 1084.90002 |
| [6] | Di Puglia Pugliese, L., & Guerriero, F. (2017). Last‐mile deliveries by using drones and classical vehicles. International conference on optimization and decision science (pp. 557-565). Springer, Cham. |
| [7] | Euchi, J., & Sadok, A. (2021). Hybrid genetic‐sweep algorithm to solve the vehicle routing problem with drones. Physical Communication, 44, 101236. |
| [8] | Irnich, S., & Desaulniers, G. (2005). Shortest path problems with resource constraints. In G.Desaulniers (ed.), J.Desrosiers (ed.), & M.Solomon (ed.) (Eds.), Column generation. Springer. · Zbl 1130.90315 |
| [9] | Jepsen, M., Petersen, B., Spoorendonk, S., & Pisinger, D. (2008). Subset‐row inequalities applied to the vehicle‐routing problem with time windows. Operations Research, 56(2), 497-511. · Zbl 1167.90413 |
| [10] | Kang, M., & Lee, C. (2021). An exact algorithm for heterogeneous drone‐truck routing problem. Transportation Science, 55(5), 1088-1112. |
| [11] | Kitjacharoenchai, P., Min, B. C., & Lee, S. (2020). Two echelon vehicle routing problem with drones in last mile delivery. International Journal of Production Economics, 225, 107598. |
| [12] | Kitjacharoenchai, P., Ventresca, M., Moshref‐Javadi, M., Lee, S., Tanchoco, J. M., & Brunese, P. A. (2019). Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering, 129, 14-30. |
| [13] | Li, H., Chen, J., Wang, F., & Bai, M. (2021). Ground‐vehicle and unmanned‐aerial‐vehicle routing problems from two‐echelon scheme perspective: A review. European Journal of Operational Research, 294, 1078-1095. · Zbl 1487.90130 |
| [14] | Li, H., Wang, H., Chen, J., & Bai, M. (2020). Two‐echelon vehicle routing problem with time windows and mobile satellites. Transportation Research Part B: Methodological, 138, 179-201. |
| [15] | Lübbecke, M., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, 53(6), 1007-1023. · Zbl 1165.90578 |
| [16] | Macrina, G., Di Puglia Pugliese, L., Guerriero, F., & Laporte, G. (2020). Drone‐aided routing: A literature review. Transportation Research Part C: Emerging Technologies, 120, 102762. |
| [17] | Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone‐assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109. |
| [18] | Otto, A., Agatz, N., Campbell, J., Golden, B., & Pesch, E. (2018). Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks, 72(4), 411-458. |
| [19] | Parragh, S. N., & Cordeau, J. F. (2017). Branch‐and‐price and adaptive large neighborhood search for the truck and trailer routing problem with time windows. Computers & Operations Research, 83, 28-44. · Zbl 1458.90127 |
| [20] | Poikonen, S., Golden, B., & Wasil, E. A. (2019). A branch‐and‐bound approach to the traveling salesman problem with a drone. INFORMS Journal on Computing, 31(2), 335-346. · Zbl 1535.90136 |
| [21] | Roberti, R., & Ruthmair, M. (2021). Exact methods for the traveling salesman problem with drone. Transportation Science, 55(2), 315-335. |
| [22] | Ropke, S., & Cordeau, J. F. (2009). Branch and cut and price for the pickup and delivery problem with time windows. Transportation Science, 43(3), 267-286. |
| [23] | Sacramento, D., Pisinger, D., & Ropke, S. (2019). An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies, 102, 289-315. |
| [24] | Sadykov, R., Uchoa, E., & Pessoa, A. (2021). A bucket graph‐based labeling algorithm with application to vehicle routing. Transportation Science, 55(1), 4-28. |
| [25] | Schermer, D., Moeini, M., & Wendt, O. (2019a). A matheuristic for the vehicle routing problem with drones and its variants. Transportation Research Part C: Emerging Technologies, 106, 166-204. |
| [26] | Schermer, D., Moeini, M., & Wendt, O. (2019b). A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Computers & Operations Research, 109, 134-158. · Zbl 1458.90138 |
| [27] | Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In International conference on principles and practice of constraint programming (pp. 417-431). Springer, Berlin, Heidelberg. |
| [28] | Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254-265. · Zbl 0625.90047 |
| [29] | Tamke, F., & Buscher, U. (2021). A branch‐and‐cut algorithm for the vehicle routing problem with drones. Transportation Research Part B: Methodological, 144, 174-203. |
| [30] | Wang, X., Poikonen, S., & Golden, B. (2017). The vehicle routing problem with drones: Several worst‐case results. Optimization Letters, 11(4), 679-697. · Zbl 1367.90012 |
| [31] | Wang, Z., & Sheu, J. B. (2019). Vehicle routing problem with drones. Transportation Research Part B: Methodological, 122, 350-364. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
