We consider the classic School Bus Routing Problem (SBRP), where a fleet of school buses is used to transport students from their residences and to a common destination (school) subject to certain constraints. The constraints that are typically imposed include a maximum fleet size, a maximum walking distance to a pickup point and a maximum commute time for each student. The SBRP is a special case of the Vehicle Routing Problem (VRP) with a common destination. We propose a new approach for solving the SBRP based on the existing notion of a shareability network, which has been used recently in the context of dynamic ridepooling problems. To adapt this method to large-scale SBRP instances, we propose i) a node compression of the shareability network method with optimality guarantees, and ii) a heuristic-based edge compression technique that works well in practice. We show that the compressed problem leads to an Integer Linear Programming (ILP) of reduced dimensionality that can be solved very efficiently using off-the-shelf ILP solvers. Numerical experiments on small-scale, large-scale and benchmark networks are used to evaluate the performance of our approach and compare it to an existing large-scale SBRP solver based on a metaheuristic approach.
Solving the School Bus Routing Problem at Scale via a Compressed Shareability Network
2018-11-01
2630566 byte
Conference paper
Electronic Resource
English
Optimising ride-sharing efficiency: innovative shareability-focused pricing strategies
Taylor & Francis Verlag | 2024
|The shareability potential of ride-pooling under alternative spatial demand patterns
Taylor & Francis Verlag | 2024
|Solving the School Bus Routing Problem by Maximizing Trip Compatibility
Transportation Research Record | 2017
|Topological properties of ride-pooling shareability graph as a proxy to key performance indicators
TIBKAT | 2022
|