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.
Vehicle scheduling in public transit and Lagrangean pricing
Management Science ; 44 , 12 Part 1 ; 1637-1649
1998
13 Seiten, 3 Bilder, 4 Tabellen, 28 Quellen
Aufsatz (Zeitschrift)
Englisch
Optimal vehicle scheduling in public transit
SLUB | 1998
|Vehicle Scheduling for Public Mass Transit - An Overview
British Library Conference Proceedings | 1995
|Network Models, Lagrangean Relaxation and Subgradients Bundle Approach in Crew Scheduling Problems
British Library Conference Proceedings | 1995
|Online Contents | 1990
|A Crew Scheduling Approach for Public Transit Enhanced with Aspects from Vehicle Scheduling
Springer Verlag | 2008
|