An Optimization Model for the University School Bus Routing Problem

Passenger transport, and particularly student transport, tends to become saturated due to on one side the growing increase and distribution of the student population, and the other the few available buses. This article proposes the use of clustering processes through the Density-Based Spatial Clustering of Applications with Noise algorithm, alongside cluster quality assessment metrics, to establish suitable bus stops. Additionally, a convex hull is employed to determine the subset of bus stops from which the transport routes will start, called terminals. Based on the elements identified through clustering and the convex hull, the parameters and dataset required for an Integer Linear Programming model were defined. In order to generate appropriate transport routes for each available bus, the model incorporates constraints based on the Vehicle Routing Problem. Furthermore, decision variables and constraints were defined to transport the maximum number of students to their designated destinations by means of the Maximum Flow Problem, resulting in a multi-objective function aimed at finding routes with minimum cost and maximum student flow per bus, and also incorporating departure times. The transport service at the Autonomous University of the State of Mexico was used as a case study to test the proposal. The model was solved using the COIN-OR Branch and Cut solver, which enabled the determination of optimal routes for each bus, successfully transporting the highest possible number of students to their respective destinations at minimal (time) cost, and ensuring that all routes start and end at appropriate times, in accordance with student entry schedules.