The vehicle scheduling problem concerns the assigning of a set of time-tabled trips to vehicles so as to minimize a given cost function. The authors consider the NP-hard multiple depot case in which, in addition, one has to assign vehicles to depots. Different lower bounds based on assignment relaxation and on connectivity constraints are presented and combined in an effective bounding procedure. A strong dominance procedure derived from new dominance criteria is also described. A branch and bound algorithm is finally proposed. Computational results are given.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A branch and bound algorithm for the multiple depot vehicle scheduling problem


    Additional title:

    Ein Verzweigungsalgorithmus fuer das Zeitplanproblem von Depotfahrzeugen


    Contributors:
    Carpaneto, G. (author) / Dell'Amico, M. (author) / Fischetti, M. (author) / Toth, P. (author)

    Published in:

    Networks ; 19 , 5 ; 531-548


    Publication date :

    1989


    Size :

    18 Seiten, 11 Quellen



    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English





    Multiple-Depot Integrated Vehicle and Crew Scheduling

    Huisman, D. / Freling, R. / Wagelmans, A. P. M. | British Library Online Contents | 2005


    Multiple-Depot Integrated Vehicle and Crew Scheduling

    Huisman, Dennis | Online Contents | 2005


    Optimizing Single-Depot Vehicle Scheduling Problem: Fixed-Interval Model and Algorithm

    Zhang, Jian / Li, Wenquan / Qiu, Feng | Taylor & Francis Verlag | 2015