2 Search Results for "Geisberger, Eva"

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/DagSemProc.06351.4
A Model-Based Approach To Requirements Analysis

Authors: Bernhard Schätz, Eva Geisberger, and Johannes Grünbauer

Published in: Dagstuhl Seminar Proceedings, Volume 6351, Methods for Modelling Software Systems (MMOSS) (2007)

Abstract
A major task in designing embedded systems is the systematic elaboration of functional system requirements and their integration into the environment of the complete technical system. The main challenge is to handle the versatile tasks of coordinating a definition of behavior, which is appropriate to the problem. The problem- and design-specifications of the customer related product definition have to be adjusted with and integrated into the manifold requirements of the technical system design. Accordingly, the model-based requirements analysis and system-definition presented here defines a well-structured modeling approach, which systematically aids the goal-oriented formulation and adjustment of the different stakeholder-requirements with the aid of views onto the system and descriptive specification techniques. Thus it allows a clear specification of a consistent and complete system design. The central steps of this approach are implemented in a requirements management (RM) tool prototype called AutoRAID
Cite as

Bernhard Schätz, Eva Geisberger, and Johannes Grünbauer. A Model-Based Approach To Requirements Analysis. In Methods for Modelling Software Systems (MMOSS). Dagstuhl Seminar Proceedings, Volume 6351, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{schatz_et_al:DagSemProc.06351.4,
  author =	{Sch\"{a}tz, Bernhard and Geisberger, Eva and Gr\"{u}nbauer, Johannes},
  title =	{{A Model-Based Approach To Requirements Analysis}},
  booktitle =	{Methods for Modelling Software Systems (MMOSS)},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6351},
  editor =	{Ed Brinksma and David Harel and Angelika Mader and Perdita Stevens and Roel Wieringa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06351.4},
  URN =		{urn:nbn:de:0030-drops-8663},
  doi =		{10.4230/DagSemProc.06351.4},
  annote =	{Keywords: Requirements, model-based, tool support}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2007

  • Refine by Author
  • 1 Breitling, Johannes
  • 1 Geisberger, Eva
  • 1 Grünbauer, Johannes
  • 1 Laupichler, Moritz
  • 1 Schätz, Bernhard

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

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

  • Refine by Keyword
  • 1 Dynamic taxi sharing
  • 1 Requirements
  • 1 dial-a-ride problem
  • 1 model-based
  • 1 ride pooling
  • 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