A New School Bus Routing Problem Considering Gender Separation, Special Students and Mix Loading: A Genetic Algorithm Approach
الموضوعات :Alireza Rashidi Komijan 1 , Peiman Ghasemi 2 , Kaveh Khalili-Damghani 3 , Fakhrosadat HashemiYazdi 4
1 - Department of Industrial Engineering
Firoozkooh Branch
Islamic Azad University
Firoozkooh, Iran
2 - Department of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran
3 - Department of Industrial Engineering, South-Tehran Branch, Islamic Azad University, Tehran, Iran
4 - Department of Industrial Management,Faculty of Management and Accounting,
Allame Tabatabai University, Tehran, Iran
الکلمات المفتاحية: Genetic Algorithm, School bus routing problem, mixed integer mathematical programming, Gender separation, Mix loading,
ملخص المقالة :
In developing countries, whereas the urban bus network is a major part of public transportation system, it is necessary to try to find the best design and routing for bus network. Optimum design of school bus routes is very important. Non-optimal solutions for this problem may increase traveling time, fuel consumption, and depreciation rate of the fleet. A new bus routing problem is presented in this study. A multi-objective mixed integer model is proposed to handle the associated problem. Minimization of transportation cost as well as traveling time is the main objectives. The main contributions of this paper are considering gender separation as well as mixed-loading properties in the school bus routing problem. Moreover, special and handicapped students are considered in this problem. The proposed model is applied in a real case study including 4 schools in Tehran. The results indicate the efficiency of the proposed model in comparison with the existing system. This comparison shows that the students’ travelling time is reduced by 28% for Peyvand middle smart school, 24% for Tehran international school, 13% for Hemmat School and 21% for Nikan High school. A customized Genetic Algorithm (GA) is proposed to solve the model. Penalty functions are used to handle the several constraints of the problem in Genetic Algorithm. The results justify the applicability and efficacy of the both proposed model and solution approach.
Abed Mohammed, M., Abd Ghani, M., Hamed, R., Mostafa, S., Ahmad, M., & Ibrahim, D. (2017). Solving Vehicle Routing Problem by Using Improved Genetic Algorithm for Optimal Solution, Journal of Computational Science, 21, 255-262
Azadeh, A., & Farrokhi-Asl, H. (2017). The close–open mixed multi depot vehicle routing problem considering internal and external fleet of vehicles, Transportation Letters, 1-15
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.
Bodin, L.D. & Berman, L. (1979). Routing and scheduling of school buses by computer. Transportation Science, 13, 113–129.
Byung-In, K., Seongbae, K. & Junhyuk, P. (2012). A school bus scheduling problem. European Journal of Operational Research, 218, 577–585.
Caceres, H., Batta, R., & He, Q. (2019). Special need students school bus routing: Consideration for mixed load and heterogeneous fleet. Socio-Economic Planning Sciences, 65, 10-19.
Chen,X., Kong,Y., Dang,L., Hou, Y. & Xinyue, Y. (2015). Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem. PLoS ONE, 11(4). doi: 10.1371/journal.pone.0132600
Daganzo, C.F., Gayah, V.V. & Gonzales, E.J. (2012). The potential of parsimonious models for understanding large scale transportation systems and answering big picture questions, EURO J. Transport. Logist, 1, 47–65.
Desrosiers, J., Ferland, J.A., Rousseau, J. M., Lapalme, G., & Chapleau. L. (1981). An overview of a school busing system. In: Jaiswal, N.K. (Ed.), Scientific Management of Transport Systems. North-Holland, Amsterdam, 235–243.
Figliozzi, M.A. (2007). Analysis of the efficiency of urban commercial vehicle tours: data collection, methodology and policy implications, Transport. Res. Part B, 41, 1014–1032.
Fleszar, K. Osman, I.H. and Hindi, K.S. (2009). A variable neighborhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, 195, 803–809.
Fügenschuh, A. (2009). Solving a school bus scheduling problem with integer programming. European Journal of Operational Research, 193, 867–884.
Galvao, L.C., Novaes, A.G., de Cursi, J.E. & Souza, J.C. (2006). A multiplicatively-weighted Voronoi diagram approach to logistics districting. Comput. Oper. Res, 33, 93–114.
Ghasemi, P., & Babaeinesami, A. (2019). Estimation of relief supplies demands through fuzzy inference system in earthquake condition. Journal of Industrial and Systems Engineering, 12(3), 154-165.
Ghasemi, P., & Babaeinesami, A. (2020). Simulation of fire stations resources considering the downtime of machines: A case study. Journal of Industrial Engineering and Management Studies, 7(1), 161-176.
Ghasemi, P., & Khalili-Damghani, K. (2020). A robust simulation-optimization approach for pre-disaster multi-period location-allocation-inventory planning. Mathematics and Computers in Simulation.
Ghasemi, P., Khalili-Damghani, K., Hafezalkotob, A., & Raissi, S. (2020). Stochastic optimization model for distribution and evacuation planning (A case study of Tehran earthquake). Socio-Economic Planning Sciences, 71, 100745.
Ghasemi, P., Khalili-Damghani, K., Hafezalkotob, A., & Raissi, S. (2019). Uncertain multi-objective multi-commodity multi-period multi-vehicle location-allocation model for earthquake evacuation planning. Applied Mathematics and Computation, 350, 105-132.
Golpîra, H., & Tirkolaee, E. B. (2019). Stable maintenance tasks scheduling: A bi-objective robust optimization model. Computers & Industrial Engineering, 137, 106007.
Goodarzian, F., & Hosseini-Nasab, H. (2019). Applying a fuzzy multi-objective model for a production–distribution network design problem by using a novel self-adoptive evolutionary algorithm. International Journal of Systems Science: Operations & Logistics, 1-22.
Goodarzian, F., Hosseini-Nasab, H., Muñuzuri, J., & Fakhrzad, M. B. (2020). A multi-objective pharmaceutical supply chain network based on a robust fuzzy model: A comparison of meta-heuristics. Applied Soft Computing, 106331.
Huang, M., Smilowitz, K., & Balcik, B. (2013). A continuous approximation approach for assessment routing in disaster relief, Transport. Res. Part B, 50, 20–41.
Ji, B., Yuan, X., & Yuan, Y. (2017). Modified NSGA-II for solving continuous berth allocation problem: Using multiobjective constraint-handling strategy. IEEE transactions on cybernetics, 47(9), 2885-2895.
Jonathan, D., & Pitu, B. (2016). The Vehicle Scheduling Problem for Fleets with Alternative-Fuel Vehicles. Transportation Science, 1-16
Junhyuk, P., Hyunchul, T. & Byung-In, K. (2012). A post-improvement procedure for the mixed load school bus routing problem. European Journal of Operational Research, 217, 204–213.
Kang, M., Kim, S., Felan, T., Rim Choi, H. & Cho, M. (2015). Development of a Genetic Algorithm for the School Bus Routing Problem, International Journal of Software Engineering and Its Applications, 9(5), 107-126.
Khalili-Damghani, K., & Ghasemi, P. (2016). Uncertain Centralized/Decentralized Production-Distribution Planning Problem in Multi-Product Supply Chains: Fuzzy Mathematical Optimization Approaches. Industrial Engineering & Management Systems, 15(2), 156-172.
Kim, T.Y., & Park, B. J. (2013). Model and Algorithm for Solving School Bus Problem. Journal of Emerging Trends in Computing and Information Sciences, 4(8), 596-600.
Kontou, E., Kepaptsoglou. K., Charalampakis, E. & Karlaftis, G. (2014). The bus to depot allocation problem revisited: a genetic algorithm. Public Transp, 6, 237-255.
Larki, H., & Yousefikhoshbakht, M. (2014). Solving the multiple traveling salesman problem by a novel meta-heuristic algorithm. Journal of Optimization in Industrial Engineering, 7(16), 55-63.
Leksakul, K., Smutkupt, U., Jintawiwat, R., Phongmoo, S. (2017). Heuristic approach for solving employee bus routes in a large-scale industrial factor, Advanced Engineering Informatics 32, 176–187
Marinakis,Y., Iordanidou, G., & Marinaki, M. (2013). Particle Swarm Optimization for the Vehicle Routing Problem with Stochastic Demands. Applied Soft Computing, 13, 1693–1704.
Niasar, M. S. F., Talarico, L., Sajadifar, M., & Tayebi, A. H. (2017). Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection. International Journal of Supply and Operations Management, 4(1), 1-14.
Ouyang, Y., Nourbakhsh, S.M., & Cassidy, M.J. (2014). Continuum approximation approach to bus network design under spatially heterogeneous demand. Transport. Res. Part B, 68, 333–344.
Pacheco, J., Caballero, R., Laguna, M., & Molina, J., (2012), Bi-Objective Bus Routing: An Application to School Buses in Rural Areas, Transportation Science, 1–15
Park, J., & Kim, B. (2010). The school bus routing problem: A review. European Journal of Operational Research, 202 (2), 311–319.
Ren, J., Jin, W., & Wu, W. (2019). A Two-Stage Algorithm for School Bus Stop Location and Routing Problem With Walking Accessibility and Mixed Load. IEEE Access, 7, 119519-119540.
Riera-Ledesman, J. & Jose Salazar-Gonzalez J. (2013). A column generation approach for a school bus routing problem with resource constraints. Computers & Operations Research, 40, 566–583.
Sahebjamnia, N., Goodarzian, F., & Hajiaghaei-Keshteli, M. (2020). Optimization of Multi-period Three-echelon Citrus Supply Chain Problem. Journal of Optimization in Industrial Engineering, 13(1), 39-53.
Sangaiah, A. K., Goli, A., Tirkolaee, E. B., Ranjbar-Bourani, M., Pandey, H. M., & Zhang, W. (2020). Big Data-Driven Cognitive Computing System for Optimization of Social Media Analytics. IEEE Access, 8, 82215-82226.
Schittekat, P., Kinable, J., Sörensen, K., Sevaux, M., Spieksma, F., & Springael, J. (2013). A metaheuristic for the school bus routing problem with bus stop selection. European Journal of Operational Research, 229, 518–528.
Shirazi, H., Kia, R., & Ghasemi, P. (2020). Ranking of hospitals in the case of COVID-19 outbreak: A new integrated approach using patient satisfaction criteria. International Journal of Healthcare Management, 1-13.
Shui, X., Zuo, X., Chen, C. & Smith, E. (2015). A clonal selection algorithm for urban bus vehicle scheduling. Applied Soft Computing, 36, 36–44.
Spada, M., Bierlaire, M., & Liebling, Th.M. (2005). Decision-aiding methodology for the school bus routing and scheduling problem. Transportation Science, 39, 477– 490.
Tirkolaee, E. B., Goli, A., & Weber, G. W. (2020a). Fuzzy Mathematical Programming and Self-Adaptive Artificial Fish Swarm Algorithm for Just-in-Time Energy-Aware Flow Shop Scheduling Problem with Outsourcing Option. IEEE Transactions on Fuzzy Systems.
Tirkolaee, E. B., Mardani, A., Dashtian, Z., Soltani, M., & Weber, G. W. (2020b). A novel hybrid method using fuzzy decision making and multi-objective programming for sustainable-reliable supplier selection in two-echelon supply chain design. Journal of Cleaner Production, 250, 119517.
Tirkolaee, E. B., Mahdavi, I., Esfahani, M. M. S., & Weber, G. W. (2020c). A robust green location-allocation-inventory problem to design an urban waste management system under uncertainty. Waste Management, 102, 340-350.
Turkensteen, M. & Klose, A. (2012). Demand dispersion and logistics costs in one-to-many distribution systems. Eur. J. Oper. Res, 223, 499-507.
Wang, Z., & Haghani, A. (2020). Column Generation-based Stochastic School Bell Time and Bus Scheduling Optimization. European Journal of Operational Research.
William, A., Campbell, F., & North, J. (2015). Continuous approximation models for mixed load school bus routing. Transportation Research Part B, 77, 182–198.
Yao, B., Cao,Q., Wang , Z., Hu, P, Zhang, M. & Yu, B. (2016). A two-stage heuristic algorithm for the school bus routing problem with mixed load plan. Transportation Letters, 8(4), 205-219
Yousefikhoshbakht, M., Didehvar, F., & Rahmati, F. (2015). A mixed integer programming formulation for the heterogeneous fixed fleet open vehicle routing problem. Journal of optimization in Industrial Engineering, 8(18), 37-46.
