The Review of Recent Trend for School Bus Routing Problem Manuscript Received: 14 August 2023, Accepted: 18 November 2023, Published: 15 March 2024, ORCiD: 0009-0002-3739-6208, https://doi.org/10.33093/jetap.2024.6.1.9

Article Sidebar

Fulltext
Published: Mar 15, 2024
DOI: https://doi.org/10.33093/jetap.2024.6.1.9
Keywords:
School Bus Routing Problem (SBRP), Exact and heuristic algorithm, GAMS software

Main Article Content

Nur Intan Liyana binti Mohd Azmi
Faculty of Science, Universiti Tunku Abdul Rahman, Kampar, Perak, Malaysia.
Afwan Hakim Md Mahdzir
Faculty of Science, Universiti Tunku Abdul Rahman, Kampar, Perak, Malaysia.
Heng Yu Xuan
Faculty of Science, Universiti Tunku Abdul Rahman, Kampar, Perak, Malaysia.
Ng Xian Yu
Faculty of Science, Universiti Tunku Abdul Rahman, Kampar, Perak, Malaysia.
Tan Mei Tiean
Faculty of Science, Universiti Tunku Abdul Rahman, Kampar, Perak, Malaysia.
Tian Yu Kun
Faculty of Science, Universiti Tunku Abdul Rahman, Kampar, Perak, Malaysia.

Abstract

The School Bus Routing Problem (SBRP) is a complex transportation challenge involving finding optimal bus routes. This review paper provides an overview of the recent developments in SBRP research and focuses on three sub-problems: Bus Route Generation, Bus Route Scheduling, and Bus Stop Selection. The paper examines recent publications from 57 relevant articles. It highlights the increasing focus on real-world and complex scenarios, as well as the growing popularity of metaheuristic approaches in addressing SBRP challenges. The analysis reveals the significance of bus route generation, bus route scheduling, and bus stop selection, showcasing the effectiveness of machine learning and heuristic or metaheuristic algorithms in improving route quality. This study also classifies SBRP problems based on the number of schools, service surroundings (urban or rural), mixed-load scenarios, and fleet mix (homogeneous or heterogeneous). Finally, the paper explores the objectives of SBRP research, including minimising the total cost, distance, time, and number of buses. Meanwhile, the constraints of this study are the capacity of a bus, the maximum riding time, time windows, the maximum walking time between two stops and so on. This comprehensive review paper aims to offer a framework for new researchers and provides valuable insights for future research directions in this transportation area.

Article Details

Issue
Vol. 6 No. 1 (2024): https://doi.org/10.33093/jetap.2024.6.1
Section
Articles
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

References

R. M. Newton and W. H. Thomas, “Design of School Bus Routes by Computer,” Socio-Economic Planning Sci., vol. 3, no. 1, pp. 75–85, 1969.

S. A. Oluwadare, I. P. Oguntuyi and J. C. Nwaiwu, “Solving School Bus Routing Problem using Genetic Algorithm-based Model,” Int. J. Intellig. Sys. and Appl., vol. 10, no. 3, pp. 50–58, 2018.

A. S. Jaradat and M. Q. Shatnawi, “Solving School Bus Routing Problem by Intelligent Water Drops Algorithm,” J. Comput. Sci., vol. 16, no. 1, pp. 25–34, 2020.

R. M. Noor, N. B. G. Rasyidi, T. Nandy and R. Kolandaisamy, “Campus Shuttle Bus Route Optimization Using Machine Learning Predictive Analysis: A Case Study,” Sustainability, vol. 13, no. 1, pp. 225, 2020.

W. A. Ellegood, S. Solomon, J. North and J. F. Campbell, “School Bus Routing Problem: Contemporary Trends and Research Directions,” Omega, vol. 95, pp. 102056, 2020.

J. Tang, Y. Yang and Y. Qi, “A Hybrid Algorithm for Urban Transit Schedule Optimization,” Physica A: Statistic. Mechanic. and its Appl., vol. 512, pp. 745–755, 2018.

A. Shafahi, Z. Wang and A. Haghani, “SpeedRoute: Fast, Efficient Solutions for School Bus Routing Problems,” Transport. Res. Part B: Methodological, vol. 117, pp. 473–493, 2018.

A. M. Armond, Y. D. Prasetyo and W. Ediningrum, “Application of Ant Colony Optimization (ACO) Algorithm to Optimize Trans Banyumas Bus Routes,” in 2022 IEEE Int. Conf. Cybernetics and Comput. Intellig., Malang, Indonesia, pp. 132–137, 2022.

X. Han and X. Zhang, “School Bus Route Optimization Based on Improved Ant Colony Algorithm,” in 2019 4th Int. Conf. Electromechanic. Contr. Technol. and Transport., Guilin, China, pp. 312–316, 2019.

R. Guo, W. Guan, W. Zhang, F. Meng and Z. Zhang, “Customized Bus Routing Problem with Time Window Restrictions: Model and Case Study,” Transportmetrica A: Transport Sci., vol. 15, no. 2, pp. 1804–1824, 2019.

M. Ozmen and H. Sahin, “Real-Time Optimization of School Bus Routing Problem in Smart Cities Using Genetic Algorithm,” in 2021 6th Int. Conf. Inventive Comput. Technol., Coimbatore, India, pp. 1152–1158, 2021.

E. Köksal Ahmed, Z. Li, B. Veeravalli and S. Ren, “Reinforcement Learning-Enabled Genetic Algorithm for School Bus Scheduling,” J. Intellig. Transport. Sys., vol. 26, no. 3, pp. 269–283, 2022.

D. Banerjee and K. Smilowitz, “Incorporating Equity into the School Bus Scheduling Problem,” Transport. Res. Part E: Logistics and Transport. Rev., vol. 131, no. 3, pp. 228-246, 2019.

M. Babaei and M. Rajabi-Bahaabadi, “School Bus Routing and Scheduling with Stochastic Time-Dependent Travel Times Considering On-Time Arrival Reliability,” Comput. & Indust, Eng., vol. 138, pp. 106125, 2019.

M. Sciortino, R. Lewis and J. Thompson, “A School Bus Routing Heuristic Algorithm Allowing Heterogeneous Fleets and Bus Stop Selection,” SN Comput. Sci., vol. 4, no. 1, pp. 74, 2022.

D. Bertsimas, A. Delarue and S. Martin, “Optimizing Schools’ Start Time and Bus Routes,” Proc. Nat. Acad. Sci., vol. 116, no. 13, pp. 5943–5948, 2019.

A. Ochoa-Zezzatti, U. Carbajal, O. Castillo, J. Mejía, G. Rivera and S. Gonzalez, “Development of A Java Library to Solve the School Bus Routing Problem,” Smart Technol. Smart Cities, pp. 175–196, 2020.

M. R. Sayyari, R. Tavakkoli-Moghaddam, A. Abraham and N. Oladzad-Abbasabady, “A School Bus Routing and Scheduling Problem with Time Windows and Possibility of Outsourcing with the Provided Service Quality,” Intellig. Sys. Design and Appl., vol. 1351, pp. 829–839, 2021.

J. Ren, W. Jin and W. Wu, “A Two-Stage Algorithm for School Bus Stop Location and Routing Problem with Walking Accessibility and Mixed Load,” IEEE Access, vol. 7, pp. 119519–119540, 2019.

M. Li and J. Y. J. Chow, “School Bus Routing Problem with A Mixed Ride, Mixed Load, and Heterogeneous Fleet,” Transport. Res. Rec., vol. 2675, no. 7, pp. 467–479, 2021.

P. Shang, L. Yang, Z. Zeng and L. (Carol) Tong, “Solving School Bus Routing Problem with Mixed-Load Allowance for Multiple Schools,” Comput. & Indust. Eng., vol. 151, pp. 106916, 2021.

A. Ansari, L. Farrokhvar and B. Kamali, “Integrated Student to School Assignment and School Bus Routing Problem for Special Needs Students,” Transport. Res. Part E: Logistics and Transport. Rev., vol. 152, pp. 102416, 2021.

D. M. Miranda, R. S. de Camargo, S. V. Conceição, M. F. Porto and N. T. R. Nunes, “A Metaheuristic for The Rural School Bus Routing Problem with Bell Adjustment,” Expert Sys. with Appl., vol. 180, pp. 115086, 2021.

N. Mokhtari and V. Ghezavati, “Integration of Efficient Multi-Objective Ant-Colony and A Heuristic Method to Solve A Novel Multi-Objective Mixed Load School Bus Routing Model,” Appl. Soft Comput., vol. 68, pp. 92–109, 2018.

A. Rashidi Komijan, P. Ghasemi, K. Khalili-Damghani and F. HashemiYazdi, “A New School Bus Routing Problem Considering Gender Separation, Special Students and Mix Loading: A Genetic Algorithm Approach,” J. Optimiz. Indust. Eng., vol. 14, no. 2, pp. 23–39, 2021.

D. M. Miranda, R. S. de Camargo, S. V. Conceição, M. F. Porto and N. T. R. Nunes, “A Multi-Loading School Bus Routing Problem,” Expert Sys. with Appl., vol. 101, pp. 228–242, 2018.

A. Shafahi, Z. Wang and A. Haghani, “A Matching-based Heuristic Algorithm for School Bus Routing Problems,” ArXiv, vol. abs/1807.05311, 2018.

X. Guo and S. Samaranayake, “Shareability Network Based Decomposition Approach for Solving Large-Scale Single School Routing Problems,” Transport. Res. Part C: Emerging Technol., vol. 140, pp. 103691, 2022.

L. Dang. Y. Hou and Q. Liu, “A Hybrid Metaheuristic Algorithm for the Bi-objective School Bus Routing Problem,” [Available Online: 12 Aug 2019] https://www.semanticscholar.org/paper/A-Hybrid-Metaheuristic-Algorithm-for-the-School-Bus-Dang-Hou/7b8e12db4d601fb8c8169967b0078bafb7df5b2b.

S. Thangiah, “Vehicle Routing with Time Windows using Genetic Algorithms,” The Practical Handbook of Genetic Algorithms, L. Chambers, Ed., CRC Press, 1995.

F. Wu and Y. Zhu, “Transportation Route Optimization Based on Heuristic Algorithm,” J. Phys.: Conf. Ser., vol. 2083, no. 3, pp. 032016, 2021.

L. Zeng, S. Chopra and K. Smilowitz, “A Bounded Formulation for The School Bus Scheduling Problem,” Transport. Sci., vol. 56, no. 5, pp. 1148–1164, 2022.

U. G. Umit and F. Kilic, "A School Bus Routing Problem Using Genetic Algorithm by Reducing the Number of Buses," in 2019 Innov. Intellig. Sys. and Appl. Conf., Izmir, Turkey, pp. 1-6, 2019.

H. I. Calvete, C. Galé, J. A. Iranzo and P. Toth, “A Partial Allocation Local Search Matheuristic for Solving the School Bus Routing Problem with Bus Stop Selection,” Mathematics, vol. 8, no. 8, pp. 1214, 2020.

H. I. Calvete, C. Galé and J. A. Iranzo, “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, vol. 10, no. 9, pp. 1390, 2022.

D. Chattopadhyay, “Application of General Algebraic Modeling System to Power System Optimization,” IEEE Trans. Power Sys., vol. 14, no. 1, pp. 15–22, 1999.

D. Bisen and H. M. Dubey, “Dynamic Economic Load Dispatch with Emission and Loss using GAMS,” Int. J. Eng. Res. and Technol., vol. 1, IJERTV1IS3127, 2012.

E. Salari and A. Askarzadeh, “A New Solution for Loading Optimization of Multi-Chiller Systems by General Algebraic Modeling System,” Appl. Thermal Eng., vol. 84, pp. 429–436, 2015.

M. R. Bussieck and A. Meeraus, “General Algebraic Modeling System (GAMS),” in Modeling Languages in Mathematical Optimization, J. Kallrath, Ed., Boston, Springer US, pp. 137–157, 2004.

M. Fischetti, J. J. Salazar González and P. Toth, “A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem,” Operation. Res., vol. 45, no. 3, pp. 378–394, 1997.

J. Lysgaard, A. N. Letchford and R. W. Eglese, “A New Branch-And-Cut Algorithm for The Capacitated Vehicle Routing Problem,” Mathematic. Program., vol. 100, no. 2, pp. 423–445, 2004.

P. Schittekat, M. Sevaux and K. Sorensen, “A Mathematical Formulation for A School Bus Routing Problem,” in 2006 Int. Conf. Serv. Sys. and Serv. Manage., Troyes, France, pp. 1552–1557, 2006.

T. Bektas and S. Elmastas, “Solving School Bus Routing Problems Through Integer Programming,” J. Operation. Res. Soc., vol. 58, no. 12, pp. 1599–1604, 2007.

A. Fügenschuh, “Solving A School Bus Scheduling Problem with Integer Programming,” European J. Operation. Res., vol. 193, no. 3, pp. 867–884, 2009.

B. Zhang, Z. Zhong, X. Zhou, Y. Qu and F. Li, “Optimization Model and Solution Algorithm for Rural Customized Bus Route Operation under Multiple Constraints,” Sustainability, vol. 15, no. 5, pp. 3883, 2023.

J. Sun, Y. Chen, J. Huang, P. Wei and C. Song, “Flexible Bus Route Optimization Scheduling Model,” Advances in Civil Engineering, vol. 2021, pp. 1–13, 2021.

F. Glover, “Tabu Search—Part I,” ORSA J. Comput., vol. 1, no. 3, pp. 190–206, 1989.

J. Homberger and H. Gehring, “A Two-Phase Hybrid Metaheuristic for the Vehicle Routing Problem with Time Windows,” European J. Operation. Res., vol. 162, no. 1, pp. 220–238, 2005.