4 Search Results for "Scheffler, Robert"

Document
DOI: 10.4230/OASIcs.ATMOS.2023.1
Optimal Bicycle Routes with Few Signal Stops

Authors: Ekkehard Köhler, Markus Rogge, Robert Scheffler, and Martin Strehler

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
With the increasing popularity of cycling as a mode of transportation, there is a growing need for efficient routing algorithms that consider the specific requirements of cyclists. This paper studies the optimization of bicycle routes while minimizing the number of stops at traffic signals. In particular, we consider three different types of stopping strategies and three types of routes, namely paths, trails, and walks. We present hardness results as well as a pseudo-polynomial algorithm for the problem of computing an optimal route with respect to a pre-defined stop bound.
Cite as

Ekkehard Köhler, Markus Rogge, Robert Scheffler, and Martin Strehler. Optimal Bicycle Routes with Few Signal Stops. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kohler_et_al:OASIcs.ATMOS.2023.1,
  author =	{K\"{o}hler, Ekkehard and Rogge, Markus and Scheffler, Robert and Strehler, Martin},
  title =	{{Optimal Bicycle Routes with Few Signal Stops}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{1:1--1:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.1},
  URN =		{urn:nbn:de:0030-drops-187628},
  doi =		{10.4230/OASIcs.ATMOS.2023.1},
  annote =	{Keywords: Constrained shortest path, traffic signals, bicycle routes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.13
Linear Time LexDFS on Chordal Graphs

Authors: Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, and Martin Strehler

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

Abstract
Lexicographic Depth First Search (LexDFS) is a special variant of a Depth First Search (DFS), which was introduced by Corneil and Krueger in 2008. While this search has been used in various applications, in contrast to other graph searches, no general linear time implementation is known to date. In 2014, Köhler and Mouatadid achieved linear running time to compute some special LexDFS orderings for cocomparability graphs. In this paper, we present a linear time implementation of LexDFS for chordal graphs. Our algorithm even implements the extended version LexDFS^+ and is, therefore, able to find any LexDFS ordering for this graph class. To the best of our knowledge this is the first unrestricted linear time implementation of LexDFS on a non-trivial graph class. In the algorithm we use a search tree computed by Lexicographic Breadth First Search (LexBFS).
Cite as

Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, and Martin Strehler. Linear Time LexDFS on Chordal Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.ESA.2020.13,
  author =	{Beisegel, Jesse and K\"{o}hler, Ekkehard and Scheffler, Robert and Strehler, Martin},
  title =	{{Linear Time LexDFS on Chordal Graphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{13:1--13:13},
  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.13},
  URN =		{urn:nbn:de:0030-drops-128790},
  doi =		{10.4230/LIPIcs.ESA.2020.13},
  annote =	{Keywords: LexDFS, chordal graphs, linear time implementation, search trees, LexBFS}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.9
Optimizing Traffic Signal Settings for Public Transport Priority

Authors: Robert Scheffler and Martin Strehler

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
In order to promote public transport many municipalities use traffic signal control with a priority for buses or trams. In this paper, we address the problem of finding optimal passive transit signal priority settings. Building on a cyclically time-expanded network model for the combined traffic assignment traffic signal coordination problem, we introduce a suitable queuing model and several modifications to model public transport vehicles appropriately. We evaluate the applicability of this approach by computing and analyzing optimal solutions for several instances of a real-world scenario.
Cite as

Robert Scheffler and Martin Strehler. Optimizing Traffic Signal Settings for Public Transport Priority. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{scheffler_et_al:OASIcs.ATMOS.2017.9,
  author =	{Scheffler, Robert and Strehler, Martin},
  title =	{{Optimizing Traffic Signal Settings for Public Transport Priority}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{9:1--9:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.9},
  URN =		{urn:nbn:de:0030-drops-79005},
  doi =		{10.4230/OASIcs.ATMOS.2017.9},
  annote =	{Keywords: transit signal priority, traffic flow, traffic signal optimization, cyclically time-expanded network, public transport}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.8
Optimizing Traffic Signal Timings for Mega Events

Authors: Robert Scheffler and Martin Strehler

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
Most approaches for optimizing traffic signal timings deal with the daily traffic. However, there are a few occasional events like football matches or concerts of musicians that lead to exceptional traffic situations. Still, such events occur more or less regularly and place and time are known in advance. Hence, it is possible to anticipate such events with special signal timings. In this paper, we present an extension of a cyclically time-expanded network flow model and a corresponding mixed-integer linear programming formulation for simultaneously optimizing traffic signal timings and traffic assignment for such events. Besides the mathematical analysis of this approach, we demonstrate its capabilities by computing signal timings for a real world scenario.
Cite as

Robert Scheffler and Martin Strehler. Optimizing Traffic Signal Timings for Mega Events. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{scheffler_et_al:OASIcs.ATMOS.2016.8,
  author =	{Scheffler, Robert and Strehler, Martin},
  title =	{{Optimizing Traffic Signal Timings for Mega Events}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{8:1--8:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.8},
  URN =		{urn:nbn:de:0030-drops-65323},
  doi =		{10.4230/OASIcs.ATMOS.2016.8},
  annote =	{Keywords: traffic flow, traffic signal timings, cyclically time-expanded network, mega event, exceptional traffic}
}
  • Refine by Author
  • 4 Scheffler, Robert
  • 4 Strehler, Martin
  • 2 Köhler, Ekkehard
  • 1 Beisegel, Jesse
  • 1 Rogge, Markus

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Mathematics of computing → Trees
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 2 cyclically time-expanded network
  • 2 traffic flow
  • 1 Constrained shortest path
  • 1 LexBFS
  • 1 LexDFS
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2016
  • 1 2017
  • 1 2020
  • 1 2023

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