Clustering and Integer Programming Optimize University Bus Routes

The study, published in the journal Discover Vehicles, proposes a combined approach using density-based clustering and integer linear programming to determine efficient bus routes. This method aims to transport the maximum number of students to their academic destinations while minimizing travel time and ensuring adherence to entry schedules. The research specifically targets the outbound routes of the university’s transport system, which currently operates with a fleet of 45 buses.

The primary motivation for this study is the increasing demand for student transport in urban areas. As student populations grow and distribute across wider geographic areas, the limited number of available buses leads to significant congestion during peak hours. The existing routes at UAEMex were originally designed empirically based on surveys or student requests, which may not be optimal for current logistical needs. The new model seeks to replace these empirical designs with a mathematically rigorous solution that accounts for specific spatial and temporal constraints.

The methodology begins with a multi-stage clustering process using the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm. This algorithm groups student locations and academic spaces based on their density distribution. The researchers applied DBSCAN to 32 academic locations and 38,496 student records to identify potential bus stops and destinations. By using clustering, the team reduced the complexity of the dataset, identifying relevant points necessary for the subsequent mathematical modeling phase.

To determine the starting points for the bus routes, known as terminals, the researchers employed a convex hull algorithm. The convex hull identifies the outermost points in a set of data, effectively creating a geometric boundary around the student population. In this study, the QuickHull method was used to select nine vertices as terminals. These terminals serve as the departure points for the buses, ensuring that the routes cover the greatest possible geographical dispersion of the student body.

The core of the optimization is an Integer Linear Programming (ILP) model that incorporates constraints from both the Vehicle Routing Problem (VRP) and the Maximum Flow Problem. The VRP component ensures that the routes are feasible for the available fleet, considering capacity and travel constraints. The Maximum Flow component aims to maximize the number of students transported to their designated destinations. The model uses a multi-objective function that balances three factors: maximizing student flow, minimizing route cost in terms of time, and optimizing the departure time of each bus.

The model was tested using data from the 7:00 a.m. entry time slot, which represents the peak demand period for students. The researchers filtered the student records to include only those with this specific entry time, resulting in a dataset of 9,988 students for the primary tests. The ILP model was solved using the COIN-OR Branch and Cut (CBC) solver, an exact method capable of finding optimal solutions for complex combinatorial problems. The tests were conducted on a virtual private server with 8 GB of RAM and a 32-core processor.

The results demonstrated that the model successfully generated optimal routes for the buses. The routes did not end at a central depot, as is common in classical VRP models, but instead terminated at various academic destinations. This design reduces the complexity of subtour elimination and allows for more flexible route endings. The solver found feasible solutions for the tested scenarios, with the objective function values indicating a balance between student flow and travel time. The model ensured that all routes started and ended at appropriate times, aligning with the students’ entry schedules.

However, the study also identified limitations regarding the scalability of the exact method. Scenario 3, which involved a larger number of nodes, destinations, and buses, could not be solved within the time limit set for the CBC solver. This indicates that as the size of the instance increases, the computational time required for an exact solution grows significantly. The researchers noted that for larger-scale instances, the incorporation of approximate methods, such as heuristics or metaheuristics, may be necessary to ensure reasonable response times.

The proposed model offers advantages over classical VRP models by avoiding bidirectional routes in the initial phase. By focusing solely on outbound journeys, the model simplifies the application of Miller-Tucker-Zemlin constraints for subtour elimination. The use of the convex hull to define route starting points further enhances this efficiency. The researchers suggest that the return direction could be modeled separately by reversing flow and arc constraints, providing a modular approach to the full transport cycle.

The study contributes to the field of logistics and combinatorial optimization by integrating clustering techniques with exact optimization methods. The use of DBSCAN for identifying bus stops and the convex hull for defining terminals provides a robust framework for handling real-world transport data. The findings suggest that such models can be effectively applied to bounded real-world scenarios, offering a path toward more efficient and reliable student transport services in university settings.

Future work proposed by the authors includes the addition of graph theory elements, such as spanning trees, to allow buses to visit multiple destinations. They also plan to implement metaheuristic algorithms to solve larger instances more quickly.

The case study at UAEMex provides a concrete example of how theoretical optimization models can be applied to real-world problems, offering insights that may be useful for other institutions facing similar transport challenges.

In conclusion, the integration of clustering, convex hulls, and integer linear programming provides a powerful tool for optimizing university bus routes. The model’s ability to handle specific constraints related to student flow and time windows makes it a valuable resource for transport planners. While computational limitations exist for very large instances, the approach offers a significant improvement over empirical route design, paving the way for more efficient and student-friendly transport systems.

To establish the geometric foundation for the routing network, the researchers evaluated specific distance metrics and clustering performance criteria. When grouping the 32 academic spaces, the team utilized the Haversine formula with an epsilon threshold of one kilometer and a minimum point parameter of one, reflecting geodesic distances on a spherical Earth with an assumed radius of 6,371 kilometers. Because the Haversine metric is restricted to two dimensions, the investigators transitioned to Euclidean distance for the subsequent three-dimensional analysis that incorporated latitude, longitude, and assigned academic space groups. To determine the most effective distance threshold for student clustering, the authors evaluated five candidate values at 250-meter intervals from one kilometer to two kilometers, corresponding to Euclidean values between 0.01 and 0.02. Cluster quality was assessed using three standard indices: the Silhouette score, which measures intra-cluster similarity relative to neighboring clusters; the Davies–Bouldin index, where lower scores reflect superior separation; and the Calinski–Harabasz variance ratio criterion, where higher values indicate stronger cluster cohesion. Across these evaluations, an epsilon threshold of 0.01, representing one kilometer, yielded the highest cluster quality.

The analytical framework also addressed spatial overlap among students who shared geographic starting coordinates but traveled to separate academic destinations. To resolve these overlapping points without discarding destination diversity, the researchers implemented a third DBSCAN stage using a refined distance threshold of 250 meters. This clustering pass isolated 216 student records as outliers, designated with a value of minus one, while successfully condensing the remaining student coordinates into 526 distinct clusters. Each resulting cluster had its geographic centroid computed to establish an official student boarding stop. Across the complete model, all graph vertices were assigned explicit categorical types to regulate routing operations, designating the central depot as type zero, academic drop-off stations as type one, academic space stops as type two, residential student stops as type three, and outlying terminals as type four.

In establishing the terminal subset from which outbound routes begin, the authors specifically contrasted the QuickHull approach against conventional network routing algorithms. Although Dijkstra’s algorithm is commonly used in transportation studies to discover shortest paths from an arbitrary source, the team discarded it because single-source shortest path calculations fail to detect global spatial distribution properties or the overarching geometric diameter of the stop network. By contrast, QuickHull wraps the outermost points in a minimal convex polygon, capturing the greatest geographical dispersion across the entire set of boarding locations.

The mathematical model also incorporated operational parameters reflecting real-world transit conditions. Arc travel times between vertices were calculated assuming an average speed of 40 kilometers per hour, alongside an average dwell time of five minutes at each stop. To enforce punctuality, the model established a minimum departure time of 5:00 a.m. for outbound journeys meeting the 7:00 a.m. entry threshold, processing temporal figures in decimal format.

Subject of Research: An optimization model for the university school bus routing problem

Article Title: An optimization model for the university school bus routing problem

Article References: Sánchez-Carmona, M. A., Marcial-Romero, J. R., Loza-Hernandez, L., & Hernández-Servín, J. A. (2026). An optimization model for the university school bus routing problem. Discover Vehicles, 2(1), Article 12. https://doi.org/10.1007/s44465-026-00017-0

Image Credits: AI Generated

DOI: 10.1007/s44465-026-00017-0

Keywords: optimization, model, university, school, routing, problem, scientific research