3 Search Results for "Nonner, Tim"

Document
DOI: 10.4230/OASIcs.ATMOS.2014.15
Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments

Authors: Tim Nonner and Marco Laumanns

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
The Shortest Path with Alternatives (SPA) policy differs from classical shortest path routing in the following way: instead of providing an exact list of means of transportation to follow, this policy gives such a list for each stop, and the traveler is supposed to pick the first option from this list when waiting at some stop. First, we show that an optimal policy of this type can be computed in polynomial time for uniform arrival times under reasonable assumptions. A similar result was so far only known for Poisson arrival times, which are less realistic for frequency-based public transportation systems. Second, we experimentally evaluate such policies. In this context, our main finding is that SPA policies are surprisingly competitive compared to traditional shortest paths, and moreover yield a significant reduction of waiting times, and therefore improvement of user experience, compared to similar greedy approaches. Specifically, for roughly 25% of considered cases, we could decrease the expected waiting time by at least 20%. To run our experiments, we also describe a tool-chain to derive the necessary information from the popular GTFS-format, therefore allowing the application of SPA policies to a wide range of public transportation systems.
Cite as

Tim Nonner and Marco Laumanns. Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 15-24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{nonner_et_al:OASIcs.ATMOS.2014.15,
  author =	{Nonner, Tim and Laumanns, Marco},
  title =	{{Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{15--24},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.15},
  URN =		{urn:nbn:de:0030-drops-47494},
  doi =		{10.4230/OASIcs.ATMOS.2014.15},
  annote =	{Keywords: Shortest Path, Stochastic Optimization, Public Transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.34
Online Train Shunting

Authors: Vianney Boeuf and Frédéric Meunier

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
At the occasion of ATMOS 2012, Tim Nonner and Alexander Souza defined a new train shunting problem that can roughly be described as follows. We are given a train visiting stations in a given order and cars located at some source stations. Each car has a target station. During the trip of the train, the cars are added to the train at their source stations and removed from it at their target stations. An addition or a removal of a car in the strict interior of the train incurs a cost higher than when the operation is performed at the end of the train. The problem consists in minimizing the total cost, and thus, at each source station of a car, the position the car takes in the train must be carefully decided. Among other results, Nonner and Souza showed that this problem is polynomially solvable by reducing the problem to the computation of a minimum independent set in a bipartite graph. They worked in the offline setting, i.e. the sources and the targets of all cars are known before the trip of the train starts. We study the online version of the problem, in which cars become known at their source stations. We derive a 2-competitive algorithm and prove than no better ratios are achievable. Other related questions are also addressed.
Cite as

Vianney Boeuf and Frédéric Meunier. Online Train Shunting. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 34-45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{boeuf_et_al:OASIcs.ATMOS.2014.34,
  author =	{Boeuf, Vianney and Meunier, Fr\'{e}d\'{e}ric},
  title =	{{Online Train Shunting}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{34--45},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.34},
  URN =		{urn:nbn:de:0030-drops-47512},
  doi =		{10.4230/OASIcs.ATMOS.2014.34},
  annote =	{Keywords: Bipartite graph, competitive analysis, online algorithm, train shunting problem, vertex cover}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.97
Optimal Algorithms for Train Shunting and Relaxed List Update Problems

Authors: Tim Nonner and Alexander Souza

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
This paper considers a Train Shunting problem which occurs in cargo train organizations: We have a locomotive travelling along a track segment and a collection of n cars, where each car has a source and a target. Whenever the train passes the source of a car, it needs to be added to the train, and on the target, the respective car needs to be removed. Any such operation at the end of the train incurs low shunting cost, but adding or removing truly in the interior requires a more complex shunting operation and thus yields high cost. The objective is to schedule the adding and removal of cars as to minimize the total cost. This problem can also be seen as a relaxed version of the well-known List Update problem, which may be of independent interest. We derive polynomial time algorithms for Train Shunting by reducing this problem to finding independent sets in bipartite graphs. This allows us to treat several variants of the problem in a generic way. Specifically, we obtain an algorithm with running time O(n^{5/2}) for the uniform case, where all low costs and all high costs are identical, respectively. Furthermore, for the non-uniform case we have running time of O(n^3). Both versions translate to a symmetric variant, where it is also allowed to add and remove cars at the front of the train at low cost. In addition, we formulate a dynamic program with running time O(n^4), which exploits the special structure of the graph. Although the running time is worse, it allows us to solve many extensions, e.g., prize-collection, economies of scale, and dependencies between consecutive stations.
Cite as

Tim Nonner and Alexander Souza. Optimal Algorithms for Train Shunting and Relaxed List Update Problems. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 97-107, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{nonner_et_al:OASIcs.ATMOS.2012.97,
  author =	{Nonner, Tim and Souza, Alexander},
  title =	{{Optimal Algorithms for Train Shunting and Relaxed List Update Problems}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{97--107},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.97},
  URN =		{urn:nbn:de:0030-drops-37066},
  doi =		{10.4230/OASIcs.ATMOS.2012.97},
  annote =	{Keywords: Train shunting, optimal algorithm, independent set, dynamic programming}
}
  • Refine by Author
  • 2 Nonner, Tim
  • 1 Boeuf, Vianney
  • 1 Laumanns, Marco
  • 1 Meunier, Frédéric
  • 1 Souza, Alexander

  • Refine by Classification

  • Refine by Keyword
  • 1 Bipartite graph
  • 1 Public Transportation
  • 1 Shortest Path
  • 1 Stochastic Optimization
  • 1 Train shunting
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2014
  • 1 2012

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact