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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Shareability network based decomposition approach for solving large-scale single school routing problems


    Contributors:


    Publication date :

    2022-04-12




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Solving the School Bus Routing Problem at Scale via a Compressed Shareability Network

    Guo, Xiaotong / Liu, Yang / Samaranayake, Samitha | IEEE | 2018




    The shareability potential of ride-pooling under alternative spatial demand patterns

    Soza-Parra, Jaime / Kucharski, Rafał / Cats, Oded | Taylor & Francis Verlag | 2024

    Free access