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.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    School Bus Routing with Stochastic Demand and Duration Constraints


    Published in:

    Publication date :

    2017




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English



    Classification :

    Local classification 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