ISSN: 1304-7191 | E-ISSN: 1304-7205
Two-stage clustering and routing problem by using FCM and K-means with Genetic Algorithm
1Department of Industrial Engineering, Samsun University, Samsun, Türkiye
2Department of Industrial Engineering, Istanbul University-Cerrahpaşa, Istanbul, Türkiye
Sigma J Eng Nat Sci - DOI: 10.14744/sigma.2023.00096
Full Text PDF


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.