DROPS

Volume

OASIcs, Volume 7

7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)

ATMOS 2007, November 15-16, 2007, Sevilla, Spain

Editors: Ravindra K. Ahuja, Christian Liebchen, and Juan A. Mesa

Document

DOI: 10.4230/OASIcs.ATMOS.2023.5

Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice

Authors: Berenike Masing, Niels Lindner, and Christian Liebchen

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract

We consider maintenance sites for urban rail systems, where unavailable tracks typically require changes to the regular timetable, and often even to the line plan. In this paper, we present an integrated mixed-integer linear optimization model to compute an optimal line plan that makes best use of the available tracks, together with a periodic timetable, including its detailed routing on the tracks within the stations. The key component is a flexible, turn-sensitive event-activity network that allows to integrate line planning and train routing using a track choice extension of the Periodic Event Scheduling Problem (PESP). Major goals are to maintain as much of the regular service as possible, and to keep the necessary changes rather local. Moreover, we present computational results on real construction site scenarios on the S-Bahn Berlin network. We demonstrate that this integrated problem is indeed solvable on practically relevant instances.

Cite as

Berenike Masing, Niels Lindner, and Christian Liebchen. Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{masing_et_al:OASIcs.ATMOS.2023.5,
  author =	{Masing, Berenike and Lindner, Niels and Liebchen, Christian},
  title =	{{Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{5:1--5:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.5},
  URN =		{urn:nbn:de:0030-drops-187669},
  doi =		{10.4230/OASIcs.ATMOS.2023.5},
  annote =	{Keywords: Periodic Timetabling, Line Planning, Track Choice, Mixed-Integer Programming, Construction Sites, Railway Rescheduling}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2021.2

Forward Cycle Bases and Periodic Timetabling

Authors: Niels Lindner, Christian Liebchen, and Berenike Masing

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract

Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance R1L1 of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.

Cite as

Niels Lindner, Christian Liebchen, and Berenike Masing. Forward Cycle Bases and Periodic Timetabling. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2021.2,
  author =	{Lindner, Niels and Liebchen, Christian and Masing, Berenike},
  title =	{{Forward Cycle Bases and Periodic Timetabling}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{2:1--2:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.2},
  URN =		{urn:nbn:de:0030-drops-148719},
  doi =		{10.4230/OASIcs.ATMOS.2021.2},
  annote =	{Keywords: Periodic Timetabling, Cycle Bases, Mixed Integer Programming}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2020.5

Determining All Integer Vertices of the PESP Polytope by Flipping Arcs

Authors: Niels Lindner and Christian Liebchen

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract

We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. We finally present better dual bounds for the smallest and largest instance of the benchmarking library PESPlib.

Cite as

Niels Lindner and Christian Liebchen. Determining All Integer Vertices of the PESP Polytope by Flipping Arcs. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2020.5,
  author =	{Lindner, Niels and Liebchen, Christian},
  title =	{{Determining All Integer Vertices of the PESP Polytope by Flipping Arcs}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{5:1--5:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.5},
  URN =		{urn:nbn:de:0030-drops-131411},
  doi =		{10.4230/OASIcs.ATMOS.2020.5},
  annote =	{Keywords: Periodic Event Scheduling Problem, Periodic Timetabling, Mixed Integer Programming}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2019.2

New Perspectives on PESP: T-Partitions and Separators

Authors: Niels Lindner and Christian Liebchen

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

Abstract

In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions and dual bounds for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that have been proposed, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. This heuristic already had been proven to be useful in computational experiments [Ralf Borndörfer et al., 2019], and we locate it in the more general concept of what we denote T-partitions. With the second of these algorithms we propose to turn a strategy, that has been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time.

Cite as

Niels Lindner and Christian Liebchen. New Perspectives on PESP: T-Partitions and Separators. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2019.2,
  author =	{Lindner, Niels and Liebchen, Christian},
  title =	{{New Perspectives on PESP: T-Partitions and Separators}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{2:1--2:18},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.2},
  URN =		{urn:nbn:de:0030-drops-114144},
  doi =		{10.4230/OASIcs.ATMOS.2019.2},
  annote =	{Keywords: Periodic Event Scheduling Problem, Periodic Timetabling, Graph Partitioning, Graph Separators, Balanced Cuts}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2018.16

A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable

Authors: Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract

We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [Julius Paetzold et al., 2017], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.

Cite as

Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner. A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2018.16,
  author =	{Bornd\"{o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels},
  title =	{{A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{16:1--16:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.16},
  URN =		{urn:nbn:de:0030-drops-97214},
  doi =		{10.4230/OASIcs.ATMOS.2018.16},
  annote =	{Keywords: Vehicle Scheduling, Periodic Timetabling, Bipartite Matching}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2017.12

An Improved Algorithm for the Periodic Timetabling Problem

Authors: Marc Goerigk and Christian Liebchen

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract

We consider the computation of periodic timetables, which is a key task in the service design process of public transportation companies. We propose a new approach for solving the periodic timetable optimisation problem. It consists of a (partially) heuristic network aggregation to reduce the problem size and make it accessible to standard mixed-integer programming (MIP) solvers. We alternate the invocation of a MIP solver with the well-known problem specific modulo network simplex heuristic (ModSim). This iterative approach helps the ModSim-method to overcome local minima efficiently, and provides the MIP solver with better initial solutions. Our computational experiments are based on the 16 railway instances of the PESPlib, which is the only currently available collection of periodic event scheduling problem instances. For each of these instances, we are able to reduce the objective values of previously best known solutions by at least 10.0%, and up to 22.8% with our iterative combined method.

Cite as

Marc Goerigk and Christian Liebchen. An Improved Algorithm for the Periodic Timetabling Problem. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{goerigk_et_al:OASIcs.ATMOS.2017.12,
  author =	{Goerigk, Marc and Liebchen, Christian},
  title =	{{An Improved Algorithm for the Periodic Timetabling Problem}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{12:1--12:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.12},
  URN =		{urn:nbn:de:0030-drops-78924},
  doi =		{10.4230/OASIcs.ATMOS.2017.12},
  annote =	{Keywords: periodic timetabling, railway optimisation, modulo network simplex, periodic event scheduling problem}
}

Document

Complete Volume

DOI: 10.4230/OASIcs.ATMOS.2007

OASIcs, Volume 7, ATMOS'07, Complete Volume

Authors: Christian Liebchen, Ravindra K. Ahuja, and Juan A. Mesa

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract

OASIcs, Volume 7, ATMOS'07, Complete Volume

Cite as

7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{liebchen_et_al:OASIcs.ATMOS.2007,
  title =	{{OASIcs, Volume 7, ATMOS'07, Complete Volume}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007},
  URN =		{urn:nbn:de:0030-drops-35695},
  doi =		{10.4230/OASIcs.ATMOS.2007},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2008.1580

The Second Chvatal Closure Can Yield Better Railway Timetables

Authors: Christian Liebchen and Elmar Swarat

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

Abstract

We investigate the polyhedral structure of the Periodic Event Scheduling Problem (PESP), which is commonly used in periodic railway timetable optimization. This is the first investigation of Chvatal closures and of the Chvatal rank of PESP instances. In most detail, we first provide a PESP instance on only two events, whose Chvatal rank is very large. Second, we identify an instance for which we prove that it is feasible over the first Chvatal closure, and also feasible for another prominent class of known valid inequalities, which we reveal to live in much larger Chvatal closures. In contrast, this instance turns out to be infeasible already over the second Chvatal closure. We obtain the latter result by introducing new valid inequalities for the PESP, the multi-circuit cuts. In the past, for other classes of valid inequalities for the PESP, it had been observed that these do not have any effect in practical computations. In contrast, the new multi-circuit cuts that we are introducing here indeed show some effect in the computations that we perform on several real-world instances - a positive effect, in most of the cases.

Cite as

Christian Liebchen and Elmar Swarat. The Second Chvatal Closure Can Yield Better Railway Timetables. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{liebchen_et_al:OASIcs.ATMOS.2008.1580,
  author =	{Liebchen, Christian and Swarat, Elmar},
  title =	{{The Second Chvatal Closure Can Yield Better Railway Timetables}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--19},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1580},
  URN =		{urn:nbn:de:0030-drops-15802},
  doi =		{10.4230/OASIcs.ATMOS.2008.1580},
  annote =	{Keywords: }
}

Document

DOI: 10.4230/OASIcs.ATMOS.2007.1237

ATMOS 2007 Preface -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Authors: Ravindra K. Ahuja, Christian Liebchen, and Juan A. Mesa

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract

Proceedings of the 7thWorkshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, held on No- vember 15 and November 16, 2007 in Sevilla, Spain.

Cite as

Ravindra K. Ahuja, Christian Liebchen, and Juan A. Mesa. ATMOS 2007 Preface -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{ahuja_et_al:OASIcs.ATMOS.2007.1237,
  author =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  title =	{{ATMOS 2007 Preface -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{1--7},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1237},
  URN =		{urn:nbn:de:0030-drops-12373},
  doi =		{10.4230/OASIcs.ATMOS.2007.1237},
  annote =	{Keywords: Operations research, scheduled transport, railway optimization}
}

Document

Front Matter

DOI: 10.4230/OASIcs.ATMOS.2007.1184

ATMOS 2007 Abstracts Collection -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Authors: Ravindra K. Ahuja, Christian Liebchen, and Juan A. Mesa

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract

Proceedings of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, held on November 15 and November 16, 2007 in Sevilla, Spain.

Cite as

7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. i-xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{ahuja_et_al:OASIcs.ATMOS.2007.1184,
  author =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  title =	{{ATMOS 2007 Abstracts Collection -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{i--xi},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1184},
  URN =		{urn:nbn:de:0030-drops-11840},
  doi =		{10.4230/OASIcs.ATMOS.2007.1184},
  annote =	{Keywords: Operations research, scheduled transport, railway optimization}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2007.1177

01. A new concept of robustness

Authors: Ricardo García, Ángel Marín, Juan A. Mesa, Federico Perea, and Doroteo Verastegui

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract

In this paper a new concept of robustness is introduced and the corresponding optimization problem is stated. This new concept is applied to transportation network designs in which the set of scenarios arising from the uncertainty of the parameters follows a probability distribution. The $p$-robustness concept is aimed to problems where the feasibility of the solutions is not affected by the uncertainty of the parameters. In order to compare the solution with those of other already known concepts of robustness, some computational experiments with real data are included.

Cite as

Ricardo García, Ángel Marín, Juan A. Mesa, Federico Perea, and Doroteo Verastegui. 01. A new concept of robustness. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{garcia_et_al:OASIcs.ATMOS.2007.1177,
  author =	{Garc{\'\i}a, Ricardo and Mar{\'\i}n, \'{A}ngel and Mesa, Juan A. and Perea, Federico and Verastegui, Doroteo},
  title =	{{01. A new concept of robustness}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1177},
  URN =		{urn:nbn:de:0030-drops-11779},
  doi =		{10.4230/OASIcs.ATMOS.2007.1177},
  annote =	{Keywords: }
}

Document

DOI: 10.4230/OASIcs.ATMOS.2007.1181

02. Applied Railway Optimization in Production Planning at DSB S-tog - tasks, tools and challenges

Authors: Jens Clausen

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract

Efficient public transportation is becoming increasingly vital for modern capitals. DSB S-tog a/s is the major supplier of rail traffic on the infrastructure of the city-rail network in Copenhagen. S-tog has experienced a demand for increasing volume and quality of the transportation offered to the customers, and has concurrently been met with demands for higher efficiency in the daily operation. The plans of timetable, rolling stock and crew must hence allow for a high level of customer service, be efficient, and be robust against disturbances of operations. It is a highly non-trivial task to meet these conflicting goals. S-tog has therefore on the strategic level decided to use software with optimization capabilities in the planning processes. We describe the current status for each activity using optimization or simulation as a tool: Timetable evaluation, rolling stock planning, and crew scheduling. In addition we describe on-going efforts in using mathematical models in activities such as timetable design and work-force planning. We also identify some organizatorial key factors, which have paved the way for extended use of optimization methods in railway production planning.

Cite as

Jens Clausen. 02. Applied Railway Optimization in Production Planning at DSB S-tog - tasks, tools and challenges. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 15-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{clausen:OASIcs.ATMOS.2007.1181,
  author =	{Clausen, Jens},
  title =	{{02. Applied Railway Optimization in Production Planning at DSB S-tog - tasks, tools and challenges}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{15--29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1181},
  URN =		{urn:nbn:de:0030-drops-11819},
  doi =		{10.4230/OASIcs.ATMOS.2007.1181},
  annote =	{Keywords: Operations research, urban railways, timetabling, crew, disruption management}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2007.1183

03. Disruption Management in PassengerTransportation - from Air to Tracks

Authors: Jens Clausen

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract

Over the last 10 years there has been a tremendous growth in air transportation of passengers. Both airports and airspace are close to saturation with respect to capacity, leading to delays caused by disruptions. At the same time the amount of vehicular traffic around and in all larger cities of the world has show a dramatic increase as well. Public transportation by e.g. rail has come into focus, and hence also the service level provided by suppliers ad public transportation. These transportation systems are likewise very vulnerable to disruptions. In the airline industry there is a long tradition for using advanced mathematical models as the basis for planning of resources as aircraft and crew. These methods are now also coming to use in the process of handling disruptions, and robustness of plans has received much interest. Commercial IT-systems supplying decision support for recovery of disrupted operations are becoming available. The use of advanced planning and recovery methods in the railway industry currently gains momentum. The current paper gives a short overview over the methods used for planning and disruption management in the airline industry. The situation regarding railway optimization is then described and discussed. The issue of robustness of timetables and plans for rolling stock and crew is also addressed.

Cite as

Jens Clausen. 03. Disruption Management in PassengerTransportation - from Air to Tracks. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 30-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{clausen:OASIcs.ATMOS.2007.1183,
  author =	{Clausen, Jens},
  title =	{{03. Disruption Management in PassengerTransportation - from Air to Tracks}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{30--47},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1183},
  URN =		{urn:nbn:de:0030-drops-11836},
  doi =		{10.4230/OASIcs.ATMOS.2007.1183},
  annote =	{Keywords: }
}

Document

DOI: 10.4230/OASIcs.ATMOS.2007.1174

04. Solution of the Train Platforming Problem

Authors: Alberto Caprara, Laura Galli, and Paolo Toth

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract

In this paper we study a general formulation of the train platforming problem, which contains as special cases all the versions previously considered in the literature as well as a case study from the Italian Infrastructure manager that we addressed. In particular, motivated by our case study, we consider a general quadratic objective function, and propose a new way to linearize it by using a small number of new variables along with a set of constraints that can be separated efficiently by solving an appropriate linear program. The resulting integer linear programming formulation has a continuous relaxation that leads to strong bounds on the optimal value. For the instances in our case study, we show that a simple diving heuristic based on this relaxation produces solutions that are much better than those produced by a simple heuristic currently in use, and that often turn out to be (nearly-) optimal.

Cite as

Alberto Caprara, Laura Galli, and Paolo Toth. 04. Solution of the Train Platforming Problem. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 49-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{caprara_et_al:OASIcs.ATMOS.2007.1174,
  author =	{Caprara, Alberto and Galli, Laura and Toth, Paolo},
  title =	{{04. Solution of the Train Platforming Problem}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{49--61},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1174},
  URN =		{urn:nbn:de:0030-drops-11741},
  doi =		{10.4230/OASIcs.ATMOS.2007.1174},
  annote =	{Keywords: Train Platforming, Train Routing, Branch-and-Cut-and-Price, Quadratic Objective Function, Linearization}
}

28 Search Results for "Liebchen, Christian"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message