IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v38y2004i4p447-458.html
   My bibliography  Save this article

A Robust Solution Approach to the Dynamic Vehicle Scheduling Problem

Author

Listed:
  • Dennis Huisman

    (Erasmus Center for Optimization in Public Transport (ECOPT), and Econometric Institute, Erasmus University Rotterdam, P.O. Box 1738, NL-3000 DR Rotterdam, The Netherlands)

  • Richard Freling

    (In memoriam: Richard Freling passed away on January 29, 2002, at the age of 34. He was with Erasmus Center for Optimization in Public Transport (ECOPT), and Econometric Institute, Erasmus University Rotterdam, The Netherlands)

  • Albert P. M. Wagelmans

    (Erasmus Center for Optimization in Public Transport (ECOPT), and Econometric Institute, Erasmus University Rotterdam, P.O. Box 1738, NL-3000 DR Rotterdam, The Netherlands)

Abstract

This paper presents a solution approach to the dynamic vehicle scheduling problem. This approach consists of solving a sequence of optimization problems, where we take into account different scenarios for future travel times. We discuss the potential benefit of our approach compared to the traditional one, where the vehicle scheduling problem is solved only once for a whole period and the travel times are assumed to be fixed. Because in the multiple-depot case we cannot solve the problem exactly within reasonable computation time, we use a “cluster-reschedule” heuristic where we first assign trips to depots by solving the static problem and then solve dynamic single-depot problems. We use new mathematical formulations of these problems that allow fast solution by standard optimization software. Results of a computational study with real-life data are presented, in which we compare different variants of our approach and perform a sensitivity analysis with respect to deviations of the actual travel times from estimated ones.

Suggested Citation

  • Dennis Huisman & Richard Freling & Albert P. M. Wagelmans, 2004. "A Robust Solution Approach to the Dynamic Vehicle Scheduling Problem," Transportation Science, INFORMS, vol. 38(4), pages 447-458, November.
    • Handle: RePEc:inm:ortrsc:v:38:y:2004:i:4:p:447-458
    DOI: 10.1287/trsc.1030.0069
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1030.0069
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1030.0069?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. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2000. "Diversion Issues in Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 34(4), pages 426-438, November.
    2. 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.
    3. Warren B. Powell & Michael T. Towns & Arun Marar, 2000. "On the Value of Optimal Myopic Solutions for Dynamic Routing and Scheduling Problems in the Presence of User Noncompliance," Transportation Science, INFORMS, vol. 34(1), pages 67-85, February.
    4. 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.
    5. 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.
    6. ,, 2000. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 16(2), pages 287-299, April.
    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. Huisman, Dennis & Wagelmans, Albert P.M., 2006. "A solution approach for dynamic vehicle and crew scheduling," European Journal of Operational Research, Elsevier, vol. 172(2), pages 453-471, July.
    2. Dennis Huisman & Richard Freling & Albert P. M. Wagelmans, 2005. "Multiple-Depot Integrated Vehicle and Crew Scheduling," Transportation Science, INFORMS, vol. 39(4), pages 491-502, November.
    3. Balázs Dávid & Miklós Krész, 2017. "The dynamic vehicle rescheduling problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(4), pages 809-830, December.
    4. Bastian Amberg & Boris Amberg & Natalia Kliewer, 2019. "Robust Efficiency in Urban Public Transportation: Minimizing Delay Propagation in Cost-Efficient Bus and Driver Schedules," Service Science, INFORMS, vol. 53(1), pages 89-112, February.
    5. Guedes, Pablo C. & Borenstein, Denis, 2018. "Real-time multi-depot vehicle type rescheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 217-234.
    6. Li, Jing-Quan & Mirchandani, Pitu B. & Borenstein, Denis, 2009. "Real-time vehicle rerouting problems with time windows," European Journal of Operational Research, Elsevier, vol. 194(3), pages 711-727, May.
    7. Shen, Yindong & Xu, Jia & Li, Jingpeng, 2016. "A probabilistic model for vehicle scheduling based on stochastic trip times," Transportation Research Part B: Methodological, Elsevier, vol. 85(C), pages 19-31.
    8. 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.
    9. van Lieshout, R.N. & Mulder, J. & Huisman, D., 2016. "The Vehicle Rescheduling Problem with Retiming," Econometric Institute Research Papers EI2016-37, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    10. Ibarra-Rojas, O.J. & Delgado, F. & Giesen, R. & Muñoz, J.C., 2015. "Planning, operation, and control of bus transport systems: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 38-75.

    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. Marlin W. Ulmer & Justin C. Goodson & Dirk C. Mattfeld & Marco Hennig, 2019. "Offline–Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests," Service Science, INFORMS, vol. 53(1), pages 185-202, February.
    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. Zolfagharinia, Hossein & Haughton, Michael A., 2017. "Operational flexibility in the truckload trucking industry," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 437-460.
    4. Farzaneh Karami & Wim Vancroonenburg & Greet Vanden Berghe, 2020. "A periodic optimization approach to dynamic pickup and delivery problems with time windows," Journal of Scheduling, Springer, vol. 23(6), pages 711-731, December.
    5. Mofidi, Seyed Shahab & Pazour, Jennifer A., 2019. "When is it beneficial to provide freelance suppliers with choice? A hierarchical approach for peer-to-peer logistics platforms," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 1-23.
    6. Markó Horváth & Tamás Kis, 2019. "Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(1), pages 39-67, March.
    7. 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.
    8. Jan Brinkmann & Marlin W. Ulmer & Dirk C. Mattfeld, 2020. "The multi-vehicle stochastic-dynamic inventory routing problem for bike sharing systems," Business Research, Springer;German Academic Association for Business Research, vol. 13(1), pages 69-92, April.
    9. Pan, Hanchuan & Liu, Zhigang & Yang, Lixing & Liang, Zhe & Wu, Qiang & Li, Sijie, 2021. "A column generation-based approach for integrated vehicle and crew scheduling on a single metro line with the fully automatic operation system by partial supervision," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    10. Ingmar Steinzen & Vitali Gintner & Leena Suhl & Natalia Kliewer, 2010. "A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots," Transportation Science, INFORMS, vol. 44(3), pages 367-382, August.
    11. Zolfagharinia, Hossein & Haughton, Michael, 2016. "Effective truckload dispatch decision methods with incomplete advance load information," European Journal of Operational Research, Elsevier, vol. 252(1), pages 103-121.
    12. Perumal, S.S.G. & Dollevoet, T.A.B. & Huisman, D. & Lusby, R.M. & Larsen, J. & Riis, M., 2020. "Solution Approaches for Vehicle and Crew Scheduling with Electric Buses," Econometric Institute Research Papers EI-2020-02, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    13. Jing-Quan Li, 2014. "Transit Bus Scheduling with Limited Energy," Transportation Science, INFORMS, vol. 48(4), pages 521-539, November.
    14. Zolfagharinia, Hossein & Haughton, Michael, 2014. "The benefit of advance load information for truckload carriers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 34-54.
    15. Stevanovic Dalibor, 2016. "Common time variation of parameters in reduced-form macroeconomic models," Studies in Nonlinear Dynamics & Econometrics, De Gruyter, vol. 20(2), pages 159-183, April.
    16. Chiara Oostuizen & Sara S. Grobbelaar & Wouter G. Bam, 2018. "Project Portfolio Management Best Practice and Implementation: A South African Perspective," International Journal of Innovation and Technology Management (IJITM), World Scientific Publishing Co. Pte. Ltd., vol. 15(04), pages 1-24, August.
    17. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    18. José M. Maisog & Andrew T. DeMarco & Karthik Devarajan & Stanley Young & Paul Fogel & George Luta, 2021. "Assessing Methods for Evaluating the Number of Components in Non-Negative Matrix Factorization," Mathematics, MDPI, vol. 9(22), pages 1-13, November.
    19. Lennart Bondesson, 2002. "On the Lévy Measure of the Lognormal and the LogCauchy Distributions," Methodology and Computing in Applied Probability, Springer, vol. 4(3), pages 243-256, September.
    20. A. Fadlelmawla & M. Al-Otaibi, 2005. "Analysis of the Water Resources Status in Kuwait," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 19(5), pages 555-570, October.

    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:ortrsc:v:38:y:2004:i:4:p:447-458. 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.