Document Open Access Logo

A Rolling Horizon Heuristic with Optimality Guarantee for an On-Demand Vehicle Scheduling Problem

Authors Johann Hartleb , Marie Schmidt

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.15.pdf
  • Filesize: 0.61 MB
  • 18 pages

Document Identifiers

Author Details

Johann Hartleb
  • Rotterdam School of Management, Erasmus University Rotterdam, The Netherlands
  • Institute for Road and Transport Science, University of Stuttgart, Germany
Marie Schmidt
  • Rotterdam School of Management, Erasmus University Rotterdam, The Netherlands

Cite AsGet BibTex

Johann Hartleb and Marie Schmidt. A Rolling Horizon Heuristic with Optimality Guarantee for an On-Demand Vehicle Scheduling Problem. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/OASIcs.ATMOS.2020.15

Abstract

We consider a basic vehicle scheduling problem that arises in the context of travel demand models: Given demanded vehicle trips, what is the minimal number of vehicles needed to fulfill the demand? In this paper, we model the vehicle scheduling problem as a network flow problem. Since instances arising in the context of travel demand models are often so big that the network flow model becomes intractable, we propose using a rolling horizon heuristic to split huge problem instances into smaller subproblems and solve them independently to optimality. By letting the horizons of the subproblems overlap, it is possible to look ahead to the demand of the next subproblem. We prove that composing the solutions of the subproblems yields an optimal solution to the whole problem if the overlap of the horizons is sufficiently large. Our experiments show that this approach is not only suitable for solving extremely large instances that are intractable as a whole, but it is also possible to decrease the solution time for large instances compared to a comprehensive approach.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
  • Theory of computation → Network flows
  • Mathematics of computing → Network flows
Keywords
  • Rolling Horizon Heuristic
  • Vehicle Scheduling
  • Network Flow

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. Network flows. Working paper (Sloan School of Management); 2059-88. Cambridge, Mass.: Alfred P. Sloan School of Management, Massachusetts Institute of Technology, 1988. URL: https://dspace.mit.edu/handle/1721.1/49424.
  2. Joschka Bischoff, Michal Maciejewski, and Kai Nagel. City-wide shared taxis: A simulation study in Berlin. In 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC), pages 275-280. IEEE, 2017. Google Scholar
  3. Stefan Bunte and Natalia Kliewer. An overview on vehicle scheduling models. Public Transport, 1(4):299-317, 2009. Google Scholar
  4. Samuela Carosi, Antonio Frangioni, Laura Galli, Leopoldo Girardi, and Giuliano Vallese. A matheuristic for integrated timetabling and vehicle scheduling. Transportation Research Part B: Methodological, 127:99-124, 2019. Google Scholar
  5. A El-Azm. The minimum fleet size problem and its applications to bus scheduling. In Computer scheduling of public transport 2, pages 493-512, 1985. Google Scholar
  6. Daniel J Fagnant and Kara M Kockelman. Dynamic ride-sharing and fleet sizing for a system of shared autonomous vehicles in Austin, Texas. Transportation, 45(1):143-158, 2018. Google Scholar
  7. Brian A Foster and David M Ryan. An integer programming approach to the vehicle scheduling problem. Journal of the Operational Research Society, 27(2):367-384, 1976. Google Scholar
  8. Markus Friedrich, Maximilian Hartl, and Christoph Magg. A modeling approach for matching ridesharing trips within macroscopic travel demand models. Transportation, 45(6):1639-1653, 2018. URL: https://doi.org/10.1007/s11116-018-9957-5.
  9. Michael R Garey and David S Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979. Google Scholar
  10. Johann Hartleb, Markus Friedrich, and Emely Richter. Umlaufbildung für on demand-fahrzeugflotten in makroskopischen nachfragemodellen (preprint). In HEUREKA'20: Optimierung in Verkehr und Transport, FGSV 002/127, 2020. Google Scholar
  11. Michael Heilig, Tim Hilgert, Nicolai Mallig, Martin Kagerbauer, and Peter Vortisch. Potentials of autonomous vehicles in a changing private transportation system – a case study in the Stuttgart region. Transportation research procedia, 26:13-21, 2017. Google Scholar
  12. Tao Liu and Avishai Avi Ceder. Battery-electric transit vehicle scheduling with optimal number of stationary chargers. Transportation Research Part C: Emerging Technologies, 114:118-139, 2020. Google Scholar
  13. Emely Richter, Markus Friedrich, Alexander Migl, and Johann Hartleb. Integrating ridesharing services with automated vehicles into macroscopic travel demand models. In 2019 6th International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), pages 1-8. IEEE, 2019. Google Scholar
  14. Anita Schöbel. An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation. Transportation Research Part C: Emerging Technologies, 74:348-365, 2017. Google Scholar
  15. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003. Google Scholar
  16. Min Wen, Esben Linde, Stefan Ropke, P Mirchandani, and Allan Larsen. An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem. Computers & Operations Research, 76:73-83, 2016. Google Scholar
  17. David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact