HİBRİT GASA İLE İSTANBUL'DA DİNAMİK OTOBÜS

Öz

Ulaşım, herhangi bir şehirde en dıştaki banliyöleri merkeze bağlayan önemli bir unsurdur. Ulaşım sistemini yükseltmek için yapılan çalışmaların çoğu, şirketin faydasına göre araçların programını optimize etmek yoluyla yapılır. Odak noktası yolculara kaydığında, diğer projeler gelecekteki talebi tahmin etmek için yolcu sayısı verilerini toplar. Ancak bu proje, hibrit genetik algoritma kullanarak bekleme istasyonlarında kalan yolcu sayısını en aza indirme amacıyla bir otobüsün programını optimize ederek yolcunun deneyimini dikkate alır. Çizelgeleme artık statik olmayacak, dinamik olacaktır ve uzaysal-zamansal faktörleri, filo büyüklüğünü, araç kapasitesini ve daha fazlasını göz önünde bulundurarak mümkün olan her yolcuya hizmet etmek için periyodik olarak değişecektir. Çoğu çizelgeleme problemi, çizelgeleme problemlerini çözmek için genetik algoritmayı ve onun varyasyonlarını kullanmaktadır ve bu çalışma genetik algoritma ile benzetilmiş tavlamayı entegre ederek, genetik algoritmanın zayıf yerel aramasından kaçınır ve süreci hızlandırır. Önerilmekte olan entegre genetik algoritma ve benzetilmiş tavlama, bir günde kalan toplam yolcu sayısını en aza indiren bir çözüm bulmada hem genetik algoritmadan hem de benzetilmiş tavlamadan daha iyi sonuçlar ürettiğini kanıtlamıştır. Bu teknik, hızlı otobüs taşımacılığı, metro, tren ve daha fazlası gibi diğer ulaşım biçimlerine uyarlanabilir.

Anahtar Kelimeler

• Dinamik Çizelgeleme
• Optimizasyon
• Genetik Algoritma
• Benzetilmiş Tavlama
• Hibrit GASA

DYNAMIC BUS SCHEDULING IN ISTANBUL WITH HYBRID GASA

Abstract

Transportation is a key element in any city, connecting the outermost suburbs to the center. Most studies done to elevate the transportation system are through optimizing the schedule of vehicles with respect to company’s benefit. When the focus shifts to the riders, other projects gather ridership data to predict future demand. However, this project considers the rider’s experience by optimizing a bus’s schedule with the objective of minimizing passengers remaining at waiting stations using a hybrid genetic algorithm. The schedule will no longer be static, but dynamic, morphing periodically, to service every passenger possible while considering spaciotemporal factors, fleet size, vehicle capacity and more. Most scheduling problems use the genetic algorithm and its variations to solve scheduling problems, and this study integrates it with simulated annealing, since their combination can avoid poor local search of genetic algorithm and speeding its process. The proposed integrated genetic algorithm and simulated annealing has proven to be the best both genetic algorithm and simulated annealing in finding a solution that minimized the total number of remaining passengers in a day. This technique can be translated into other forms of transportation such as bus rapid transport, subways, trains and more.

Keywords

• Dynamic Scheduling
• Optimization
• Genetic Algorithm
• Simulated Annealing
• Hybrid GASA

Kaynakça

1. Abdulal, W., & Ramachandram, S. (2011, June). Reliability-aware genetic scheduling algorithm in grid environment. In 2011 International Conference on Communication Systems and Network Technologies (pp. 673-677). IEEE.
2. Ai, G., Zuo, X., Chen, G., & Wu, B. (2022). Deep reinforcement learning based dynamic optimization of bus timetable. Applied Soft Computing, 131, 109752.
3. Arifoğulları, Ö., & Alptekin, G. I. (2022). Public Transportation Data Analysis to Estimate Road Status in Metropolitan Areas: The Case of İstanbul. Procedia Computer Science, 210, 12-18.
4. Baeldung. (06.01.2025). Simulated Annealing in Computer Science. Retrieved from https://www.baeldung.com/cs/simulated-annealing.
5. Buran, B. (2013). Istanbul metrobus system. In Proceedings of the International Conference on Tourism, Transport, and Logistics, Paris (pp. 547-559).
6. Chuanjiao, S. U. N., Wei, Z. H. O. U., & Yuanqing, W. A. N. G. (2008). Scheduling combination and headway optimization of bus rapid transit. Journal of transportation systems engineering and information technology, 8(5), 61-67.
7. Databricks. (a.d. 27.12.2024). Comparing Databricks to Apache Spark. Databricks. Retrieved, from https://www.databricks.com/spark/comparing-databricks-to-apache-spark.
8. De Jong, K. A. (1975). An analysis of the behavior of a class of genetic adaptive systems. University of Michigan.

9. Fox B, McMahon M (1991) Genetic operators for sequencing problems, in Foundations of Genetic Algorithms, G. Rawlins, Ed. Morgan Kaufmann Publishers, San Mateo,CA, Ed. 1991, pp. 284–300.
10. Freisleben, B., & Merz, P. (1996, September). New genetic local search operators for the traveling salesman problem. In International Conference on Parallel Problem Solving from Nature (pp. 890-899). Berlin, Heidelberg: Springer Berlin Heidelberg.
11. F. Wang et al., "Millisecond-Scale Real-Time Scheduling of Buses: A Controller-Based Approach," in IEEE Transactions on Intelligent Transportation Systems, vol. 25, no. 7, pp. 7893-7906, July 2024, doi: 10.1109/TITS.2023.3348115.
12. Gkiotsalitis, K., & Alesiani, F. (2019). Robust timetable optimization for bus lines subject to resource and regulatory constraints. Transportation Research Part E: Logistics and Transportation Review, 128, 30-51.
13. Holland, J. H. (1992). Genetic algorithms. Scientific american, 267(1), 66-73.
14. IETT – Istanbul Electric Tram and Tunnel Company. (a.d. 15.10.2024). Route detail: 429A Kirac - Avcilar Metrobus. IETT. [Online: https://iett.istanbul/EnRouteDetail?hkod=429A&routename=kirac-avcilar-metrobus]
15. Istanbul Metropolitan Municipality. (a.d. 15.03.2024). Hourly Public Transport Data Set. Istanbul Metropolitan Municipality Open Data Portal. [Online: https://data.ibb.gov.tr/en/dataset/hourly-public-transport-data-set]
16. Jebari, K., & Madiafi, M. (2013). Selection methods for genetic algorithms. International Journal of Emerging Sciences, 3(4), 333-344.
17. Katoch, S., Chauhan, S. S., & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia tools and applications, 80, 8091-8126.
18. Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
19. Lee, C. Y. (2003). Entropy-Boltzmann selection in the genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 33(1), 138-149.
20. Li, X., Du, H., Ma, H., & Shang, C. (2018). Timetable optimization for single bus line involving fuzzy travel time. Soft Computing, 22, 6981-6994.
21. Lin, H., & Tang, C. (2021). Intelligent bus operation optimization by integrating cases and data driven based on business chain and enhanced quantum genetic algorithm. IEEE Transactions on Intelligent Transportation Systems, 23(7), 9869-9882.
22. Lu, K., Liu, J., Zhou, X., & Han, B. (2020). A review of big data applications in urban transit systems. IEEE Transactions on Intelligent Transportation Systems, 22(5), 2535-2552.
23. Luhua, S., Yin, H., & Xinkai, J. (2011). Study on method of bus service frequency optimal ModelBased on genetic algorithm. Procedia Environmental Sciences, 10, 869-874.
24. Michalewicz, Z., & Schoenauer, M. (1996). Evolutionary algorithms for constrained parameter optimization problems. Evolutionary computation, 4(1), 1-32.
25. Mo, S., Bao, Z., Zheng, B., & Peng, Z. (2020). Towards an optimal bus frequency scheduling: When the waiting time matters. IEEE Transactions on Knowledge and Data Engineering, 34(9), 4484-4498.
26. Moovit (a.d. 11.11.2024). 429A route: Timetables, stops & maps - Avcılar Metrobüs. Moovit. [Available online at: https://moovitapp.com/istanbul-1563/lines/429a/72389532/6567568/en]
27. Ning, Z., Tao, C., Fei, L., & Haitao, X. (2015). A hybrid heuristic algorithm for the intelligent transportation scheduling problem of the BRT system. Journal of Intelligent Systems, 24(4), 437-448.
28. Qian, Z., Feng-Lian, W., & Ju, L. (2015). A bus headway optimization model based on genetic taboo algorithm. Journal of Transport Science and Engineering.
29. Saini, N. (2017). Review of selection methods in genetic algorithms. International Journal of Engineering and Computer Science, 6(12), 22261-22263.
30. Samasti, M., (2023) Integrated planning of public transportation systems in smart cities–istanbul case study. In International Research and Reviews in Engineering Volume 1, 47-75, Serüven Yayınevi.
31. Sevim, I., Tekiner‐Moğulkoç, H., & Güler, M. G. (2022). Scheduling the vehicles of bus rapid transit systems: a case study. International Transactions in Operational Research, 29(1), 347-371.
32. Song, C. Y., Wang, H. L., Chen, L., & Niu, X. Q. (2024). An optimized two‐phase demand‐responsive transit scheduling model considering dynamic demand. IET Intelligent Transport Systems, 18(5), 853-871.
33. Soon, G. K., Guan, T. T., On, C. K., Alfred, R., & Anthony, P. (2013, November). A comparison on the performance of crossover techniques in video game. In 2013 IEEE international conference on control system, computing and engineering (pp. 493-498). IEEE.
34. Tang, J., Yang, Y., & Qi, Y. (2018). A hybrid algorithm for urban transit schedule optimization. Physica A: Statistical Mechanics and its Applications, 512, 745-755.
35. Tang, J., Yang, Y., Hao, W., Liu, F., & Wang, Y. (2020). A data-driven timetable optimization of urban bus line based on multi-objective genetic algorithm. IEEE Transactions on Intelligent Transportation Systems, 22(4), 2417-2429.
36. Tech Steel & Materials. (06.01.2025) What is Annealing and Why is it Done? Retrieved from https://www.techsteel.net/what-is-annealing-and-why-is-it-done
37. TUIK, Turkish Statistical Institute: (2024, February 06). The Results of Address Based Population Registration System, 2023 [Press Release]. https://data.tuik.gov.tr/Bulten/Index?p=The-Results-of-Address-Based-Population-Registration-System-2023-49684&dil=2.
38. TWI - The Welding Institute. (06.01.2025). What is Annealing? Retrieved from https://www.twi-global.com/technical-knowledge/faqs/what-is-annealing
39. Ushakov, D., Dudukalov, E., Shmatko, L., & Shatila, K. (2022). Artificial Intelligence as a factor of public transportations system development. Transportation Research Procedia, 63, 2401-2408.
40. Utku, A., & Kaya, S. K. (2022). Multi-layer perceptron based transfer passenger flow prediction in Istanbul transportation system. Decision Making: Applications in Management and Engineering, 5(1), 208-224.
41. Utku, A., & Kaya, S. K. (2023). New deep learning-based passenger flow prediction model. Transportation research record, 2677(3), 1-17.
42. Vemuri, N., Tatikonda, V. M., & Thaneeru, N. (2024). Enhancing Public Transit System through AI and IoT. Valley International Journal Digital Library, 1057-1071.
43. Wei Pu and Yi-Ren Zou, "Using GASA to solve distributed real-time scheduling problems," Proceedings. International Conference on Machine Learning and Cybernetics, Beijing, China, 2002, pp. 958-961 vol.2, doi: 10.1109/ICMLC.2002.1174525.
44. Welch, T. F., & Widita, A. (2019). Big data in public transportation: a review of sources and methods. Transport reviews, 39(6), 795-818.
45. Wihartiko, F. D., Buono, A., & Silalahi, B. P. (2017). Integer programming model for optimizing bus timetable using genetic algorithm. In IOP Conference Series: Materials Science and Engineering (Vol. 166, No. 1, p. 012016). IOP Publishing.
46. ZhongXi, C., QiJie, H., DeBin, F., & ZhenCheng, L. (2019, June). An Intelligent Bus Scheduling System Based On Real-Time Passenger Flow Data. In 2019 International Conference on Robots & Intelligent System (ICRIS) (pp. 174-178). IEEE.