Samuel A. Oluwadare; Iyanu P. Oguntuyi; John C. Nwaiwu

Solving School Bus Routing Problem using Genetic Algorithm-based Model

Full Text (PDF, 391KB), PP.50-58

Views: 0 Downloads: 0

Author(s)

Samuel A. Oluwadare ^1,* Iyanu P. Oguntuyi ² John C. Nwaiwu ³

1. Federal University of Technology Akure/Computer Science Department, Akure, +234, Nigeria

2. Rufus Giwa Polytechnic, Owo/ Computer Science Department, Owo, +234, Nigeria

3. Federal University of Technology Akure / Computer Science Department, Akure, +234, Nigeria

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2018.03.06

Received: 30 May 2017 / Revised: 1 Aug. 2017 / Accepted: 15 Sep. 2017 / Published: 8 Mar. 2018

Index Terms

Genetic algorithm, School bus routing problem, Optimization, School bus routes, Time complexity, High performance computing

Abstract

School Bus Routing Problem is an optimization problem which falls under the class of the Vehicle Routing Problem. It involves the use of a fleet of vehicles to efficiently and optimally transport students to and from their schools. To solve this problem, optimal school bus routes are found by minimizing the number of buses, the number of routes and the total distance traversed along all routes. Manual routing of school buses have led to creation of many routes, increased number of buses and several buses navigating the same route, thereby incurring more cost. One of such methods used in solving school bus routing problems is meta-heuristic method which has proven better results in terms of optimal solution and reduced time complexity. In this study, Genetic algorithm is utilized to solve the school bus routing problem because of its simplicity and ability to generate many possible solutions. The algorithm is implemented in C# programming language and tested using secondary data obtained from Ondo State Free-School Bus Shuttle Scheme, Akure, Nigeria. The result shows that of all four nodes (bus stops) used in performance evaluation, Alakure to Oke-Aro junction bus stop presents as the best route which covers a total of 69 nodes with a total distance of 34.5km. This shows that there can be less number of buses in use and reduced number of routes in which the buses are assigned.

Cite This Paper

Samuel A. Oluwadare, Iyanu P. Oguntuyi, John C. Nwaiwu, "Solving School Bus Routing Problem using Genetic Algorithm-based Model", International Journal of Intelligent Systems and Applications(IJISA), Vol.10, No.3, pp.50-58, 2018. DOI:10.5815/ijisa.2018.03.06

Reference

[1]K. A. Eldrandaly, and A. F. Abdallah, “A novel GIS-based decision-making framework for the school bus routing problem,” Geo-spatial Information Science, Vol. 15, No. 1, pp. 51–59, 2012, http://dx.doi.org/10.1080/10095020.2012.708151.

[2]S. R. Thangiah, and K. E. Nygard, “School bus routing using genetic algorithms,” Proceedings of SPIE, Applications of Artificial Intelligence X: Knowledge-Based Systems, Vol. 1707, pp. 387-398, 1992.

[3]T. Kim, and B-J. Park, “Model and Algorithm for Solving School Bus Problem,” Journal of Emerging Trends in Computing and Information Sciences, Vol. 4, No. 8, pp. 596 - 600, 2013, ISSN 2079-8407.

[4]D. Ripplinger, “Rural school vehicle routing problem”, Transportation Research Record, vol. 1922, pp. 105-110, 2005.

[5]S. R. Thangiah, A. Fergany, B. Wilson, A. Pitluga and W. Mennell, “School Bus Routing in Rural School Districts,” Lecture Notes in Economics and Mathematical Systems, Vol. 600, No. 2, pp. 209-232, 2008.

[6]J. Park and B. Kim, “The school bus routing problem: A review”, European Journal of Operational Research, Vol. 202, pp. 311-319, 2010.

[7]T. Bektaş, and S. Elmastaş “Solving school bus routing problems through integer programming,” Journal of the Operational Research Society. Vol. 58, No. 12, pp. 1599–1604, 2007.

[8]J. Riera-Ledesma, and J-J. Salazar-González, “Solving school bus routing using the multiple vehicle travelling purchaser problem: A branch-and-cut approach,” Computers & Operations Research. Vol. 39, No. 2, pp. 391–404, 2012.

[9]J. Riera-Ledesma and J-J. Salazar-González, “A column generation approach for a school bus routing problem with resource constraints,” Computers & Operations Research, Vol. 40, No. 2, pp. 566–83, 2013.

[10]P. Schittekat, M. Sevaux, and K. Sorensen, (editors) “A mathematical formulation for a school bus routing problem,” International Conference on Service Systems and Service Management, pp. 1552–7, Oct. 2006.

[11]L. Huo, G. Yan, B. Fan, H. Wang, and W. Gao, (editors) “School bus routing problem based on ant colony optimization algorithm,” Transportation Electrification Asia-Pacific (ITEC Asia-Pacific), 2014 IEEE Conference and Expo; Beijing IEEE. pp. 1–5, Aug. 31 2014-Sept. 3 2014.

[12]J. S. Arias-Rojas, J. F. Jiménez, and J. R. Montoya-Torres, “Solving of school bus routing problem by ant colony optimization,” Revista EIA. Vol. 9, No. 17, pp. 193–208, 2012.

[13]L. Spasovic, S. Chien, C. Kelnhofer-Feeley, Y. Wang, and Q. Hu, (editors) “A methodology for evaluating of school bus routing-a case study of riverdale,” New Jersey. transportation research board 80th annual meeting, Washington, DC, pp. 7–11, 2001.

[14]J. Pacheco, R. Caballero, M. Laguna, and J. Molina, “Bi-objective bus routing: an application to school buses in rural areas,” Transportation Science, Vol. 47, No. 3, pp. 397–411, 2013.

[15]R. P. Aparicio, S. J. Muñuzuri, M. J. Guadix, “Mixed Trips in the School Bus Routing Problem with Public Subsidy,” In: P. Cortés, E. Maeso-González, A. Escudero-Santana, editors. Enhancing Synergies in a Collaborative Environment. Lecture Notes in Management and Industrial Engineering: Springer International Publishing; pp. 105–113, 2015.

[16]M. Zhang, “The Research on Multi-objective School Bus Vehicle Routing Problems Based On Bi-level Programming. Chengdu, China: Southwest Jiaotong University; 2008.

[17]B. S. Sghaier, B. N. Guedria, and R. Mraihi, (editors) “Solving School Bus Routing Problem with genetic algorithm,” Advanced Logistics and Transport (ICALT), International Conference on; IEEE. pp. 7–12, 2013.

[18]B. Minocha, and S. Tripathi, (editors) “Solving School Bus Routing Problem Using Hybrid Genetic Algorithm: A Case Study,” Proceedings of the Second International Conference on Soft Computing for Problem Solving (SocProS 2012), December 28–30, 2012; Springer. pp. 93–103, 2014.

[19]F.Y.O. Li, and Z. Fu, “The School Bus Routing Problem: A Case Study,” Journal of the Operational Research Society, Vol. 53, pp. 552-558, 2002.

[20]O. Al-Jadaan, L. Rajamani, and R. Rao, “Improved selection operator for GA,” Journal of Theoretical and Applied Information Technology, 4(4), pp. 269-277, April 2008.

[21]Z. B. Ismail, “Development of heuristic methods based on genetic algorithm for solving vehicle routing problem,” Dept. of Mathematics, University Technology Malaysia, Skudai Johor, Malaysia, 2008.

[22]D. E. Goldberg, “Genetic algorithms in search, optimization and machine learning,” Addison-Wesley, USA, 1989.

[23]J. Berger, and M. Barkaoui, “A hybrid genetic algorithm for the capacitated vehicle routing problem,” Genetic and Evolutionary Computation (GECCO, 2003), Lecture Notes in Computer Science, Vol. 2723, pp. 646-656, 2003.

[24]O. Díaz-Parra, J. A. Ruiz-Vanoye, Á. Buenabad-Arias, F. Cocón, “A Vertical Transfer Algorithm for School Bus Routing Problem,” Conference: Fourth World Congress on Nature and Biologically Inspired Computing (NaBIC2012), pp. 66-71, November 2012, ISSN: 978-1-4673-4768-6, 2012 IEEE DOI: 10.1109/NaBIC.2012.6402241 ·

[25]A. J. Awuah, S. K. Amponsah, J. Annan, and C. Sebil, “School Bus Routing: A case study of Wood Bridge school complex,” Sekondi-Takorandi, Ghana. International Journal of Business and Social Research, Vol. 3, No. 12, pp. 26-36, 2013.

[26]K. M. Abdul, and F. Faruque, “Solving the vehicle routing problem using genetic algorithm,” International Journal of Advanced Computer Science and Applications, Vol. 2, No, 7, pp. pp. 126-131, 2011.

[27]M. Kang, S-K. Kim, J. T. Felan, H. R. Choi, and M. Cho, “Development of a Genetic Algorithm for the School Bus Routing Problem,” International Journal of Software Engineering and Its Applications, Vol. 9, No. 5, pp. 107-126, 2015.

[28]X. Chen, Y. Kong, L. Dang, Y. Hou, X. Ye, “Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem,” PLoS ONE, Vol. 10, No. 7, DOI:10.1371/journal. pone.0132600, 2015.

[29]P-R. Ricardo, and H-A. Arturo, “Probability model to Solve the School Bus Routing Problem with Stops Selection,” International Journal of Combinatorial Optimization Problems and Informatics, Vol. 7, No. 1, pp. 30-39. ISSN: 2007-1558, 2016.

[30]H. A. Salami, and E. Y. Mamman, “A Genetic algorithm for Allocating Project Supervisors to Students,” International Journal of Intelligent Systems and Applications, vol. 10, pp. 51-59, DOI: 10.5815/ijisa.2016.10.06, October 2016.

[31]M. Mavrovouniotis, and S. Yang, “Ant colony optimization with immigrants schemes for dynamic vehicle routing problem,” EvoApplications, Vol. 11, pp. 519-528, April 2012.

[32]A. Gupta, and P. R. Sharma, “Application of GA for Optimal Allocation of FACT devices for Steady State Voltage Stability Enhancement of Power System,” International Journal of Intelligent Systems and Applications, Vol. 6, No. 3, pp. 51-59, DOI: 10.5815/ijisa.2014.03.07, February 2014

[33]I. H. Khan, “Assessing Different Crossover Operators for Travelling Salesman Problem,” International Journal of Intelligent Systems and Applications, Vol. 7, No. 11, pp. 19, October 2015

International Journal of Intelligent Systems and Applications (IJISA)