CLUSTER-BASED CLONAL SELECTION ALGORITHM FOR VEHICLE ROUTING PROBLEMS WITH TIME WINDOWS

Year 2023, , 307 - 320, 31.12.2023

Bilge Kagan Dedeturk , Burak Kolukisa , Mihrimah Özmen

https://doi.org/10.54365/adyumbd.1381562

Abstract

Today, the number of natural disasters is increasing and occurring more frequently, and these disasters deeply affect human life. Dealing with the devastation caused by natural disasters such as earthquakes, floods, and pandemics is quite challenging. The earthquake in Turkey on February 6 affected 11 provinces and affecting approximately 14 million people. After earthquakes, transportation infrastructure like roads, bridges, tunnels, and railways can become non-functional, making it challenging to quickly determine alternative routes. Vehicle routing problems (VRP) approaches can offer solutions for post-earthquake relief distribution activities. VRP is a combinatorial optimization and integer programming problem that optimizes a vehicle fleet to serve many customers. The Vehicle Routing Problem with Time Window (VRPTW) aims to determine routes with the lowest cost under specific time and capacity constraints. In this study, a Clustering-Based Clonal Selection Algorithm (CSA) is proposed for VRPTW. The initial solution set of the algorithm has been improved using K-means and K-means++ algorithms, and then results for VRPTW have been obtained with CSA. Experiments were conducted on the Solomon C1 and R1 datasets frequently used in the literature for testing VRP algorithms, and results were obtained for various problems. According to the experimental results, obtaining an initial solution with the clustering algorithm improved the results of the CSA and prevented the CSA from getting stuck in a local optimum.

Keywords

Clustering, Clonal Selection Algorithm, Vehicle Routing Problem, Solomon Dataset

Project Number

Bu çalışma; Türkiye Bilimsel ve Teknolojik Araştırma Kurumu tarafından 121E406 nolu proje kapsamında desteklenmiştir.

ZAMAN PENCERELİ ARAÇ ROTALAMA PROBLEMLERİ İÇİN KÜMELEME TEMELLİ KLONAL SEÇİM ALGORİTMASI

Abstract

Günümüzde doğal felaketlerin sayısı artmakta, daha sık yaşanmakta ve bu afetler, insan hayatını derinden etkilemektedir. Depremler, sel olayları ve salgınlar gibi doğal felaketlerin yol açtığı tahribatla başa çıkmak oldukça zordur. Türkiye'de gerçekleşen 6 Şubat depremi 11 ili etkileyerek yaklaşık 14 milyon insanı mağdur etmiştir. Deprem sonrası yol, köprü, tünel ve demiryolu gibi ulaşım altyapıları işlevsiz hale gelebilmekte ve alternatif rotaların hızla belirlenmesi zorlaşabilmektedir. Deprem sonrası yardım dağıtım faaliyetlerinde, araç rotalama problemleri (ARP) ile çözüm üretilebilir. ARP, çok sayıda müşteriye hizmet vermek amacıyla bir araç filosunu optimize eden kombinatoryal bir optimizasyon ve tam sayılı programlama problemidir. Zaman pencereli araç rotalama problemi (ZP-ARP) belirli zaman ve kapasite kısıtları altında en düşük maliyetle rotaların belirlenmesini amaçlar. Bu çalışmada, ZP-ARP için Kümeleme Temelli Klonal Seçim Algoritması (KSA) önerilmektedir. K-ortalama ve K-ortalama++ algoritmaları kullanılarak algoritmanın başlangıç çözüm kümesi iyileştirilmiş ve ardından KSA ile ZR-ARP için sonuçlar elde edilmiştir. Deneyler, ARP algoritmalarının sınanmasında literatürde sıklıkla kullanılan Solomon C1 ve R1 veri setleri üzerinde gerçekleştirilmiş olup, çeşitli problemler için sonuçları alınmıştır. Deney sonuçlarına göre, kümeleme algoritması ile başlangıç çözümü elde edilmesi, KSA’nın sonuçlarını iyileştirdiği ve KSA’ nın yerel optimuma takılmasını önlediği görülmüştür.

Keywords

Kümeleme, Klonal Seçim Algorithması, Araç Rotalama Problemi, Solomon Veri Seti

Project Number

Bu çalışma; Türkiye Bilimsel ve Teknolojik Araştırma Kurumu tarafından 121E406 nolu proje kapsamında desteklenmiştir.

References

• [1] https://reliefweb.int/report/turkiye/cred-crunch-newsletter-issue-no-72-september-2023-earthquakes-turkiye-review-1900-today
• [2] Zhong, S., Cheng, R., Jiang, Y., Wang, Z., Larsen, A., & Nielsen, O. A. (2020). Risk-averse optimization of disaster relief facility location and vehicle routing under stochastic demand. Transportation Research Part E: Logistics and Transportation Review, 141, 102015.
• [3] Benson, M., Koenig, K. L., & Schultz, C. H. (1996). Disaster triage: START, then SAVE—a new method of dynamic triage for victims of a catastrophic earthquake. Prehospital and disaster medicine, 11(2), 117-124.
• [4] Zhang, J., Zhang, J., Qin, Z., & Jia, Y. (2022). Vehicle routing problems with time windows based on the improved hybrid fish swarm-ant colony algorithm. International Journal on Interactive Design and Manufacturing (IJIDeM), 1-8.
• [5] Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
• [6] Hang, Z., Luo, Z. L., & Huang, S. W. (2015). Application research of hybrid ant colony algorithm in vehicle routing problem with time windows. Acta Scientiarum Naturali-um Universitatis Sunyatseni, 54(1), 41-46.
• [7] Pang, Y., Luo, H. L., Xing, L. N., & Ren, T. (2019). A survey of vehicle routing optimization problems and solution methods. Control Theory Appl, 36(10), 1574-1582.
• [8] Gocken, T., & Yaktubay, M. (2019). Comparison of different clustering algorithms via genetic algorithm for VRPTW.
• [9] Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
• [10] Xiao-nan, Z. H. A. N. G., & Hou-ming, F. A. N. (2021). Hybrid memetic algorithm for vehicle routing problem with time windows. Operations Research and Management Science, 30(7), 128.
• [11] Tang, J., Zhang, J., & Pan, Z. (2010). A scatter search algorithm for solving vehicle routing problem with loading cost. Expert Systems with Applications, 37(6), 4073-4083.
• [12] Dasgupta, D. (Ed.). (2012). Artificial immune systems and their applications. Springer Science & Business Media.
• [13] De Castro, L. N., & Timmis, J. (2002). Artificial immune systems: a new computational intelligence approach. Springer Science & Business Media.
• [14] De Castro, L. N., & Von Zuben, F. J. (2002). Learning and optimization using the clonal selection principle. IEEE transactions on evolutionary computation, 6(3), 239-251.
• [15] Brabazon, A., & O'Neill, M. (2006). Biologically inspired algorithms for financial modelling. Springer Science & Business Media.
• [16] Marinakis, Y., Marinaki, M., & Migdalas, A. (2014). A hybrid clonal selection algorithm for the vehicle routing problem with stochastic demands. In Learning and Intelligent Optimization: 8th International Conference, Lion 8, Gainesville, FL, USA, February 16-21, 2014. Revised Selected Papers 8 (pp. 258-273). Springer International Publishing.
• [17] Pan, L., & Fu, Z. (2009, October). A clone selection algorithm for the open vehicle routing problem. In 2009 Third International Conference on Genetic and Evolutionary Computing (pp. 786-790). IEEE.
• [18] Dabrowski, J. (2008, May). Clonal selection algorithm for vehicle routing. In 2008 1st International Conference on Information Technology (pp. 1-4). IEEE.
• [19] Ogiołda, M. (2017). The use of clonal selection algorithm for the vehicle routing problem with time windows. In Symposium for Young Scientists in Technology, Engineering and Mathematics (pp. 68-74).
• [20] Toğan, V., & Daloğlu, A. T. (2008). An improved genetic algorithm with initial population strategy and self-adaptive member grouping. Computers & Structures, 86(11-12), 1204-1218.
• [21] Bin, Z., & Xiao-Jun, L. (2015). Study on logistics distribution route optimization based on clustering algorithm and ant colony algorithm. The Open Cybernetics & Systemics Journal, 9(1).
• [22] Wang, J., Ji, Z., Shi, M., Huang, F., Zhu, C., & Zhang, D. (2015). Scenario analysis and application research on big data in smart power distribution and consumption systems. Proceedings of the CSEE, 35(8), 1829-1836.
• [23] Zhao, Z., Wang, J., & Liu, Y. (2017, December). User electricity behavior analysis based on K-means plus clustering algorithm. In 2017 International Conference on Computer Technology, Electronics and Communication (ICCTEC) (pp. 484-487). IEEE.
• [24] Syakur, M. A., Khotimah, B. K., Rochman, E. M. S., & Satoto, B. D. (2018, April). Integration K-means clustering method and elbow method for identification of the best customer profile cluster. In IOP conference series: materials science and engineering (Vol. 336, p. 012017). IOP Publishing.