Search Results

Documents authored by Delling, Daniel

Document
DOI: 10.4230/OASIcs.ATMOS.2021.11
Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles

Authors: Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J. West, Dennis Schieferdecker, and Daniel Delling

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
Electric Vehicle routing is often modeled as a Shortest Feasible Path Problem (SFPP), which minimizes total travel time while maintaining a non-zero State of Charge (SoC) along the route. However, the problem assumes perfect information about energy consumption and charging stations, which are difficult to even estimate in practice. Further, drivers might have varying risk tolerances for different trips. To overcome these limitations, we propose two generalizations to the SFPP; they compute the shortest feasible path for any initial SoC and, respectively, for every possible minimum SoC threshold. We present algorithmic solutions for each problem, and provide two constructs: Starting Charge Maps and Buffer Maps, which represent the tradeoffs between robustness of feasible routes and their travel times. The two constructs are useful in many ways, including presenting alternate routes or providing charging prompts to users. We evaluate the performance of our algorithms on realistic input instances.
Cite as

Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J. West, Dennis Schieferdecker, and Daniel Delling. Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rajan_et_al:OASIcs.ATMOS.2021.11,
  author =	{Rajan, Payas and Baum, Moritz and Wegner, Michael and Z\"{u}ndorf, Tobias and West, Christian J. and Schieferdecker, Dennis and Delling, Daniel},
  title =	{{Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{11:1--11:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.11},
  URN =		{urn:nbn:de:0030-drops-148807},
  doi =		{10.4230/OASIcs.ATMOS.2021.11},
  annote =	{Keywords: Electric Vehicles, Route Planning}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.26
Fast and Stable Repartitioning of Road Networks

Authors: Valentin Buchhold, Daniel Delling, Dennis Schieferdecker, and Michael Wegner

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We study the problem of graph partitioning for evolving road networks. While the road network of the world is mostly stable, small updates happen on a relatively frequent basis, as can been observed with the OpenStreetMap project (http://www.openstreetmap.org). For various reasons, professional applications demand the graph partition to stay roughly the same over time, and that changes are limited to areas where graph updates occur. In this work, we define the problem, present algorithms to satisfy the stability needs, and evaluate our techniques on continental-sized road networks. Besides the stability gains, we show that, when the changes are low and local, running our novel techniques is an order of magnitude faster than running graph partitioning from scratch.
Cite as

Valentin Buchhold, Daniel Delling, Dennis Schieferdecker, and Michael Wegner. Fast and Stable Repartitioning of Road Networks. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchhold_et_al:LIPIcs.SEA.2020.26,
  author =	{Buchhold, Valentin and Delling, Daniel and Schieferdecker, Dennis and Wegner, Michael},
  title =	{{Fast and Stable Repartitioning of Road Networks}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.26},
  URN =		{urn:nbn:de:0030-drops-121000},
  doi =		{10.4230/LIPIcs.SEA.2020.26},
  annote =	{Keywords: Graph repartitioning, stable partitions, road networks, algorithm engineering}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.8
Faster Transit Routing by Hyper Partitioning

Authors: Daniel Delling, Julian Dibbelt, Thomas Pajor, and Tobias Zündorf

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

Abstract
We present a preprocessing-based acceleration technique for computing bi-criteria Pareto-optimal journeys in public transit networks, based on the well-known RAPTOR algorithm [Delling et al 2015]. Our key idea is to first partition a hypergraph into cells, in which vertices correspond to routes (e.g., bus lines) and hyperedges to stops, and to then mark routes sufficient for optimal travel across cells. The query can then be restricted to marked routes and those in the source and target cells. This results in a practical approach, suitable for networks that are too large to be efficiently handled by the basic RAPTOR algorithm.
Cite as

Daniel Delling, Julian Dibbelt, Thomas Pajor, and Tobias Zündorf. Faster Transit Routing by Hyper Partitioning. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2017.8,
  author =	{Delling, Daniel and Dibbelt, Julian and Pajor, Thomas and Z\"{u}ndorf, Tobias},
  title =	{{Faster Transit Routing by Hyper Partitioning}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{8:1--8:14},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.8},
  URN =		{urn:nbn:de:0030-drops-78962},
  doi =		{10.4230/OASIcs.ATMOS.2017.8},
  annote =	{Keywords: Routing, speed-up techniques, public transport, partitioning}
}
Document
DOI: 10.4230/DagRep.6.3.24
Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111)

Authors: Daniel Delling, Camil Demetrescu, David S. Johnson, and Jan Vitek

Published in: Dagstuhl Reports, Volume 6, Issue 3 (2016)

Abstract
This report documents the talks and discussions at the Dagstuhl seminar 16111 "Rethinking Experimental Methods in Computing". The seminar brought together researchers from several computer science communities, including algorithm engineering, programming languages, information retrieval, high-performance computing, operations research, performance analysis, embedded systems, distributed systems, and software engineering. The main goals of the seminar were building a network of experimentalists and fostering a culture of sound quantitative experiments in computing. During the seminar, groups of participants have worked on distilling useful resources based on the collective experience gained in different communities and on planning actions to promote sound experimental methods and reproducibility efforts.
Cite as

Daniel Delling, Camil Demetrescu, David S. Johnson, and Jan Vitek. Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111). In Dagstuhl Reports, Volume 6, Issue 3, pp. 24-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{delling_et_al:DagRep.6.3.24,
  author =	{Delling, Daniel and Demetrescu, Camil and Johnson, David S. and Vitek, Jan},
  title =	{{Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111)}},
  pages =	{24--43},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{3},
  editor =	{Delling, Daniel and Demetrescu, Camil and Johnson, David S. and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.3.24},
  URN =		{urn:nbn:de:0030-drops-61463},
  doi =		{10.4230/DagRep.6.3.24},
  annote =	{Keywords: Algorithms, Benchmarks, Data sets, Experiments, Repeatability, Reproducibility, Software Artifacts, Statistics}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2012
OASIcs, Volume 25, ATMOS'12, Complete Volume

Authors: Daniel Delling and Leo Liberti

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

Abstract
OASIcs, Volume 25, ATMOS'12, Complete Volume
Cite as

12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{delling_et_al:OASIcs.ATMOS.2012,
  title =	{{OASIcs, Volume 25, ATMOS'12, Complete Volume}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  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},
  URN =		{urn:nbn:de:0030-drops-37255},
  doi =		{10.4230/OASIcs.ATMOS.2012},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2012.i
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Daniel Delling and Leo Liberti

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

Abstract
Frontmatter, Table of contents, Preface, Workshop Organization
Cite as

12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. i-xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2012.i,
  author =	{Delling, Daniel and Liberti, Leo},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{i--xi},
  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.i},
  URN =		{urn:nbn:de:0030-drops-36980},
  doi =		{10.4230/OASIcs.ATMOS.2012.i},
  annote =	{Keywords: Frontmatter, Table of contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.52
Faster Batched Shortest Paths in Road Networks

Authors: Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
We study the problem of computing batched shortest paths in road networks efficiently. Our focus is on computing paths from a single source to multiple targets (one-to-many queries). We perform a comprehensive experimental comparison of several approaches, including new ones. We conclude that a new extension of PHAST (a recent one-to-all algorithm), called RPHAST, has the best performance in most cases, often by orders of magnitude. When used to compute distance tables (many-to-many queries), RPHAST often outperforms all previous approaches.
Cite as

Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Faster Batched Shortest Paths in Road Networks. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 52-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2011.52,
  author =	{Delling, Daniel and Goldberg, Andrew V. and Werneck, Renato F.},
  title =	{{Faster Batched Shortest Paths in Road Networks}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{52--63},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.52},
  URN =		{urn:nbn:de:0030-drops-32663},
  doi =		{10.4230/OASIcs.ATMOS.2011.52},
  annote =	{Keywords: shortest paths, contraction hierarchies, many-to-many, one-to-many}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2009.2148
Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected

Authors: Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller-Hannemann

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)

Abstract
Speeding up multi-criteria search in real timetable information systems remains a challenge in spite of impressive progress achieved in recent years for related problems in road networks. Our goal is to perform multi-criteria range queries, that is, to find all Pareto-optimal connections with respect to travel time and number of transfers within a given start time interval. This problem can be modeled as a path search problem in a time- and event-dependent graph. In this paper, we investigate two key speed-up techniques for a multi-criteria variant of \textsc{Dijkstra}'s algorithm --- arc flags and contraction --- which seem to be strong candidates for railway networks, too. We describe in detail how these two techniques have to be adapted for a multi-criteria scenario and explain why we can expect only marginal speed-ups (compared to observations in road networks) from a direct implementation. Based on these insights we extend traditional arc-flags to \emph{time-period flags} and introduce \emph{route contraction} as a substitute for node contraction. A computational study on real queries demonstrates that these techniques combined with goal-directed search lead to a speed-up of factor 13.08 over the baseline variant for range queries for a full day.
Cite as

Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller-Hannemann. Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:OASIcs.ATMOS.2009.2148,
  author =	{Berger, Annabell and Delling, Daniel and Gebhardt, Andreas and M\"{u}ller-Hannemann, Matthias},
  title =	{{Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2148},
  URN =		{urn:nbn:de:0030-drops-21481},
  doi =		{10.4230/OASIcs.ATMOS.2009.2148},
  annote =	{Keywords: Timetable information, multi-criteria search, time-dependent networks, arc flags, contraction Timetable information, multi-criteria search, time-dependent networks, arc flags, contraction}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2009.2149
Arc-Flags in Dynamic Graphs

Authors: Emanuele Berrettini, Gianlorenzo D'Angelo, and Daniel Delling

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)

Abstract
Computation of quickest paths has undergoing a rapid development in recent years. It turns out that many high-performance route planning algorithms are made up of several basic ingredients. However, not all of those ingredients have been analyzed in a \emph{dynamic} scenario where edge weights change after preprocessing. In this work, we present how one of those ingredients, i.e., Arc-Flags can be applied in dynamic scenarios
Cite as

Emanuele Berrettini, Gianlorenzo D'Angelo, and Daniel Delling. Arc-Flags in Dynamic Graphs. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{berrettini_et_al:OASIcs.ATMOS.2009.2149,
  author =	{Berrettini, Emanuele and D'Angelo, Gianlorenzo and Delling, Daniel},
  title =	{{Arc-Flags in Dynamic Graphs}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2149},
  URN =		{urn:nbn:de:0030-drops-21490},
  doi =		{10.4230/OASIcs.ATMOS.2009.2149},
  annote =	{Keywords: Shortest Path, Speed-Up Technique, Dynamic Graph Algorithm Shortest Path, Speed-Up Technique, Dynamic Graph Algorithm}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2009.2145
Efficient Route Planning in Flight Networks

Authors: Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)

Abstract
We present a set of three new time-dependent models with increasing flexibility for realistic route planning in flight networks. By these means, we obtain small graph sizes while modeling airport procedures in a realistic way. With these graphs, we are able to efficiently compute a set of best connections with multiple criteria over a full day. It even turns out that due to the very limited graph sizes it is feasible to precompute full distance tables between all airports. As a result, best connections can be retrieved in a few microseconds on real world data.
Cite as

Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis. Efficient Route Planning in Flight Networks. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2009.2145,
  author =	{Delling, Daniel and Pajor, Thomas and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Efficient Route Planning in Flight Networks}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2145},
  URN =		{urn:nbn:de:0030-drops-21450},
  doi =		{10.4230/OASIcs.ATMOS.2009.2145},
  annote =	{Keywords: Timetable information, flight modeling, shortest paths, multi criteria, table lookups Timetable information, flight modeling, shortest paths, multi criteria, table lookups}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1582
Engineering Time-Expanded Graphs for Faster Timetable Information

Authors: Daniel Delling, Thomas Pajor, and Dorothea Wagner

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
We present an extension of the well-known time-expanded approach for timetable information. By remodeling unimportant stations, we are able to obtain faster query times with less space consumption than the original model. Moreover, we show that our extensions harmonize well with speed-up techniques whose adaption to timetable networks is more challenging than one might expect.
Cite as

Daniel Delling, Thomas Pajor, and Dorothea Wagner. Engineering Time-Expanded Graphs for Faster Timetable Information. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2008.1582,
  author =	{Delling, Daniel and Pajor, Thomas and Wagner, Dorothea},
  title =	{{Engineering Time-Expanded Graphs for Faster Timetable Information}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1582},
  URN =		{urn:nbn:de:0030-drops-15826},
  doi =		{10.4230/OASIcs.ATMOS.2008.1582},
  annote =	{Keywords: Timetable information, shortest path, modeling}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2007.1169
14. Experimental Study on Speed-Up Techniques for Timetable Information Systems

Authors: Reinhard Bauer, Daniel Delling, and Dorothea Wagner

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract
During the last years, impressive speed-up techniques for Dijkstra's algorithm have been developed. Unfortunately, recent research mainly focused on road networks. However, fast algorithms are also needed for other applications like timetable information systems. Even worse, the adaption of recently developed techniques to timetable information is often more complicated than expected. In this work, we check whether results from road networks are transferable to timetable information. To this end, we present an extensive experimental study of the most prominent speed-up techniques on different types of inputs. It turns out that recently developed techniques are much slower on graphs derived from timetable information than on road networks. In addition, we gain amazing insights into the behavior of speed-up techniques in general.
Cite as

Reinhard Bauer, Daniel Delling, and Dorothea Wagner. 14. Experimental Study on Speed-Up Techniques for Timetable Information Systems. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 209-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.ATMOS.2007.1169,
  author =	{Bauer, Reinhard and Delling, Daniel and Wagner, Dorothea},
  title =	{{14. Experimental Study on Speed-Up Techniques for Timetable Information Systems}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{209--225},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1169},
  URN =		{urn:nbn:de:0030-drops-11695},
  doi =		{10.4230/OASIcs.ATMOS.2007.1169},
  annote =	{Keywords: Speed-up techniques, timetable information, shortest path}
}
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