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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:
    Guo, Xiaotong (Autor:in) / Liu, Yang (Autor:in) / Samaranayake, Samitha (Autor:in)


    Erscheinungsdatum :

    2018-11-01


    Format / Umfang :

    2630566 byte





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    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

    Freier Zugriff