Search Results

Documents authored by Nachtigall, Karl

Document
DOI: 10.4230/OASIcs.ATMOS.2016.3
Integrating Passengers' Routes in Periodic Timetabling: A SAT approach

Authors: Philine Gattermann, Peter Großmann, Karl Nachtigall, and Anita Schöbel

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
The periodic event scheduling problem (PESP) is a well studied problem known as intrinsically hard. Its main application is for designing periodic timetables in public transportation. To this end, the passengers' paths are required as input data. This is a drawback since the final paths which are used by the passengers depend on the timetable to be designed. Including the passengers' routing in the PESP hence improves the quality of the resulting timetables. However, this makes PESP even harder. Formulating the PESP as satisfiability problem and using SAT solvers for its solution has been shown to be a highly promising approach. The goal of this paper is to exploit if SAT solvers can also be used for the problem of integrated timetabling and passenger routing. In our model of the integrated problem we distribute origin-destination (OD) pairs temporally through the network by using time-slices in order to make the resulting model more realistic. We present a formulation of this integrated problem as integer program which we are able to transform to a satisfiability problem. We tested the latter formulation within numerical experiments, which are performed on Germany's long-distance passenger railway network. The computation's analysis in which we compare the integrated approach with the traditional one with fixed passengers' weights, show promising results for future scientific investigations.
Cite as

Philine Gattermann, Peter Großmann, Karl Nachtigall, and Anita Schöbel. Integrating Passengers' Routes in Periodic Timetabling: A SAT approach. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gattermann_et_al:OASIcs.ATMOS.2016.3,
  author =	{Gattermann, Philine and Gro{\ss}mann, Peter and Nachtigall, Karl and Sch\"{o}bel, Anita},
  title =	{{Integrating Passengers' Routes in Periodic Timetabling: A SAT approach}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{3:1--3:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.3},
  URN =		{urn:nbn:de:0030-drops-65279},
  doi =		{10.4230/OASIcs.ATMOS.2016.3},
  annote =	{Keywords: PESP, Timetabling, Public Transport, Passengers' Routes, SAT}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1589
Simultaneous Network Line Planning and Traffic Assignment

Authors: Karl Nachtigall and Karl Jerosch

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

Abstract
One of the basic problems in strategic planning of public and rail transport is the line planning problem to find a system of lines and its associated frequencies. The objectives of this planning process are usually manifold and often contradicting. The transport operator wants to minimize cost, whereas passengers want to have travel time shortest routes without any or only few changings between different lines. The travel quality of a passenger route depends on the travel time and on the number of necessary changings between lines and is usually measured by a disutility or impedance function. In practice the disutility strongly depends on the line plan, which is not known, but should be calculated. The presented model combines line planning models and traffic assignment model to overcome this dilemma. Results with data of Berlin's city public transportion network are reported.
Cite as

Karl Nachtigall and Karl Jerosch. Simultaneous Network Line Planning and Traffic Assignment. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{nachtigall_et_al:OASIcs.ATMOS.2008.1589,
  author =	{Nachtigall, Karl and Jerosch, Karl},
  title =	{{Simultaneous Network Line Planning and Traffic Assignment}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--16},
  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.1589},
  URN =		{urn:nbn:de:0030-drops-15899},
  doi =		{10.4230/OASIcs.ATMOS.2008.1589},
  annote =	{Keywords: Line planning problem, integer programming}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1588
Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations

Authors: Karl Nachtigall and Jens Opitz

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

Abstract
In the last 15 years periodic timetable problems have found much interest in the combinatorial optimization community. We will focus on the optimisation task to minimise a weighted sum of undesirable slack times. This problem can be formulated as a mixed integer linear problem, which for real world instances is hard to solve. This is mainly caused by the integer variables, the so-called modulo parameter. At first we will discuss some results on the polyhedral structure of the periodic timetable problem. These ideas allow to define a modulo simplex basic solution by calculating the basic variables from modulo equations. This leads to a modulo network simplex method, which iteratively improves the solution by changing the simplex basis.
Cite as

Karl Nachtigall and Jens Opitz. Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{nachtigall_et_al:OASIcs.ATMOS.2008.1588,
  author =	{Nachtigall, Karl and Opitz, Jens},
  title =	{{Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--15},
  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.1588},
  URN =		{urn:nbn:de:0030-drops-15884},
  doi =		{10.4230/OASIcs.ATMOS.2008.1588},
  annote =	{Keywords: Periodic event scheduling problem, integer programming, modulo network simplex}
}
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