The school bus routing problem (SBRP) is crucial because of its impact on economic and social objectives. A single bus is assigned to each route, picking up students and arriving at the school within a specified time window. SBRP aims to find the fewest buses needed to cover all of the routes while minimizing the total travel distance and meeting required constraints. We propose a mathematical formulation responding to the overbooking policies applied in a real-world school district. According to our empirical studies, the probability of a student riding a bus varies from 22% to 77%, opening the opportunity to overbook the buses to improve utilization of their capacity. However, SBRP with overbooking has not attracted much attention in previous studies. In this work, overbooking is modeled via chance constrained programming. Additionally, to account for the uncertainty of the total travel time of the buses, a constraint limiting the probability of being late to school is also proposed in this paper. As a result of the NP-hard nature of the problem, a cascade simplification algorithm is proposed to partition the multiple stage SBRP problems into multiple multi-depot and one-school subproblems that are solved sequentially, where the results for one are data inputs for the next. Furthermore, we develop column-generation-based algorithms to solve the scheduling problem, and different instances of the problem are examined. Our computational experiments on a real-world school district demonstrate desirable cost savings in terms of the total number of buses used.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    School Bus Routing with Stochastic Demand and Duration Constraints


    Erschienen in:

    Erscheinungsdatum :

    2017




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch



    Klassifikation :

    Lokalklassifikation TIB:    770/1935/7000
    BKL:    55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines



    School Bus Routing with Stochastic Demand and Duration Constraints

    Caceres, Hernan / Batta, Rajan / He, Qing | British Library Online Contents | 2017


    The Vehicle Routing Problem with Stochastic Demand and Duration Constraints

    Erera, A.L. / Morales, J.C. / Savelsbergh, M. | British Library Online Contents | 2010



    School Bus Routing with Stocand Duration Constraints

    Caceres, Hernan | Online Contents | 2017


    Inventory Routing Problem with Route Duration Limits and Stochastic Inventory Capacity Constraints

    Karoonsoontawong, Ampol / Unnikrishnan, Avinash | Transportation Research Record | 2013