IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v85y2016icp19-31.html
   My bibliography  Save this article

A probabilistic model for vehicle scheduling based on stochastic trip times

Author

Listed:
  • Shen, Yindong
  • Xu, Jia
  • Li, Jingpeng

Abstract

Vehicle scheduling plays a profound role in public transit planning. Traditional approaches for the Vehicle Scheduling Problem (VSP) are based on a set of predetermined trips in a given timetable. Each trip contains a departure point/time and an arrival point/time whilst the trip time (i.e. the time duration of a trip) is fixed. Based on fixed durations, the resulting schedule is hard to comply with in practice due to the variability of traffic and driving conditions. To enhance the robustness of the schedule to be compiled, the VSP based on stochastic trip times instead of fixed ones is studied. The trip times follow the probability distributions obtained from the data captured by Automatic Vehicle Locating (AVL) systems. A network flow model featuring the stochastic trips is devised to better represent this problem, meanwhile the compatibility of any pair of trips is redefined based on trip time distributions instead of fixed values as traditionally done. A novel probabilistic model of the VSP is proposed with the objectives of minimizing the total cost and maximizing the on-time performance. Experiments show that the probabilistic model may lead to more robust schedules without increasing fleet size.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:85:y:2016:i:c:p:19-31
    DOI: 10.1016/j.trb.2015.12.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261515002830
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2015.12.016?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. Ibarra-Rojas, Omar J. & Giesen, Ricardo & Rios-Solis, Yasmin A., 2014. "An integrated approach for timetabling and vehicle scheduling problems to analyze the trade-off between level of service and operating costs of transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 35-46.
    3. Michael Ball & Lawrence Bodin & Robert Dial, 1983. "A Matching Based Heuristic for Scheduling Mass Transit Crews and Vehicles," Transportation Science, INFORMS, vol. 17(1), pages 4-31, February.
    4. 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.
    5. Jiamin Zhao & Maged Dessouky & Satish Bukkapatnam, 2006. "Optimal Slack Time for Schedule-Based Transit Operations," Transportation Science, INFORMS, vol. 40(4), pages 529-539, November.
    6. Hassold, Stephan & Ceder, Avishai (Avi), 2014. "Public transport vehicle scheduling featuring multiple vehicle types," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 129-143.
    7. Salicrú, M. & Fleurent, C. & Armengol, J.M., 2011. "Timetable-based operation in urban transport: Run-time optimisation and improvements in the operating process," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(8), pages 721-740, October.
    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. Gavish, B. & Shlifer, E., 1979. "An approach for solving a class of transportation scheduling problems," European Journal of Operational Research, Elsevier, vol. 3(2), pages 122-134, March.
    10. 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.
    11. Xuan, Yiguang & Argote, Juan & Daganzo, Carlos F., 2011. "Dynamic bus holding strategies for schedule reliability: Optimal linear control and performance analysis," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1831-1845.
    12. Shen, Yindong & Peng, Kunkun & Chen, Kai & Li, Jingpeng, 2013. "Evolutionary crew scheduling with adaptive chromosomes," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 174-185.
    13. 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.
    14. Haghani, Ali & Banihashemi, Mohamadreza, 2002. "Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(4), pages 309-333, May.
    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. Wu, Weitiao & Lin, Yue & Liu, Ronghui & Jin, Wenzhou, 2022. "The multi-depot electric vehicle scheduling problem with power grid characteristics," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 322-347.
    2. 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.
    3. Ricard, Léa & Desaulniers, Guy & Lodi, Andrea & Rousseau, Louis-Martin, 2024. "Increasing schedule reliability in the multiple depot vehicle scheduling problem with stochastic travel time," Omega, Elsevier, vol. 127(C).
    4. Stanislav PALÚCH & Tomáš MAJER, 2017. "Kastor – A Vehicle And Crew Scheduling System For Regular Bus Passenger Transport," Transport Problems, Silesian University of Technology, Faculty of Transport, vol. 12(1), pages 103-110, March.
    5. Wenjing Wang & Yanyan Chen & Haodong Sun & Yusen Chen, 2021. "Multiple Binary Classification Model of Trip Chain Based on the Fusion of Internet Location Data and Transport Data," Sustainability, MDPI, vol. 13(21), pages 1-15, November.
    6. Cui, Shaohua & Gao, Kun & Yu, Bin & Ma, Zhenliang & Najafi, Arsalan, 2023. "Joint optimal vehicle and recharging scheduling for mixed bus fleets under limited chargers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 180(C).

    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. 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.
    2. 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.
    3. 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.
    4. Jing-Quan Li, 2014. "Transit Bus Scheduling with Limited Energy," Transportation Science, INFORMS, vol. 48(4), pages 521-539, November.
    5. 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.
    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. 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. Shyam S. G. Perumal & Jesper Larsen & Richard M. Lusby & Morten Riis & Tue R. L. Christensen, 2022. "A column generation approach for the driver scheduling problem with staff cars," Public Transport, Springer, vol. 14(3), pages 705-738, October.
    9. Ricard, Léa & Desaulniers, Guy & Lodi, Andrea & Rousseau, Louis-Martin, 2024. "Increasing schedule reliability in the multiple depot vehicle scheduling problem with stochastic travel time," Omega, Elsevier, vol. 127(C).
    10. Zhang, Wei & (Ato) Xu, Wangtu, 2017. "Simulation-based robust optimization for the schedule of single-direction bus transit route: The design of experiment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 203-230.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. Fonseca, João Paiva & van der Hurk, Evelien & Roberti, Roberto & Larsen, Allan, 2018. "A matheuristic for transfer synchronization through integrated timetabling and vehicle scheduling," Transportation Research Part B: Methodological, Elsevier, vol. 109(C), pages 128-149.
    17. 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.
    18. Li, Shukai & Liu, Ronghui & Yang, Lixing & Gao, Ziyou, 2019. "Robust dynamic bus controls considering delay disturbances and passenger demand uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 88-109.
    19. S. Sajikumar & D. Bijulal, 2022. "Zero bunching solution for a local public transport system with multiple-origins bus operation," Public Transport, Springer, vol. 14(3), pages 655-681, October.
    20. Gkiotsalitis, K. & Cats, O. & Liu, T. & Bult, J.M., 2023. "An exact optimization method for coordinating the arrival times of urban rail lines at a common corridor," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 178(C).

    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:eee:transb:v:85:y:2016:i:c:p:19-31. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.