Abstract We consider the Single School Routing Problem (SSRP) where students from a single school are picked up by a fleet of school buses, subject to a set of constraints. The constraints that are typically imposed for school buses are bus capacity, a maximum student walking distance to a pickup point, and a maximum commute time for each student. This is a special case of the Vehicle Routing Problem (VRP) with a common destination. We propose a decomposition approach for solving this problem based on the existing notion of a shareability network, which has been used recently in the context of dynamic ridepooling problems. Moreover, we come up with a simplified formulation for solving the SSRP by introducing the connection between the SSRP and the weighted set covering problem (WSCP). To scale this method to large-scale problem instances, we propose (i) a node compression method for the shareability network based decomposition approach, and (ii) heuristic-based edge pruning techniques that perform well in practice. We show that the compressed problem leads to an Integer Linear Program (ILP) of reduced dimensionality that can be solved efficiently using off-the-shelf ILP solvers. Numerical experiments on the synthetic Boston Public School (BPS) instances are conducted to evaluate the performance of our approach. Meanwhile, our proposed SSRP formulation allows a natural extension for introducing alternate transportation modes to students, which effectively reduces the number of buses needed for each school and leads to a 15% cost reduction on average. Moreover, two state-of-art large-scale SSRP solving techniques are compared with our proposed approaches on benchmark networks and our methods outperform both techniques under a single school setting.
Highlights Propose methods to solve the large-scale single-school routing problems (SSRP). Connect the SSRP with the weighted set covering problems (WSCP). Introduce network compression techniques for solving problems efficiently. Conduct real-world experiments to show performance improvements over benchmark models.
Shareability network based decomposition approach for solving large-scale single school routing problems
2022-04-12
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
The shareability potential of ride-pooling under alternative spatial demand patterns
Taylor & Francis Verlag | 2024
|Solving large-scale dial-a-ride vehicle routing and scheduling problems
DSpace@MIT | 1984
|