یک رویکرد جدید برای مسیریابی اتوبوس مدرسه با استفاده از الگوریتم بهینه‌ساز کوسه سفید
محورهای موضوعی : پردازش چند رسانه ای، سیستمهای ارتباطی، سیستمهای هوشمندمحمد سالمی فر 1 , محمدرضا محمدرضائی 2
1 - کارشناسی ارشد، گروه مهندسی کامپیوتر، واحد بردسیر، دانشگاه آزاد اسلامی، بردسیر، ایران
2 - استادیار، گروه مهندسی کامپیوتر، واحد رامهرمز، دانشگاه آزاد اسلامی، رامهرمز، ایران
کلید واژه: SBRP, مسیریابی اتوبوس مدرسه, الگوریتم بهینه‌ساز کوسه سفید,
چکیده مقاله :
مسئله مسیریابی اتوبوس مدرسه (SBRP) چالش پیچیدهای در حمل‌ونقل است که شامل یافتن مسیرهای اتوبوس بهینه است. پرداختن به مسائل اضطراری مانند افزایش بار ترافیک، جمعیت بالای دانش‌آموزان، کمبود منابع، ایمنی و خطرات می‌تواند نقش اساسی در طراحی یک برنامه کارآمد برای سیستم حمل‌ونقل دانش‌آموزی داشته باشد. اهمیت این موضوع زمانی برجسته می‌شود که نیازها و انتظارات همه ذینفعان از جمله دانش‌آموزان، بخش خصوصی و شهرداری‌ها درنظرگرفته شوند. هدف SBRP طراحی مسیرهایی برای ناوگان اتوبوس مدرسه است که دانش‌آموزان را در یک سری از ایستگاه‌های اتوبوس از پیش تعریف‌شده سوارمی‌کند و آن‌ها را در مدرسه پیاده می‌کند. این مسئله به‌عنوان NP-Hard شناخته می‌شود؛ بنابراین پرداختن به مسئله مسیریابی اتوبوس مدرسه برای اطمینان از راه‌حل ایمن و مقرون‌به‌صرفه برای دانش‌آموزان، والدین و ذینفعان مهم است. بااین حال، چالش‌هایی از نظر محدودیت‌ها و اهداف متعدد وجوددارد. در این مقاله، مسئله مسیریابی اتوبوس مدرسه به‌عنوان مسئله بهینه‌سازی فرموله شده است. برای حل این مسئله از الگوریتم بهینه‌ساز کوسه سفید استفاده شده است. روش پیشنهادی در شبیه‌ساز متلب اجرا شده است. تعداد دانش‌آموز، 100 در نظر گرفته شده است. تعداد اتوبوس، 7 اتوبوس و تعداد مدرسه، 5 مدرسه است. معیارهای ارزیابی شامل مجموع فواصل حرکت سرویس‌های مدارس، میانگین زمان رفت‌وآمد دانش‌آموزان، کل زمان سفر و مطلوبیت مسیریابی بوده‌اند. روش پیشنهادی توانسته است معیارهای ارزیابی را نسبت به طرح پایه مبتنی بر الگوریتم ژنتیک و روش مبتنی بر الگوریتم مورچگان بهبوددهد.
Abstract
Introduction:School Bus Routing Problem (SBRP) is a complex transportation challenge that involves finding optimal bus routes. addressing urgent issues such as increased traffic load, high student population, lack of resources, safety, and hazards can play an essential role in designing an efficient program for the student transportation system. The importance of this issue is highlighted when the needs and expectations of all stakeholders, including students, the private sector, and municipalities, are considered.
Method: The goal of SBRP is to design routes for the school bus fleet that pick up students at a series of pre-defined bus stops and drop them off at school. This problem is known as NP-Hard; It is therefore important to address the issue of school bus routing to ensure a safe and cost-effective solution for students, parents and stakeholders. However, there are challenges in terms of limitations and multiple objectives. In this paper, the school bus routing problem is formulated as an optimization problem. To solve this problem, the white shark optimization algorithm has been used.
Results: The proposed method has been implemented in MATLAB simulator. The number of students is 100. The number of buses is 7 and the number of schools is 5. The evaluation criteria included the total travel distances of school services, the average commuting time of students, the total travel time and the desirability of routing.
Discussion: The proposed method has been able to improve the evaluation criteria compared to the basic plan based on the genetic algorithm and the method based on the ant algorithm.
[1] Hariri, Mehdi, (1402), face recognition in the image using the Viola-Jones method and image texture analysis, intelligent multimedia processing and communication systems.. 1-10. [Persian]
[2] Mousavi, Zeinab, Kerami, Elaha, Gholami, Kobra, (1402), Using discrete-time Zhang neural networks for time-varying nonlinear optimization, intelligent multimedia processing and communication systems. 31-42. [Persian]
[3] Nazarpour, Mohammad, Nazafti, Naveed, Shakuhyar, Sajjad, (1402), using the modified colonial competition algorithm to increase the speed and accuracy of intelligent intrusion detection system, intelligent multimedia processing and communication systems. [Persian]
[4] Bakeshlu, Maryam, Tahghighi Sharbyan, Mohammad, (1401), presenting a new approach based on deep learning technique to investigate the factors affecting the use of social networks and students' academic performance, intelligent multimedia processing and communication systems. 29-41 [Persian]
[5] Bala Kodehi, Javad, Research Sharbian, Mohammad, (1401), presenting a method to identify and detect fraud in credit cards using the hybrid algorithm of neural network and colonial competition, intelligent multimedia processing and communication systems 62-51. [Persian]
[6] Xue, Z., Deng, X., Chen, B., & Khamis, A. (2023, March). School bus routing using metaheuristics algorithms. In 2023 IEEE International Conference on Smart Mobility (SM) (pp. 33-38). IEEE.
[7] Feng, R., Zhang, J., Wu, Y., Wu, R., & Yao, B. (2023). School accessibility evaluation under mixed-load school bus routing problem strategies. Transport policy, 131, 75-86.
[8] Calvete, H. I., Galé, C., Iranzo, J. A., & Toth, P. (2023). The school bus routing problem with student choice: a bilevel approach and a simple and effective metaheuristic. International Transactions in Operational Research, 30(2), 1092-1119.
[9] Qian, L. (2023). A Neural Combinatorial Approach for School Bus Routing System Optimization (Doctoral dissertation, Northeastern University).
[10] Braik, M., Hammouri, A., Atwan, J., Al-Betar, M. A., & Awadallah, M. A. (2022). White Shark Optimizer: A novel bio-inspired meta-heuristic algorithm for global optimization problems. Knowledge-Based Systems, 243, 108457.
[11] Konstantinos, G., & Dimitra, A. (2023, July). School Bus Routing Problem-Algorithm Optimization Using Graph Theory. In Science and Information Conference (pp. 185-218). Cham: Springer Nature Switzerland.
[12] Ellegood, W. A., Riley, J. M., & Berg, M. D. (2024). The many costs of operating school buses in America. Research in Transportation Economics, 103, 101401.
[13] Effendy, S., & Yap, R. H. (2023). Real-time passenger bus routing problems with preferences and tradeoffs. Annals of Mathematics and Artificial Intelligence, 91(2), 287-307.
[14] Kumar, Y., & Jain, S. (2015, September). School bus routing based on branch and bound approach. In 2015 International Conference on Computer, Communication and Control (IC4) (pp. 1-4). IEEE.
[15] Wang, J. Y., Wu, Z., Kang, Y., Brown, E., Wen, M., Rushton, C., & Ehrgott, M. (2023). Walking school bus line routing for efficiency, health and walkability: A multi‐objective optimisation approach. Journal of Multi‐Criteria Decision Analysis, 30(3-4), 109-131.
[16] Calvete, H. I., Galé, C., & Iranzo, J. A. (2022). Approaching the Pareto front in a biobjective bus route design problem dealing with routing cost and individuals’ walking distance by using a novel evolutionary algorithm. Mathematics, 10(9), 1390.
[17] Caldas, L., Martinelli, R., & Rosa, B. (2022, September). Solving a School Bus Routing Problem in Rural Areas: An Application in Brazil. In International Conference on Computational Logistics (pp. 162-176). Cham: Springer International Publishing.
[18] Sciortino, M., Lewis, R., & Thompson, J. (2022). A school bus routing heuristic algorithm allowing heterogeneous fleets and bus stop selection. SN Computer Science, 4(1), 74.
[19] Liu, Z., Gang, L., Yu, B., & Zhang, H. (2022). The routing problem for school buses considering accessibility and equity. Transportation Research Part D: Transport and Environment, 107, 103299.
[20] Botian, L., Xinglu, L., & Kin, C. W. (2022, August). Multi School Bus Routing Problem with Road Safety Factor via A Heuristic Algorithm. In 2022 34th Chinese Control and Decision Conference (CCDC) (pp. 5013-5018). IEEE.
[21] Rashidi Komijan, A., Ghasemi, P., Khalili-Damghani, K., & HashemiYazdi, F. (2021). A new school bus routing problem considering gender separation, special students and mix loading: a genetic algorithm approach. Journal of optimization in industrial engineering, 14(2), 23-39.
[22] Babaei, M., & Rajabi-Bahaabadi, M. (2019). School bus routing and scheduling with stochastic time-dependent travel times considering on-time arrival reliability. Computers & Industrial Engineering, 138, 106125.
[23] Ümit, Ü. G., & Kılıç, F. (2019, October). A school bus routing problem using genetic algorithm by reducing the number of buses. In 2019 Innovations in Intelligent Systems and Applications Conference (ASYU) (pp. 1-6). IEEE.
[24] Hashi, E. K., Hasan, M. R., & Zaman, M. S. U. (2016, December). GIS based heuristic solution of the vehicle routing problem to optimize the school bus routing and scheduling. In 2016 19th International Conference on Computer and Information Technology (ICCIT) (pp. 56-60). IEEE.
[25] Huo, L., Yan, G., Fan, B., Wang, H., & Gao, W. (2014, August). School bus routing problem based on ant colony optimization algorithm. In 2014 IEEE Conference and Expo Transportation Electrification Asia-Pacific (ITEC Asia-Pacific) (pp. 1-5). IEEE.
[26] Han, X., & Zhang, X. (2019, April). School Bus Route Optimization Based on Improved Ant Colony Algorithm. In 2019 4th International Conference on Electromechanical Control Technology and Transportation (ICECTT) (pp. 312-316). IEEE.
[27] Wang, J., & Huang, X. (2017, August). Routing school bus for better student learning. In 2017 25th International Conference on Geoinformatics (pp. 1-7). IEEE.
[28] Sarubbi, J. F., Mesquita, C. M., Wanner, E. F., Santos, V. F., & Silva, C. M. (2016, April). A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem. In NOMS 2016-2016 IEEE/IFIP network operations and management symposium (pp. 1175-1180). IEEE.
[29] Guo, X., Liu, Y., & Samaranayake, S. (2018, November). Solving the school bus routing problem at scale via a compressed shareability network. In 2018 21st International Conference on Intelligent Transportation Systems (ITSC) (pp. 1900-1907). IEEE.
[30] Silva, C. M., Sarubbi, J. F., Silva, D. F., Porto, M. F., & Nunes, N. T. (2015, September). A mixed load solution for the rural school bus routing problem. In 2015 IEEE 18th International Conference on Intelligent Transportation Systems (pp. 1940-1945). IEEE.
[31] Hou, Y. E., Dang, L., Dong, W., & Kong, Y. (2020). A metaheuristic algorithm for routing school buses with mixed load. IEEE Access, 8, 158293-158305.
[32] Ra'ed, M., & Nahar, K. M. (2017, December). SRT-GA: smart real-time system using a powerful genetic algorithm for school bus routing problem. In 2017 2nd International Conference on the Applications of Information Technology in Developing Renewable Energy Processes & Systems (IT-DREPS) (pp. 1-8). IEEE.
[33] Ozmen, M., & Sahin, H. (2021, January). Real-time optimization of school bus routing problem in smart cities using genetic algorithm. In 2021 6th International Conference on Inventive Computation Technologies (ICICT) (pp. 1152-1158). IEEE.