4 Search Results for "Radermacher, Marcel"


Document
Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks

Authors: Ben Strasser, Dorothea Wagner, and Tim Zeitz

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


Abstract
We study the problem of computing shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques follow a two-phase approach: In a preprocessing step, an index is built. The index depends on the road network and the traffic patterns but not on the path start and end. The latter are the input of the query phase, in which shortest paths are computed. All existing techniques have either large index size, slow query running times, or may compute suboptimal paths. In this work, we introduce CATCHUp (Customizable Approximated Time-dependent Contraction Hierarchies through Unpacking), the first algorithm that simultaneously achieves all three objectives. The core idea of CATCHUp is to store paths instead of travel times at shortcuts. Shortcut travel times are derived lazily from the stored paths. We perform an experimental study on a set of real world instances and compare our approach with state-of-the-art techniques. Our approach achieves the fastest preprocessing, competitive query running times and up to 30 times smaller indexes than competing approaches.

Cite as

Ben Strasser, Dorothea Wagner, and Tim Zeitz. Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 81:1-81:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{strasser_et_al:LIPIcs.ESA.2020.81,
  author =	{Strasser, Ben and Wagner, Dorothea and Zeitz, Tim},
  title =	{{Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{81:1--81:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.81},
  URN =		{urn:nbn:de:0030-drops-129479},
  doi =		{10.4230/LIPIcs.ESA.2020.81},
  annote =	{Keywords: realistic road networks, time-dependent route planning, shortest paths}
}
Document
Engineering Negative Cycle Canceling for Wind Farm Cabling

Authors: Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
In a wind farm turbines convert wind energy into electrical energy. The generation of each turbine is transmitted, possibly via other turbines, to a substation that is connected to the power grid. On every possible interconnection there can be at most one of various different cable types. Each cable type comes with a cost per unit length and with a capacity. Designing a cost-minimal cable layout for a wind farm to feed all turbine production into the power grid is called the Wind Farm Cabling Problem (WCP). We consider a formulation of WCP as a flow problem on a graph where the cost of a flow on an edge is modeled by a step function originating from the cable types. Recently, we presented a proof-of-concept for a negative cycle canceling-based algorithm for WCP [Sascha Gritzbach et al., 2018]. We extend key steps of that heuristic and build a theoretical foundation that explains how this heuristic tackles the problems arising from the special structure of WCP. A thorough experimental evaluation identifies the best setup of the algorithm and compares it to existing methods from the literature such as Mixed-integer Linear Programming (MILP) and Simulated Annealing (SA). The heuristic runs in a range of half a millisecond to under two minutes on instances with up to 500 turbines. It provides solutions of similar quality compared to both competitors with running times of one hour and one day. When comparing the solution quality after a running time of two seconds, our algorithm outperforms the MILP- and SA-approaches, which allows it to be applied in interactive wind farm planning.

Cite as

Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf. Engineering Negative Cycle Canceling for Wind Farm Cabling. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gritzbach_et_al:LIPIcs.ESA.2019.55,
  author =	{Gritzbach, Sascha and Ueckerdt, Torsten and Wagner, Dorothea and Wegner, Franziska and Wolf, Matthias},
  title =	{{Engineering Negative Cycle Canceling for Wind Farm Cabling}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{55:1--55:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.55},
  URN =		{urn:nbn:de:0030-drops-111766},
  doi =		{10.4230/LIPIcs.ESA.2019.55},
  annote =	{Keywords: Negative Cycle Canceling, Step Cost Function, Wind Farm Planning}
}
Document
Geometric Crossing-Minimization - A Scalable Randomized Approach

Authors: Marcel Radermacher and Ignaz Rutter

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
We consider the minimization of edge-crossings in geometric drawings of graphs G=(V, E), i.e., in drawings where each edge is depicted as a line segment. The respective decision problem is NP-hard [Daniel Bienstock, 1991]. Crossing-minimization, in general, is a popular theoretical research topic; see Vrt'o [Imrich Vrt'o, 2014]. In contrast to theory and the topological setting, the geometric setting did not receive a lot of attention in practice. Prior work [Marcel Radermacher et al., 2018] is limited to the crossing-minimization in geometric graphs with less than 200 edges. The described heuristics base on the primitive operation of moving a single vertex v to its crossing-minimal position, i.e., the position in R^2 that minimizes the number of crossings on edges incident to v. In this paper, we introduce a technique to speed-up the computation by a factor of 20. This is necessary but not sufficient to cope with graphs with a few thousand edges. In order to handle larger graphs, we drop the condition that each vertex v has to be moved to its crossing-minimal position and compute a position that is only optimal with respect to a small random subset of the edges. In our theoretical contribution, we consider drawings that contain for each edge uv in E and each position p in R^2 for v o(|E|) crossings. In this case, we prove that with a random subset of the edges of size Theta(k log k) the co-crossing number of a degree-k vertex v, i.e., the number of edge pairs uv in E, e in E that do not cross, can be approximated by an arbitrary but fixed factor delta with high probability. In our experimental evaluation, we show that the randomized approach reduces the number of crossings in graphs with up to 13 000 edges considerably. The evaluation suggests that depending on the degree-distribution different strategies result in the fewest number of crossings.

Cite as

Marcel Radermacher and Ignaz Rutter. Geometric Crossing-Minimization - A Scalable Randomized Approach. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 76:1-76:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{radermacher_et_al:LIPIcs.ESA.2019.76,
  author =	{Radermacher, Marcel and Rutter, Ignaz},
  title =	{{Geometric Crossing-Minimization - A Scalable Randomized Approach}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{76:1--76:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.76},
  URN =		{urn:nbn:de:0030-drops-111977},
  doi =		{10.4230/LIPIcs.ESA.2019.76},
  annote =	{Keywords: Geometric Crossing Minimization, Randomization, Approximation, VC-Dimension, Experiments}
}
Document
Evolution and Evaluation of the Penalty Method for Alternative Graphs

Authors: Moritz Kobitzsch, Marcel Radermacher, and Dennis Schieferdecker

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)


Abstract
Computing meaningful alternative routes in a road network is a complex problem -- already giving a clear definition of a best alternative seems to be impossible. Still, multiple methods describe how to compute reasonable alternative routes, each according to their own quality criteria. Among these methods, the penalty method has received much less attention than the via-node or plateaux based approaches. A mayor cause for the lack of interest might be the unavailability of an efficient implementation. In this paper, we take a closer look at the penalty method and extend upon its ideas. We provide the first viable implementation --suitable for interactive use-- using dynamic runtime adjustments to perform up to multiple orders of magnitude faster queries than previous implementations. Using our new implementation, we thoroughly evaluate the penalty method for its flaws and benefits.

Cite as

Moritz Kobitzsch, Marcel Radermacher, and Dennis Schieferdecker. Evolution and Evaluation of the Penalty Method for Alternative Graphs. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 94-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{kobitzsch_et_al:OASIcs.ATMOS.2013.94,
  author =	{Kobitzsch, Moritz and Radermacher, Marcel and Schieferdecker, Dennis},
  title =	{{Evolution and Evaluation of the Penalty Method for Alternative Graphs}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{94--107},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.94},
  URN =		{urn:nbn:de:0030-drops-42474},
  doi =		{10.4230/OASIcs.ATMOS.2013.94},
  annote =	{Keywords: Alternatives, Routing, Shortest Paths, Penalties, Parallelization}
}
  • Refine by Author
  • 2 Radermacher, Marcel
  • 2 Wagner, Dorothea
  • 1 Gritzbach, Sascha
  • 1 Kobitzsch, Moritz
  • 1 Rutter, Ignaz
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Network flows
  • 1 Mathematics of computing → Network optimization
  • 1 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 1 Alternatives
  • 1 Approximation
  • 1 Experiments
  • 1 Geometric Crossing Minimization
  • 1 Negative Cycle Canceling
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2019
  • 1 2013
  • 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