The Optimization of Routes Using Evolutionary Algorithms in Public Transportation Systems

Year 2022, Volume: 5 Issue: 1, 64 - 74, 02.03.2022

Salih Serkan Kaleli Mehmet Bayğın Abdullah Naralan

https://doi.org/10.38016/jista.951008

Abstract

This study aims to examine, regulate, and update the land transportation of the Erzurum Metropolitan Municipality (EMM), Turkey using computerized calculation techniques. In line with these targets, some critical information has been obtained for study: the number of buses, the number of expeditions, the number of bus lines, and the number and maps of existing routes belonging to EMM. By using the information that has been obtained, this study aims at outlining specific outputs according to the input parameters, such as determining the optimal routes, the average travel, and the journey time. Once all of these situations were considered, various optimization algorithms were used to get the targeted outputs in response to the determined input parameters. In addition, the study found that the problem involved in modeling the land transport network of the EMM is in line with the so-called “traveling salesman problem,” which is a scenario about optimization often discussed in the literature. This study tried to solve this problem by using the genetic algorithm, the clonal selection algorithm, and the DNA computing algorithm. The location data for each bus stops on the bus lines selected for the study were obtained from the EMM, and the distances between these coordinates were obtained by using Google Maps via a Google API. These distances were stored in a distance matrix file and used as input parameters in the application and then were put through optimization algorithms developed initially on the MATLAB platform. The study’s results show that the algorithms developed for the proposed approaches work efficiently and that the distances for the selected bus lines can be shortened.

Keywords

Optimization, Evolutionary Algorithms, Traveling Salesman Problem, Genetic Algorithm, Management Information Systems

Thanks

In this study, we thank the Erzurum Metropolitan Municipality Public Transportation Administration for the data it provided.

Toplu Taşıma Sistemlerinin Evrimsel Algoritmalarla Optimizasyonu

Abstract

Bu çalışma, Erzurum Büyükşehir Belediyesi'nin (EBB) Türkiye kara ulaşımını bilgisayarlı hesaplama teknikleri kullanarak incelemeyi, düzenlemeyi ve güncellemeyi amaçlamaktadır. Bu hedefler doğrultusunda, çalışma için bazı önemli bilgiler: otobüs sayısı, sefer sayısı, otobüs hattı sayısı ve EBB’ye ait mevcut güzergâh sayısı ve haritaları elde edilmiştir. Bu çalışma, elde edilen bilgileri kullanarak, optimal rotaların belirlenmesi, ortalama seyahat ve yolculuk süresi gibi girdi parametrelerine göre belirli çıktıların ana hatlarını çizmeyi amaçlamaktadır. Tüm bu durumlar göz önüne alındığında, belirlenen girdi parametrelerine karşılık hedeflenen çıktıları elde etmek için çeşitli optimizasyon algoritmaları kullanılmıştır. Çalışma, EBB’ nin ulaşım ağının modellenmesindeki problemin, literatürde sıklıkla tartışılan optimizasyonla ilgili bir senaryo olan “gezgin satıcı problemi” ile uyumlu olduğunu bulmuştur. Çalışmada genetik algoritma, klonal seçim algoritması ve DNA hesaplama algoritması kullanılarak bu problem çözülmeye çalışılmıştır. Çalışmada seçilen otobüs hatlarındaki her bir durak için konum bilgisi EBB'den alınmış ve bu koordinatlar arasındaki mesafeler bir Google API üzerinden Google Maps kullanılarak elde edilmiştir. Bu mesafeler bir mesafe matrisi dosyasında saklanmış ve uygulamada giriş parametreleri olarak kullanılmış daha sonra MATLAB platformunda geliştirilen optimizasyon algoritmalarına aktarılmıştır. Çalışmanın sonuçları, önerilen yaklaşımlar için geliştirilen algoritmaların verimli çalıştığını ve seçilen otobüs hatları için mesafelerin kısaltılabileceğini göstermektedir.

Keywords

Optimizasyon, Evrimsel Algoritmalar, Gezgin Satıcı Problemi, Genetik Algoritma, Yönetim Bilişim Sistemleri

References

• Asadpour, A., Goemans, M. X., Ma̧dry, A., Gharan, S. O., and Saberi, A. 2010. “An O(Log n/ Log Log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem,” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (June), pp. 379–389. (https://doi.org/10.1137/1.9781611973075.32).
• Baygin, M., and Karakose, M. 2013. “Immunity-Based Optimal Estimation Approach for a New Real Time Group Elevator Dynamic Control Application for Energy and Time Saving,” The Scientific World Journal (2013). (https://doi.org/10.1155/2013/805343).
• Bolat, B., and Cortés, P. 2011. “Genetic and Tabu Search Approaches for Optimizing the Hall Call - Car Allocation Problem in Elevator Group Systems,” Applied Soft Computing Journal (11:2), pp. 1792–1800. (https://doi.org/10.1016/j.asoc.2010.05.023).
• Chen, P. 2013. “An Improved Genetic Algorithm for Solving the Traveling Salesman Problem,” Proceedings - International Conference on Natural Computation (6), pp. 397–401. (https://doi.org/10.1109/ICNC.2013.6818008).
• Choong, S. S., Wong, L. P., and Lim, C. P. 2019. “An Artificial Bee Colony Algorithm with a Modified Choice Function for the Traveling Salesman Problem,” Swarm and Evolutionary Computation (44:December 2017), pp. 622–635. (https://doi.org/10.1016/j.swevo.2018.08.004).
• Deng, W., Zhao, H., Zou, L., Li, G., Yang, X., and Wu, D. 2017. “A Novel Collaborative Optimization Algorithm in Solving Complex Optimization Problems,” Soft Computing (21:15), Springer Berlin Heidelberg, pp. 4387–4398. (https://doi.org/10.1007/s00500-016-2071-8).
• Dodge, M., MirHassani, S. A., and Hooshmand, F. 2020. “Solving Two-Dimensional Cutting Stock Problem via a DNA Computing Algorithm,” Natural Computing (3), Springer Netherlands. (https://doi.org/10.1007/s11047-020-09786-3).
• Groba, C., Sartal, A., and Vázquez, X. H. 2015. “Solving the Dynamic Traveling Salesman Problem Using a Genetic Algorithm with Trajectory Prediction: An Application to Fish Aggregating Devices,” Computers and Operations Research (56), Elsevier, pp. 22–32. (https://doi.org/10.1016/j.cor.2014.10.012).
• Guney, K., Babayigit, B., and Akdagli, A. 2007. “Position Only Pattern Nulling of Linear Antenna Array by Using a Clonal Selection Algorithm (CLONALG),” Electrical Engineering (90:2), pp. 147–153. (https://doi.org/10.1007/s00202-006-0056-9).
• Guo, Z., Koehler, G. J., and Whinston, A. B. 2007. “A Market-Based Optimization Algorithm for Distributed Systems,” Management Science (53:8), pp. 1345–1358. (https://doi.org/10.1287/mnsc.1060.0690).
• Hasan Söyler, T. K. 2007. Karınca Kolonisi Algoritması Ile Gezen Satıcı Probleminin Çözümğ.
• Hiassat, A., Diabat, A., and Rahwan, I. 2017. “A Genetic Algorithm Approach for Location-Inventory-Routing Problem with Perishable Products,” Journal of Manufacturing Systems (42), The Society of Manufacturing Engineers, pp. 93–103. (https://doi.org/10.1016/j.jmsy.2016.10.004).
• Ibrahim, G. J., Rashid, T. A., and Sadiq, A. T. 2018. “Evolutionary DNA Computing Algorithm for Job Scheduling Problem,” IETE Journal of Research (64:4), pp. 514–527. (https://doi.org/10.1080/03772063.2017.1362964).
• Kovács, L., Iantovics, L. B., and Iakovidis, D. K. 2018. “IntraClusTSP-An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem,” Symmetry (10:12). (https://doi.org/10.3390/sym10120663).
• Mahi, M., Baykan, Ö. K., and Kodaz, H. 2015. “A New Hybrid Method Based on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt Algorithms for Traveling Salesman Problem,” Applied Soft Computing Journal (30), Elsevier B.V., pp. 484–490. (https://doi.org/10.1016/j.asoc.2015.01.068).
• Malhotra, R., Singh, N., and Singh, Y. 2011. “Genetic Algorithms: Concepts, Design for Optimization of Process Controllers,” Computer and Information Science (4:2), pp. 39–54. (https://doi.org/10.5539/cis.v4n2p39).
• Mohammed, M. A., Abd Ghani, M. K., Hamed, R. I., Mostafa, S. A., Ahmad, M. S., and Ibrahim, D. A. 2017. “Solving Vehicle Routing Problem by Using Improved Genetic Algorithm for Optimal Solution,” Journal of Computational Science (21), Elsevier B.V., pp. 255–262. (https://doi.org/10.1016/j.jocs.2017.04.003).
• Muthreja, I., and Kaur, D. 2018. “A Comparative Analysis of Immune System Inspired Algorithms for Traveling Salesman Problem,” 2018 World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2018 - Proceedings of the 2018 International Conference on Artificial Intelligence, ICAI 2018, pp. 164–170.
• NARALAN, A., KALELİ, S. S., and BAYĞIN, M. 2017. “Shortest Path Detection Using Clonal Selection Algorithm for Erzurum Metropolitan Municipality,” Mugla Journal of Science and Technology (3:2), pp. 138–142. (https://doi.org/10.22531/muglajsci.357621).
• Nguyen, H. D., Yoshihara, I., Yamamori, K., and Yasunaga, M. 2002. “Greedy Genetic Algorithms for Symmetric and Asymmetric TSPs,” IPSJ Trans. Mathematical Modeling and Its Applications (43:10), pp. 165–175.
• Priyo Anggodo, Y., Kartika Ariyani, A., Khaerul Ardi, M., and Firdaus Mahmudy, W. 2016. “Optimization of Multi-Trip Vehicle Routing Problem With Time Windows Using Genetic Algorithm,” Journal of Enviromental Engineering and Sustainable Technology (3:2), pp. 92–97. (https://doi.org/10.21776/ub.jeest.2017.003.02.4).
• Saji, Y., and Riffi, M. E. 2016. “A Novel Discrete Bat Algorithm for Solving the Travelling Salesman Problem,” Neural Computing and Applications (27:7), Springer London, pp. 1853–1866. (https://doi.org/10.1007/s00521-015-1978-9).
• Shrikrishna, K., B, N. V. N. K., and Shyamasundar, R. K. 2018. Security Analysis of EMV Protocol, (2:December), pp. 69–85. (https://doi.org/10.1007/978-3-319-72344-0).
• Suman, S. K. 2015. “Genetic Algorithms: Basic Concepts and Real World Applications,” International Journal of Electrical, Electronics and Computer Systems (November). (https://scholar.google.co.in/citations?view_op=view_citation&continue=/scholar%3Fhl%3Den%26as_sdt%3D0,5%26scilib%3D1&citilm=1&citation_for_view=dj9eYFMAAAAJ:UebtZRa9Y70C&hl=en&oi=p).
• Sundararaghavan, P. S., Kunnathur, A., and Fang, X. 2010. “Sequencing Questions to Ferret out Terrorists: Models and Heuristics,” Omega (38:1–2), Elsevier, pp. 12–19. (https://doi.org/10.1016/j.omega.2009.01.002).
• Wang, J., Ersoy, O. K., He, M., and Wang, F. 2016. “Multi-Offspring Genetic Algorithm and Its Application to the Traveling Salesman Problem,” Applied Soft Computing Journal (43), Elsevier B.V., pp. 415–423. (https://doi.org/10.1016/j.asoc.2016.02.021).
• Xu, Z., Wang, Y., Li, S., Liu, Y., Todo, Y., and Gao, S. 2016. “Immune Algorithm Combined with Estimation of Distribution for Traveling Salesman Problem,” IEEJ Transactions on Electrical and Electronic Engineering (11), pp. S142–S154. (https://doi.org/10.1002/tee.22247).
• Zhang, Y. 2018. “The Image Encryption Algorithm Based on Chaos and DNA Computing,” Multimedia Tools and Applications (77:16), Multimedia Tools and Applications, pp. 21589–21615. (https://doi.org/10.1007/s11042-017-5585-x).