Two-stage clustering and routing problem by using FCM and K-means with genetic algorithm

Year 2024, Volume: 42 Issue: 4, 1030 - 1038, 01.08.2024

Ebru Pekel Özmen , Tarık Küçükdeniz

Abstract

The School Bus Routing Problem (SBRP) is a challenging optimization problem that has received increasing attention in recent years. The problem is composed of three sub-problems: facility location selection, assignment problem, and vehicle routing problem, which can be solved in a single stage or across multiple stages. In this study, we propose a novel two-stage approach to solve the SBRP that combines Fuzzy C Means (FCM) and K-means clustering algorithms with a Genetic Algorithm (GA). In the first stage, we used FCM and K-means to identify the optimal bus stop locations and assigned students to the nearest stop based on the distance metric. This two-stage approach reduces the search space and improves the efficiency of the GA in the second stage. In the second stage, we employed the GA to generate the optimal vehicle route that minimizes the total distance traveled by all vehicles. We compared our results with those in the literature and found that the K Means-GA approach outperformed the previous results. However, the FCM-GA approach yielded significantly inferior results, indicating that the choice of clustering algorithm plays a crucial role in the performance of the overall system. Our study provides insights into the importance of selecting appropriate clustering algorithms for solving the SBRP and proposes a two-stage solution that can be easily implemented in real-world scenarios. Our approach reduces the computational time and provides an effective solution for reducing the total distance traveled by school buses.

Keywords

Fuzzy Clustering, Genetic Algorithms, K-means, LAR SBRP

References

• [1] Miranda DM, de Camargo RS, Conceição SV, Porto MF, Nunes NTR. A multi-loading school bus routing problem. Exp Syst Appl 2018;101:228242. [CrossRef]
• [2] Oluwadare SA, Oguntuyi IP, Nwaiwu JC. Solving school bus routing problem using genetic algorithm-based model. Int J Intell Syst Appl 2018;12:50. [CrossRef]
• [3] Sun S, Duan Z, Xu Q. School bus routing problem in the stochastic and time-dependent transportation network. PloS One 2018;13:e0202618. [CrossRef]
• [4] Mahmoudzadeh A, Wang XB. Cluster Based Methodology for Scheduling a University Shuttle System. Trans Res Record 2020;2674:236248. [CrossRef]
• [5] Kiriş SB, Özcan T. Metaheuristics approaches to solve the employee bus routing problem with clustering-based bus stop selection, in Artificial Intelligence and Machine Learning Applications in Civil, Mechanical, and Industrial Engineering, 2020, p. 217239, IGI Global. [CrossRef]
• [6] Xie Y, Kong Y, Xiang H, Hou Y, Han D. A metaheuristic with learning mechanism for solving the multi-school heterogeneous school bus routing problem. IAENG Int J Comput Sci 2021;48:19.
• [7] Pérez ACP, Ansola ES, Suárez AR. A metaheuristic solution for the school bus routing problem with homogeneous fleet and bus stop selection. Ingeniería 2021;2:233253. [CrossRef]
• [8] Miranda DM, de Camargo RS, Conceição SV, Porto MF, Nunes NTR. A metaheuristic for the rural school bus routing problem with bell adjustment. Exp Syst Appl 2021;180:115086. [CrossRef]
• [9] Calvete HI, Gale C, Iranzo JA, Toth P. The school bus routing problem with student choice: a bilevel approach and a simple and effective metaheuristic. Int Trans Oper Res 2021;30:10921119. [CrossRef]
• [10] Pérez AC, Sánchez-Ansola E, Rosete A, Rojas O, Sosa-Gómez G. A partial evaluation approach for the school bus routing problem. Heliyon, 2022;8:e09291. [CrossRef]
• [11] Hou Y, Liu B, Dang L He W, Gu W. A local search-based metaheuristic algorithm framework for the school bus routing problem. Eng Lett 2022;30:112.
• [12] Feng R, Zhang J, Wu Y, Wu R, Yao B. School accessibility evaluation under mixed-load school bus routing problem strategies. Trans Policy, 2023;131:7586. [CrossRef]
• [13] Calvete HI, Carmen G, Iranzo JA, Toth P. The school bus routing problem with student choice: a bilevel approach and a simple and effective metaheuristic. Int Trans Oper Res 2023;30:10921119.
• [14] Sinaga KP, Yang M-S. Unsupervised K-means clustering algorithm. IEEE Access 2020;8:8071680727. [CrossRef]
• [15] Küçükdeniz T, Erkal Sönmez Ö. Integrated Warehouse Layout Planning with Fuzzy C-Means Clustering. in International Conference on Intelligent and Fuzzy Systems. 2022. Springer. [CrossRef]
• [16] Pekel Özmen E, Özcan T. Diagnosis of diabetes mellitus using artificial neural network and classification and regression tree optimized with genetic algorithm. J Forecast 2020;39:661670. [CrossRef]
• [17] Abubakar AM, Francis OC, Sarkinbaka ZM, Sabo Yahaya M. Simplex C++ syntax for solving chemical engineering cost optimization problems. Res Invent Int J of Eng Sci 2021;11:3947. [CrossRef]
• [18] Schittekat P, Kinable J, Sörensen K, Sevaux M, Spieksma F, Springael J. A metaheuristic for the school bus routing problem with bus stop selection. Eur J Oper Res 2013;229:518528. [CrossRef]