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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Vehicle scheduling in public transit and Lagrangean pricing


    Beteiligte:
    Löbel, A. (Autor:in)

    Erschienen in:

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


    Erscheinungsdatum :

    1998


    Format / Umfang :

    13 Seiten, 3 Bilder, 4 Tabellen, 28 Quellen




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch





    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


    Transit pricing research

    Cervero, Robert | Online Contents | 1990


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

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