Vehicle Scheduling in Public Transit and Lagrangean Pricing

Andreas Löbel
Additional contact information
Andreas Löbel: Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), Takustraße 7, D-14195, Berlin, Germany

Management Science, 1998, vol. 44, issue 12-Part-1, 1637-1649

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.

Keywords: Transportation; Logistics; Vehicle Scheduling; Flows In Networks; Linear Programming; Lagrangean Relaxation; Large-Scale (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.12.1637 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:44:y:1998:i:12-part-1:p:1637-1649

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().