OASIcs, Volume 2

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



Thumbnail PDF

Event

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

Editors

Leo G. Kroon
Rolf H. Möhring

Publication Details

  • published at: 2006-07-25
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
  • ISBN: 978-3-939897-00-2
  • DBLP: db/conf/atmos/atmos2005

Access Numbers

Documents

No documents found matching your filter selection.
Document
Complete Volume
OASIcs, Volume 2, ATMOS'05, Complete Volume

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


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-dev.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
Front Matter
ATMOS Preface -- Algorithmic Methods and Models for Optimization of Railways

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


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

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


Copy BibTex To Clipboard

@InProceedings{kroon_et_al:OASIcs.ATMOS.2005.656,
  author =	{Kroon, Leo G. and M\"{o}hring, Rolf H.},
  title =	{{ATMOS  Preface -- Algorithmic Methods and Models for Optimization of Railways}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{i--vi},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.656},
  URN =		{urn:nbn:de:0030-drops-6565},
  doi =		{10.4230/OASIcs.ATMOS.2005.656},
  annote =	{Keywords: Railway traffic, networks, algorithms, optimization}
}
Document
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


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-dev.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
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


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-dev.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
Combinatorial Optimization Model for Railway Engine Assignment Problem

Authors: Tibor Illés, Márton Makai, and Zsuzsanna Vaik


Abstract
This paper presents an experimental study for the Hungarian State Railway Company (M\'AV). The engine assignment problem was solved at M\'AV by their experts without using any explicit operations research tool. Furthermore, the operations research model was not known at the company. The goal of our project was to introduce and solve an operations research model for the engine assignment problem on real data sets. For the engine assignment problem we are using a combinatorial optimization model. At this stage of research the single type train that is pulled by a single type engine is modeled and solved for real data. There are two regions in Hungary where the methodology described in this paper can be used and M\'AV started to use it regularly. There is a need to generalize the model for multiple type trains and multiple type engines.

Cite as

Tibor Illés, Márton Makai, and Zsuzsanna Vaik. Combinatorial Optimization Model for Railway Engine Assignment Problem. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{illes_et_al:OASIcs.ATMOS.2005.662,
  author =	{Ill\'{e}s, Tibor and Makai, M\'{a}rton and Vaik, Zsuzsanna},
  title =	{{Combinatorial Optimization Model for Railway Engine Assignment Problem}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--10},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.662},
  URN =		{urn:nbn:de:0030-drops-6629},
  doi =		{10.4230/OASIcs.ATMOS.2005.662},
  annote =	{Keywords: Engine assignment, circulation}
}
Document
Computer-based decision support for railway traffic scheduling and dispatching: A review of models and algorithms

Authors: Johanna Törnquist


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-dev.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
Line Planning with Minimal Traveling Time

Authors: Anita Schöbel and Susanne Scholl


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-dev.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}
}
Document
Paying Less for Train Connections with MOTIS

Authors: Matthias Müller-Hannemann and Mathias Schnee


Abstract
Finding cheap train connections for long-distance traffic is algorithmically a hard task due to very complex tariff regulations. Several new tariff options have been developed in recent years, partly to react on the stronger competition with low-cost airline carriers. In such an environment, it becomes more and more important that search engines for travel connections are able to find special offers efficiently. We have developed a multi-objective traffic information system (MOTIS) which finds all attractive train connections with respect to travel time, number of interchanges, and ticket costs. In contrast, most servers for timetable information as well as the theoretical literature on this subject focus only on travel time as the primary objective, and secondary objectives like the number of interchanges are treated only heuristically. The purpose of this paper is to show by means of a case study how several of the most common tariff rules (including special offers) can be embedded into a general multi-objective search tool. Computational results show that a multi-objective search with a mixture of tariff rules can be done almost as fast as just with one regular tariff. For the train schedule of Germany, a query can be answered within 1.9s on average on a standard PC.

Cite as

Matthias Müller-Hannemann and Mathias Schnee. Paying Less for Train Connections with MOTIS. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{mullerhannemann_et_al:OASIcs.ATMOS.2005.657,
  author =	{M\"{u}ller-Hannemann, Matthias and Schnee, Mathias},
  title =	{{Paying Less for Train Connections with MOTIS}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--19},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.657},
  URN =		{urn:nbn:de:0030-drops-6572},
  doi =		{10.4230/OASIcs.ATMOS.2005.657},
  annote =	{Keywords: Timetable information system, multi-criteria optimization, shortest paths, fares, special offers, long-distance traffic}
}
Document
Station Location - Complexity and Approximation

Authors: Steffen Mecke, Anita Schöbel, and Dorothea Wagner


Abstract
We consider a geometric set covering problem. In its original form it consists of adding stations to an existing geometric transportation network so that each of a given set of settlements is not too far from a station. The problem is known to be NP-hard in general. However, special cases with certain properties have been shown to be efficiently solvable in theory and in practice, especially if the covering matrix has (almost) consecutive ones property. In this paper we are narrowing the gap between intractable and efficiently solvable cases of the problem. We also present an approximation algorithm for cases with almost consecutive ones property.

Cite as

Steffen Mecke, Anita Schöbel, and Dorothea Wagner. Station Location - Complexity and Approximation. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{mecke_et_al:OASIcs.ATMOS.2005.661,
  author =	{Mecke, Steffen and Sch\"{o}bel, Anita and Wagner, Dorothea},
  title =	{{Station Location - Complexity and Approximation}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  pages =	{1--11},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2005.661},
  URN =		{urn:nbn:de:0030-drops-6612},
  doi =		{10.4230/OASIcs.ATMOS.2005.661},
  annote =	{Keywords: Station Location, facility location, complexity, approximation}
}

Filters


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