The Vehicle Routing Problem with Simultaneous Pickup and Delivery Approach for Cbrn Kit Distribution Network Design Optimization

Yıl 2023, Sayı: 1 - CUMHURİYETİN YÜZÜNCÜ YILI ÖZEL SAYISI, 171 - 196, 27.12.2023

Aygün Altundaş , Kemal Gürol Kurtay , Hakan Ayhan Dağıstanlı

https://doi.org/10.54078/savsad.1370431

Öz

Today, states are faced with complex security threats due to the rapid advancement of technological developments and the impact of globalization. In particular, the combination of Chemical, Biological, Radiological and Nuclear (CBRN) incidents with terrorism is becoming a major concern for international security. International communities face new challenges as terrorist organizations have the potential to use CBRN elements instead of traditional tactics. The intention and threat of terrorist organizations to use these materials is increasing day by day. Emergency plans, improving the capabilities of security forces and sharing information are critical in combating CBRN incidents. At the same time, it is vital to operate health control systems effectively and accelerate treatment processes for the early diagnosis of people at risk of exposure to such substances. In this study, the simultaneous collection and distribution of test kits, which is the most important factor in early diagnosis, was examined. A mathematical model has been proposed to distribute test kits from the main center where the tests are located to hospitals in Ankara and also collect the test kits waiting to be finalized there. In order to solve the problem examined, a model was proposed for the problem in practice by using the model called simultaneous collect-delivery vehicle routing problem in the literature. In order to analyze the effectiveness and limitations of the proposed model, sensitivity analysis was performed with examples consisting of different numbers of nodes. Afterwards, for defense against a possible CBRN attack, an application was made with the scenario created to create a test kit pick up and delivery route in every district of Ankara, and then the model was solved.When the limitations of the model were examined, the optimal solution was achieved up to 35 nodes with the mathematical model at different node numbers, and it was determined that the mathematical model did not yield results in appropriate solution times for larger size problems. In the sample application, minimum cost routes for vehicles to visit hospitals for all districts of Ankara were created and the solutions obtained were presented.

Anahtar Kelimeler

CBRN, Simultaneous Pick Up - Delivery, Vehicle Routing Problem

KBRN Kiti Dağıtım Ağı Tasarımı Optimizasyonu İçin Eş Zamanlı Topla Dağıt Araç Rotalama Problemi Yaklaşımı

Öz

Günümüzde teknolojik gelişmelerin hızla ilerlemesi ve küreselleşmenin etkisiyle devletler karmaşık güvenlik tehditleriyle karşı karşıya kalmaktadır. Özellikle Kimyasal, Biyolojik, Radyolojik ve Nükleer (KBRN) olaylarının terörizmle birleşmesi, uluslararası güvenlik açısından büyük bir endişe kaynağı haline gelmektedir. Terör örgütleri, geleneksel taktikler yerine KBRN unsurlarını kullanma potansiyeline sahip olduğundan uluslararası topluluklar yeni zorluklarla karşılaşmaktadır. Terör örgütlerinin bu materyalleri kullanma niyeti ve tehdidi gün geçtikçe artmaktadır. Acil durum planları, güvenlik güçlerinin yeteneklerinin geliştirilmesi ve bilgi paylaşımı KBRN olayları ile mücadelede kritik öneme sahiptir. Aynı zamanda bu tür maddelere maruz kalma riski taşıyan kişilerin erken teşhisi için sağlık kontrol sistemlerinin etkin bir şekilde çalıştırılması ve tedavi süreçlerinin hızlandırılması da hayati önem taşımaktadır. Bu çalışmada, erken teşhiste en önemli faktör olan test kitlerinin eş zamanlı toplanması ve dağıtılması incelenmiştir. Testlerin bulunduğu ana merkezden Ankara ilinde bulunan hastanelere test kiti dağıtımının ve aynı zamanda burada sonuçlandırılmak için bekleyen test kitlerinin toplanmasının gerçekleştirilmesi için matematiksel bir model önerisi yapılmıştır. İncelenen problemin çözümü için literatürde eş zamanlı topla dağıt araç rotalama problemi olarak adlandırılan model kullanılarak uygulamadaki problem için model önerisinde bulunulmuştur. Önerilen modelin etkinlik ve sınırlılığını analiz etmek amacıyla farklı sayıda düğümden oluşan örneklerle duyarlılık analizi yapılmıştır. Daha sonrasında olası bir KBRN saldırısına karşı savunma için Ankara ilinin her ilçesinde test kiti toplama ve dağıtım rotası oluşturmaya yönelik oluşturulan senaryo ile uygulama yapılmış ardından model çözülmüştür. Modelin sınırlılığı incelendiğinde farklı düğüm sayılarında matematiksel model ile 35 düğüme kadar optimal çözüme ulaşılmış, daha büyük boyuttaki problemler için matematiksel modelin uygun çözüm zamanlarında sonuç vermediği belirlenmiştir. Örnek uygulama da ise Ankara ilinin tüm ilçeleri için hastaneleri ziyaret edecek araçların minimum maliyetli rotaları oluşturulmuş ve elde edilen çözümler sunulmuştur.

Anahtar Kelimeler

KBRN, Eş Zamanlı Topla-Dağıt, Araç Rotalama Problemi

Kaynakça

• Ai, J., Kachitvichyanukul, V., 2009. A particle swarm optimization for the vehicle routing problem with simultaneous pick up and delivery. Computers and Operations Research, 36(5): 1693-1702.
• Ackerman, G. A. (2019). Chemical, biological, radiological and nuclear (CBRN) terrorism. Routledge handbook of terrorism and counterterrorism, 240-252.
• Belgin, O., Karaoglan, I., & Altiparmak, F. (2018). Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers & Industrial Engineering, 115, 1-16.
• Bianchessi, N., Righini, G., “Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery”, Computers and Operations Research, 34: 578-594 (2007).
• Chen, J.F., Approaches for the vehicle routing problem with simultaneous deliveries and pickups (2006) Journal of the Chinese Institute of Industrial Engineers, 23 (2), pp. 141-150
• Chen, J. F., Wu, T. H., “Vehicle routing problem with simultaneous deliveries and pickups”, Journal of the Operational Research Society, 57: 579-587 (2006).
• Crispim, J., Brandão, J., “Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls”, Journal of the Operational Research Society, 56: 1296-1302 (2005).
• Cruz, R. C. et al., 2012. Genvns-ts-cl-pr: A heuristic approach for solving the vehicle routing problem with simultaneous pick up and delivery. Electronic Notes in Discrete Mathematics, 39, 217-224.
• Dağıstanlı, H. A. (2023). Çok ürünlü çok depolu araç rotalama problemi: askerî ilaç fabrikası örneği. Politeknik Dergisi, 1-1.
• Dantzig, G.B. and Ramser, J.H. “The Truck Dispatching Problem”, Management Science, 6(1), 80-91, (1959).
• Dell’Amico, M., Righini, G., Salani, M. (2006). A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection. Transportation Science, 40 (2), 235–247.
• Desticioğlu, B., Kurtay, K. G., Altundaş, A., & Dağıstanlı, H. A. (2023). Hastanelere aşı dağıtımı için uygun rotaların belirlenmesi: Ankara ili örneği. Politeknik Dergisi, 26(1), 231-241.
• Desticioğlu, B. ve Özyörük, B. “Stokastik Talepli Araç Rotalama Problemi İçin Literatür Taraması.” Savunma Bilimleri Dergisi, 18(36), 181-222. (2019).
• Dethloff, J., “Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up”, OR Spektrum, 23: 79-96 (2001).
• Ekşi, A. (2016). “KBRN terörizminde risk değerlendirmesi ve yönetimi”, Journal of International Social Research, 9(42).
• Fan, J., 2011. "The vehicle routing problem with simultaneous pick up and delivery based on customer satisfaction. Advanced in Control Engineering and Information Science, 15, 5284-5289.
• Fakhrzad, M. B., Hoseini Shorshani, S. M., Hosseininasab, H., & Mostafaeipour, A. (2022). Developing a green vehicle routing problem model with time windows and simultaneous pickup and delivery under demand uncertainty: Minimizing fuel consumption. International journal of nonlinear analysis and applications.
• Gajpal, Y., Abad, P., “An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup”, Computers and Operations Research, 36(12): 3215-3223 (2009).
• Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & industrial engineering, 65(1), 39-53.
• Golsefidi, A. H., & Jokar, M. R. A. (2020). A robust optimization approach for the production-inventory-routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 143, 106388.
• Gschwind, T. (2015). A comparison of column generation approaches to the Synchronized Pickup and Delivery Problem. European Journal of Operational Research, 247, 60– 71.
• Halse, K. (1992). Modeling and solving complex vehcile routing problems. Ph.D thesis, Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, Denmark.
• Hornstra, R. P., Silva, A., Roodbergen, K. J., & Coelho, L. C. (2020). The vehicle routing problem with simultaneous pickup and delivery and handling costs. Computers & Operations Research, 115, 104858.
• Iassinovskaia, G., Limbourg, S. and Riane, F. (2017). The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains. International Journal Production Economics, 183, 570–582.
• Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. (2011). A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery. European Journal of Operational Research, 211(2), 318-332.
• Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4), 465-477.
• Koblentz, G. D. (2020). Emerging technologies and the future of CBRN terrorism. The Washington Quarterly, 43(2), 177-196.
• Koç, Ç., Laporte, G., & Tükenmez, İ. (2020). A review of vehicle routing with simultaneous pickup and delivery. Computers & Operations Research, 122, 104987.
• Kumar, V. S., & Jayachitra, R. (2016). Linear Sweep Algorithm for Vehicle Routing Problem with Simultaneous Pickup and Delivery between Two Depots with Several Nodes. Global Journal of Pure and Applied Mathematics, 12(1), 897-908.
• Lagos, C., Guerrero, G., Cabrera, E., Moltedo, A., Johnson, F., & Paredes, F. (2018). An improved particle swarm optimization algorithm for the VRP with simultaneous pickup and delivery and time windows. IEEE Latin America Transactions, 16(6), 1732-1740.
• Li, J., Pardalos, P. M., Sun, H., Pei, J., & Zhang, Y. (2015). Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups.Expert Systems with Applications,42(7), 3551-3561.
• Ma, Y., Li, Z., Yan, F., & Feng, C. (2019). A hybrid priority-based genetic algorithm for simultaneous pickup and delivery problems in reverse logistics with time windows and multiple decision-makers. Soft Computing, 23(15), 6697-6714.
• Min, H., 1989. The Multiple vehicle routing problem with simultaneous delivery and pick up points. Transportation Reseach,. 377-386.
• Minyong, L., Erbao, C. (2010). An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence, 23, 188-195.
• Montane, F. A. T., Galvao, R. D., “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service”, Computers and Operations Research, 33: 595-619 (2006).
• Nagy, G., Salhi, S., “The many-to-many location-routing problem”, TOP, 6: 261-275 (1998).
• Nagy, G., Salhi, S., “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries”, European Journal of Operational Research, 162: 126-141 (2005).
• Olgun, B., Koç, Ç., & Altıparmak, F. (2021). A hyper heuristic for the green vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 153, 107010.
• Öztaş, T., & Tuş, A. (2022). A hybrid metaheuristic algorithm based on iterated local search for vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications, 202, 117401.
• Park, H., Son, D., Koo, B., & Jeong, B. (2021). Waiting strategy for the vehicle routing problem with simultaneous pickup and delivery using genetic algorithm. Expert Systems with Applications, 165, 113959.
• Polat, O., Kalayci, C. B., Kulak, O., & Günther, H. O. (2015). A perturbation based variable neighborhood search heuristic for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time Limit. European Journal of Operational Research, 242(2), 369-382.
• Ropke, S., Pisinger, D., “A unified heuristic for a large class of vehicle routing problems with backhauls”, European Journal of Operational Research, 171: 750- 775 (2006).
• Sağlık Bakanlığı (2021), 19 Ağustos 2021 tarihinde https://covid19asi.saglik.gov.tr/TR-77809/turkiyenin- asi-soguk-zincir-ve-lojistik-kapasitesi.html adresinden alınmıştır.
• Song, X. Y., Zhu, J. Y., & Sun, H. L. (2014). Hybrid Differential Evolution Algorithm for Vehicle Routing Problem with Time Windows. Computer Science, 12, 049.
• Subramanian, A., Drummond, L. M. A., Bentes, C., Ochi, L. S., Farias, R. (2010). A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computers and Operations Research, 37 (11), 1899-1911. Subramanian, A., Uchoa, E., Pessoa, A. A., Ochi, L. S. (2011). Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Operations Research Letters, 39, 338-341.
• Sherif, S. U., Asokan, P., Sasikumar, P., Mathiyazhagan, K., & Jerald, J. (2021). Integrated optimization of transportation, inventory and vehicle routing with simultaneous pickup and delivery in two-echelon green supply chain network. Journal of Cleaner Production, 287, 125434.
• Tang, F. A., Galvao, R. D., “Vehicle routing problems with simultaneous pick-up and delivery service”, Journal of the Operational Research Society of India, 39: 19-33 (2002).
• Tasan, S., Gen, M., 2012. A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Computer Industrial Engineering, 62, 755-761.
• Toth, P. and Vigo, D. “Branch and Bound Algorithms for the Capacitated VRP”, In P., The Vehicle Routing Problem, SIAM, Philadelphia, USA, (2002).
• Wassan, N. A, Wassan, A. H., Nagy, G., “A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries”, Journal of Combinatorial Optimization, 15: 368-386 (2007).
• Wang, H. F., Chen, Y. Y., 2012. A genetic algorithm for the simultaneous delivery and pick up problems with time windows. Computer Industrial Engineering, 62, 84-95.
• 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. (2022). Research on Hybrid Immune Algorithm for Solving the Location-Routing Problem With Simultaneous Pickup and Delivery. Journal of Cases on Information Technology (JCIT), 24(5), 1-17.
• Yu, V. F., Susanto, H., Yeh, Y. H., Lin, S. W., & Huang, Y. T. (2022). The Vehicle Routing Problem with Simultaneous Pickup and Delivery and Parcel Lockers. Mathematics, 10(6), 920.
• Zachariadis, E. E., Tarantilis, C. D. Kiranoudis, C. T., “A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service”, Expert Systems with Applications, 36(2): 1070-1081 (2009a).
• Zachariadis, E. E., Tarantilis, C. D., Kiranoudis, C. T., “An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries”, European Journal of Operational Research, doi: 10.1016/j.ejor.2009.05.015 (2009b).
• Zachariadis, E. E., Kiranoudis, C. T. (2011). A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications, 38, 2717-2726.
• Zhang, Z., Cheang, B., Li, C., & Lim, A. (2019). Multi-commodity demand fulfillment via simultaneous pickup and delivery for a fast fashion retailer. Computers & Operations Research, 103, 81-96.
• Zhang, T., Chaovalitwongse, W. A., & Zhang, Y. (2014). Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery. Journal of Combinatorial Optimization, 28(1), 288-309.
• Zhang, J., & Yı, J. (2016). A hybrid Genetic-Monkey Algorithm for the Vehicle Routing Problem. International Journal of Hybrid Information Technology, 9(1), 397-404.
• Zhao, Y., Leng, L., & Zhang, C. (2021). A novel framework of hyper-heuristic approach and its application in location-routing problem with simultaneous pickup and delivery. Operational Research, 21(2), 1299-1332.
• Zhou, H., Qin, H., Zhang, Z., & Li, J. (2022). Two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery. Soft Computing, 26(7), 3345-3360.
• Zhu, L., & Sheu, J. B. (2018). Failure-specific cooperative recourse strategy for simultaneous pickup and delivery problem with stochastic demands. European Journal of Operational Research, 271(3), 896-912.