Vehicle Scheduling in Public Transit and Lagrangean Pricing
- 1 December 1998
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 44 (12-part-1), 1637-1649
- https://doi.org/10.1287/mnsc.44.12.1637
Abstract
This paper investigates the solution of the linear programming (LP) relaxation of the multi-commodity flow formulation of the multiple-depot vehicle scheduling problems arising in public mass transit. We develop a column generation technique that makes it possible to solve the huge linear programs that come up there. The technique, which we call Lagrangean pricing, is based on two different Lagrangean relaxations. We describe in detail the basic ingredients of our approach and give computational results for large-scale test data (with up to 70 million variables) from three German public transportation companies. Because of these results, we propose Lagrangean pricing as one of the basic ingredients of an effective method to solve multiple-depot vehicle scheduling problems to proven optimality.Transportation, Logistics, Vehicle Scheduling, Flows In Networks, Linear Programming, Lagrangean Relaxation, Large-ScaleKeywords
This publication has 17 references indexed in Scilit:
- Airline Crew Scheduling: A New Formulation and Decomposition AlgorithmOperations Research, 1997
- Optimierung des Fahrzeugumlaufs im Öffentlichen NahverkehrPublished by Springer Science and Business Media LLC ,1997
- Integer multicommodity flow problemsLecture Notes in Computer Science, 1996
- Chapter 2 Time constrained routing and schedulingPublished by Elsevier BV ,1995
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse CutsSIAM Journal on Computing, 1994
- An exact algorithm for multiple depot bus schedulingEuropean Journal of Operational Research, 1994
- Heuristic Algorithms for the Multiple Depot Vehicle Scheduling ProblemManagement Science, 1993
- A branch and bound algorithm for the multiple depot vehicle scheduling problemNetworks, 1989
- Computer-Aided Vehicle and Duty Scheduling Using the HOT Programme SystemPublished by Springer Science and Business Media LLC ,1988
- On some matching problems arising in vehicle scheduling modelsNetworks, 1987