20 Search Results for "Kroon, Leo"

Volume

OASIcs, Volume 2

5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)

ATMOS 2005, October 7, 2005, Palma de Mallorca, Spain

Editors: Leo G. Kroon and Rolf H. Möhring

Document
DOI: 10.4230/OASIcs.ATMOS.2025.18
Energy-Efficient Line Planning by Implementing Express Lines

Authors: Sarah Roth and Anita Schöbel

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

Abstract
While a shift from individual transport to public transport reduces greenhouse gas emissions, public transport itself also consumes a non-negligible amount of energy. Acceleration processes have a high part in that, especially in urban transportation networks where stops are not far from each other. Express lines which skip stops hence use less energy than a vehicle on a normal line on the same route. Additionally, they increase the attractiveness of public transport by reducing travel times. In this paper, we introduce the express line planning problem ELP which extends the well-known line planning problem by the additional planning of express lines and which stops they skip. The problem is stated in a bicriteria setting minimizing the passengers travel time and the energy consumption of the public transport system. We investigate the problem’s complexity and develop two different MIP formulations and show their equivalence. The models are tested numerically on medium sized instances.
Cite as

Sarah Roth and Anita Schöbel. Energy-Efficient Line Planning by Implementing Express Lines. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{roth_et_al:OASIcs.ATMOS.2025.18,
  author =	{Roth, Sarah and Sch\"{o}bel, Anita},
  title =	{{Energy-Efficient Line Planning by Implementing Express Lines}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{18:1--18:21},
  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.18},
  URN =		{urn:nbn:de:0030-drops-247746},
  doi =		{10.4230/OASIcs.ATMOS.2025.18},
  annote =	{Keywords: Line Planning, Express Lines, Sustainable Public Transport}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.55
Safe Sequences via Dominators in DAGs for Path-Covering Problems

Authors: Francisco Sena, Romeo Rizzi, and Alexandru I. Tomescu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A path-covering problem on a directed acyclic graph (DAG) requires finding a set of source-to-sink paths that cover all the nodes, all the arcs, or subsets thereof, and additionally they are optimal with respect to some function. In this paper we study safe sequences of nodes or arcs, namely sequences that appear in some path of every path cover of a DAG. We show that safe sequences admit a simple characterization via cutnodes. Moreover, we establish a connection between maximal safe sequences and leaf-to-root paths in the source- and sink-dominator trees of the DAG, which may be of independent interest in the extensive literature on dominators. With dominator trees, safe sequences admit an O(n)-size representation and a linear-time output-sensitive enumeration algorithm running in time O(m + o), where n and m are the number of nodes and arcs, respectively, and o is the total length of the maximal safe sequences. We then apply maximal safe sequences to simplify Integer Linear Programs (ILPs) for two path-covering problems, LeastSquares and MinPathError, which are at the core of RNA transcript assembly problems from bioinformatics. On various datasets, maximal safe sequences can be computed in under 0.1 seconds per graph, on average, and ILP solvers whose search space is reduced in this manner exhibit significant speed-ups. For example on graphs with a large width, average speed-ups are in the range 50-250× for MinPathError and in the range 80-350× for LeastSquares. Optimizing ILPs using safe sequences can thus become a fast building block of practical RNA transcript assembly tools, and more generally, of path-covering problems.
Cite as

Francisco Sena, Romeo Rizzi, and Alexandru I. Tomescu. Safe Sequences via Dominators in DAGs for Path-Covering Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sena_et_al:LIPIcs.ESA.2025.55,
  author =	{Sena, Francisco and Rizzi, Romeo and Tomescu, Alexandru I.},
  title =	{{Safe Sequences via Dominators in DAGs for Path-Covering Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.55},
  URN =		{urn:nbn:de:0030-drops-245230},
  doi =		{10.4230/LIPIcs.ESA.2025.55},
  annote =	{Keywords: directed acyclic graph, path cover, dominator tree, integer linear programming, least squares, minimum path error}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.34
On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

Authors: Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, and Laura Vargas Koch

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In train routing, the headway is the minimum distance that must be maintained between successive trains for safety and robustness. We introduce a model for train routing that requires a fixed headway to be maintained between trains, and study the problem of minimizing the makespan, i.e., the arrival time of the last train, in a single-source single-sink network. For this problem, we first show that there exists an optimal solution where trains move in convoys - that is, the optimal paths for any two trains are either the same or are arc-disjoint. Via this insight, we are able to reduce the approximability of our train routing problem to that of the min-max disjoint paths problem, which asks for a collection of disjoint paths where the maximum length of any path in the collection is as small as possible. While min-max disjoint paths inherits a strong inapproximability result on directed acyclic graphs from the multi-level bottleneck assignment problem, we show that a natural greedy composition approach yields a logarithmic approximation in the number of disjoint paths for series-parallel graphs. We also present an alternative analysis of this approach that yields a guarantee depending on how often the decomposition tree of the series-parallel graph alternates between series and parallel compositions on any root-leaf path.
Cite as

Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, and Laura Vargas Koch. On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.ESA.2025.34,
  author =	{Bhaskar, Umang and Eickhoff, Katharina and Kauther, Lennart and Matuschke, Jannik and Peis, Britta and Vargas Koch, Laura},
  title =	{{On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.34},
  URN =		{urn:nbn:de:0030-drops-245029},
  doi =		{10.4230/LIPIcs.ESA.2025.34},
  annote =	{Keywords: Train Routing, Scheduling, Approximation Algorithms, Flows over Time, Min-Max Disjoint Paths}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.33
Constraint-Based In-Station Train Dispatching

Authors: Andreas Schutt, Matteo Cardellini, Jip J. Dekker, Daniel Harabor, Marco Maratea, and Mauro Vallati

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
In-station dispatching is the problem of planning the movements of scheduled trains inside a railway station. Effective solutions for in-station dispatching are important for maximising the utilisation of railway infrastructure and for mitigating the impact of incidents and delays in the broader network. In this paper, we explore a constraint-based approach to perform in-station train dispatching. Our extensive empirical analysis of multiple modelling, search strategy, and solver choices, performed over synthetically generated, yet realistic, data, shows that our method outperforms the existing planning-based state-of-the-art approach. In addition, we present different optimisation criteria, which can be effortless defined thanks to the constraint-based approach.
Cite as

Andreas Schutt, Matteo Cardellini, Jip J. Dekker, Daniel Harabor, Marco Maratea, and Mauro Vallati. Constraint-Based In-Station Train Dispatching. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 33:1-33:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schutt_et_al:LIPIcs.CP.2025.33,
  author =	{Schutt, Andreas and Cardellini, Matteo and Dekker, Jip J. and Harabor, Daniel and Maratea, Marco and Vallati, Mauro},
  title =	{{Constraint-Based In-Station Train Dispatching}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{33:1--33:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.33},
  URN =		{urn:nbn:de:0030-drops-238941},
  doi =		{10.4230/LIPIcs.CP.2025.33},
  annote =	{Keywords: in-station train dispatching, train scheduling, railway scheduling, constraint programming, mixed-integer programming}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.7
Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs

Authors: David C. Kutner and Anouk Sommer

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
In train networks, carefully-chosen delays may be beneficial for certain passengers, who would otherwise miss some connection. Given a simple (directed or undirected) temporal graph and a set of passengers (each specifying a starting vertex, an ending vertex, and a desired arrival time), we ask whether it is possible to delay some of the edges of the temporal graph to realize all the passengers' demands. We call this problem DelayBetter (DB), and study it along with two variants: in δ-DelayBetter, each delay must be of at most δ; in (δ-)Path DB, passengers also fully specify the vertices they should visit on their journey. On the positive side, we give a polynomial-time algorithm for Path DB and δ-Path DB, and obtain as a corollary a polynomial-time algorithm for DB and δ-DB on trees. We also provide an fpt algorithm for both problems parameterized by the size of the graph’s Feedback Edge Set together with the number of passengers. On the negative side, we show NP-completeness of (1-)DB on bounded-degree temporal graphs even when the lifetime is 2, and of (10-)DB on bounded-degree planar temporal graphs of lifetime 19. Our results complement previous work studying reachability problems in temporal graphs with delaying operations. This is to our knowledge the first such problem in which the aim is to facilitate travel between specific points (as opposed to facilitating or impeding a broadcast from one or many sources).
Cite as

David C. Kutner and Anouk Sommer. Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kutner_et_al:LIPIcs.SAND.2025.7,
  author =	{Kutner, David C. and Sommer, Anouk},
  title =	{{Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.7},
  URN =		{urn:nbn:de:0030-drops-230604},
  doi =		{10.4230/LIPIcs.SAND.2025.7},
  annote =	{Keywords: Temporal Graphs, Computational Complexity, Delay Management, Train Networks}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.1
A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance

Authors: Boris Grimm, Ralf Borndörfer, Markus Reuther, and Thomas Schlechte

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
For providing railway services the company’s railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Maróti and Kroon, 2005; Gábor Maróti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Borndörfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.
Cite as

Boris Grimm, Ralf Borndörfer, Markus Reuther, and Thomas Schlechte. A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 1:1-1:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grimm_et_al:OASIcs.ATMOS.2019.1,
  author =	{Grimm, Boris and Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas},
  title =	{{A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{1:1--1:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.1},
  URN =		{urn:nbn:de:0030-drops-114136},
  doi =		{10.4230/OASIcs.ATMOS.2019.1},
  annote =	{Keywords: Railway Operations Research, Integer Programming, Infeasible Path Cuts, Cut Separation, Rolling Stock Rotation Problem}
}
Document
DOI: 10.4230/DagRep.6.4.139
Algorithmic Methods for Optimization in Public Transport (Dagstuhl Seminar 16171)

Authors: Leo G. Kroon, Anita Schöbel, and Dorothea Wagner

Published in: Dagstuhl Reports, Volume 6, Issue 4 (2016)

Abstract
This report documents the talks and discussions at the Dagstuhl seminar 16171 “Algorithmic Methods for Optimization in Public Transport”. The seminar brought together researchers from algorithm, algorithm engineering, operations research, mathematical optimization and engineering, all interested in algorithms in public transportation. Also several practitioners were able to join the group and brought valuable insights on current practice and challenging problems.
Cite as

Leo G. Kroon, Anita Schöbel, and Dorothea Wagner. Algorithmic Methods for Optimization in Public Transport (Dagstuhl Seminar 16171). In Dagstuhl Reports, Volume 6, Issue 4, pp. 139-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{kroon_et_al:DagRep.6.4.139,
  author =	{Kroon, Leo G. and Sch\"{o}bel, Anita and Wagner, Dorothea},
  title =	{{Algorithmic Methods for Optimization in Public Transport (Dagstuhl Seminar 16171)}},
  pages =	{139--160},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{4},
  editor =	{Kroon, Leo G. and Sch\"{o}bel, Anita and Wagner, Dorothea},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.4.139},
  URN =		{urn:nbn:de:0030-drops-66949},
  doi =		{10.4230/DagRep.6.4.139},
  annote =	{Keywords: delay and disruption management, dynamic passenger information, public transportation, resource scheduling, timetabling}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2005
OASIcs, Volume 2, ATMOS'05, Complete Volume

Authors: Leo G. Kroon and Rolf H. Möhring

Published in: OASIcs, Volume 2, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (2006)

Abstract
OASIcs, Volume 2, ATMOS'05, Complete Volume
Cite as

5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{kroon_et_al:OASIcs.ATMOS.2005,
  title =	{{OASIcs, Volume 2, ATMOS'05, Complete Volume}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-00-2},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{2},
  editor =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005},
  URN =		{urn:nbn:de:0030-drops-35642},
  doi =		{10.4230/OASIcs.ATMOS.2005},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.24
Robust Train Routing and Online Re-scheduling

Authors: Alberto Caprara, Laura Galli, Leo Kroon, Gábor Maróti, and Paolo Toth

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
Train Routing is a problem that arises in the early phase of the passenger railway planning process, usually several months before operating the trains. The main goal is to assign each train a stopping platform and the corresponding arrival/departure paths through a railway station. It is also called Train Platforming when referring to the platform assignment task. Railway stations often represent bottlenecks and train delays can easily disrupt the routing schedule. Thereby railway stations are responsible for a large part of the delay propagation in the whole network. In this research we present different models to compute robust routing schedules and we study their power in an online context together with different re-scheduling strategies. We also design a simulation framework and use it to evaluate and compare the effectiveness of the proposed robust models and re-scheduling algorithms using real-world data from Rete Ferroviaria Italiana, the main Italian Railway Infrastructure Manager.
Cite as

Alberto Caprara, Laura Galli, Leo Kroon, Gábor Maróti, and Paolo Toth. Robust Train Routing and Online Re-scheduling. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 24-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{caprara_et_al:OASIcs.ATMOS.2010.24,
  author =	{Caprara, Alberto and Galli, Laura and Kroon, Leo and Mar\'{o}ti, G\'{a}bor and Toth, Paolo},
  title =	{{Robust Train Routing and Online Re-scheduling}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{24--33},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.24},
  URN =		{urn:nbn:de:0030-drops-27470},
  doi =		{10.4230/OASIcs.ATMOS.2010.24},
  annote =	{Keywords: Railway optimisation, Train platforming, Robust planning, Online re-scheduling, Simulation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1590
Recoverable Robustness for Railway Rolling Stock Planning

Authors: Valentina Cacchiani, Alberto Caprara, Laura Galli, Leo Kroon, and Gábor Maróti

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

Abstract
In this paper we explore the possibility of applying the notions of Recoverable Robustness and Price of Recoverability (introduced by [5]) to railway rolling stock planning, being interested in recoverability measures that can be computed in practice, thereby evaluating the robustness of rolling stock schedules. In order to lower bound the Price of Recoverability for any set of recovery algorithms, we consider an "optimal" recovery algorithm and propose a Benders decomposition approach to assess the Price of Recoverability for this "optimal" algorithm. We evaluate the approach on real-life rolling stock planning problems of NS, the main operator of passenger trains in the Netherlands. The preliminary results show that, thanks to Benders decomposition, our lower bound can be computed within relatively short time for our case study.
Cite as

Valentina Cacchiani, Alberto Caprara, Laura Galli, Leo Kroon, and Gábor Maróti. Recoverable Robustness for Railway Rolling Stock Planning. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2008.1590,
  author =	{Cacchiani, Valentina and Caprara, Alberto and Galli, Laura and Kroon, Leo and Mar\'{o}ti, G\'{a}bor},
  title =	{{Recoverable Robustness for Railway Rolling Stock Planning}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--13},
  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.1590},
  URN =		{urn:nbn:de:0030-drops-15902},
  doi =		{10.4230/OASIcs.ATMOS.2008.1590},
  annote =	{Keywords: Recoverable robustness, Railway rolling stock scheduling, Benders decomposition}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2005.668
ATMOS 2005 Abstracts Collection -- Selected Papers from the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways

Authors: Leo G. Kroon and Rolf H. Möhring

Published in: OASIcs, Volume 2, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (2006)

Abstract
This issue contains six papers that were presented in preliminary form at the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2005), held at Palma de Mallorca, Spain, October 7, 2005 in conjunction with ALGO 2005. These papers are representative of several areas of research within the scope of ATMOS: rolling stock circulation and engine assignment, station location, line planning, railway traffic scheduling and dispatching, transfer optimization within network design, and fast traffic information systems.
Cite as

Leo G. Kroon and Rolf H. Möhring. ATMOS 2005 Abstracts Collection -- Selected Papers from the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kroon_et_al:OASIcs.ATMOS.2005.668,
  author =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  title =	{{ATMOS 2005 Abstracts Collection -- Selected Papers from the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--4},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-00-2},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{2},
  editor =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.668},
  URN =		{urn:nbn:de:0030-drops-6688},
  doi =		{10.4230/OASIcs.ATMOS.2005.668},
  annote =	{Keywords: Railway traffic, networks, algorithms, optimization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2005.658
Analysis of the Parameters of Transfers in Rapid Transit Network Design

Authors: Ricardo García, Armando Garzón-Astolfi, Angel Marín, Juan A. Mesa, and Francisco A. Ortega

Published in: OASIcs, Volume 2, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (2006)

Abstract
The rapid transit network design problem consists of the location of train alignments and stations in an urban traffic context. The originality of our study is to incorporate into the location model the decisions about the transportation mode and the route, to be chosen for urban trips. This paper proposes a new design model which includes transfers between train lines. The objective of the model is to maximize the number of expected users in the transit network taking limited budgets into consideration, in addition to location and allocation constraints. Furthermore, the transfer costs are considered in the generalized public costs when the users change lines. Waiting time to take the metro and walking time to transfer is included in the formulation of the costs. The analysis of transfer parameters is carried out using a test network. Some computational experience is included in the paper.
Cite as

Ricardo García, Armando Garzón-Astolfi, Angel Marín, Juan A. Mesa, and Francisco A. Ortega. Analysis of the Parameters of Transfers in Rapid Transit Network Design. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{garcia_et_al:OASIcs.ATMOS.2005.658,
  author =	{Garc{\'\i}a, Ricardo and Garz\'{o}n-Astolfi, Armando and Mar{\'\i}n, Angel and Mesa, Juan A. and Ortega, Francisco A.},
  title =	{{Analysis of the Parameters of Transfers in Rapid Transit Network Design}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-00-2},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{2},
  editor =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.658},
  URN =		{urn:nbn:de:0030-drops-6583},
  doi =		{10.4230/OASIcs.ATMOS.2005.658},
  annote =	{Keywords: Parameter analysis, rapid transit network design, trip choice in urban traffic}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2005.659
Computer-based decision support for railway traffic scheduling and dispatching: A review of models and algorithms

Authors: Johanna Törnquist

Published in: OASIcs, Volume 2, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (2006)

Abstract
This paper provides an overview of the research in railway scheduling and dispatching. A distinction is made between tactical scheduling, operational scheduling and re-scheduling. Tactical scheduling refers to master scheduling, whereas operational scheduling concerns scheduling at a later stage. Re-scheduling focuses on the re-planning of an existing timetable when deviations from it have occurred. 48 approaches published between 1973 and 2005 have been reviewed according to a framework that classifies them with respect to problem type, solution mechanism, and type of evaluation. 26 of the approaches support the representation of a railway network rather than a railway line, but the majority has been experimentally evaluated for traffic on a line. 94 % of the approaches have been subject to some kind of experimental evaluation, while approximately 4 % have been implemented. The solutions proposed vary from myopic, priority-based algorithms, to traditional operations research techniques and the application of agent technology.This paper provides an overview of the research in railway scheduling and dispatching. A distinction is made between tactical scheduling, operational scheduling and re-scheduling. Tactical scheduling refers to master scheduling, whereas operational scheduling concerns scheduling at a later stage. Re-scheduling focuses on the re-planning of an existing timetable when deviations from it have occurred. 48 approaches published between 1973 and 2005 have been reviewed according to a framework that classifies them with respect to problem type, solution mechanism, and type of evaluation. 26 of the approaches support the representation of a railway network rather than a railway line, but the majority has been experimentally evaluated for traffic on a line. 94 % of the approaches have been subject to some kind of experimental evaluation, while approximately 4 % have been implemented. The solutions proposed vary from myopic, priority-based algorithms, to traditional operations research techniques and the application of agent technology.
Cite as

Johanna Törnquist. Computer-based decision support for railway traffic scheduling and dispatching: A review of models and algorithms. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{tornquist:OASIcs.ATMOS.2005.659,
  author =	{T\"{o}rnquist, Johanna},
  title =	{{Computer-based decision support for railway traffic scheduling and dispatching: A review of models and algorithms}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-00-2},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{2},
  editor =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.659},
  URN =		{urn:nbn:de:0030-drops-6592},
  doi =		{10.4230/OASIcs.ATMOS.2005.659},
  annote =	{Keywords: Decision support, railway traffic scheduling, railway traffic dispatching, overview}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2005.660
Line Planning with Minimal Traveling Time

Authors: Anita Schöbel and Susanne Scholl

Published in: OASIcs, Volume 2, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (2006)

Abstract
An important strategic element in the planning process of public transportation is the development of a line concept, i.e. to find a set of paths for operating lines on them. So far, most of the models in the literature aim to minimize the costs or to maximize the number of direct travelers. In this paper we present a new approach minimizing the travel times over all customers including penalties for the transfers needed. This approach maximizes the comfort of the passengers and will make the resulting timetable more reliable. To tackle our problem we present integer programming models and suggest a solution approach using Dantzig-Wolfe decomposition for solving the LP-relaxation. Numerical results of real-world instances are presented.
Cite as

Anita Schöbel and Susanne Scholl. Line Planning with Minimal Traveling Time. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schobel_et_al:OASIcs.ATMOS.2005.660,
  author =	{Sch\"{o}bel, Anita and Scholl, Susanne},
  title =	{{Line Planning with Minimal Traveling Time}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-00-2},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{2},
  editor =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.660},
  URN =		{urn:nbn:de:0030-drops-6601},
  doi =		{10.4230/OASIcs.ATMOS.2005.660},
  annote =	{Keywords: Line planning, real-world problem, integer programming, Dantzig-Wolfe decomposition}
}
  • Refine by Type
  • 19 Document/PDF
  • 5 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 5 2025
  • 1 2019
  • 1 2016
  • 1 2012
  • 1 2010
  • Show More...

  • Refine by Author
  • 5 Kroon, Leo G.
  • 4 Schöbel, Anita
  • 3 Möhring, Rolf H.
  • 3 Wagner, Dorothea
  • 2 Caprara, Alberto
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 13 OASIcs
  • 1 DagRep
  • 1 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Applied computing → Decision analysis
  • 1 Applied computing → Operations research
  • 1 Applied computing → Sequencing and genotyping technologies
  • 1 Applied computing → Transportation
  • Show More...

  • Refine by Keyword
  • 2 Railway traffic
  • 2 algorithms
  • 2 networks
  • 2 optimization
  • 1 Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications
  • 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