Two-stage clustering and routing problem by using FCM and K-means with Genetic Algorithm

Abstract

Keywords: Fuzzy Clustering; Genetic Algorithms; K-means; LAR; SBRP

Introduction

With urbanization, urban transportation has become a major concern for many large cities. However, public transit systems are often perceived as inefficient, leading people to rely on their own vehicles or taxis instead. In the context of school transportation, the inefficiency of school-provided

transportation systems can result in an increase in private vehicle usage, which contributes to traffic congestion, air pollution, and environmental harm. Therefore, it is essential to develop efficient and cost-effective transportation systems for students that prioritize their comfort and safety while reducing the overall environmental impact.

*Corresponding author. *E-mail address: ebru.pekel@samsun.edu.tr This paper was recommended for publication in revised form by Editor in Chief Ahmet Selim Dalkilic Published by Yıldız Technical University Press, İstanbul, Turkey Copyright 2021, Yıldız Technical University. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Sigma J Eng Nat Sci, Vol. 42, No. 4, pp. 1030−1038, August, 2024

Several studies have addressed the school bus routing problem (SBRP) in recent years. These studies have proposed various mathematical models and metaheuristic algorithms to improve the efficiency of school transportation systems while balancing the service provider’s costs and students’ convenience. Some studies have considered factors such as students’ travel patterns, class periods, and school bell times to optimize school bus routing. However, there is still room for improvement in terms of minimizing the walking distance of individuals and the total distance traveled by vehicles, especially in the context of the first cluster and second route approach. Miranda, de Camargo [1] have discussed SBRP by extending it with mixed loads. Oluwadare, Oguntuyi [2] proposed a Genetic Algorithm to solve the school bus route problem. Sun, Duan [3] addressed the school bus routing problem in a stochastic and time-dependent road environment. Mahmoudzadeh and Wang [4] tried to identify a feasible technique for scheduling the university shuttle fleet, considering students’ travel patterns and class periods. The annual ridership data for 2018–2019 of the Texas A&M University (TAMU) shuttle system were utilized to detect unique weekday and weekend travel patterns. A clustering strategy was presented to create uniform departure times within the current schedules for on-campus and off-campus routes, considering the high student loads and graduate/ undergraduate habits. [5] studied a case for the capacitated employee bus routing problem using data from a retail company. They constructed a mathematical model to minimize the total distance of bus routes. The number and location of bus stops was identified using k-means and fuzzy c-means clustering techniques. Then, due to the NP-Hard nature of the bus routing problem, simulated annealing (SA) and genetic algorithm (GA)-based solutions were presented. A hybrid iterative local search (ILS) metaheuristic algorithm for SBRP with various planning scenarios, such as homogeneous or heterogeneous fleets, single load or mixed load modes of operation, is an attempt made in [6]. Pérez, Ansola [7] created a mathematical model based on literature and modified it such that metaheuristics could be used to solve it. Incorporating school bell times as decision variables rather than input data allowed them to extend the traditional school bus routing problem [8]. The authors used the Memetic algorithm to solve the proposed model and argue that changing school working hours (bell ringing times) is especially helpful in reducing transportation costs. Calvete, Galé [9] consider the SBRP if students are free to select the bus stop of their choice. It is created and presented to convert a two-stage optimization model to a single-level mixed integer linear programming (MILP) model. To address the issue, a straightforward and efficient metaheuristic algorithm has been created. Pérez, Sánchez-Ansola [10] introduced a novel method for reducing execution time, which is one of the factors considered while solving a problem using SBRP. Hou, Liu

[11] proposed a local search-based metaheuristic algorithm framework for SBRP based on the analysis of SBRP problem models. The proposed framework provides metaheuristic development for the Capacitated Vehicle Routing Problem by reducing or modifying the constraints of SBRP. Experimental results of several examples show that the metaheuristic algorithm based on the proposed approach can be implemented quickly and applied to different SBRP applications. Feng, Zhang [12] proposed two strategies (mixed-load and single-load) for the mixed-load school bus routing problem (SBRP) to improve student commuting efficiency while reducing operational costs. A bi-level programming model was constructed to maximize school accessibility and minimize the number of school buses. The entropy-based weight method was used to evaluate the strategies, and case studies were conducted using school bus data in Dalian, China. [13] addressed SBRP with student input in bus stop selection. A bilevel optimization model with multiple followers was proposed and transformed into a single-level mixed integer linear programming model. A metaheuristic algorithm was developed to solve the problem, which involved solving four MILP problems to obtain upper bounds. Computational experiments using benchmark instances showed the algorithm was effective in terms of solution quality and required computing time. In this study, the School Bus Routing Problem (SBRP) was addressed in a two-stage approach. Initially, the Fuzzy C Means (FCM) method was utilized to identify the optimal locations for bus stops. Subsequently, students were assigned to the nearest bus stop. Alongside FCM, the K-means algorithm was also employed to pinpoint the optimal bus stop locations. In the second stage, the Genetic Algorithm (GA) was employed to generate the most efficient vehicle route with the goal of minimizing the total distance traveled by all vehicles. The remainder of this paper is organized as follows: In the second section, the literature review is presented. In the third section, the proposed approaches are introduced. The fourth part shows experimental results to compare the performances of the proposed approaches. Finally, the discussion and conclusions are presented.

Materials And Methods

This section presents the materials and methods used in this study to solve the SBRP problem. The first part introduces the K Means algorithm used to identify the bus stop locations, while the second part explains the Fuzzy C-means (FCM) algorithm used as an alternative method. Additionally, the Genetic Algorithm (GA) is described to be utilized in the second stage. K-Means Algorithm The K-means method is an iterative technique that attempts to divide the dataset into K unique, non-overlapping

Sigma J Eng Nat Sci, Vol. 42, No. 4, pp. 1030−1038, August, 2024

subgroups (clusters), where each data point belongs to only one group. It attempts to make intra-cluster data points as comparable as feasible while maintaining clusters as distinct as possible. It allocates data points to a cluster such that the sum of the squared distance between the data points and the cluster’s centroid (the arithmetic mean of all data points belonging to that cluster) is the smallest possible value. Data points within the same cluster are more homogenous (similar) the less variance there is within clusters. The implementation of the K-means algorithm is as follows ([14]: Step 1: Indicate the number of cluster K. Step 2: Initialize centroids by first shuffling the dataset and then picking K data points at random without replacement for use as centroids. Step 3: Repeat iterating until the centroids do not change. Thus, the assignment of data points to clusters remains unchanged. Fuzzy C Means (FCM) The fuzzy C-Means method is a variant of the K-Means algorithm that employs fuzzy logic and seeks to find the least value of the objective function. It is possible for a data sample to belong to more than one cluster at the same time in FCM. Similarity is indicated by the membership value. In FCM, a membership value and a data sample are assigned based on cluster center and similarity ([15]. Membership values range from 0 to 1, and the higher the similarity, the higher the membership value. Steps of the Fuzzy C-Means algorithm are given in Equations 1-3 ([15]. (1) where yj is the mean for that points over cluster i, is a squared inner product distance norm, and mikµ represents the fuzzy partitions, where mik denotes the membership degree that the ith data point belongs to the kth cluster and µ is a scalar for controlling the fuzziness of the resulting clusters. Besides, x represents the geographical X and Y coordinates. . Step 1: Assign membership matrix Step 2: Compute cluster centers using Equation 2. (2)

In those equations, k and N represent the number of clusters and students, respectively. xi means the coordinates of the student i, and yk means the coordinates of the cluster k. Genetic Algorithm (GA) Genetic algorithms are stochastic algorithms whose search techniques are based on biological genetics and natural evolution concepts. Holland first presented the fundamental ideas of genetic algorithms in 1975. Individuals in a population are represented as chromosomes in this methodology, and a sequence of genetic operations is performed. It is widely acknowledged that the possible solution to each problem is an individual who may be represented using a set of parameters. Every cell in nature contains chromosomes that make up the DNA of that cell. Chromosomes contain the genes that regulate a living organism’s character differentiation. An individual or chromosome is the potential solution to a problem in a genetic algorithm. The population is made up of individuals. Population, on the other hand, refers to the sum of the genetic algorithm’s solutions. Mating, mutation, and reproduction are all genetic processes that are employed in genetic algorithms. Genetic algorithms offer an ideal setting for tackling large-scale optimization challenges. Although it belongs to the class of probabilistic algorithms, it differs from random number generation methods. Genetic operators, such as mutation, can readily escape local optimal points in genetic algorithms ([16]. The details of the method are not provided in this paper because it is a well-known universal algorithm. A typical GA focuses on two things: fitness function and solutions. Constraints cannot be defined as in linear programming ([17]. As a result, the solution space and fitness function must be suitably adjusted. The pseudocode of GA to solve the proposed SBRP is presented in Table 1.

Table 1. Pseudo code of the applied metaheuristic algorithm for proposed SBRP. Stage 0: Obtain student’s coordinates Pi

Step 4: If the differences in total costs estimated by consecutive membership matrices are less than the stopping criteria, the algorithm terminates.

Sigma J Eng Nat Sci, Vol. 42, No. 4, pp. 1030−1038, August, 2024

Cluster-First Route-Second Approach for School Bus Routing Problem

Mathematical model for multi-vehicle SBRP The aim of the mathematical model is to design a system that will minimize the walking distance of each student to the assigned stops and minimize the total distance traveled by the vehicles. The mathematical model of the proposed SBRP problem is a bi-objective mixed integer location routing model. Even the single-objective location routing problem is an NP-hard problem because it combines the two problems, which are the facility location and vehicle routing problem and the location routing problem ([10]. Because the bi-objective position routing issue is more complicated, it is also NP-hard. The representation of the model, its parameters, and the decision variables are presented below. Model A:

(11) Table 2. Symbols used in the mathematical model Indices m

the number of the stop coordinate value of the mth student on the x-axis

coordinate value of the mth student on the y-axis the capacity of the vehicle

{if the vehicle v visits to ith stop, 1 otherwise, 0 {if mth student assigns to ith stop, 1 otherwise, 0 the distance between ith stop and mth student the distance between ith stop and jth stop

Coordinate value of the ith stop on the x - axis Coordinate value of the ith stop on the y - axis {if the vehicle v travels from ith stop to jth stop, 1 otherwise, 0

Equation 4 expresses the objective function. It minimizes the walking distance of students and the total distance traveled by vehicles. Equation 5 and Equation 7 calculate the walking distance of students and the distance between cluster centers, respectively. Equation 6 checks that each student is assigned to only one cluster. Equations 8–9 state that only one vehicle should be assigned between any two points. Equation 10 verifies that the number of students served by the vehicle along the entire route of each vehicle does not exceed the vehicle’s capacity. Equations 11–12 state that a bus arriving at a bus stop also leaves the station and stops only on its route. Equation 11 ensures that the flow of each vehicle is maintained. Equation 14 states that each bus departs from school and returns to school. Equations 15–16 are MTZ equations. Miller-Tucker-Zemlin (MTZ) formulation uses an extra positive variable called as pi. pi takes a value for each node except the school. If a vehicle is traveling from node i to node J, pj must be greater than pi. The value of pi grows with each subsequent call point.

Sigma J Eng Nat Sci, Vol. 42, No. 4, pp. 1030−1038, August, 2024

(16) The process of selecting bus stops and generating bus routes is frequently referred to as a location-routing problem (LRP), which is an example of an NP-hard problem. An NP-hard problem is one for which there are no known polynomial-time algorithms that can provide an optimal solution for every instance of the problem. In such situations, dividing the problem into parts helps facilitate its resolution. The foundational “divide and conquer” approach served as the primary inspiration for the creation of this heuristic, which was built on that method. An assignment model is

first solved to establish a cluster of pickup locations for each vehicle using the cluster-first and route-second approaches. Subsequently, the traveling salesman problem (TSP) is addressed for all clusters. Finally, a route is generated using the TSP solutions. The results obtained from the fuzzy C-means algorithm under different conditions are presented in Figures 1 and 2. Figure 1 depicts the cluster centers obtained for a scenario involving 10 bus stops, whereas Figure 2 presents the cluster centers for a scenario with n = 40 bus stops. It is common practice to locate bus stops in parts of a community that have a high concentration of student inhabitants. The decision variables Cix and Ciy in Model A may be derived from the outputs that are provided by the FCM. The last variable that must be determined is the one that is referred to as Xijv. Route Generation The most expedient route is determined with the help of GA. An initial solution is chosen at random by the genetic algorithm. The resolution that was randomly given is called an initial chromosome. If we assume that the value of each gene (ri) falls somewhere between 0 and 1, then the composition of a chromosome with 5 stops is as follows:

Each gene value is sorted from lowest to highest, and the final order of the rankings is kept. This rank indicates the order in which the bus stops are located along the route. When the number of students on the bus that is making the stops exceeds the capacity of the vehicle, another bus is brought into service. There is a limit of one stop per bus when overbooking is permitted. The calculations are done based on the premise that the school serves as both the beginning and the finish point for the vehicle routes. The fundamental procedures that GA employs to determine the most efficient route are summarized in Table 3.

Results And Discussion

The dataset originally consisted of 112 cases, all of which were taken from [18]. Sample sizes vary anywhere from 5 stops and 25 students to 80 stops and 800 students. In addition, the dataset took into consideration a maximum

Sigma J Eng Nat Sci, Vol. 42, No. 4, pp. 1030−1038, August, 2024

of four different maximum walking distances. Since the maximum walking distance was not included as a parameter in this study, there were no experiments conducted to investigate the effects of varying the maximum walking distance. As a result, the experiments were only conducted in

a total of 28 instances. The instances have a standard fleet of buses that can accommodate 25 or 50 students. The parameter values of the employed metaheuristic algorithm are shown in Table 4. The maximum value of the decision variable is set to 1 in GA, while the minimum value is set to 0. Table 5 contains the results for the problem instances. The number of stops is indicated in the stop column. The Student column specifies the number of students served, while the CAP column indicates the bus capacity. The students are transported by a homogeneous fleet of vehicles of identical capacity. Total walking distance is shown by the total walking column, while total driving distance is indicated by the total driving distance. The Total driving* columns are vital to compare former_ best and new_best value. As an example, the best value is found as 241.68 for Instance 09, which is found in this work; also, this value is obtained as 286.68 in [18] as seen in Table

FCM & GA

CAP: Capacity of the vehicle; FCM: Fuzzy C means; GA: Genetic algorithm.

Sigma J Eng Nat Sci, Vol. 42, No. 4, pp. 1030−1038, August, 2024

The purpose of this research was not only to lower the total distance traveled by vehicles but also the total distance traveled by pedestrians. When the first phase of the clustering procedure is complete, it is verified that the students’ stopping locations are placed at the geographically closest points to them. This reduces the amount of walking distance these students must travel. In addition, the predefined bus stop locations were used to find the optimal routes Table 5 displays the results of the suggested approach, indicating that favorable performance was achieved in 17 out of the 28 analyses. It is noteworthy that the “driving” column is of particular significance for the purpose of comparison, while the “walking” column represents an additional accomplishment that we aim to achieve. This is because students are required to walk less concurrently, which has had a notable impact on the identification of bus

stop locations. Consequently, the search for the shortest driving distance is complicated by the need to consider the walking distance factor. Despite the multiplicity of focus points, the suggested approach still yielded better results in more than half of the instances. Table 6 demonstrates the results of the K-means and GA methodology, indicating that this strategy outperformed the suggested approach in 19 of the 28 evaluations. However, it is important to note that as the sample size grows, the two-stage strategy’s performance has shown signs of deterioration. This study aimed to compare the FCM and K-means clustering algorithms, as depicted in Figure 3. The graph illustrates the results obtained from each algorithm, and a detailed analysis of the graph revealed that the K-means

Sigma J Eng Nat Sci, Vol. 42, No. 4, pp. 1030−1038, August, 2024

Fcm-Ga

approach demonstrated superior efficiency in reducing the walking distance for students. Furthermore, Table 7 provides a comprehensive statistical summary of the proposed approaches. The K-Means-GA approach yielded the best mean value of 817.28, surpassing the previous results reported in the literature which stood at 817.945. However, given that the mean alone may not suffice for comparison purposes, the median value was also considered. Remarkably, the K-Means-GA approach also resulted in the smallest median value. In summary, the findings of this study provide evidence that the K-means clustering algorithm, particularly the K-Means-GA approach, is a promising method for optimizing bus stop locations and reducing walking distances for students.

Conclusion

This paper presents a two-stage approach to the school bus routing problem, with the aim of reducing both the

total distance traveled by vehicles and students. The first stage involves selecting suitable bus stops using the FCM and K-Means algorithms, while the second stage uses GA to plan bus routes. The dataset utilized in this study was obtained from an easily accessible source. The application process was conducted in a total of 28 distinct instances, wherein both the Fuzzy C Means and the GA implementations were employed to attain optimal outcomes. Analysis of the experimental results revealed that the proposed approach yielded significant advantages overall. The proposed approach offers decision makers possible solutions and trade-offs between the objectives. The study shows that the proposed approach offers significant benefits, including a considerable reduction in solution time. However, there are some limitations, such as the lack of coordination across phases’ objective functions. A brief summary of the fundamental points outlined in this study is presented below.: • The proposed two-stage approach reduces solution time and enables modifications at any stage.

Sigma J Eng Nat Sci, Vol. 42, No. 4, pp. 1030−1038, August, 2024

Overbooking is a common occurrence in real-life scenarios, but it is rarely discussed in the SBRP literature. • The unchangeable rule that prohibits exceeding the maximum capacity of a vehicle’s seating capacity has been loosened in this study. • The first bus stop locations are uncertain, and there is no available sequence of potential bus stops. In future studies, it may be beneficial to investigate a method that integrates both objective functions into a single phase, potentially enhancing the efficiency and effectiveness of the solution. However, it is important to note that the utilization of a goal programming approach in a one-step process may result in an increased level of complexity in the problem formulation and solution procedure. Thus, the aim of any such approach should be to provide reasonable and convincing results in a practical and feasible manner.

Data Availability Statement

The authors confirm that the data that supports the findings of this study are available within the article. Raw data that support the finding of this study are available from the corresponding author, upon reasonable request.

Conflict Of Interest

The author declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Ethics

There are no ethical issues with the publication of this manuscript.

References

1. Miranda DM, de Camargo RS, Conceição SV, Porto Layout Planning with Fuzzy C-Means Clustering. in MF, Nunes NTR. A multi-loading school bus rout- International Conference on Intelligent and Fuzzy ing problem. Exp Syst Appl 2018;101:228−242. Systems. 2022. Springer. [CrossRef] [CrossRef] [16] Pekel Özmen E, Özcan T. Diagnosis of diabetes
2. Oluwadare SA, Oguntuyi IP, Nwaiwu JC. Solving mellitus using artificial neural network and classi- school bus routing problem using genetic algo- fication and regression tree optimized with genetic rithm-based model. Int J Intell Syst Appl 2018;12:50. algorithm. J Forecast 2020;39:661−670. [CrossRef] [CrossRef] [17] Abubakar AM, Francis OC, Sarkinbaka ZM, Sabo
3. Sun S, Duan Z, Xu Q. School bus routing problem Yahaya M. Simplex C++ syntax for solving chemical in the stochastic and time-dependent transportation engineering cost optimization problems. Res Invent network. PloS One 2018;13:e0202618. [CrossRef] Int J of Eng Sci 2021;11:39−47. [CrossRef]
4. Mahmoudzadeh A, Wang XB. Cluster Based [18] Schittekat P, Kinable J, Sörensen K, Sevaux M, Methodology for Scheduling a University Shuttle Spieksma F, Springael J. A metaheuristic for the System. Trans Res Record 2020;2674:236−248. school bus routing problem with bus stop selection. [CrossRef] Eur J Oper Res 2013;229:518−528. [CrossRef]

Share and Cite