The study analyzes how last-mile delivery performance can be improved based on one truck and multiple drones in tandem. The Rerouting Traveling Salesman Problem with Drones (RTSP-D) model is proposed to minimize the tour time delivery. In RTSP-D, a truck plays the role of a dynamic platform for dispatching and collecting drones and free of parcel delivery, while multiple drones distribute parcels to customers to minimize the time spent on the entire route. A three-stage heuristic is also proposed to solve the problem. The heuristic consists of bisecting radius K-means for clustering at the first stage, guided local search for a virtual truck route at the second stage, and the rerouting mechanism at the third stage. The RTSP-D significantly achieves tour time reduction up to 63% compared to vehicle routing mode and 6.99% compared to the flexible drones TSP (FDTSP) mode. The number of drones equipped with the truck should be three or four to gain the maximum benefits; otherwise, the RTSP-D yields declining marginal returns. The study also examines the two other indicators, i.e., service level and waiting time. The results reveal that the service level is overall higher than 90%, while the waiting time varies, depending on specific factored settings. The RTSP-D is suitable for suburban and countryside areas with lower customer density. Additionally, the higher the drone speed, the higher the efficiency of the RTSP-D.

Accenture. (2020). The sustainable last mile: Faster, Cheaper, Greener. https://www.accenture.com/_acnmedia/PDF-148/Accenture-Sustainable-Mile-POV.pdf
Accenture. (2021). How could last mile delivery evolve to sustainable meet customer expectations? https://www.accenture.com/_acnmedia/pdf-95/accenture-last-mile-delivery-meet-customer-expectations.pdf
Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4), 965-981.
Anbuudayasankar, S., Ganesh, K., & Mohapatra, S. (2016). Models for practical routing problems in logistics. Springer.
Aurambout, J.-P., Gkoumas, K., & Ciuffo, B. (2019). Last mile delivery by drones: An estimation of viable market potential and access to citizens across European cities. European Transport Research Review, 11(1), 1-21.
Barrett, T. (2019, April 24, 2019). Consumers more likely to shop somewhere with sustainable delivery. Airquality News. https://airqualitynews.com/2019/04/24/consumers-more-likely-to-shop-somewhere-with-green-delivery-options/
Bouman, P., Agatz, N., & Schmidt, M. (2018). Dynamic programming approaches for the traveling salesman problem with drone. Networks, 72(4), 528-542.
Boysen, N., Fedtke, S., & Schwerdfeger, S. (2021). Last-mile delivery concepts: a survey from an operational research perspective. Or Spectrum, 43(1), 1-58.
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313. https://doi.org/https://doi.org/10.1016/j.cie.2015.12.007
Business Insider. (2019, Jan 25, 2019). The crowdsourced delivery market continues to improve last mile supply chain economics in the e-commerce era. https://www.businessinsider.com/crowdsourced-delivery-report
Chung, S. H., Sah, B., & Lee, J. (2020). Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions. Computers & Operations Research, 123, 105004.
CISION. (2021). At 9.29% CAGR, Last-mile delivery Market size is Expected to reach USD 200.42 Bn in 2027. PN Newswire. https://www.prnewswire.com/news-releases/at-9-29-cagr-last-mile-delivery-market-size-is-expected-to-reach-usd-200-42-bn-in-2027--says-brandessence-market-research-301387705.html
Collins, K. (2021, Aug 3, 2021). Amazon scales back Prime Air drone delivery project in the UK. CNET. https://www.cnet.com/tech/tech-industry/amazon-scales-back-prime-air-drone-delivery-project-in-the-uk/
Comi, A. (2021). Shopping and Transport Modes. In R. Vickerman (Ed.), International Encyclopedia of Transportation (pp. 98-105). Elsevier. https://doi.org/https://doi.org/10.1016/B978-0-08-102671-7.10412-9
Crevier, B., Cordeau, J.-F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2), 756-773. https://doi.org/https://doi.org/10.1016/j.ejor.2005.08.015
Cullen, J., & Bruce, R. (2021). Managing costs of supply chain risks beyond the pandemic. Financial Management. https://www.fm-magazine.com/issues/2021/sep/mange-costs-of-supply-chain-risks.html
Curlander, J. C., Gilboa-Amir, A., Kisser, L. M., Koch, R. A., & Welsh, R. D. (2017). Multi-level fulfillment center for unmanned aerial vehicles. In: Google Patents.
Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2(4), 393-410.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
Davendra, D. (2010). Traveling salesman problem: Theory and applications. BoD–Books on Demand.
Deb, S., Fong, S., Tian, Z., Wong, R. K., Mohammed, S., & Fiaidhi, J. (2016). Finding approximate solutions of NP-hard optimization and TSP problems using elephant search algorithm. The Journal of Supercomputing, 72(10), 3960-3992.
Deng, Y., Liu, Y., & Zhou, D. (2015). An improved genetic algorithm with initial population strategy for symmetric TSP. Mathematical Problems in Engineering, 2015.
Falcocchio, J. C., & Levinson, H. S. (2015). The costs and other consequences of traffic congestion. In Road Traffic Congestion: A Concise Guide (pp. 159-182). Springer.
Ferrandez, S. M., Harbison, T., Weber, T., Sturges, R., & Rich, R. (2016). Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. Journal of Industrial Engineering and Management (JIEM), 9(2), 374-388.
Figliozzi, M. A. (2017). Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO2e emissions. Transportation Research Part D: Transport and Environment, 57, 251-261.
Gartner, I. (2021). Reinventing Supply Chain for the Future: 4 innovations to build a disruption-tough supply chain. https://www.gartner.com/en/supply-chain/trends/future-of-supply-chain
Global Industry Analysts. (2022). Last Mile Delivery: World Market Report. https://www.strategyr.com/market-report-last-mile-delivery-forecasts-global-industry-analysts-inc.asp
Golob, T. F., & Regan, A. C. (2001). Impacts of highway congestion on freight operations: perceptions of trucking industry managers. Transportation Research Part A: Policy and Practice, 35(7), 577-599.
Goodchild, A., & Toy, J. (2018). Delivery by drone: An evaluation of unmanned aerial vehicle technology in reducing CO2 emissions in the delivery service industry. Transportation Research Part D: Transport and Environment, 61, 58-67.
Gutin, G., & Punnen, A. P. (2006). The traveling salesman problem and its variations (Vol. 12). Springer Science & Business Media.
Ha, Q. M., Deville, Y., Pham, Q. D., & Hà, M. H. (2018). On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 86, 597-621.
Ham, A. M. (2018). Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming. Transportation Research Part C: Emerging Technologies, 91, 1-14.
Huang, Y.-H., Blazquez, C. A., Huang, S.-H., Paredes-Belmar, G., & Latorre-Nuñez, G. (2019). Solving the Feeder Vehicle Routing Problem using ant colony optimization. Computers & Industrial Engineering, 127, 520-535. https://doi.org/https://doi.org/10.1016/j.cie.2018.10.037
Kapser, S., & Abdelrahman, M. (2020). Acceptance of autonomous delivery vehicles for last-mile delivery in Germany–Extending UTAUT2 with risk perceptions. Transportation Research Part C: Emerging Technologies, 111, 210-225.
Karagul, K., Sahin, Y., Aydemir, E., & Oral, A. (2019). A Simulated Annealing Algorithm Based Solution Method for a Green Vehicle Routing Problem with Fuel Consumption. In T. Paksoy, G.-W. Weber, & S. Huber (Eds.), Lean and Green Supply Chain Management: Optimization Models and Algorithms (pp. 161-187). Springer International Publishing. https://doi.org/10.1007/978-3-319-97511-5_6
Keeney, T. (2015). How Can Amazon Charge $1 for Drone Delivery? https://ark-invest.com/analyst-research/drone-delivery-amazon/
Khanduja, N., & Bhushan, B. (2021). Recent Advances and Application of Metaheuristic Algorithms: A Survey (2014–2020). In H. Malik, A. Iqbal, P. Joshi, S. Agrawal, & F. I. Bakhsh (Eds.), Metaheuristic and Evolutionary Computation: Algorithms and Applications (pp. 207-228). Springer Singapore. https://doi.org/10.1007/978-981-15-7571-6_10
Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M., & Brunese, P. A. (2019). Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering, 129, 14-30.
Koetsier, J. (2021). Drone Delivery Is Live Today, And It’s 90% Cheaper Than Car-Based Services. Forbes. https://www.forbes.com/sites/johnkoetsier/2021/08/18/drone-delivery-is-live-today-and-its-90-cheaper-than-car-based-services/?sh=4bed19554d02
Kong, W., Zhang, D., Wang, X., Xian, Z., & Zhang, J. (2013). Autonomous landing of an UAV with a ground-based actuated infrared stereo vision system. 2013 IEEE/RSJ international conference on intelligent robots and systems,
Kuo, R., Lu, S.-H., Lai, P.-Y., & Mara, S. T. W. (2022). Vehicle routing problem with drones considering time windows. Expert Systems with Applications, 191, 116264.
Labadie, N., Prins, C., & Prodhon, C. (2016). Metaheuristics for vehicle routing problems. John Wiley & Sons.
Lai, D. S. W., Caliskan Demirag, O., & Leung, J. M. Y. (2016). A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E: Logistics and Transportation Review, 86, 32-52. https://doi.org/https://doi.org/10.1016/j.tre.2015.12.001
Lawton, G. (2021, Jul 13, 2021). The environmental challenges of last-mile delivery. Techtarget. The environmental challenges of last-mile delivery
Li, H., & Alidaee, B. (2016). Tabu search for solving the black-and-white travelling salesman problem. Journal of the Operational Research Society, 67(8), 1061-1079.
Lim, S. F. W., Jin, X., & Srai, J. S. (2018). Consumer-driven e-commerce: A literature review, design framework, and research agenda on last-mile logistics models. International Journal of Physical Distribution & Logistics Management.
Lin, C., Choy, K. L., Ho, G. T. S., Chung, S. H., & Lam, H. Y. (2014). Survey of Green Vehicle Routing Problem: Past and future trends. Expert Systems with Applications, 41(4, Part 1), 1118-1138. https://doi.org/https://doi.org/10.1016/j.eswa.2013.07.107
Lin, J., & Singer, P. W. (2018, Jul 4, 2018). Meet China’s growing fleet of automated delivery drones. Popular Science. https://www.popsci.com/china-drone-deliveries/
Lisa, A. (2020). How Traffic Jams Are Costing Us Billions of Dollars and Even More Hours. Yahoo! Finance. https://finance.yahoo.com/news/17-ways-traffic-costing-fortune-161307495.html
Liu, C., Wang, Q., & Susilo, Y. O. (2019). Assessing the impacts of collection-delivery points to individual’s activity-travel patterns: A greener last mile alternative? Transportation Research Part E: Logistics and Transportation Review, 121, 84-99.
Lu, S.-H., Kuo, R., Ho, Y. T., & Nguyen, A.-T. (2022). Improving the efficiency of last-mile delivery with the flexible drones traveling salesman problem. In. manuscript submitted for publication.
Mangiaracina, R., Perego, A., Seghezzi, A., & Tumino, A. (2019). Innovative solutions to increase last-mile delivery efficiency in B2C e-commerce: a literature review. International Journal of Physical Distribution & Logistics Management.
Mohammed, M. A., Abd Ghani, M. K., Hamed, R. I., Mostafa, S. A., Ahmad, M. S., & Ibrahim, D. A. (2017). Solving vehicle routing problem by using improved genetic algorithm for optimal solution. Journal of Computational Science, 21, 255-262. https://doi.org/https://doi.org/10.1016/j.jocs.2017.04.003
Montoya-Torres, J. R., López Franco, J., Nieto Isaza, S., Felizzola Jiménez, H., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115-129. https://doi.org/https://doi.org/10.1016/j.cie.2014.10.029
Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109.
Murray, C. C., & Raj, R. (2020). The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transportation Research Part C: Emerging Technologies, 110, 368-398. https://doi.org/https://doi.org/10.1016/j.trc.2019.11.003
Nagy, G., & Salhi, S. d. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162(1), 126-141. https://doi.org/https://doi.org/10.1016/j.ejor.2002.11.003
Perron, L., & Furnon, V. (2019). OR-Tools (version 7.2), 2019. URL https://developers. google. com/optimization.
Poikonen, S., Wang, X., & Golden, B. (2017). The vehicle routing problem with drones: Extended models and connections. Networks, 70(1), 34-43.
Qiu, M., Fu, Z., Eglese, R., & Tang, Q. (2018). A Tabu Search algorithm for the vehicle routing problem with discrete split deliveries and pickups. Computers & Operations Research, 100, 102-116. https://doi.org/https://doi.org/10.1016/j.cor.2018.07.021
Raj, R., & Murray, C. (2020). The multiple flying sidekicks traveling salesman problem with variable drone speeds. Transportation Research Part C: Emerging Technologies, 120, 102813.
Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003). On the capacitated vehicle routing problem. Mathematical Programming, 94(2), 343-359. https://doi.org/10.1007/s10107-002-0323-0
Renwick, J. D., Klein, L. J., & Hamann, H. F. (2016). Drone-based reconstruction for 3D geospatial data processing. 2016 IEEE 3rd World Forum on Internet of Things (WF-IoT),
Ric. (2017). What Do China’s Delivery Drones Look Like? – JD.Com Spotlight. Unmanned Cargo. http://unmannedcargo.org/chinese-delivery-drones/
Ruiz, E., Soto-Mendoza, V., Ruiz Barbosa, A. E., & Reyes, R. (2019). Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Computers & Industrial Engineering, 133, 207-219. https://doi.org/https://doi.org/10.1016/j.cie.2019.05.002
Sacramento, D., Pisinger, D., & Ropke, S. (2019). An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies, 102, 289-315. https://doi.org/https://doi.org/10.1016/j.trc.2019.02.018
Saraiva, A. (2021, June 24, 2021). The Pandemic’s Supply Shocks Go Far Beyond Empty Store Shelves. Bloomberg. https://www.bloomberg.com/news/newsletters/2021-06-24/supply-chain-latest-the-mounting-costs-of-covid-supply-shocks
Shah, B. (2015). FJORD. https://www.fjordnet.com/conversations/liquid-expectations/
Shavarani, S. M., Mosallaeipour, S., Golabi, M., & İzbirak, G. (2019). A congested capacitated multi-level fuzzy facility location problem: An efficient drone delivery system. Computers & Operations Research, 108, 57-68.
Simoni, M. D., Marcucci, E., Gatta, V., & Claudel, C. G. (2020). Potential last-mile impacts of crowdshipping services: a simulation-based evaluation. Transportation, 47(4), 1933-1954.
Statista. (2022a). Size of the global last mile delivery market from 2020 to 2027. https://www.statista.com/statistics/1286612/last-mile-delivery-market-size-worldwide/
Statista. (2022b). Startup funding in last mile solutions worldwide in 2020, by region. https://www.statista.com/statistics/1088797/last-mile-startup-investment-worldwide/
Stodola, P. (2020). Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem. Natural Computing, 19(2), 463-475. https://doi.org/10.1007/s11047-020-09783-6
Stolaroff, J. K., Samaras, C., O’Neill, E. R., Lubers, A., Mitchell, A. S., & Ceperley, D. (2018). Energy use and life cycle greenhouse gas emissions of drones for commercial package delivery. Nature communications, 9(1), 1-13.
Taniguchi, E. (2014). Concepts of city logistics for sustainable and liveable cities. Procedia-social and behavioral sciences, 151, 310-317.
Tavares, T. (2019). Comparing the cost-effectiveness of drones v ground vehicles for medical, food and parcel deliveries. https://www.unmannedairspace.info/commentary/comparing-the-cost-effectiveness-of-drones-v-ground-vehicles-for-medical-food-and-parcel-deliveries/#_ftn4
Texas A&M Transportation Institute. (2021). 2021 Urban Mobility Report. https://mobility.tamu.edu/umr/
Toth, P., & Vigo, D. (2002). The vehicle routing problem. SIAM.
Ulmer, M. W., & Thomas, B. W. (2018). Same‐day delivery with heterogeneous fleets of drones and vehicles. Networks, 72(4), 475-505.
UN-Habitat. (2020). Worl Cities Report 2020: The Value of Sustainable Urbanization. https://unhabitat.org/sites/default/files/2020/10/wcr_2020_report.pdf
Vincent, J. (2021, Aug 25, 2021). Alphabet’s drone delivery service Wing hits 100,000 deliveries milestone. The Verge. https://www.theverge.com/2021/8/25/22640833/drone-delivery-google-alphabet-wing-milestone
Voudouris, C., Tsang, E. P., & Alsheddy, A. (2010). Guided local search. In Handbook of metaheuristics (pp. 321-361). Springer.
Vuong, Q. H., Dang, G. T.-H., Quang, T. D., & Pham, M.-T. (2021). Traveling Salesman Problem with Truck and Drones: A Case Study of Parcel Delivery in Hanoi. International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences,
Wang, C., Mu, D., Zhao, F., & Sutherland, J. W. (2015). A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering, 83, 111-122.
Wang, X., Poikonen, S., & Golden, B. (2017). The vehicle routing problem with drones: several worst-case results. Optimization Letters, 11(4), 679-697.
Wang, Y., Zhang, D., Liu, Q., Shen, F., & Lee, L. H. (2016). Towards enhancing the last-mile delivery: An effective crowd-tasking model with scalable solutions. Transportation Research Part E: Logistics and Transportation Review, 93, 279-293.
Weisbrod, G., & Fitzroy, S. (2011). Traffic congestion effects on supply chains: Accounting for behavioral elements in planning and economic impact models. In Supply Chain Management-New Perspectives. IntechOpen.
Woeginger, G. J. (2003). Exact Algorithms for NP-Hard Problems: A Survey. In M. Jünger, G. Reinelt, & G. Rinaldi (Eds.), Combinatorial Optimization — Eureka, You Shrink!: Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers (pp. 185-207). Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-36478-1_17
World Economic Forum. (2020). The Future of the Last-Mile Ecosystem. https://www.weforum.org/reports/the-future-of-the-last-mile-ecosystem
World Economic Forum. (2021). Pandemic, Parcels and Public Vaccination: Envisioning the Next Normal for the Last-Mile Ecosystem. https://www3.weforum.org/docs/WEF_Pandemic_Parcels_and_Public_Vaccination_report_2021.pdf
Zhan, S.-h., Lin, J., Zhang, Z.-j., & Zhong, Y.-w. (2016). List-based simulated annealing algorithm for traveling salesman problem. Computational intelligence and neuroscience, 2016.
Zijm, H., Klumpp, M., Regattieri, A., & Heragu, S. (2019). Operations, logistics and supply chain management. Springer.