Abstract
A promising new model for future logistics networks involves the collaboration between traditional trucks and modern drones. The drone can pick up packages from the truck and deliver them by air while the truck is serving other customers. The operational challenge combines the allocation of delivery locations to either the truck or the drone, and the coordinated routing of the truck and the drone. In this work, we consider the scenario of a single truck and one drone, with the objective to minimize the completion time (or makespan). As our first contribution, we prove that this problem is strongly NP-hard, even in the restricted case when drone deliveries need to be optimally integrated in a given truck route. We then present a constraint programming formulation that compactly represents the operational constraints between the truck and the drone. Our computational experiments show that solving the CP model to optimality is significantly faster than the state-of-the-art exact algorithm. For larger instances, our CP-based heuristic algorithm is competitive with a state-of-the-art heuristic method.
This work was supported by Office of Naval Research grant N00014-18-1-2129.
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
Agatz, N., Bouman, P., Schmidt, M.: Optimization approaches for the traveling salesman problem with drone. Transp. Sci. 52(4), 965–981 (2018)
Bouman, P., Agatz, N., Schmidt, M.: Dynamic programming approaches for the traveling salesman problem with drone. Networks 72(4), 528–542 (2018)
Daknama, R., Kraus, E.: Vehicle routing with drones. ar**v preprint ar**v:1705.06431 (2017)
Dorling, K., Heinrichs, J., Messier, G.G., Magierowski, S.: Vehicle routing problems for drone delivery. IEEE Trans. Syst. Man Cybern. Syst. 47(1), 70–85 (2017)
Ha, Q.M., Deville, Y., Dung, P.Q., HÃ , M.H.: Heuristic methods for the traveling salesman problem with drone. CoRR abs/1509.08764 (2015)
Ha, Q.M., Deville, Y., Pham, Q.D., Hà , M.H.: On the min-cost traveling salesman problem with drone. Transp. Res. Part C Emerg. Technol. 86, 597–621 (2018)
Ham, A.M.: Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming. Transp. Res. Part C Emerg. Technol. 91, 1–14 (2018)
IBM ILOG CPLEX: CP Optimizer 12.7 Users Manual (2017)
Laborie, P.: IBM ILOG CP optimizer for detailed scheduling illustrated on three problems. In: van Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol. 5547, pp. 148–162. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01929-6_12
Laborie, P., Rogerie, J., Shaw, P., VilÃm, P.: IBM ILOG CP optimizer for scheduling. Constraints 23(2), 210–250 (2018)
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)
Otto, A., Agatz, N., Campbell, J., Golden, B., Pesch, E.: Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: a survey. Networks 72(4), 411–458 (2018)
Poikonen, S., Golden, B., Wasil, E.: A branch and bound approach to the TSP with drone. INFORMS J. Comput. (to appear)
Poikonen, S., Wang, X., Golden, B.: The vehicle routing problem with drones: extended models and connections. Networks 70(1), 34–43 (2017)
UPS: UPS Tests Residential Delivery Via Drone. Youtube (2017). https://www.youtube.com/watch?v=xx9_6OyjJrQ
Wang, X., Poikonen, S., Golden, B.: The vehicle routing problem with drones: several worst-case results. Optim. Lett. 11(4), 679–697 (2017)
Yurek, E.E., Ozmutlu, H.C.: A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transp. Res. Part C Emerg. Technol. 91, 249–262 (2018)
Acknowledgement
The first author would like to thank Thomas Bosman for helpful discussions on the complexity proof.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Tang, Z., Hoeve, WJ.v., Shaw, P. (2019). A Study on the Traveling Salesman Problem with a Drone. In: Rousseau, LM., Stergiou, K. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019. Lecture Notes in Computer Science(), vol 11494. Springer, Cham. https://doi.org/10.1007/978-3-030-19212-9_37
Download citation
DOI: https://doi.org/10.1007/978-3-030-19212-9_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-19211-2
Online ISBN: 978-3-030-19212-9
eBook Packages: Computer ScienceComputer Science (R0)