{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T03:20:57Z","timestamp":1776396057190,"version":"3.51.2"},"reference-count":21,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T00:00:00Z","timestamp":1673136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Drones are currently seen as a viable way of improving the distribution of parcels in urban and rural environments, while working in coordination with traditional vehicles, such as trucks. In this paper, we consider the parallel drone scheduling traveling salesman problem, where a set of customers requiring a delivery is split between a truck and a fleet of drones, with the aim of minimizing the total time required to serve all the customers. We propose a constraint programming model for the problem, discuss its implementation and present the results of an experimental program on the instances previously cited in the literature to validate exact and heuristic algorithms. We were able to decrease the cost (the time required to serve customers) for some of the instances and, for the first time, to provide a demonstrated optimal solution for all the instances considered. These results show that constraint programming can be a very effective tool for attacking optimization problems with traveling salesman components, such as the one discussed.<\/jats:p>","DOI":"10.3390\/a16010040","type":"journal-article","created":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T04:47:08Z","timestamp":1673239628000},"page":"40","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Solving the Parallel Drone Scheduling Traveling Salesman Problem via Constraint Programming"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0229-0465","authenticated-orcid":false,"given":"Roberto","family":"Montemanni","sequence":"first","affiliation":[{"name":"Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Via Amendola 2, 42122 Reggio Emilia, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3283-6131","authenticated-orcid":false,"given":"Mauro","family":"Dell\u2019Amico","sequence":"additional","affiliation":[{"name":"Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Via Amendola 2, 42122 Reggio Emilia, Italy"},{"name":"Interdepartmental Center En&Tech, University of Modena and Reggio Emilia, Capannone 19 Tecnopolo, Piazza Europa 1, 42122 Reggio Emilia, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,8]]},"reference":[{"key":"ref_1","unstructured":"Joerss, M., Schroeder, J., Neuhaus, F., Klink, C., and Mann, F. (2016). Parcel Delivery\u2014The Future of Last Mile, McKinsey and Company."},{"key":"ref_2","unstructured":"Wolleswinkel, R., Lukic, V., Jap, W., Chan, R., Govers, J., and Banerjee, S. (2018). An Onslaught of New Rivals in Parcel and Express, Boston Consulting Group."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.trc.2015.03.005","article-title":"The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery","volume":"54","author":"Murray","year":"2015","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"102493","DOI":"10.1016\/j.omega.2021.102493","article-title":"Algorithms based on branch and bound for the flying sidekick traveling salesman problem","volume":"104","author":"Montemanni","year":"2021","journal-title":"Omega"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Toklu, N.E., Montemanni, R., and Gambardella, L.M. (2013, January 16\u201319). An ant colony system for the capacitated vehicle routing problem with uncertain travel costs. Proceedings of the 2013 IEEE Symposium on Swarm Intelligence (SIS), Singapore.","DOI":"10.1109\/SIS.2013.6615156"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2014","DOI":"10.1109\/JIOT.2021.3089334","article-title":"BrainIoT: Brain-Like Productive Services Provisioning With Federated Learning in Industrial IoT","volume":"9","author":"Yang","year":"2022","journal-title":"IEEE Internet Things J."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/net.21846","article-title":"An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem","volume":"72","author":"Deroussi","year":"2018","journal-title":"Networks"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/j.ejor.2021.08.014","article-title":"The parallel drone scheduling problem with multiple drones and vehicles","volume":"300","author":"Deroussi","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","unstructured":"Donati, A.V., Montemanni, R., Gambardella, L.M., and Rizzoli, A.E. (2003, January 29\u201331). Integration of a robust shortest path algorithm with a time dependent vehicle routing model and applications. Proceedings of the International Symposium on Computational Intelligence for Measurement Systems and Applications, Lugano, Switzerland."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s10479-020-03562-3","article-title":"Matheuristic algorithms for the parallel drone scheduling traveling salesman problem","volume":"289","author":"Montemanni","year":"2020","journal-title":"Ann. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Dinh, Q.T., Do, D.D., and H\u00e1, M.H. (2021, January 10\u201314). Ants can solve the parallel drone scheduling traveling salesman problem. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Lille, France.","DOI":"10.1145\/3449639.3459342"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"109416","DOI":"10.1016\/j.asoc.2022.109416","article-title":"An improved variable neighborhood search for parallel drone scheduling traveling salesman problem","volume":"127","author":"Lei","year":"2022","journal-title":"Appl. Soft Comput."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Raj, R., Lee, D., Lee, S., Walteros, J., and Murray, C. (2021). A Branch-and-Price Approach for the Parallel Drone Scheduling Vehicle Routing Problem. SSRN Electron. J., 3879710.","DOI":"10.2139\/ssrn.3879710"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1016\/j.ejor.2021.07.008","article-title":"The min-cost parallel drone scheduling vehicle routing problem","volume":"299","author":"Nguyen","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/net.21818","article-title":"Optimization approaches for civil applications of unmanned aerial vehicles (uavs) or aerial drones: A survey","volume":"72","author":"Otto","year":"2018","journal-title":"Networks"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"14224","DOI":"10.1109\/TITS.2022.3155072","article-title":"The Drone Scheduling Problem: A Systematic State-of-the-Art Review","volume":"23","author":"Pasha","year":"2022","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1108\/AEAT-03-2020-0057","article-title":"Improvement of the thrust-torque ratio of an unmanned helicopter by using the ABC algorithm","volume":"92","author":"Konar","year":"2020","journal-title":"Aircr. Eng. Aerosp. Technol."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1108\/AEAT-04-2019-0077","article-title":"Analysis of combined passively and actively morphing blade root chord length and blade taper for helicopter control","volume":"92","author":"Sal","year":"2020","journal-title":"Aircr. Eng. Aerosp. Technol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1109\/LRA.2015.2509024","article-title":"A Machine Learning Approach to Visual Perception of Forest Trails for Mobile Robots","volume":"1","author":"Giusti","year":"2016","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"102079","DOI":"10.1016\/j.techsoc.2022.102079","article-title":"Safety and privacy regulations for unmanned aerial vehicles: A multiple comparative analysis","volume":"71","author":"Lee","year":"2022","journal-title":"Technol. Soc."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"TSPLIB\u2014A Traveling Salesman Problem Library","volume":"3","author":"Reinelt","year":"1991","journal-title":"ORSA J. Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/40\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:03:39Z","timestamp":1760119419000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,8]]},"references-count":21,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["a16010040"],"URL":"https:\/\/doi.org\/10.3390\/a16010040","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,8]]}}}