Shareability network based decomposition approach for solving large-scale single school routing problems
The authors 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. The authors 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, the authors 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, the authors 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. The authors 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 the authors' approach. Meanwhile, their 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 the authors' proposed approaches on benchmark networks and their methods outperform both techniques under a single school setting.
- Record URL:
- Record URL:
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/issn/0968090X
-
Supplemental Notes:
- © 2022 Elsevier Ltd. All rights reserved. Abstract reprinted with permission of Elsevier.
-
Authors:
- Guo, Xiaotong
-
0000-0003-0079-7665
- Samaranayake, Samitha
- Publication Date: 2022-7
Language
- English
Media Info
- Media Type: Web
- Features: Appendices; Figures; References; Tables;
- Pagination: 103691
-
Serial:
- Transportation Research Part C: Emerging Technologies
- Volume: 140
- Issue Number: 0
- Publisher: Elsevier
- ISSN: 0968-090X
- Serial URL: http://www.sciencedirect.com/science/journal/0968090X
Subject/Index Terms
- TRT Terms: Optimization; Ridesharing; Routing; School buses; School trips
- Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; Public Transportation;
Filing Info
- Accession Number: 01846758
- Record Type: Publication
- Files: TRIS
- Created Date: May 24 2022 1:55PM