3 Search Results for "Geiger, Martin Josef"

Document
DOI: 10.4230/OASIcs.ATMOS.2025.2
A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing

Authors: Fabian Löbel and Niels Lindner

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

Abstract
We offer a geometric perspective on the problem of integrated periodic timetabling and passenger routing in public transport. Inside the space of periodic tensions, we single out those regions, where the same set of paths provides shortest passenger routes. This results in a polyhedral subdivision, which we combine with the known decomposition by polytropes. On each maximal region of the common refinement, the integrated problem is solvable in polynomial time. We transform these insights into a new geometry-driven primal heuristic, integrated tropical neighborhood search (ITNS). Computationally, we compare implementations of ITNS and the integrated (restricted) modulo network simplex algorithm on the TimPassLib benchmark set, and contribute better solutions in terms of total travel time for all but one of the twenty-five instances for which a proven optimal solution is not yet known.
Cite as

Fabian Löbel and Niels Lindner. A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lobel_et_al:OASIcs.ATMOS.2025.2,
  author =	{L\"{o}bel, Fabian and Lindner, Niels},
  title =	{{A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{2:1--2:19},
  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.2},
  URN =		{urn:nbn:de:0030-drops-247580},
  doi =		{10.4230/OASIcs.ATMOS.2025.2},
  annote =	{Keywords: Periodic Timetabling, Passenger Routing, Polyhedral Complexes}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2024.32
PACE Solver Description: Martin_J_Geiger

Authors: Martin Josef Geiger

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
This extended abstract outlines our contribution to the Parameterized Algorithms and Computational Experiments Challenge (PACE), which invited to work on the one-sided crossing minimization problem. Our ideas are primarily based on the principles of Iterated Local Search and Variable Neighborhood Search. For obvious reasons, the initial alternative stems from the barycenter heuristic. This first sequence (permutation) of nodes is then quickly altered/ improved by a set of operators, keeping the elite configuration while allowing for worsening moves and hence, escaping local optima.
Cite as

Martin Josef Geiger. PACE Solver Description: Martin_J_Geiger. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 32:1-32:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{geiger:LIPIcs.IPEC.2024.32,
  author =	{Geiger, Martin Josef},
  title =	{{PACE Solver Description: Martin\underlineJ\underlineGeiger}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{32:1--32:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.32},
  URN =		{urn:nbn:de:0030-drops-222587},
  doi =		{10.4230/LIPIcs.IPEC.2024.32},
  annote =	{Keywords: PACE 2024, one-sided crossing minimization, Variable Neighborhood Search, Iterated Local Search}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2021.34
PACE Solver Description: A Simplified Threshold Accepting Approach for the Cluster Editing Problem

Authors: Martin Josef Geiger

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
We present a simple heuristic for the Cluster Editing Problem as presented in the Parameterized Algorithms and Computational Experiments (PACE) 2021. Our method makes use of a simple Threshold Accepting strategy and employs single neighborhood moves only. Despite its simplicity, the results of the method are encouraging. However, and this has to be expected, the approach cannot ultimately win in a competitive setting such as PACE 2021. Nevertheless, some interesting insights can be derived from such a simple method, as this gives an idea of how good results can be by a comparable basic approach with a reasonable implementation effort.
Cite as

Martin Josef Geiger. PACE Solver Description: A Simplified Threshold Accepting Approach for the Cluster Editing Problem. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 34:1-34:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{geiger:LIPIcs.IPEC.2021.34,
  author =	{Geiger, Martin Josef},
  title =	{{PACE Solver Description: A Simplified Threshold Accepting Approach for the Cluster Editing Problem}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{34:1--34:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.34},
  URN =		{urn:nbn:de:0030-drops-154176},
  doi =		{10.4230/LIPIcs.IPEC.2021.34},
  annote =	{Keywords: Cluster Editing Problem, Threshold Accepting, Local Search}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2024
  • 1 2021

  • Refine by Author
  • 2 Geiger, Martin Josef
  • 1 Lindner, Niels
  • 1 Löbel, Fabian

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

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Optimization with randomized search heuristics
  • 1 Theory of computation → Network optimization
  • 1 Theory of computation → Randomized local search

  • Refine by Keyword
  • 1 Cluster Editing Problem
  • 1 Iterated Local Search
  • 1 Local Search
  • 1 PACE 2024
  • 1 Passenger Routing
  • 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