IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v44y1998i12-part-1p1637-1649.html
   My bibliography  Save this article

Vehicle Scheduling in Public Transit and Lagrangean Pricing

Author

Listed:
  • Andreas Löbel

    (Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), Takustraße 7, D-14195, Berlin, Germany)

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.

Suggested Citation

  • Andreas Löbel, 1998. "Vehicle Scheduling in Public Transit and Lagrangean Pricing," Management Science, INFORMS, vol. 44(12-Part-1), pages 1637-1649, December.
    • Handle: RePEc:inm:ormnsc:v:44:y:1998:i:12-part-1:p:1637-1649
    DOI: 10.1287/mnsc.44.12.1637
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.44.12.1637
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.44.12.1637?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Mauro Dell'Amico & Matteo Fischetti & Paolo Toth, 1993. "Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem," Management Science, INFORMS, vol. 39(1), pages 115-125, January.
    2. Pamela H. Vance & Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser, 1997. "Airline Crew Scheduling: A New Formulation and Decomposition Algorithm," Operations Research, INFORMS, vol. 45(2), pages 188-200, April.
    3. Celso C. Ribeiro & François Soumis, 1994. "A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem," Operations Research, INFORMS, vol. 42(1), pages 41-52, February.
    4. Forbes, M. A. & Holt, J. N. & Watts, A. M., 1994. "An exact algorithm for multiple depot bus scheduling," European Journal of Operational Research, Elsevier, vol. 72(1), pages 115-124, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Avella, Pasquale & Boccia, Maurizio & Sforza, Antonio, 2004. "Solving a fuel delivery problem by heuristic and exact approaches," European Journal of Operational Research, Elsevier, vol. 152(1), pages 170-179, January.
    2. P. Chardaire & G. P. McKeown & S. A. Verity-Harrison & S. B. Richardson, 2005. "Solving a Time-Space Network Formulation for the Convoy Movement Problem," Operations Research, INFORMS, vol. 53(2), pages 219-230, April.
    3. Kim, Byung-In & Kim, Seongbae & Park, Junhyuk, 2012. "A school bus scheduling problem," European Journal of Operational Research, Elsevier, vol. 218(2), pages 577-585.
    4. Benchimol, Pascal & Desaulniers, Guy & Desrosiers, Jacques, 2012. "Stabilized dynamic constraint aggregation for solving set partitioning problems," European Journal of Operational Research, Elsevier, vol. 223(2), pages 360-371.
    5. Karabuk, Suleyman, 2009. "A nested decomposition approach for solving the paratransit vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 43(4), pages 448-465, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kulkarni, Sarang & Krishnamoorthy, Mohan & Ranade, Abhiram & Ernst, Andreas T. & Patil, Rahul, 2018. "A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 457-487.
    2. Perumal, Shyam S.G. & Lusby, Richard M. & Larsen, Jesper, 2022. "Electric bus planning & scheduling: A review of related problems and methodologies," European Journal of Operational Research, Elsevier, vol. 301(2), pages 395-413.
    3. Desaulniers, Guy & Lavigne, June & Soumis, Francois, 1998. "Multi-depot vehicle scheduling problems with time windows and waiting costs," European Journal of Operational Research, Elsevier, vol. 111(3), pages 479-494, December.
    4. Matteo Fischetti & Andrea Lodi & Silvano Martello & Paolo Toth, 2001. "A Polyhedral Approach to Simplified Crew Scheduling and Vehicle Scheduling Problems," Management Science, INFORMS, vol. 47(6), pages 833-850, June.
    5. Richard Freling & Albert P. M. Wagelmans & José M. Pinto Paixão, 2001. "Models and Algorithms for Single-Depot Vehicle Scheduling," Transportation Science, INFORMS, vol. 35(2), pages 165-180, May.
    6. Niu, Huimin & Zhou, Xuesong & Tian, Xiaopeng, 2018. "Coordinating assignment and routing decisions in transit vehicle schedules: A variable-splitting Lagrangian decomposition approach for solution symmetry breaking," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 70-101.
    7. Timo Gschwind & Stefan Irnich & Simon Emde & Christian Tilk, 2018. "Branch-Cut-and-Price for the Scheduling Deliveries with Time Windows in a Direct Shipping Network," Working Papers 1805, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    8. Ahmed Hadjar & Odile Marcotte & François Soumis, 2006. "A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem," Operations Research, INFORMS, vol. 54(1), pages 130-149, February.
    9. Timo Gschwind & Stefan Irnich & Christian Tilk & Simon Emde, 2020. "Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network," Journal of Scheduling, Springer, vol. 23(3), pages 363-377, June.
    10. Van der Perre, Peter P. G. & Van Oudheusden, Dirk D. L., 1997. "Reducing depot-related costs of large bus operators a case study in Bangkok," European Journal of Operational Research, Elsevier, vol. 96(1), pages 45-53, January.
    11. Chris Martin & David Jones & Pinar Keskinocak, 2003. "Optimizing On-Demand Aircraft Schedules for Fractional Aircraft Operators," Interfaces, INFORMS, vol. 33(5), pages 22-35, October.
    12. Uçar, Ezgi & İlker Birbil, Ş. & Muter, İbrahim, 2017. "Managing disruptions in the multi-depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 249-269.
    13. A. Mingozzi & M. A. Boschetti & S. Ricciardelli & L. Bianco, 1999. "A Set Partitioning Approach to the Crew Scheduling Problem," Operations Research, INFORMS, vol. 47(6), pages 873-888, December.
    14. Sundararajan Arunapuram & Kamlesh Mathur & Daniel Solow, 2003. "Vehicle Routing and Scheduling with Full Truckloads," Transportation Science, INFORMS, vol. 37(2), pages 170-182, May.
    15. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    16. Ciancio, Claudio & Laganà, Demetrio & Musmanno, Roberto & Santoro, Francesco, 2018. "An integrated algorithm for shift scheduling problems for local public transport companies," Omega, Elsevier, vol. 75(C), pages 139-153.
    17. Kliewer, Natalia & Mellouli, Taieb & Suhl, Leena, 2006. "A time-space network based exact optimization model for multi-depot bus scheduling," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1616-1627, December.
    18. Knut Haase & Guy Desaulniers & Jacques Desrosiers, 2001. "Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems," Transportation Science, INFORMS, vol. 35(3), pages 286-303, August.
    19. Jing-Quan Li, 2014. "Transit Bus Scheduling with Limited Energy," Transportation Science, INFORMS, vol. 48(4), pages 521-539, November.
    20. Gkiotsalitis, K. & Iliopoulou, C. & Kepaptsoglou, K., 2023. "An exact approach for the multi-depot electric bus scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 306(1), pages 189-206.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:44:y:1998:i:12-part-1:p:1637-1649. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.