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

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

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

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

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]

Details

Primary Language

English

Subjects

Structural Biology

Journal Section

Research Article

Authors

Ebru Pekel Özmen ^*
0000-0001-7717-6790
Türkiye

Tarık Küçükdeniz
0000-0002-6670-1809
Türkiye

Publication Date

August 1, 2024

Submission Date

January 27, 2023

Acceptance Date

May 4, 2023

Published in Issue

Year 2024 Volume: 42 Number: 4

IZ

https://izlik.org/JA62SW28FD

Cite

RIS / Bibtex

APA

Pekel Özmen, E., & Küçükdeniz, T. (2024). Two-stage clustering and routing problem by using FCM and K-means with genetic algorithm. Sigma Journal of Engineering and Natural Sciences, 42(4), 1030-1038. https://izlik.org/JA62SW28FD

AMA

1.Pekel Özmen E, Küçükdeniz T. Two-stage clustering and routing problem by using FCM and K-means with genetic algorithm. SIGMA. 2024;42(4):1030-1038. https://izlik.org/JA62SW28FD

Chicago

Pekel Özmen, Ebru, and Tarık Küçükdeniz. 2024. “Two-Stage Clustering and Routing Problem by Using FCM and K-Means With Genetic Algorithm”. Sigma Journal of Engineering and Natural Sciences 42 (4): 1030-38. https://izlik.org/JA62SW28FD.

EndNote

Pekel Özmen E, Küçükdeniz T (August 1, 2024) Two-stage clustering and routing problem by using FCM and K-means with genetic algorithm. Sigma Journal of Engineering and Natural Sciences 42 4 1030–1038.

IEEE

[1]E. Pekel Özmen and T. Küçükdeniz, “Two-stage clustering and routing problem by using FCM and K-means with genetic algorithm”, SIGMA, vol. 42, no. 4, pp. 1030–1038, Aug. 2024, [Online]. Available: https://izlik.org/JA62SW28FD

ISNAD

Pekel Özmen, Ebru - Küçükdeniz, Tarık. “Two-Stage Clustering and Routing Problem by Using FCM and K-Means With Genetic Algorithm”. Sigma Journal of Engineering and Natural Sciences 42/4 (August 1, 2024): 1030-1038. https://izlik.org/JA62SW28FD.

JAMA

1.Pekel Özmen E, Küçükdeniz T. Two-stage clustering and routing problem by using FCM and K-means with genetic algorithm. SIGMA. 2024;42:1030–1038.

MLA

Pekel Özmen, Ebru, and Tarık Küçükdeniz. “Two-Stage Clustering and Routing Problem by Using FCM and K-Means With Genetic Algorithm”. Sigma Journal of Engineering and Natural Sciences, vol. 42, no. 4, Aug. 2024, pp. 1030-8, https://izlik.org/JA62SW28FD.

Vancouver

1.Ebru Pekel Özmen, Tarık Küçükdeniz. Two-stage clustering and routing problem by using FCM and K-means with genetic algorithm. SIGMA [Internet]. 2024 Aug. 1;42(4):1030-8. Available from: https://izlik.org/JA62SW28FD