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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2018-11-01


    Size :

    2630566 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Optimising ride-sharing efficiency: innovative shareability-focused pricing strategies

    Alisoltani, Negin / Zargayouna, Mahdi / Ameli, Mostafa | Taylor & Francis Verlag | 2024


    Solving School Bus Routing Problem with genetic algorithm

    Ben Sghaier, Sayda / Ben Guedria, Najeh / Mraihi, Rafaa | IEEE | 2013


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

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

    Free access

    Solving the School Bus Routing Problem by Maximizing Trip Compatibility

    Shafahi, Ali / Wang, Zhongxiang / Haghani, Ali | Transportation Research Record | 2017


    Topological properties of ride-pooling shareability graph as a proxy to key performance indicators

    Bujak, Michał Piotr / Kucharski, Rafał | TIBKAT | 2022

    Free access