This paper investigates the solution of the LP relaxation (linear programming) of the multi-commodity flow formulation of the multiple-depot vehicle scheduling problems arising in public mass transit. A column generation technique is developed that makes it possible to solve the huge linear programs that come up there. The technique, which is called Lagrangean pricing, is based on two different Lagrangean relaxations. The basic ingredients of the approach are described in detail and computational results for large-scale test data (with up to 70 million variables) from three German public transportation companies are given. Because of these results, Lagrangean pricing is proposed as one of the basic ingredients of an effective method to solve multiple-depot vehicle scheduling problems to proven optimality.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Vehicle scheduling in public transit and Lagrangean pricing


    Contributors:
    Löbel, A. (author)

    Published in:

    Management Science ; 44 , 12 Part 1 ; 1637-1649


    Publication date :

    1998


    Size :

    13 Seiten, 3 Bilder, 4 Tabellen, 28 Quellen




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English





    Vehicle and Driver Scheduling for Public Transit

    K. Torrance / A. R. Haire / R. B. Machemehl | NTIS | 2009


    Vehicle Scheduling for Public Mass Transit - An Overview

    Daduna, J. R. / Paixao, J. M. P. / University of Lisbon et al. | British Library Conference Proceedings | 1995


    Network Models, Lagrangean Relaxation and Subgradients Bundle Approach in Crew Scheduling Problems

    Carraresi, P. / Nonato, M. / Girardi, L. et al. | British Library Conference Proceedings | 1995


    A Crew Scheduling Approach for Public Transit Enhanced with Aspects from Vehicle Scheduling

    Gintner, Vitali / Kliewer, Natalia / Suhl, Leena | Springer Verlag | 2008