Abstract
Last-mile delivery problems where trucks and drones collaborate to deliver goods to final customers are considered. We focus on settings where a fleet with several homogeneous trucks work in parallel to collaborative drones, able to combine with each other to optimize speed and power consumption for deliveries. A heuristic for the min-max vehicle routing problem is coupled with constraint programming models, leading to an effective method able to provide several state-of-the-art solutions for the instances commonly adopted in the literature.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bertazzi, L., Golden, B., Wang, X.: Min-max vs. min-sum vehicle routing: a worst-case analysis. Eur. J. Oper. Res. 240(2), 372–381 (2015)
Google: OR-Tools (2023). https://developers.google.com/optimization/. Accessed 03 Mar 2023
Montemanni, R., Dell’Amico, M.: Solving the parallel drone scheduling traveling salesman problem via constraint programming. Algorithms 16(1), 40 (2023)
Montemanni, R., Dell’Amico, M., Corsini, A.: Parallel drone scheduling vehicle routing problems with collective drones. Comput. Oper. Res. 163, 106514 (2024)
Murray, C.C., Chu, A.G.: The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transp. Res. Part C: Emerg. Technol. 54, 86–109 (2015)
Nguyen, M.A., Hà, M.H.: The parallel drone scheduling traveling salesman problem with collective drones. Transp. Sci. 4(57), 866–888 (2023)
Nguyen, M.A., Luong, H.L., Hà, M.H., Ban, H.B.: An efficient branch-and-cut algorithm for the parallel drone scheduling traveling salesman problem. 4OR 21, 609–637 (2023)
Paczan, N.M., Elzinga, M.J., Hsieh, R., Nguyen, L.K.: Collective unmanned aerial vehicle configurations (2022). Patent US 11,480,958 B2
Raj, R., Lee, D., Lee, S., Walteros, J., Murray, C.: A branch-and-price approach for the parallel drone scheduling vehicle routing problem. SSRN Electron. J. 1–47 (2021)
Toth, P., Vigo, D.: The Vehicle Routing Problem. SIAM (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Montemanni, R., Dell’Amico, M., Corsini, A. (2024). Combining Heuristics and Constraint Programming for the Parallel Drone Scheduling Vehicle Routing Problem with Collective Drones. In: Sevaux, M., Olteanu, AL., Pardo, E.G., Sifaleras, A., Makboul, S. (eds) Metaheuristics. MIC 2024. Lecture Notes in Computer Science, vol 14753 . Springer, Cham. https://doi.org/10.1007/978-3-031-62912-9_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-62912-9_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-62911-2
Online ISBN: 978-3-031-62912-9
eBook Packages: Computer ScienceComputer Science (R0)