{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T19:32:26Z","timestamp":1780428746113,"version":"3.54.1"},"reference-count":27,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2025,4,26]],"date-time":"2025-04-26T00:00:00Z","timestamp":1745625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>ABSTRACT<\/jats:title><jats:p>Nowadays, driven by factors such as the rapid growth of online sales, different delivery methods are being explored to improve last\u2010mile logistics processes. Among these, the combined use of trucks and drones and the option of utilizing parcel lockers as an alternative to home delivery have led to the definition of new optimization problems. In this work, we study the Traveling Salesman Problem with Drone and Lockers (<jats:italic>TSP\u2010DL<\/jats:italic>), the first optimization problem to integrate both of these innovative delivery methods. The goal is to determine the optimal route for a tandem consisting of a truck and a drone to serve a set of customers. Each customer can either be served at home or retrieve their package from a parcel locker where the tandem has delivered it. The objective is to minimize total delivery costs, which depend on the total delivery time and compensation provided by the delivery company to customers served via parcel lockers. We propose a new formulation for the TSP\u2010DL, strengthened by additional valid inequalities and solved using a Branch\u2010and\u2010Cut algorithm. Unlike other formulations in the literature, our approach does not use time variables. Computational experiments on benchmark instances demonstrate that the proposed approach outperforms the current state of the art for the <jats:italic>TSP\u2010DL<\/jats:italic>, providing either optimal solutions or improved bounds for several previously unsolved instances. Additionally, we introduce a new set of benchmark instances to evaluate the scalability of the proposed approach. Finally, we provide managerial insights derived from an analysis of different coordination policies between the truck and the drone.<\/jats:p>","DOI":"10.1002\/net.22280","type":"journal-article","created":{"date-parts":[[2025,4,26]],"date-time":"2025-04-26T09:45:27Z","timestamp":1745660727000},"page":"112-143","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A New Formulation for the Traveling Salesman Problem With Drone and Lockers"],"prefix":"10.1002","volume":"86","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0009-0005-4903-3406","authenticated-orcid":false,"given":"Danilo","family":"Amitrano","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Information Technology University of Naples Federico II  Naples Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maurizio","family":"Boccia","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Information Technology University of Naples Federico II  Naples Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adriano","family":"Masone","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Information Technology University of Naples Federico II  Naples Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claudio","family":"Sterle","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Information Technology University of Naples Federico II  Naples Italy"},{"name":"Istituto di Analisi dei Sistemi ed Informatica A.Ruberti, IASI\u2010CNR  Rome Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2025,4,26]]},"reference":[{"issue":"1","key":"e_1_2_10_2_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00291-020-00607-8","article-title":"Last\u2010Mile Delivery Concepts: A Survey From an Operational Research Perspective","volume":"43","author":"Boysen N.","year":"2021","journal-title":"OR Spectrum"},{"issue":"9","key":"e_1_2_10_3_1","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1108\/IJPDLM-02-2019-0048","article-title":"Innovative Solutions to Increase Last\u2010Mile Delivery Efficiency in B2C e\u2010Commerce: A Literature Review","volume":"49","author":"Mangiaracina R.","year":"2019","journal-title":"International Journal of Physical Distribution and Logistics Management"},{"key":"e_1_2_10_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105004"},{"key":"e_1_2_10_5_1","volume-title":"A Guide to Parcel Lockers in Last Mile Distribution: Highlighting Challenges and Opportunities From an OR Perspective","author":"Rohmer S.","year":"2020"},{"key":"e_1_2_10_6_1","doi-asserted-by":"crossref","first-page":"102913","DOI":"10.1016\/j.trc.2020.102913","article-title":"A Column\u2010And\u2010Row Generation Approach for the Flying Sidekick Travelling Salesman Problem","volume":"124","author":"Boccia M.","year":"2021","journal-title":"Transportation Research Part C: Emerging Technologies"},{"key":"e_1_2_10_7_1","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\u2010Assisted Parcel Delivery","volume":"54","author":"Murray C. C.","year":"2015","journal-title":"Transportation Research Part C: Emerging Technologies"},{"issue":"4","key":"e_1_2_10_8_1","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1287\/trsc.2017.0791","article-title":"Optimization Approaches for the Traveling Salesman Problem With Drone","volume":"52","author":"Agatz N.","year":"2018","journal-title":"Transportation Science"},{"issue":"2","key":"e_1_2_10_9_1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1287\/ijoc.2018.0826","article-title":"A Branch\u2010And\u2010Bound Approach to the Traveling Salesman Problem With a Drone","volume":"31","author":"Poikonen S.","year":"2019","journal-title":"INFORMS Journal on Computing"},{"issue":"18","key":"e_1_2_10_10_1","doi-asserted-by":"crossref","first-page":"12843","DOI":"10.1007\/s00500-021-06592-6","article-title":"Last Mile Deliveries With Lockers: Formulations and Algorithms","volume":"27","author":"Buzzega G.","year":"2023","journal-title":"Soft Computing"},{"key":"e_1_2_10_11_1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s10100-020-00725-2","article-title":"The Vehicle Routing Problem With Heterogeneous Locker Boxes","volume":"29","author":"Grabenschweiger J.","year":"2021","journal-title":"Central European Journal of Operations Research"},{"issue":"2","key":"e_1_2_10_12_1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1002\/net.22190","article-title":"Last\u2010Mile Delivery With Drone and Lockers","volume":"83","author":"Boschetti M. A.","year":"2024","journal-title":"Networks"},{"issue":"2","key":"e_1_2_10_13_1","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s40305-021-00383-4","article-title":"A Survey of Truck\u2013Drone Routing Problem: Literature Review and Research Prospects","volume":"10","author":"Liang Y. J.","year":"2022","journal-title":"Journal of the Operations Research Society of China"},{"issue":"2","key":"e_1_2_10_14_1","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1287\/trsc.2020.1017","article-title":"Exact Methods for the Traveling Salesman Problem With Drone","volume":"55","author":"Roberti R.","year":"2021","journal-title":"Transportation Science"},{"issue":"8","key":"e_1_2_10_15_1","doi-asserted-by":"crossref","first-page":"1617","DOI":"10.1007\/s11590-019-01492-z","article-title":"Drone\u2010Assisted Deliveries: New Formulations for the Flying Sidekick Traveling Salesman Problem","volume":"15","author":"Dell'Amico M.","year":"2021","journal-title":"Optimization Letters"},{"issue":"3","key":"e_1_2_10_16_1","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1002\/net.22172","article-title":"A New MILP Formulation for the Flying Sidekick Traveling Salesman Problem","volume":"82","author":"Boccia M.","year":"2023","journal-title":"Networks"},{"key":"e_1_2_10_17_1","doi-asserted-by":"crossref","first-page":"1064","DOI":"10.1287\/ijoc.2022.0390","article-title":"Decremental State\u2010Space Relaxations for the Basic Traveling Salesman Problem With a Drone","volume":"36","author":"Blufstein M.","year":"2024","journal-title":"INFORMS Journal on Computing"},{"issue":"16","key":"e_1_2_10_18_1","doi-asserted-by":"crossref","first-page":"5077","DOI":"10.1080\/00207543.2019.1656842","article-title":"A Traveling Salesman Problem With Time Windows for the Last Mile Delivery in Online Shopping","volume":"58","author":"Jiang L.","year":"2020","journal-title":"International Journal of Production Research"},{"key":"e_1_2_10_19_1","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2021.105361","article-title":"Vehicle Routing With Private and Shared Delivery Locations","volume":"133","author":"Mancini S.","year":"2021","journal-title":"Computers & Operations Research"},{"issue":"1","key":"e_1_2_10_20_1","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1080\/00207543.2017.1395490","article-title":"A Parcel Locker Network as a Solution to the Logistics Last Mile Problem","volume":"56","author":"Deutsch Y.","year":"2018","journal-title":"International Journal of Production Research"},{"issue":"3","key":"e_1_2_10_21_1","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1016\/j.ejor.2017.06.034","article-title":"An Approximate Dynamic Programming Approach to Attended Home Delivery Management","volume":"263","author":"Yang X.","year":"2017","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"e_1_2_10_22_1","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ejor.2016.04.059","article-title":"Orienteering Problem: A Survey of Recent Variants, Solution Approaches and Applications","volume":"255","author":"Gunawan A.","year":"2016","journal-title":"European Journal of Operational Research"},{"key":"e_1_2_10_23_1","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.cor.2017.08.013","article-title":"Multi\u2010Commodity Location\u2010Routing: Flow Intercepting Formulation and Branch\u2010And\u2010Cut Algorithm","volume":"89","author":"Boccia M.","year":"2018","journal-title":"Computers & Operations Research"},{"key":"e_1_2_10_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_2_10_25_1","unstructured":"PayScale \u201cJob Salaries \u201d(2024) https:\/\/2.zoppoz.workers.dev:443\/https\/www.payscale.com\/."},{"key":"e_1_2_10_26_1","unstructured":"PassMark Software \u201cCPU Benchmarks \u201d(2024) https:\/\/2.zoppoz.workers.dev:443\/http\/www.cpubenchmark.net."},{"key":"e_1_2_10_27_1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-3-030-86433-0_9","volume-title":"Mathematical Optimization Theory and Operations Research: Recent Trends: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5\u201310, 2021, Revised Selected Papers","author":"Boccia M.","year":"2021"},{"key":"e_1_2_10_28_1","doi-asserted-by":"crossref","DOI":"10.1016\/j.eswa.2023.123106","article-title":"New Features for Customer Classification in the Flying Sidekick Traveling Salesman Problem","volume":"247","author":"Boccia M.","year":"2024","journal-title":"Expert Systems with Applications"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.22280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T12:51:31Z","timestamp":1754052691000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/net.22280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,26]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10.1002\/net.22280"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/net.22280","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,26]]},"assertion":[{"value":"2024-07-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}