[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Multi-depot vehicle routing problem with drones in emergency logistics

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

In order to expand the application of truck-drone cooperative delivery in emergency logistics, this paper investigates the multi-depot vehicle routing problem with drones for emergency logistics scheduling. A mixed-integer programming model with the objective of minimizing the total rescue time from urban distribution centres to temporary distribution stations is proposed. To address this problem, a new two-stage hybrid heuristic algorithm is proposed. In the first stage, we employ an improved K-means clustering algorithm to cluster the temporary distribution stations. In the second stage, a combination of Tabu search (TS), enhanced genetic algorithm (GA), and simulated annealing (SA) is applied to optimize the routes of both trucks and drones. The numerical study involves the validation of the model using real-world cases. Through comparison experiments with the Gurobi solver, we demonstrate the significant advantages of the proposed heuristic algorithm in terms of solution quality and efficiency.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Data availability

No datasets were generated or analysed during the current study.

References

  1. Jana, R.K., Sharma, D.K., Mehta, P.: A probabilistic fuzzy goal programming model for managing the supply of emergency relief materials. Ann. Oper. Res. (2021). https://doi.org/10.1007/s10479-021-04267-x

    Article  Google Scholar 

  2. Liu, J., Bai, J., Wu, D.: Medical supplies scheduling in major public health emergencies. Transp. Res. Part E 154, 102464 (2021). https://doi.org/10.1016/j.tre.2021.102464

    Article  Google Scholar 

  3. Özdamar, L., Ekinci, E., Küçükyazici, B.: Emergency logistics planning in natural disasters. Ann. Oper. Res. 129(1–4), 217–245 (2004). https://doi.org/10.1023/b:anor.0000030690.27939.39

    Article  MathSciNet  Google Scholar 

  4. Liu, C., Huang, L., Dong, Z.: A two-stage approach of joint route planning and resource allocation for multiple UAVs in unmanned logistics distribution. IEEE Access 10, 113888–113901 (2022). https://doi.org/10.1109/access.2022.3218134

    Article  Google Scholar 

  5. Wang, X., Wong, Y.D., Yuen, K.F.: Does COVID-19 promote self-service usage among modern shoppers? An exploration of pandemic-driven behavioural changes in self-collection users. Int. J. Environ. Res. Public Health 18(16), 8574 (2021). https://doi.org/10.3390/ijerph18168574

    Article  Google Scholar 

  6. Wang, X., Wong, Y.D., Kim, T.Y., Yuen, K.F.: Does COVID-19 change consumers’ involvement in e-commerce last-mile delivery? An investigation on behavioural change, maintenance and habit formation. Electron. Commerce Res. (2023). https://doi.org/10.1016/j.elerap.2023.101273

    Article  Google Scholar 

  7. Lee, H.-W.: Research on multi-functional logistics intelligent unmanned aerial vehicle. Eng. Appl. Artif. Intell. 116, 105341 (2022). https://doi.org/10.1016/j.engappai.2022.105341

    Article  Google Scholar 

  8. Wankmüller, C., Kunovjanek, M., Mayrgündter, S.: Drones in emergency response—evidence from cross-border, multi-disciplinary usability tests. Int. J. Disaster Risk Reduc. 65, 102567 (2021). https://doi.org/10.1016/j.ijdrr.2021.102567

    Article  Google Scholar 

  9. Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J.M.A., Brunese, P.A.: Multiple traveling salesman problem with drones: mathematical model and heuristic approach. Comput. Ind. Eng. 129, 14–30 (2019). https://doi.org/10.1016/j.cie.2019.01.020

    Article  Google Scholar 

  10. Rose, C.: Amazon's Jeff Bezos looks to the future (2013). https://www.cbsnews.com/news/amazons-jeff-bezos-looks-to-the-future/

  11. Hern, A.: DHL launches first commercial drone 'parcelcopter' delivery service (2014). https://www.theguardian.com/technology/2014/sep/25/german-dhl-launches-first commercial-drone-delivery-service/

  12. Muoio, D.: Google’s secretive drone delivery project just got cleared for testing—here’s everything we know about the program (2016). http://www.businessinsider.com/google-project-wing-drone-service-2016-8?r=US&IR=T&IR=T/#david-vos-the-leader-of-project-wing-said-google-x-wants-to-use-drones-to-deliver-packages-starting-in-2017-8

  13. Murray, C.C., Chu, A.G.: The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transp. Res. Part C 54, 86–109 (2015). https://doi.org/10.1016/j.trc.2015.03.005

    Article  Google Scholar 

  14. Agatz, N., Bouman, P., Schmidt, M.: Optimization approaches for the traveling salesman problem with drone. Transp. Sci. 52(4), 965–981 (2018). https://doi.org/10.1287/trsc.2017.0791

    Article  Google Scholar 

  15. Poikonen, S., Wang, X., Golden, B.: The vehicle routing problem with drones: extended models and connections. Networks 70(1), 34–43 (2017). https://doi.org/10.1002/net.21746

    Article  MathSciNet  Google Scholar 

  16. Wang, Z., Sheu, J.-B.: Vehicle routing problem with drones. Transp. Res. Part B 122, 350–364 (2019). https://doi.org/10.1016/j.trb.2019.03.005

    Article  Google Scholar 

  17. Sacramento, D., Pisinger, D., Ropke, S.: An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transp. Res. Part C 102, 289–315 (2019). https://doi.org/10.1016/j.trc.2019.02.018

    Article  Google Scholar 

  18. Karakatič, S., Podgorelec, V.: A survey of genetic algorithms for solving multi depot vehicle routing problem. Appl. Soft Comput. 27, 519–532 (2015). https://doi.org/10.1016/j.asoc.2014.11.005

    Article  Google Scholar 

  19. Gkiotsalitis, K., Iliopoulou, C., Kepaptsoglou, K.: An exact approach for the multi-depot electric bus scheduling problem with time windows. Eur. J. Oper. Res. 306(1), 189–206 (2023). https://doi.org/10.1016/j.ejor.2022.07.017

    Article  MathSciNet  Google Scholar 

  20. Li, J., Dai, B.T., Niu, Y., Xiao, J., Wu, Y.: Multi-type attention for solving multi-depot vehicle routing problems. IEEE Trans. Intell. Transp. Syst. (2024). https://doi.org/10.1109/tits.2024.3413077.Accessed21Sept.2024

    Article  Google Scholar 

  21. Sheu, J.-B.: An emergency logistics distribution approach for quick response to urgent relief demand in disasters. Transp. Res. Part E 43(6), 687–709 (2007). https://doi.org/10.1016/j.tre.2006.04.004

    Article  Google Scholar 

  22. Xu, L., Wang, Z., Chen, X., Lin, Z.: Multi-parking lot and shelter heterogeneous vehicle routing problem with split pickup under emergencies. IEEE Access 10, 36073–36090 (2022). https://doi.org/10.1109/access.2022.3163715.Accessed16Dec.2022

    Article  Google Scholar 

  23. Xu, P., Liu, Q., Wu, Y.: Energy saving-oriented multi-depot vehicle routing problem with time windows in disaster relief. Energies 16(4), 1992 (2023). https://doi.org/10.3390/en16041992.Accessed21Sept.2024

    Article  Google Scholar 

  24. Chang, F.-S., Wu, J.-S., Lee, C.-N., Shen, H.-C.: Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling. Expert Syst. Appl. 41(6), 2947–2956 (2014). https://doi.org/10.1016/j.eswa.2013.10.026

    Article  Google Scholar 

  25. Fontem, B.A., Melouk, S.H., Keskin, B.B., Bajwa, N.: A decomposition-based heuristic for stochastic emergency routing problems. Expert Syst. Appl. 59, 47–59 (2016). https://doi.org/10.1016/j.eswa.2016.04.002

    Article  Google Scholar 

  26. Zhang, Q., Xiong, S.: Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithm. Appl. Soft Comput. 71, 917–925 (2018). https://doi.org/10.1016/j.asoc.2018.07.050

    Article  Google Scholar 

  27. Vieira, Y.E.M., et al.: Multi-depot vehicle routing problem for large scale disaster relief in drought scenarios: the case of the Brazilian northeast region. Int. J. Disaster Risk Reduc. 58, 102193 (2021). https://doi.org/10.1016/j.ijdrr.2021.102193.Accessed22Apr.2022

    Article  Google Scholar 

  28. Wan, F., et al.: A mathematical method for solving multi-depot vehicle routing problem. SSRN Electron. J. (2021). https://doi.org/10.2139/ssrn.3943419.Accessed19Mar.2023

    Article  Google Scholar 

  29. Dondo, R., Cerdá, J.: A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. Eur. J. Oper. Res. 176(3), 1478–1507 (2007). https://doi.org/10.1016/j.ejor.2004.07.077

    Article  Google Scholar 

  30. Calvet, L., Ferrer, A., Gomes, M.I., Juan, A.A., Masip, D.: Combining statistical learning with metaheuristics for the multi-depot vehicle routing problem with market segmentation. Comput. Ind. Eng. 94, 93–104 (2016). https://doi.org/10.1016/j.cie.2016.01.016

    Article  Google Scholar 

  31. Wang, Y., Zhang, S., Guan, X., Peng, S., Wang, H., Liu, Y., Xu, M.: Collaborative multi-depot logistics network design with time window assignment. Expert Syst. Appl. 140, 112910 (2020). https://doi.org/10.1016/j.eswa.2019.112910

    Article  Google Scholar 

  32. Wang, Y., et al.: A clustering-based extended genetic algorithm for the multi-depot vehicle routing problem with time windows and three-dimensional loading constraints. Appl. Soft Comput. 133, 109922 (2023). https://doi.org/10.1016/j.asoc.2022.109922

    Article  Google Scholar 

  33. Hamid, M., et al.: A mixed closed-open multi-depot routing and scheduling problem for homemade meal delivery incorporating drone and crowd-sourced fleet: a self-adaptive hyper-heuristic approach. Eng. Appl. Artif. Intell. 120, 105876 (2023). https://doi.org/10.1016/j.engappai.2023.105876.Accessed31Jan.2023

    Article  Google Scholar 

  34. Stodola, P., Kutěj, L.: Multi-depot vehicle routing problem with drones: mathematical formulation, solution algorithm and experiments. Expert Syst. Appl. 241, 122483 (2024). https://doi.org/10.1016/j.eswa.2023.122483.Accessed5Mar.2024

    Article  Google Scholar 

  35. Boccia, M., Masone, A., Sforza, A., Sterle, C.: A column-and-row generation approach for the flying sidekick travelling salesman problem. Transp. Res. Part C 124, 102913–102913 (2021). https://doi.org/10.1016/j.trc.2020.102913

    Article  Google Scholar 

  36. Dell’Amico, M., Montemanni, R., Novellani, S.: Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem. Optim. Lett. (2019). https://doi.org/10.1007/s11590-019-01492-z

    Article  Google Scholar 

  37. de Freitas, J.C., Penna, P.H.V.: A variable neighbourhood search for flying sidekick traveling salesman problem. Int. Trans. Oper. Res. (2019). https://doi.org/10.1111/itor.12671

    Article  Google Scholar 

  38. Tamke, F., Buscher, U.: A branch-and-cut algorithm for the vehicle routing problem with drones. Transp. Res. Part B 144, 174–203 (2021). https://doi.org/10.1016/j.trb.2020.11.011

    Article  Google Scholar 

  39. Murray, C.C., Raj, R.: The multiple flying sidekicks traveling salesman problem: parcel delivery with multiple drones. Transp. Res. Part C 110, 368–398 (2020). https://doi.org/10.1016/j.trc.2019.11.003

    Article  Google Scholar 

  40. Jeong, H.Y., Song, B.D., Lee, S.: Truck-drone hybrid delivery routing: payload-energy dependency and no-fly zones. Int. J. Prod. Econ. 214, 220–233 (2019). https://doi.org/10.1016/j.ijpe.2019.01.010

    Article  Google Scholar 

  41. Gonzalez-R, P.L., Canca, D., Andrade-Pineda, J.L., Calle, M., Leon-Blanco, J.M.: Truck-drone team logistics: a heuristic approach to multi-drop route planning. Transp. Res. Part C 114, 657–680 (2020). https://doi.org/10.1016/j.trc.2020.02.030

    Article  Google Scholar 

  42. Ha, Q.M., Deville, Y., Pham, Q.D., Hà, M.H.: On the min-cost traveling salesman problem with drone. Transp. Res. Part C 86, 597–621 (2018). https://doi.org/10.1016/j.trc.2017.11.015

    Article  Google Scholar 

  43. Cavani, S., Iori, M., Roberti, R.: Exact methods for the traveling salesman problem with multiple drones. Transp. Res. Part C 130, 103280 (2021). https://doi.org/10.1016/j.trc.2021.103280

    Article  Google Scholar 

  44. Luo, Z., Gu, R., Poon, M., Liu, Z., Lim, A.: A last-mile drone-assisted one-to-one pickup and delivery problem with multi-visit drone trips. Comput. Oper. Res. (2022). https://doi.org/10.1016/j.cor.2022.106015

    Article  MathSciNet  Google Scholar 

  45. Kuo, R.J., Lu, S.-H., Lai, P.-Y., Mara, S.T.W.: Vehicle routing problem with drones considering time windows. Expert Syst. Appl. 191, 116264 (2022). https://doi.org/10.1016/j.eswa.2021.116264

    Article  Google Scholar 

  46. Han, J., et al.: Vehicle routing problem with drones considering time windows and dynamic demand. Appl. Sci. 13(24), 13086 (2023). https://doi.org/10.3390/app132413086.Accessed21Aug.2024

    Article  Google Scholar 

  47. Montemanni, R., et al.: Parallel drone scheduling vehicle routing problems with collective drones. Comput. Oper. Res. 163, 106514 (2023). https://doi.org/10.1016/j.cor.2023.106514.Accessed22Sept.2024

    Article  MathSciNet  Google Scholar 

  48. Tong, B., Wang, J., Wang, X., Zhou, F., Mao, X., Zheng, W.: Optimal route planning for truck-drone delivery using variable neighbourhood Tabu search algorithm. Appl. Sci. 12(1), 529 (2022). https://doi.org/10.3390/app12010529

    Article  Google Scholar 

  49. Tian, S., Chen, H., Wu, G., Cheng, J.: Asymmetric arc routing by coordinating a truck and multiple drones. Sensors (Basel) (2022). https://doi.org/10.3390/s22166077

    Article  Google Scholar 

  50. Sampson, J.R.: Adaptation in natural and artificial systems (John H. Holland). SIAM Rev. 18(3), 529–530 (1976)

    Article  MathSciNet  Google Scholar 

  51. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087–1092 (1953). https://doi.org/10.1063/1.1699114

    Article  Google Scholar 

  52. Akhand, M.A.H., Peya, Z.J., Sultana, T.: Solving capacitated vehicle routing problem with route optimization using swarm intelligence. In: 2015 2nd International Conference on Electrical Information and Communication Technologies (EICT), pp. 112–117. IEEE. December 2015. https://doi.org/10.1109/EICT.2015.7391932

  53. Du, L., Li, X., Gan, Y., Leng, K.: Optimal model and algorithm of medical materials delivery drone routing problem under major public health emergencies. Sustainability 14(8), 4651 (2022). https://doi.org/10.3390/su14084651

    Article  Google Scholar 

Download references

Acknowledgements

The fund was provided by National Science and Technology Major Project (Grant No. 2021ZD0114204).

Funding

The fund was provided by National Science and Technology Major Project (Grant No. 2021ZD0114204).

Author information

Authors and Affiliations

  1. School of Intelligent Engineering and Automation, Beijing University of Posts and Telecommunications, Beijing, People’s Republic of China

    Xun Weng, Wenke She, Hongqiang Fan & Jingtian Zhang

  2. School of Traffic and Transportation, Beijing Jiaotong University, Beijing, People’s Republic of China

    Lifen Yun

Authors
  1. Xun Weng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wenke She
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hongqiang Fan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jingtian Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Lifen Yun
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Xun Weng: Conceptualization, methodology, project administration. Wenke She: Software, writing—original draft, visualization. Hongqiang Fan: Supervision, writing—review and editing. Jingtian Zhang: Investigation, funding acquisition. Lifen Yuan: Formal analysis, validation.

Corresponding author

Correspondence to Lifen Yun.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Weng, X., She, W., Fan, H. et al. Multi-depot vehicle routing problem with drones in emergency logistics. Cluster Comput 28, 64 (2025). https://doi.org/10.1007/s10586-024-04809-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10586-024-04809-5

Keywords

Search

Navigation