7 Search Results for "Buchhold, Valentin"

Document
DOI: 10.4230/OASIcs.ATMOS.2025.15
Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques

Authors: Johannes Breitling and Moritz Laupichler

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
We introduce a first-of-its-kind efficient, exact algorithm for the dynamic taxi-sharing problem with single-transfer journeys, i.e., a dispatcher that assigns traveler requests to a fleet of shared taxi-like vehicles allowing transfers between vehicles. We extend an existing no-transfer solution by collecting all viable pickup and dropoff vehicles for a request and computing the optimal transfer point for every pair of vehicles. We analyze underlying shortest-path problems and employ state-of-the-art routing algorithms to compute distances on-the-fly, which serves as the basis of dispatching requests with exact and up-to-date travel time information. We utilize constraints on existing routes, pruning techniques for transfer points, and both instruction- and thread-level parallelism to speed up the computation of the best assignment for every traveler. In addition to the exact variant, we propose a tunable heuristic approach that sacrifices solution quality in favor of improved running time. We evaluate our algorithm on a large road network with realistic input sets (up to 150000 requests). We demonstrate the effectiveness of our speedup techniques and the heuristic. We show first results on the benefits of transfers for taxi sharing on dense request sets, proving that our algorithm is well suited for the analysis of taxi sharing with transfers on large input instances.
Cite as

Johannes Breitling and Moritz Laupichler. Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{breitling_et_al:OASIcs.ATMOS.2025.15,
  author =	{Breitling, Johannes and Laupichler, Moritz},
  title =	{{Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{15:1--15:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.15},
  URN =		{urn:nbn:de:0030-drops-247718},
  doi =		{10.4230/OASIcs.ATMOS.2025.15},
  annote =	{Keywords: Dynamic taxi sharing, ride pooling, dial-a-ride problem, transfers, route planning}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.12
Separator-Based Alternative Paths in Customizable Contraction Hierarchies

Authors: Scott Bacherle, Thomas Bläsius, and Michael Zündorf

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
We propose an algorithm for computing alternatives to the shortest path in a road network, based on the speed-up technique CCH (customizable contraction hierarchy). Computing alternative paths is a well-studied problem, motivated by the fact that route-planning applications benefit from presenting different high-quality options the user can choose from. Another crucial feature of modern routing applications is the inclusion of live traffic, which requires speed-up techniques that allow efficient metric updates. Besides CCH, the other speed-up technique supporting metric updates is CRP (customizable route planning). Of the two, CCH is the more modern solution with the advantages of providing faster queries and being substantially simpler to implement efficiently. However, so far, CCH has been lacking a way of computing alternative paths. While for CRP, the commonly used plateau method for computing alternatives can be applied, this is not so straightforward for CCH. With this paper, we make CCH a viable option for alternative paths, by proposing a new separator-based approach to computing alternative paths that works hand-in-hand with the CCH data structure. With our experiments, we demonstrate that CCH can indeed be used to compute alternative paths efficiently. With this, we provide an alternative to CRP that is simpler and has lower query times.
Cite as

Scott Bacherle, Thomas Bläsius, and Michael Zündorf. Separator-Based Alternative Paths in Customizable Contraction Hierarchies. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bacherle_et_al:OASIcs.ATMOS.2025.12,
  author =	{Bacherle, Scott and Bl\"{a}sius, Thomas and Z\"{u}ndorf, Michael},
  title =	{{Separator-Based Alternative Paths in Customizable Contraction Hierarchies}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{12:1--12:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.12},
  URN =		{urn:nbn:de:0030-drops-247685},
  doi =		{10.4230/OASIcs.ATMOS.2025.12},
  annote =	{Keywords: Alternative routes, realistic road networks, customizable contraction hierarchies, route planning, shortest paths}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.18
Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications

Authors: Valentin Buchhold and Dorothea Wagner

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
Customizable contraction hierarchies are one of the most popular route planning frameworks in practice, due to their simplicity and versatility. In this work, we present a novel algorithm for finding k-nearest neighbors in customizable contraction hierarchies by systematically exploring the associated separator decomposition tree. Compared to previous bucket-based approaches, our algorithm requires much less target-dependent preprocessing effort. Moreover, we use our novel approach in two concrete applications. The first application are online k-closest point-of-interest queries, where the points of interest are only revealed at query time. We achieve query times of about 25 milliseconds on a continental road network, which is fast enough for interactive systems. The second application is travel demand generation. We show how to accelerate a recently introduced travel demand generator by a factor of more than 50 using our novel nearest-neighbor algorithm.
Cite as

Valentin Buchhold and Dorothea Wagner. Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buchhold_et_al:LIPIcs.SEA.2021.18,
  author =	{Buchhold, Valentin and Wagner, Dorothea},
  title =	{{Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.18},
  URN =		{urn:nbn:de:0030-drops-137908},
  doi =		{10.4230/LIPIcs.SEA.2021.18},
  annote =	{Keywords: Nearest neighbors, points of interest, travel demand generation, radiation model, customizable contraction hierarchies}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.9
Customizable Contraction Hierarchies with Turn Costs

Authors: Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf

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

Abstract
We incorporate turn restrictions and turn costs into the route planning algorithm customizable contraction hierarchies (CCH). There are two common ways to represent turn costs and restrictions. The edge-based model expands the network so that road segments become vertices and allowed turns become edges. The compact model keeps intersections as vertices, but associates a turn table with each vertex. Although CCH can be used as is on the edge-based model, the performance of preprocessing and customization is severely affected. While the expanded network is only three times larger, both preprocessing and customization time increase by up to an order of magnitude. In this work, we carefully engineer CCH to exploit different properties of the expanded graph. We reduce the increase in customization time from up to an order of magnitude to a factor of about 3. The increase in preprocessing time is reduced even further. Moreover, we present a CCH variant that works on the compact model, and show that it performs worse than the variant on the edge-based model. Surprisingly, the variant on the edge-based model even uses less space than the one on the compact model, although the compact model was developed to keep the space requirement low.
Cite as

Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf. Customizable Contraction Hierarchies with Turn Costs. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchhold_et_al:OASIcs.ATMOS.2020.9,
  author =	{Buchhold, Valentin and Wagner, Dorothea and Zeitz, Tim and Z\"{u}ndorf, Michael},
  title =	{{Customizable Contraction Hierarchies with Turn Costs}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{9:1--9:15},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.9},
  URN =		{urn:nbn:de:0030-drops-131453},
  doi =		{10.4230/OASIcs.ATMOS.2020.9},
  annote =	{Keywords: Turn costs, realistic road networks, customizable contraction hierarchies, route planning, shortest paths}
}
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/LIPIcs.ESA.2019.14
UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution

Authors: Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf

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

Abstract
We study a multi-modal route planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or taxis). The objective is to compute all journeys that are Pareto-optimal with respect to arrival time and the number of required transfers. While various existing algorithms can efficiently compute optimal journeys in either a pure public transit network or a pure transfer graph, combining the two increases running times significantly. As a result, even walking between stops is typically limited by a maximal duration or distance, or by requiring the transfer graph to be transitively closed. To overcome these shortcomings, we propose a novel preprocessing technique called ULTRA (UnLimited TRAnsfers): Given a complete transfer graph (without any limitations, representing an arbitrary non-schedule-based mode of transportation), we compute a small number of transfer shortcuts that are provably sufficient for computing all Pareto-optimal journeys. We demonstrate the practicality of our approach by showing that these transfer shortcuts can be integrated into a variety of state-of-the-art public transit algorithms, establishing the ULTRA-Query algorithm family. Our extensive experimental evaluation shows that ULTRA is able to improve these algorithms from limited to unlimited transfers without sacrificing query speed, yielding the fastest known algorithms for multi-modal routing. This is true not just for walking, but also for other transfer modes such as cycling or driving.
Cite as

Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{baum_et_al:LIPIcs.ESA.2019.14,
  author =	{Baum, Moritz and Buchhold, Valentin and Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-111352},
  doi =		{10.4230/LIPIcs.ESA.2019.14},
  annote =	{Keywords: Algorithms, Optimization, Route Planning, Public Transportation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.27
Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies

Authors: Valentin Buchhold, Peter Sanders, and Dorothea Wagner

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
Given an urban road network and a set of origin-destination (OD) pairs, the traffic assignment problem asks for the traffic flow on each road segment. A common solution employs a feasible-direction method, where the direction-finding step requires many shortest-path computations. In this paper, we significantly accelerate the computation of flow patterns, enabling interactive transportation and urban planning applications. We achieve this by revisiting and carefully engineering known speedup techniques for shortest paths, and combining them with customizable contraction hierarchies. In particular, our accelerated elimination tree search is more than an order of magnitude faster for local queries than the original algorithm, and our centralized search speeds up batched point-to-point shortest paths by a factor of up to 6. These optimizations are independent of traffic assignment and can be generally used for (batched) point-to-point queries. In contrast to prior work, our evaluation uses real-world data for all parts of the problem. On a metropolitan area encompassing more than 2.7 million inhabitants, we reduce the flow-pattern computation for a typical two-hour morning peak from 76.5 to 10.5 seconds on one core, and 4.3 seconds on four cores. This represents a speedup of 18 over the state of the art, and three orders of magnitude over the Dijkstra-based baseline.
Cite as

Valentin Buchhold, Peter Sanders, and Dorothea Wagner. Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{buchhold_et_al:LIPIcs.SEA.2018.27,
  author =	{Buchhold, Valentin and Sanders, Peter and Wagner, Dorothea},
  title =	{{Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.27},
  URN =		{urn:nbn:de:0030-drops-89623},
  doi =		{10.4230/LIPIcs.SEA.2018.27},
  annote =	{Keywords: traffic assignment, equilibrium flow pattern, customizable contraction hierarchies, batched shortest paths}
}
  • Refine by Type
  • 7 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2021
  • 2 2020
  • 1 2019
  • 1 2018

  • Refine by Author
  • 5 Buchhold, Valentin
  • 4 Wagner, Dorothea
  • 2 Zündorf, Michael
  • 1 Bacherle, Scott
  • 1 Baum, Moritz
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 3 OASIcs

  • Refine by Classification
  • 6 Theory of computation → Shortest paths
  • 5 Applied computing → Transportation
  • 4 Mathematics of computing → Graph algorithms
  • 1 Information systems → Geographic information systems
  • 1 Theory of computation → Dynamic graph algorithms
  • Show More...

  • Refine by Keyword
  • 4 customizable contraction hierarchies
  • 3 route planning
  • 2 realistic road networks
  • 2 shortest paths
  • 1 Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact