15 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.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-dev.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-dev.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-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
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-dev.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-dev.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-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
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-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
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-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
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-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
DOI: 10.4230/OASIcs.ATMOS.2005.657
Paying Less for Train Connections with MOTIS

Authors: Matthias Müller-Hannemann and Mathias Schnee

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

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
DOI: 10.4230/OASIcs.ATMOS.2005.661
Station Location - Complexity and Approximation

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

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

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}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2005.656
ATMOS Preface -- 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

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
DOI: 10.4230/OASIcs.ATMOS.2005.662
Combinatorial Optimization Model for Railway Engine Assignment Problem

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

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

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
DOI: 10.4230/DagSemProc.04261.1
04261 Abstracts Collection – Algorithmic Methods for Railway Optimization

Authors: Leo G. Kroon, Dorothea Wagner, Frank Geraets, and Christos Zaroliagis

Published in: Dagstuhl Seminar Proceedings, Volume 4261, Algorithmic Methods for Railway Optimization (2006)

Abstract
From 20.06.04 to 25.06.04, the Dagstuhl Seminar 04261 ``Algorithmic Methods for Railway Optimization'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Leo G. Kroon, Dorothea Wagner, Frank Geraets, and Christos Zaroliagis. 04261 Abstracts Collection – Algorithmic Methods for Railway Optimization. In Algorithmic Methods for Railway Optimization. Dagstuhl Seminar Proceedings, Volume 4261, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kroon_et_al:DagSemProc.04261.1,
  author =	{Kroon, Leo G. and Wagner, Dorothea and Geraets, Frank and Zaroliagis, Christos},
  title =	{{04261 Abstracts Collection – Algorithmic Methods for Railway Optimization}},
  booktitle =	{Algorithmic Methods for Railway Optimization},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{4261},
  editor =	{Leo G. Kroon and Frank Geraets and Dorothea Wagner and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04261.1},
  URN =		{urn:nbn:de:0030-drops-4712},
  doi =		{10.4230/DagSemProc.04261.1},
  annote =	{Keywords: }
}
  • Refine by Author
  • 5 Kroon, Leo G.
  • 3 Möhring, Rolf H.
  • 3 Schöbel, Anita
  • 3 Wagner, Dorothea
  • 2 Caprara, Alberto
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization

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

  • Refine by Type
  • 14 document
  • 1 volume

  • Refine by Publication Year
  • 10 2006
  • 1 2008
  • 1 2010
  • 1 2012
  • 1 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact