{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T18:09:32Z","timestamp":1767982172954,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T00:00:00Z","timestamp":1718409600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T00:00:00Z","timestamp":1718409600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62373380"],"award-info":[{"award-number":["62373380"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Intell. Syst."],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Owing to low cost, high flexibility and delivery efficiency, effectively addressing the challenges of \u201clast-mile\u201d delivery. While collaborative truck-drone delivery systems have been proposed to overcome limitations such as limited battery life and payload capacity, they are not well-suited for large and heavy parcel delivery. To solve the issue, a pioneering heterogeneous multi-drone delivery system. In this system, the mother drone handles the delivery of large and heavy parcels, releasing small drones to manage the delivery of smaller and lighter parcels. To address the complexities of this multi-drone delivery system, we introduce a divide-and-conquer framework consisting of two integral phases. The first phase, the task allocation phase, generates multiple task allocation schemes, while the second phase, the single-drone route planning phase, produces high-quality routes for each individual drone. Two phases are performed in an iterative manner until the predefined stopping criteria are satisfied. In the task allocation phase, we propose a simulated annealing algorithm (SA) to facilitate task allocation among multiple drones, utilizing transfer and recombination operators to generate high-quality solutions. After obtaining the task allocation scheme, a satisfactory route of a mother drone is generated by a variable neighborhood descent algorithm (VND). A desirable route for each single small drone is produced by dynamic programming (DP).Extensive experiments are conducted, demonstrating the outstanding optimization and time efficiency of the proposed two-phase optimization method by the fact that it obtains within a 4.89% gap from the optimal solution generated by CPLEX in 15.48\u00a0s for instance up to 125 nodes.<\/jats:p>","DOI":"10.1007\/s40747-024-01472-6","type":"journal-article","created":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T08:02:37Z","timestamp":1718438557000},"page":"6449-6466","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["An iterative two-phase optimization method for heterogeneous multi-drone routing problem considering differentiated demands"],"prefix":"10.1007","volume":"10","author":[{"given":"Huan","family":"Liu","sequence":"first","affiliation":[]},{"given":"Guohua","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Yufei","family":"Yuan","sequence":"additional","affiliation":[]},{"given":"Dezhi","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Long","family":"Zheng","sequence":"additional","affiliation":[]},{"given":"Wei","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,15]]},"reference":[{"key":"1472_CR1","unstructured":"Statistics CB (2023) Statistical bulletin on national economic and social development of the people\u2019s republic of china in 2022. https:\/\/www.gov.cn\/xinwen\/2023-02\/28\/content_5743623.htm?eqid=d710c1730025226200000003645730fd\/. Accessed Dec 2023"},{"key":"1472_CR2","unstructured":"Daily C (2021) China Post Office releases transcript of double eleven express delivery. https:\/\/www.spb.gov.cn\/gjyzj\/c200081\/202111\/d0b5e290dcf448a891938d3421fce903.shtml\/. Accessed Dec 2023"},{"key":"1472_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105004","volume":"123","author":"SH Chung","year":"2020","unstructured":"Chung SH, Sah B, Lee J (2020) Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions. Comput Oper Res 123:105004","journal-title":"Comput Oper Res"},{"key":"1472_CR4","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.trc.2018.04.009","volume":"91","author":"EE Yurek","year":"2018","unstructured":"Yurek EE, Ozmutlu HC (2018) A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transport Res Part C Emerg Technol 91:249\u2013262","journal-title":"Transport Res Part C Emerg Technol"},{"issue":"2","key":"1472_CR5","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1287\/trsc.2020.1017","volume":"55","author":"R Roberti","year":"2021","unstructured":"Roberti R, Ruthmair M (2021) Exact methods for the traveling salesman problem with drone. Transp Sci 55(2):315\u2013335","journal-title":"Transp Sci"},{"key":"1472_CR6","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s10732-019-09431-y","volume":"26","author":"QM Ha","year":"2020","unstructured":"Ha QM, Deville Y, Pham QD, H\u00e0 MH (2020) A hybrid genetic algorithm for the traveling salesman problem with drone. J Heuristics 26:219\u2013247","journal-title":"J Heuristics"},{"key":"1472_CR7","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1016\/j.trb.2019.03.005","volume":"122","author":"Z Wang","year":"2019","unstructured":"Wang Z, Sheu J-B (2019) Vehicle routing problem with drones. Transport Res Part B Methodol 122:350\u2013364","journal-title":"Transport Res Part B Methodol"},{"key":"1472_CR8","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.trc.2019.06.016","volume":"106","author":"D Schermer","year":"2019","unstructured":"Schermer D, Moeini M, Wendt O (2019) A matheuristic for the vehicle routing problem with drones and its variants. Transport Res Part C Emerg Technol 106:166\u2013204","journal-title":"Transport Res Part C Emerg Technol"},{"key":"1472_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2021.116264","volume":"191","author":"R Kuo","year":"2022","unstructured":"Kuo R, Lu S-H, Lai P-Y, Mara STW (2022) Vehicle routing problem with drones considering time windows. Expert Syst Appl 191:116264","journal-title":"Expert Syst Appl"},{"key":"1472_CR10","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.trc.2015.03.005","volume":"54","author":"CC Murray","year":"2015","unstructured":"Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transport Res Part C Emerg Technol 54:86\u2013109","journal-title":"Transport Res Part C Emerg Technol"},{"issue":"4","key":"1472_CR11","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1109\/TASE.2015.2461213","volume":"12","author":"N Mathew","year":"2015","unstructured":"Mathew N, Smith SL, Waslander SL (2015) Planning paths for package delivery in heterogeneous multirobot teams. IEEE Trans Autom Sci Eng 12(4):1298\u20131308","journal-title":"IEEE Trans Autom Sci Eng"},{"key":"1472_CR12","volume-title":"Optimization of drone-assisted parcel delivery","author":"A Ponza","year":"2016","unstructured":"Ponza A (2016) Optimization of drone-assisted parcel delivery. University of Padova, Thesis of Master Degree"},{"issue":"9","key":"1472_CR13","doi-asserted-by":"publisher","first-page":"4052","DOI":"10.1287\/mnsc.2017.2824","volume":"64","author":"JG Carlsson","year":"2018","unstructured":"Carlsson JG, Song S (2018) Coordinated logistics with a truck and a drone. Manag Sci 64(9):4052\u20134069","journal-title":"Manag Sci"},{"issue":"4","key":"1472_CR14","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1287\/trsc.2017.0791","volume":"52","author":"N Agatz","year":"2018","unstructured":"Agatz N, Bouman P, Schmidt M (2018) Optimization approaches for the traveling salesman problem with drone. Transp Sci 52(4):965\u2013981","journal-title":"Transp Sci"},{"key":"1472_CR15","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.eswa.2018.03.032","volume":"104","author":"YS Chang","year":"2018","unstructured":"Chang YS, Lee HJ (2018) Optimal delivery routing with wider drone-delivery areas along a shorter truck-route. Expert Syst Appl 104:307\u2013317","journal-title":"Expert Syst Appl"},{"key":"1472_CR16","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1016\/j.trc.2019.11.003","volume":"110","author":"CC Murray","year":"2020","unstructured":"Murray CC, Raj R (2020) The multiple flying sidekicks traveling salesman problem: parcel delivery with multiple drones. Transport Res Part C Emerg Technol 110:368\u2013398","journal-title":"Transport Res Part C Emerg Technol"},{"key":"1472_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2021.103172","volume":"128","author":"Z Luo","year":"2021","unstructured":"Luo Z, Poon M, Zhang Z, Liu Z, Lim A (2021) The multi-visit traveling salesman problem with multi-drones. Transport Res Part C Emerg Technol 128:103172","journal-title":"Transport Res Part C Emerg Technol"},{"issue":"8","key":"1472_CR18","doi-asserted-by":"publisher","first-page":"13011","DOI":"10.1109\/TITS.2021.3119080","volume":"23","author":"Q Luo","year":"2021","unstructured":"Luo Q, Wu G, Ji B, Wang L, Suganthan PN (2021) Hybrid multi-objective optimization approach with pareto local search for collaborative truck-drone routing problems considering flexible time windows. IEEE Trans Intell Transp Syst 23(8):13011\u201313025","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"1472_CR19","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s11590-016-1035-3","volume":"11","author":"X Wang","year":"2017","unstructured":"Wang X, Poikonen S, Golden B (2017) The vehicle routing problem with drones: Several worst-case results. Optim Lett 11:679\u2013697","journal-title":"Optim Lett"},{"issue":"1","key":"1472_CR20","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1002\/net.21746","volume":"70","author":"S Poikonen","year":"2017","unstructured":"Poikonen S, Wang X, Golden B (2017) The vehicle routing problem with drones: extended models and connections. Networks 70(1):34\u201343","journal-title":"Networks"},{"key":"1472_CR21","unstructured":"Campbell JF, Sweeney D, Zhang J (2017) Strategic design for delivery with trucks and drones. Supply Chain Analytics Report SCMA (04 2017), 47\u201355"},{"issue":"2","key":"1472_CR22","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1016\/j.ejor.2023.03.031","volume":"310","author":"M Ostermeier","year":"2023","unstructured":"Ostermeier M, Heimfarth A, H\u00fcbner A (2023) The multi-vehicle truck-and-robot routing problem for last-mile delivery. Eur J Oper Res 310(2):680\u2013697","journal-title":"Eur J Oper Res"},{"key":"1472_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.trc.2018.03.025","volume":"91","author":"AM Ham","year":"2018","unstructured":"Ham AM (2018) Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming. Transport Res Part C Emerg Technol 91:1\u201314","journal-title":"Transport Res Part C Emerg Technol"},{"key":"1472_CR24","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.trc.2019.02.018","volume":"102","author":"D Sacramento","year":"2019","unstructured":"Sacramento D, Pisinger D, Ropke S (2019) An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transport Res Part C Emerg Technol 102:289\u2013315","journal-title":"Transport Res Part C Emerg Technol"},{"key":"1472_CR25","doi-asserted-by":"crossref","unstructured":"Chen C, Demir E, Huang Y (2021) An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots. Eur J Oper Res 294(3):1164\u20131180","DOI":"10.1016\/j.ejor.2021.02.027"},{"issue":"1","key":"1472_CR26","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.ejor.2023.06.021","volume":"312","author":"J Jiang","year":"2024","unstructured":"Jiang J, Dai Y, Yang F, Ma Z (2024) A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services. Eur J Oper Res 312(1):125\u2013137","journal-title":"Eur J Oper Res"},{"issue":"12","key":"1472_CR27","doi-asserted-by":"publisher","first-page":"25077","DOI":"10.1109\/TITS.2022.3181282","volume":"23","author":"G Wu","year":"2022","unstructured":"Wu G, Mao N, Luo Q, Xu B, Shi J, Suganthan PN (2022) Collaborative truck-drone routing for contactless parcel delivery during the epidemic. IEEE Trans Intell Transp Syst 23(12):25077\u201325091","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"1472_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2023.101295","volume":"79","author":"STW Mara","year":"2023","unstructured":"Mara STW, Sarker R, Essam D, Elsayed S (2023) Solving electric vehicle-drone routing problem using memetic algorithm. Swarm Evol Comput 79:101295","journal-title":"Swarm Evol Comput"},{"issue":"3","key":"1472_CR29","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1177\/0162243920943665","volume":"46","author":"A Delfanti","year":"2021","unstructured":"Delfanti A, Frey B (2021) Humanly extended automation or the future of work seen through Amazon patents. Sci Technol Human Values 46(3):655\u2013682","journal-title":"Sci Technol Human Values"},{"issue":"12","key":"1472_CR30","doi-asserted-by":"publisher","first-page":"7521","DOI":"10.1109\/TITS.2020.3003900","volume":"22","author":"HY Jeong","year":"2020","unstructured":"Jeong HY, Song BD, Lee S (2020) The flying warehouse delivery system: A quantitative approach for the optimal operation policy of airborne fulfillment center. IEEE Trans Intell Transp Syst 22(12):7521\u20137530","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"1472_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2022.103763","volume":"141","author":"X Wen","year":"2022","unstructured":"Wen X, Wu G (2022) Heterogeneous multi-drone routing problem for parcel delivery. Transport Res Part C Emerg Technol 141:103763","journal-title":"Transport Res Part C Emerg Technol"},{"issue":"9","key":"1472_CR32","doi-asserted-by":"publisher","first-page":"5926","DOI":"10.1109\/TITS.2020.3042670","volume":"22","author":"H Liu","year":"2020","unstructured":"Liu H, Li X, Wu G, Fan M, Wang R, Gao L, Pedrycz W (2020) An iterative two-phase optimization method based on divide and conquer framework for integrated scheduling of multiple uavs. IEEE Trans Intell Transp Syst 22(9):5926\u20135938","journal-title":"IEEE Trans Intell Transp Syst"},{"issue":"1","key":"1472_CR33","first-page":"100","volume":"28","author":"JA Hartigan","year":"1979","unstructured":"Hartigan JA, Wong MA (1979) Algorithm AS 136: a k-means clustering algorithm. J R Stat Soc Ser C (Applied Statistics) 28(1):100\u2013108","journal-title":"J R Stat Soc Ser C (Applied Statistics)"},{"issue":"3731","key":"1472_CR34","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1126\/science.153.3731.34","volume":"153","author":"R Bellman","year":"1966","unstructured":"Bellman R (1966) Dynamic programming. Science 153(3731):34\u201337","journal-title":"Science"},{"issue":"1","key":"1472_CR35","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman R (1962) Dynamic programming treatment of the travelling salesman problem. J ACM (JACM) 9(1):61\u201363","journal-title":"J ACM (JACM)"},{"key":"1472_CR36","volume-title":"Variable neighborhood search","author":"P Hansen","year":"2019","unstructured":"Hansen P, Mladenovi\u0107 N, Brimberg J, P\u00e9rez JAM (2019) Variable neighborhood search. Springer"},{"issue":"4598","key":"1472_CR37","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671\u2013680","journal-title":"Science"},{"key":"1472_CR38","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/j.trc.2017.11.015","volume":"86","author":"QM Ha","year":"2018","unstructured":"Ha QM, Deville Y, Pham QD, H\u00e0 MH (2018) On the min-cost traveling salesman problem with drone. Transport Res Part C Emerg Technol 86:597\u2013621","journal-title":"Transport Res Part C Emerg Technol"},{"key":"1472_CR39","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.cor.2019.04.021","volume":"109","author":"D Schermer","year":"2019","unstructured":"Schermer D, Moeini M, Wendt O (2019) A hybrid VNS\/tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Comput Oper Res 109:134\u2013158","journal-title":"Comput Oper Res"},{"issue":"4","key":"1472_CR40","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1287\/trsc.1030.0049","volume":"38","author":"R Bent","year":"2004","unstructured":"Bent R, Van Hentenryck P (2004) A two-stage hybrid local search for the vehicle routing problem with time windows. Transp Sci 38(4):515\u2013530","journal-title":"Transp Sci"},{"key":"1472_CR41","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2023.3287163","author":"X Bai","year":"2023","unstructured":"Bai X, Ye Y, Zhang B, Ge SS (2023) Efficient package delivery task assignment for truck and high capacity drone. IEEE Trans Intell Transport Syst. https:\/\/doi.org\/10.1109\/TITS.2023.3287163","journal-title":"IEEE Trans Intell Transport Syst"}],"container-title":["Complex &amp; Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-024-01472-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40747-024-01472-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-024-01472-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T15:11:33Z","timestamp":1726326693000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40747-024-01472-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,15]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1472"],"URL":"https:\/\/doi.org\/10.1007\/s40747-024-01472-6","relation":{},"ISSN":["2199-4536","2198-6053"],"issn-type":[{"value":"2199-4536","type":"print"},{"value":"2198-6053","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,15]]},"assertion":[{"value":"3 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 March 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all the authors, the corresponding author states that there is no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}