1 Search Results for "Hartleb, Johann"

Document
DOI: 10.4230/OASIcs.ATMOS.2020.15
A Rolling Horizon Heuristic with Optimality Guarantee for an On-Demand Vehicle Scheduling Problem

Authors: Johann Hartleb and Marie Schmidt

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{hartleb_et_al:OASIcs.ATMOS.2020.15,
  author =	{Hartleb, Johann and Schmidt, Marie},
  title =	{{A Rolling Horizon Heuristic with Optimality Guarantee for an On-Demand Vehicle Scheduling Problem}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{15:1--15:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.15},
  URN =		{urn:nbn:de:0030-drops-131513},
  doi =		{10.4230/OASIcs.ATMOS.2020.15},
  annote =	{Keywords: Rolling Horizon Heuristic, Vehicle Scheduling, Network Flow}
}
  • Refine by Author
  • 1 Hartleb, Johann
  • 1 Schmidt, Marie

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Network flows
  • 1 Theory of computation → Network flows

  • Refine by Keyword
  • 1 Network Flow
  • 1 Rolling Horizon Heuristic
  • 1 Vehicle Scheduling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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