2 Search Results for "Briem, Lars"

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/LIPIcs.SEA.2017.20
Efficient Traffic Assignment for Public Transit Networks

Authors: Lars Briem, Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
We study the problem of computing traffic assignments for public transit networks: Given a public transit network and a demand (i.e. a list of passengers, each with associated origin, destination, and departure time), the objective is to compute the utilization of every vehicle. Efficient assignment algorithms are a core component of many urban traffic planning tools. In this work, we present a novel algorithm for computing public transit assignments. Our approach is based upon a microscopic Monte Carlo simulation of individual passengers. In order to model realistic passenger behavior, we base all routing decisions on travel time, number of transfers, time spent walking or waiting, and delay robustness. We show how several passengers can be processed during a single scan of the network, based on the Connection Scan Algorithm [Dibbelt et al., LNCS Springer 2013], resulting in a highly efficient algorithm. We conclude with an experimental study, showing that our assignments are comparable in terms of quality to the state-of-the-art. Using the parallelized version of our algorithm, we are able to compute a traffic assignment for more than ten million passengers in well below a minute, which outperforms previous works by more than an order of magnitude.
Cite as

Lars Briem, Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf. Efficient Traffic Assignment for Public Transit Networks. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{briem_et_al:LIPIcs.SEA.2017.20,
  author =	{Briem, Lars and Buck, Sebastian and Ebhart, Holger and Mallig, Nicolai and Strasser, Ben and Vortisch, Peter and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{Efficient Traffic Assignment for Public Transit Networks}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.20},
  URN =		{urn:nbn:de:0030-drops-76109},
  doi =		{10.4230/LIPIcs.SEA.2017.20},
  annote =	{Keywords: Algorithms, Optimization, Route planning, Public transportation}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2017

  • Refine by Author
  • 1 Breitling, Johannes
  • 1 Briem, Lars
  • 1 Buck, Sebastian
  • 1 Ebhart, Holger
  • 1 Laupichler, Moritz
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Information systems → Geographic information systems
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 Algorithms
  • 1 Dynamic taxi sharing
  • 1 Optimization
  • 1 Public transportation
  • 1 Route planning
  • 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