Research Article
BibTex RIS Cite

Collaborative Truck/Drone Routing Problem: An Application to Disaster Logistics

Year 2024, Issue: 9, 77 - 94, 30.06.2024

Alparslan Güzey , Mehmet Hakan Satman

https://doi.org/10.52693/jsas.1474515

Abstract

This study focuses on collaborative UAV/UGV routing problem in emergency logistics aiming to optimize the coordinated delivery efforts of both vehicles during disaster situations. By using a mixed integer model the study identifies the best delivery points and assigns specific drones to transport medical supplies to designated emergency assembly points. The research methodically assesses how UAV speed, UGV stops and cluster numbers affect delivery time. The results show that increasing UAV speeds and reducing stops and clusters generally lead to deliveries but achieving the time requires a careful balance due to their complex interactions. The study suggests that strategic coordination between UAVs and UGVs can significantly improve the efficiency of emergency logistics systems potentially reducing response times in disaster relief and medical supply deliveries. In conclusion the model highlights the potential for enhancements, in emergency response capabilities that could help save lives and lessen disaster impacts. Future studies should consider adapting the model for conditions and unpredictable scenarios to ensure resilience against demands.

Keywords

Disaster Logistic Autonomous Vehicles Traveling Salesman Problem Routing Problem

References

  • [1] L. Zhang, Y. Liu, X. Liu, and Y. Zhang, “Rescue efforts management and characteristics of casualties of the Wenchuan earthquake in China,” Emerg. Med. J., vol. 28, no. 7, pp. 618–622, 2011.
  • [2] H. Karaman, M. Şahin, A. S. Elnashai, and O. Pineda, “Loss assessment study for the Zeytinburnu district of Istanbul using Maeviz-Istanbul (HAZTURK),” J. Earthq. Eng., vol. 12, no. S2, pp. 187–198, 2008.
  • [3] A. Bibbee, R. Gönenç, S. Jacobs, J. Konvitz, and R. Price, “Economic Effects of the 1999 Turkish Earthquakes: An Interim Report,” OECD, Paris, Jun. 2000. doi: 10.1787/233456804045.
  • [4] R. I. E. and O. A. and D. Gunasekera James Edward and Pomonis,Antonios and Macabuag,Joshua Lee David Clifton and Brand,Johannes and Schaefer, Andreas and Romero, Roberth and Esper, Sarah and Otálora, Samuel González and Khazai,Bijan and Cox,Kerri Dionne, “Global Rapid Post-Disaster Damage Estimation (GRADE) Report : February 6, 2023 Kahramanmaraş Earthquakes - Türkiye Report (English),” Text/HTML, 2023. Accessed: Mar. 15, 2023. [Online]. Available: https://documents.worldbank.org/en/publication/documents-reports/documentdetail
  • [5] A. S. Safaei, S. Farsad, and M. M. Paydar, “Emergency logistics planning under supply risk and demand uncertainty,” Oper. Res., vol. 20, no. 3, pp. 1437–1460, Sep. 2020, doi: 10.1007/s12351-018-0376-3.
  • [6] Y. Jiang and Y. Yuan, “Emergency logistics in a large-scale disaster context: Achievements and challenges,” Int. J. Environ. Res. Public. Health, vol. 16, no. 5, p. 779, 2019.
  • [7] Statista, “Number of natural disasters worldwide 2022,” Statista. Accessed: Mar. 15, 2023. [Online]. Available: https://www.statista.com/statistics/510959/number-of-natural-disasters-events-globally/
  • [8] T. Gabe, E. H. Falk, V. W. Mason, and M. McCarty, “Hurricane Katrina: Social-demographic characteristics of impacted areas,” Congressional Research Service, The Library of Congress Washington, DC, 2005.
  • [9] A. Suppasri et al., “Damage characteristic and field survey of the 2011 Great East Japan Tsunami in Miyagi Prefecture,” Coast. Eng. J., vol. 54, no. 1, pp. 1250005–1, 2012.
  • [10] K. Goda et al., “The 2015 Gorkha Nepal earthquake: insights from earthquake damage survey,” Front. Built Environ., vol. 1, p. 8, 2015.
  • [11] W. Chen, G. Rao, D. Kang, Z. Wan, and D. Wang, “Early Report of the Source Characteristics, Ground Motions, and Casualty Estimates of the 2023 M w 7.8 and 7.5 Turkey Earthquakes,” J. Earth Sci., pp. 1–7, 2023.
  • [12] O. K. Kwon, “How is the COVID-19 pandemic affecting global supply chains, logistics, and transportation?,” J. Int. Logist. Trade, vol. 18, no. 3, pp. 107–111, 2020.
  • [13] “Logistics Cluster.” Accessed: Mar. 16, 2023. [Online]. Available: https://logcluster.org/preparedness
  • [14] M. Erdelj and E. Natalizio, “UAV-assisted disaster management: Applications and open issues,” in 2016 international conference on computing, networking and communications (ICNC), IEEE, 2016, pp. 1–5.
  • [15] F. He and J. Zhuang, “Balancing pre-disaster preparedness and post-disaster relief,” Eur. J. Oper. Res., vol. 252, no. 1, pp. 246–256, 2016.
  • [16] D. P. Coppola, Introduction to international disaster management. Elsevier, 2006.
  • [17] S. Chowdhury, A. Emelogu, M. Marufuzzaman, S. G. Nurre, and L. Bian, “Drones for disaster response and relief operations: A continuous approximation model,” Int. J. Prod. Econ., vol. 188, pp. 167–184, 2017.
  • [18] T. Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures,” omega, vol. 34, no. 3, pp. 209–219, 2006.
  • [19] A. Dixit, A. Mishra, and A. Shukla, “Vehicle routing problem with time windows using meta-heuristic algorithms: a survey,” in Harmony Search and Nature Inspired Optimization Algorithms: Theory and Applications, ICHSA 2018, Springer, 2018, pp. 539–546.
  • [20] G. Laporte, “The traveling salesman problem: An overview of exact and approximate algorithms,” Eur. J. Oper. Res., vol. 59, no. 2, pp. 231–247, 1992.
  • [21] T. Lust and J. Teghem, “The multiobjective traveling salesman problem: a survey and a new approach,” Adv. Multi-Object. Nat. Inspired Comput., pp. 119–141, 2010.
  • [22] A. Goodchild and J. Toy, “Delivery by drone: An evaluation of unmanned aerial vehicle technology in reducing CO2 emissions in the delivery service industry,” Transp. Res. Part Transp. Environ., vol. 61, pp. 58–67, 2018. [23] S. Khalaj Rahimi and D. Rahmani, “A Hybrid Truck-Drone Routing Problem Considering Deprivation Cost in the Post-Disaster Situation,” J. Qual. Eng. Prod. Optim., vol. 6, no. 1, pp. 233–256, 2021.
  • [24] R. Raj and C. Murray, “The multiple flying sidekicks traveling salesman problem with variable drone speeds,” Transp. Res. Part C Emerg. Technol., vol. 120, p. 102813, 2020.
  • [25] N. Agatz, P. Bouman, and M. Schmidt, “Optimization approaches for the traveling salesman problem with drone,” Transp. Sci., vol. 52, no. 4, pp. 965–981, 2018.
  • [26] N. Boysen, D. Briskorn, S. Fedtke, and S. Schwerdfeger, “Drone delivery from trucks: Drone scheduling for given truck routes,” Networks, vol. 72, no. 4, pp. 506–527, 2018.
  • [27] C. C. Murray and A. G. Chu, “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery,” Transp. Res. Part C Emerg. Technol., vol. 54, pp. 86–109, 2015.
  • [28]S. Poikonen and J. F. Campbell, “Future directions in drone routing research,” Networks, vol. 77, no. 1, 2020, doi: 10.1002/net.21982.
  • [29]A. Ponza, “Optimization of drone-assisted parcel delivery,” 2016.
  • [30]D. Schermer, M. Moeini, and O. Wendt, “A matheuristic for the vehicle routing problem with drones and its variants,” Transp. Res. Part C Emerg. Technol., vol. 106, pp. 166–204, 2019.
  • [31] S. M. Ferrandez, T. Harbison, T. Weber, R. Sturges, and R. Rich, “Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm,” J. Ind. Eng. Manag. JIEM, vol. 9, no. 2, pp. 374–388, 2016.
  • [32] Emergenresearch, “Emergenresearch Drone Package Delivery Industry Top Companies | Drone Package Delivery Market Top Players by 2028.” Accessed: Mar. 19, 2023. [Online]. Available: https://www.emergenresearch.com/blog/top-10-companies-in-the-drone-package-delivery-industry
  • [33] E. Roth, “Matternet’s delivery drone design has been approved by the FAA,” The Verge. Accessed: Mar. 19, 2023. [Online]. Available: https://www.theverge.com/2022/9/11/23347199/matternet-delivery-drone-model-m2-design-approved-faa
  • [34] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A fresh approach to numerical computing,” SIAM Review, vol. 59, no. 1. pp. 65–98, Sep. 2017. doi: 10.1137/141000671.
  • [35] “Clustering.jl.” Julia Statistics, Mar. 25, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/JuliaStats/Clustering.jl
  • [36] “Distances.jl.” Julia Statistics, Mar. 24, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/JuliaStats/Distances.jl
  • [37] E. Fields, “TravelingSalesmanHeuristics.” Feb. 19, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/evanfields/TravelingSalesmanHeuristics.jl
  • [38] “HiGHS.jl.” JuMP-dev, Mar. 28, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/jump-dev/HiGHS.jl
  • [39] “matplotlib/matplotlib.” Matplotlib Developers, Mar. 28, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/matplotlib/matplotlib
  • [40] The pandas development team, “pandas-dev/pandas: Pandas.” Mar. 28, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/pandas-dev/pandas

İnsansız Kara ve Hava Aracı Rotalama Problemleri: Afet Lojistiği Üzerine Bir Uygulama

Year 2024, Issue: 9, 77 - 94, 30.06.2024

Alparslan Güzey , Mehmet Hakan Satman

https://doi.org/10.52693/jsas.1474515

Abstract

Bu çalışma, afet durumlarında her iki aracın koordineli teslimat çabalarını optimize etmeyi amaçlayan acil durum lojistiğinde işbirlikçi İHA / UGV rotalama problemine odaklanmaktadır. Çalışma, karma tamsayılı bir model kullanarak en iyi teslimat noktalarını belirlemekte ve belirlenen acil durum toplanma noktalarına tıbbi malzeme taşımak için belirli İHA'ları görevlendirmektedir. Araştırma, İHA hızı, UGV durakları ve küme sayılarının teslimat süresini nasıl etkilediğini metodik olarak değerlendirmektedir. Sonuçlar, İHA hızlarının artırılmasının, durakların ve kümelerin azaltılmasının genel olarak teslimatlara yol açtığını, ancak karmaşık etkileşimleri nedeniyle zamana ulaşmanın dikkatli bir denge gerektirdiğini göstermektedir. Çalışma, İHA'lar ve UGV'ler arasındaki stratejik koordinasyonun acil durum lojistik sistemlerinin verimliliğini önemli ölçüde artırabileceğini ve afet yardımı ve tıbbi malzeme teslimatlarında müdahale sürelerini azaltabileceğini öne sürmektedir. Sonuç olarak model, acil durum müdahale kabiliyetlerinde hayat kurtarmaya ve afet etkilerini azaltmaya yardımcı olabilecek iyileştirme potansiyelini vurgulamaktadır. Gelecekteki çalışmalar, taleplere karşı esneklik sağlamak için modeli koşullara ve öngörülemeyen senaryolara uyarlamayı düşünmelidir.

Keywords

Afet Lojistiği Otonom Araçlar Gezgin Satıcı Problemi Rotalama Problemi

References

  • [1] L. Zhang, Y. Liu, X. Liu, and Y. Zhang, “Rescue efforts management and characteristics of casualties of the Wenchuan earthquake in China,” Emerg. Med. J., vol. 28, no. 7, pp. 618–622, 2011.
  • [2] H. Karaman, M. Şahin, A. S. Elnashai, and O. Pineda, “Loss assessment study for the Zeytinburnu district of Istanbul using Maeviz-Istanbul (HAZTURK),” J. Earthq. Eng., vol. 12, no. S2, pp. 187–198, 2008.
  • [3] A. Bibbee, R. Gönenç, S. Jacobs, J. Konvitz, and R. Price, “Economic Effects of the 1999 Turkish Earthquakes: An Interim Report,” OECD, Paris, Jun. 2000. doi: 10.1787/233456804045.
  • [4] R. I. E. and O. A. and D. Gunasekera James Edward and Pomonis,Antonios and Macabuag,Joshua Lee David Clifton and Brand,Johannes and Schaefer, Andreas and Romero, Roberth and Esper, Sarah and Otálora, Samuel González and Khazai,Bijan and Cox,Kerri Dionne, “Global Rapid Post-Disaster Damage Estimation (GRADE) Report : February 6, 2023 Kahramanmaraş Earthquakes - Türkiye Report (English),” Text/HTML, 2023. Accessed: Mar. 15, 2023. [Online]. Available: https://documents.worldbank.org/en/publication/documents-reports/documentdetail
  • [5] A. S. Safaei, S. Farsad, and M. M. Paydar, “Emergency logistics planning under supply risk and demand uncertainty,” Oper. Res., vol. 20, no. 3, pp. 1437–1460, Sep. 2020, doi: 10.1007/s12351-018-0376-3.
  • [6] Y. Jiang and Y. Yuan, “Emergency logistics in a large-scale disaster context: Achievements and challenges,” Int. J. Environ. Res. Public. Health, vol. 16, no. 5, p. 779, 2019.
  • [7] Statista, “Number of natural disasters worldwide 2022,” Statista. Accessed: Mar. 15, 2023. [Online]. Available: https://www.statista.com/statistics/510959/number-of-natural-disasters-events-globally/
  • [8] T. Gabe, E. H. Falk, V. W. Mason, and M. McCarty, “Hurricane Katrina: Social-demographic characteristics of impacted areas,” Congressional Research Service, The Library of Congress Washington, DC, 2005.
  • [9] A. Suppasri et al., “Damage characteristic and field survey of the 2011 Great East Japan Tsunami in Miyagi Prefecture,” Coast. Eng. J., vol. 54, no. 1, pp. 1250005–1, 2012.
  • [10] K. Goda et al., “The 2015 Gorkha Nepal earthquake: insights from earthquake damage survey,” Front. Built Environ., vol. 1, p. 8, 2015.
  • [11] W. Chen, G. Rao, D. Kang, Z. Wan, and D. Wang, “Early Report of the Source Characteristics, Ground Motions, and Casualty Estimates of the 2023 M w 7.8 and 7.5 Turkey Earthquakes,” J. Earth Sci., pp. 1–7, 2023.
  • [12] O. K. Kwon, “How is the COVID-19 pandemic affecting global supply chains, logistics, and transportation?,” J. Int. Logist. Trade, vol. 18, no. 3, pp. 107–111, 2020.
  • [13] “Logistics Cluster.” Accessed: Mar. 16, 2023. [Online]. Available: https://logcluster.org/preparedness
  • [14] M. Erdelj and E. Natalizio, “UAV-assisted disaster management: Applications and open issues,” in 2016 international conference on computing, networking and communications (ICNC), IEEE, 2016, pp. 1–5.
  • [15] F. He and J. Zhuang, “Balancing pre-disaster preparedness and post-disaster relief,” Eur. J. Oper. Res., vol. 252, no. 1, pp. 246–256, 2016.
  • [16] D. P. Coppola, Introduction to international disaster management. Elsevier, 2006.
  • [17] S. Chowdhury, A. Emelogu, M. Marufuzzaman, S. G. Nurre, and L. Bian, “Drones for disaster response and relief operations: A continuous approximation model,” Int. J. Prod. Econ., vol. 188, pp. 167–184, 2017.
  • [18] T. Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures,” omega, vol. 34, no. 3, pp. 209–219, 2006.
  • [19] A. Dixit, A. Mishra, and A. Shukla, “Vehicle routing problem with time windows using meta-heuristic algorithms: a survey,” in Harmony Search and Nature Inspired Optimization Algorithms: Theory and Applications, ICHSA 2018, Springer, 2018, pp. 539–546.
  • [20] G. Laporte, “The traveling salesman problem: An overview of exact and approximate algorithms,” Eur. J. Oper. Res., vol. 59, no. 2, pp. 231–247, 1992.
  • [21] T. Lust and J. Teghem, “The multiobjective traveling salesman problem: a survey and a new approach,” Adv. Multi-Object. Nat. Inspired Comput., pp. 119–141, 2010.
  • [22] A. Goodchild and J. Toy, “Delivery by drone: An evaluation of unmanned aerial vehicle technology in reducing CO2 emissions in the delivery service industry,” Transp. Res. Part Transp. Environ., vol. 61, pp. 58–67, 2018. [23] S. Khalaj Rahimi and D. Rahmani, “A Hybrid Truck-Drone Routing Problem Considering Deprivation Cost in the Post-Disaster Situation,” J. Qual. Eng. Prod. Optim., vol. 6, no. 1, pp. 233–256, 2021.
  • [24] R. Raj and C. Murray, “The multiple flying sidekicks traveling salesman problem with variable drone speeds,” Transp. Res. Part C Emerg. Technol., vol. 120, p. 102813, 2020.
  • [25] N. Agatz, P. Bouman, and M. Schmidt, “Optimization approaches for the traveling salesman problem with drone,” Transp. Sci., vol. 52, no. 4, pp. 965–981, 2018.
  • [26] N. Boysen, D. Briskorn, S. Fedtke, and S. Schwerdfeger, “Drone delivery from trucks: Drone scheduling for given truck routes,” Networks, vol. 72, no. 4, pp. 506–527, 2018.
  • [27] C. C. Murray and A. G. Chu, “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery,” Transp. Res. Part C Emerg. Technol., vol. 54, pp. 86–109, 2015.
  • [28]S. Poikonen and J. F. Campbell, “Future directions in drone routing research,” Networks, vol. 77, no. 1, 2020, doi: 10.1002/net.21982.
  • [29]A. Ponza, “Optimization of drone-assisted parcel delivery,” 2016.
  • [30]D. Schermer, M. Moeini, and O. Wendt, “A matheuristic for the vehicle routing problem with drones and its variants,” Transp. Res. Part C Emerg. Technol., vol. 106, pp. 166–204, 2019.
  • [31] S. M. Ferrandez, T. Harbison, T. Weber, R. Sturges, and R. Rich, “Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm,” J. Ind. Eng. Manag. JIEM, vol. 9, no. 2, pp. 374–388, 2016.
  • [32] Emergenresearch, “Emergenresearch Drone Package Delivery Industry Top Companies | Drone Package Delivery Market Top Players by 2028.” Accessed: Mar. 19, 2023. [Online]. Available: https://www.emergenresearch.com/blog/top-10-companies-in-the-drone-package-delivery-industry
  • [33] E. Roth, “Matternet’s delivery drone design has been approved by the FAA,” The Verge. Accessed: Mar. 19, 2023. [Online]. Available: https://www.theverge.com/2022/9/11/23347199/matternet-delivery-drone-model-m2-design-approved-faa
  • [34] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A fresh approach to numerical computing,” SIAM Review, vol. 59, no. 1. pp. 65–98, Sep. 2017. doi: 10.1137/141000671.
  • [35] “Clustering.jl.” Julia Statistics, Mar. 25, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/JuliaStats/Clustering.jl
  • [36] “Distances.jl.” Julia Statistics, Mar. 24, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/JuliaStats/Distances.jl
  • [37] E. Fields, “TravelingSalesmanHeuristics.” Feb. 19, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/evanfields/TravelingSalesmanHeuristics.jl
  • [38] “HiGHS.jl.” JuMP-dev, Mar. 28, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/jump-dev/HiGHS.jl
  • [39] “matplotlib/matplotlib.” Matplotlib Developers, Mar. 28, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/matplotlib/matplotlib
  • [40] The pandas development team, “pandas-dev/pandas: Pandas.” Mar. 28, 2023. Accessed: Mar. 28, 2023. [Online]. Available: https://github.com/pandas-dev/pandas
There are 39 citations in total.

Details

Primary Language English
Subjects Operations Research
Journal Section Research Articles
Authors

Alparslan Güzey 0000-0002-9043-304X

Mehmet Hakan Satman 0000-0002-9402-1982

Publication Date June 30, 2024
Submission Date April 27, 2024
Acceptance Date June 2, 2024
Published in Issue Year 2024 Issue: 9

Cite

IEEE A. Güzey and M. H. Satman, “Collaborative Truck/Drone Routing Problem: An Application to Disaster Logistics”, JSAS, no. 9, pp. 77–94, June 2024, doi: 10.52693/jsas.1474515.
 Download Cover Image