Volume
OASIcs, Volume 7
7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)
Event
ATMOS 2007, November 15-16, 2007, Sevilla, SpainEditors
Publication Details
- published at: 2007-11-06
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-939897-04-0
- DBLP: db/conf/atmos/atmos2007
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
OASIcs, Volume 7, ATMOS'07, Complete Volume
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.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
Front Matter
ATMOS 2007 Abstracts Collection -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems
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.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
ATMOS 2007 Preface -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems
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.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
01. A new concept of robustness
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.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
02. Applied Railway Optimization in Production Planning at DSB S-tog - tasks, tools and challenges
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.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
03. Disruption Management in PassengerTransportation - from Air to Tracks
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.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
04. Solution of the Train Platforming Problem
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.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}
}
Document
05. Models for Railway Track Allocation
Abstract
The optimal track allocation problem (OPTRA) is to find, in a given
railway network, a conflict free set of train routes of maximum
value. We study two types of integer programming formulations for
this problem: a standard formulation that models block conflicts in
terms of packing constraints, and a novel formulation of the
`extended' type that is based on additional `configuration'
variables. The packing constraints in the standard formulation stem
from an interval graph and can therefore be separated in polynomial
time. It follows that the LP-relaxation of a strong version of this
model, including all clique inequalities from block conflicts, can
be solved in polynomial time. We prove that the LP-relaxation of
the extended formulation can also be solved in polynomial time, and
that it produces the same LP-bound. Albeit the two formulations are
in this sense equivalent, the extended formulation has advantages
from a computational point of view. It features a constant number of
rows and is amenable to standard column generation
techniques. Results of an empirical model comparison on mesoscopic
data for the Hanover-Fulda-Kassel region of the German long
distance railway network are reported.
Cite as
Ralf Borndörfer and Thomas Schlechte. 05. Models for Railway Track Allocation. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 62-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2007.1170,
author = {Bornd\"{o}rfer, Ralf and Schlechte, Thomas},
title = {{05. Models for Railway Track Allocation}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {62--78},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1170},
URN = {urn:nbn:de:0030-drops-11701},
doi = {10.4230/OASIcs.ATMOS.2007.1170},
annote = {Keywords: Track allocation, train timetabling,integer programming, column generation}
}
Document
06. Solving a Real-World Train Unit Assignment Problem
Abstract
INVALID Windows-1252: We face a real-world train unit assignment problem for an
operator running trains in a regional area. Given a set of timetabled
train trips, each with a required number of passenger seats, and a set
of train units, each with a given number of available seats, the problem
calls for an assignment of the train units to trips, possibly combining
more than one train unit for a given trip, that fulfills the seat requests.
With respect to analogous case studies previously faced in the literature,
ours is characterized by the fairly large number of distinct train unit
types available (in addition to the fairly large number of trips to be
covered). As a result, although there is a wide margin of improvement
over the solution used by the practitioners (as our results show), even
only finding a solution of the same value is challenging in practice. We
present a successful approach, based on an ILP formulation in which
the seat requirement constraints are stated in a “strong†form, derived
from the description of the convex hull of the variant of the knapsack
polytope arising when the sum of the variables is restricted not to exceed
two, illustrating computational results on our case study.
Cite as
Valentina Cacchiani, Alberto Caprara, and Paolo Toth. 06. Solving a Real-World Train Unit Assignment Problem. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 79-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2007.1172,
author = {Cacchiani, Valentina and Caprara, Alberto and Toth, Paolo},
title = {{06. Solving a Real-World Train Unit Assignment Problem}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {79--95},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1172},
URN = {urn:nbn:de:0030-drops-11726},
doi = {10.4230/OASIcs.ATMOS.2007.1172},
annote = {Keywords: }
}
Document
07. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning
Abstract
This paper deals with large-scale crew scheduling problems arising
at the Dutch railway operator, Netherlands Railways (NS). We discuss
several methods to partition large instances into several smaller
ones. These smaller instances are then solved with the commercially
available crew scheduling algorithm TURNI. In this paper, we compare
several partitioning methods with each other. Moreover, we report
some results where we applied different partitioning methods after
each other. With this approach, we were able to cut crew costs with
2\% (about 6 million euro per year).
Cite as
Erwin Abbink, Joel Van't Wout, and Dennis Huisman. 07. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 96-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{abbink_et_al:OASIcs.ATMOS.2007.1168,
author = {Abbink, Erwin and Van't Wout, Joel and Huisman, Dennis},
title = {{07. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {96--106},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1168},
URN = {urn:nbn:de:0030-drops-11686},
doi = {10.4230/OASIcs.ATMOS.2007.1168},
annote = {Keywords: Crew scheduling, large-scale optimization, partitioning}
}
Document
08. Branching Strategies to Improve Regularity of Crew Schedules in Ex-Urban Public Transit
Abstract
We discuss timetables in ex-urban bus traffic that consist of many trips serviced every day together with some exceptions that do not repeat daily. Traditional optimization methods for vehicle and crew scheduling in such cases usually produce schedules that contain irregularities which are not desirable especially from the point of view of the bus drivers. We propose a solution method which improves regularity while partially integrating the vehicle and crew scheduling problems. The approach includes two phases: first we solve the LP relaxation of a set partitioning formulation, using column generation together with Lagrangean relaxation techniques. In a second phase we generate integer solutions using a new combination of local branching and various versions of follow-on branching. Numerical tests with artificial and real instances show that regularity can be improved significantly with no or just a minor increase of costs.
Cite as
Ingmar Steinzen, Leena Suhl, and Natalia Kliewer. 08. Branching Strategies to Improve Regularity of Crew Schedules in Ex-Urban Public Transit. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 107-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{steinzen_et_al:OASIcs.ATMOS.2007.1167,
author = {Steinzen, Ingmar and Suhl, Leena and Kliewer, Natalia},
title = {{08. Branching Strategies to Improve Regularity of Crew Schedules in Ex-Urban Public Transit}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {107--123},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1167},
URN = {urn:nbn:de:0030-drops-11674},
doi = {10.4230/OASIcs.ATMOS.2007.1167},
annote = {Keywords: }
}
Document
09. Periodic Railway Timetabling with Event Flexibility
Abstract
This paper addresses the problem of generating conflict-free periodic train schedules for large railway networks. We follow a two level approach, where a simplified track topology is used to obtain a macro level schedule and the detailed topology is considered locally on the micro level.
To increase the solution space in the interface of the two levels, we propose an extension of the well-known Periodic Event Scheduling Problem (PESP) such that it allows to generate flexible time slots for the departure and arrival times instead of exact times. This Flexible Periodic Event Scheduling Problem (FPESP) formulation considerably increases the chance to obtain feasible solutions (exact train routings) subsequently on the micro level, in particular for stations with dense peak traffic. Total trip time and the time slot sizes are used as multiple objectives and weighted and/or constrained to allocate the flexibility where it is most useful.
Tests on an instance of the 2007 service intention of the Swiss Federal Railways demonstrate the advantage of the FPESP model, while it only moderate increases its solution time in most cases.
Cite as
Gabrio Curzio Caimi, Martin Fuchsberger, Marco Laumanns, and Kaspar Schüpbach. 09. Periodic Railway Timetabling with Event Flexibility. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 124-141, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{caimi_et_al:OASIcs.ATMOS.2007.1173,
author = {Caimi, Gabrio Curzio and Fuchsberger, Martin and Laumanns, Marco and Sch\"{u}pbach, Kaspar},
title = {{09. Periodic Railway Timetabling with Event Flexibility}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {124--141},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1173},
URN = {urn:nbn:de:0030-drops-11735},
doi = {10.4230/OASIcs.ATMOS.2007.1173},
annote = {Keywords: }
}
Document
10. Fast Approaches to Robust Railway Timetabling
Abstract
The Train Timetabling Problem (TTP) consists in finding a train schedule on a railway network that satisfies some operational constraints and maximizes some profit function which counts for the effciency of the infrastructure usage. In practical cases, however, the maximization of the objective function is not enough and one calls for a robust solution that is capable of absorbing as much as possible delays/disturbances on the network. In this paper we propose and analyze computationally four different methods to find robust TTP solutions for the aperiodic (non cyclic) case, that combine Mixed Integer Programming (MIP) and ad-hoc Stochastic Programming/Robust Optimization techniques. We compare
computationally the effectiveness and practical applicability of the four techniques under investigation on real-world test cases from the Italian railway company (Trenitalia). The outcome is that two of the proposed techniques are very fast and provide robust solutions of comparable quality with respect to the standard (but very time consuming) Stochastic
Programming approach.
Cite as
Matteo Fischetti, Arrigo Zanette, and Domenico Salvagnin. 10. Fast Approaches to Robust Railway Timetabling. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 142-157, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{fischetti_et_al:OASIcs.ATMOS.2007.1176,
author = {Fischetti, Matteo and Zanette, Arrigo and Salvagnin, Domenico},
title = {{10. Fast Approaches to Robust Railway Timetabling}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {142--157},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1176},
URN = {urn:nbn:de:0030-drops-11762},
doi = {10.4230/OASIcs.ATMOS.2007.1176},
annote = {Keywords: Train timetabling, Robust Optimization, Stochastic Programming, Computational Experiments}
}
Document
11. Multistage Methods for Freight Train Classification
Abstract
In this paper we establish a consistent encoding of freight train classification methods.
This encoding scheme presents a powerful tool for efficient presentation and analysis of classification methods, which we successfully apply to illustrate the most relevant historic results from a more theoretical point of view.
We analyze their performance precisely and develop new classification methods making use of the inherent optimality condition of the encoding.
We conclude with deriving optimal algorithms and complexity results for restricted real-world settings.
Cite as
Riko Jacob, Peter Marton, Jens Maue, and Marc Nunkesser. 11. Multistage Methods for Freight Train Classification. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 158-174, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{jacob_et_al:OASIcs.ATMOS.2007.1179,
author = {Jacob, Riko and Marton, Peter and Maue, Jens and Nunkesser, Marc},
title = {{11. Multistage Methods for Freight Train Classification}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {158--174},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1179},
URN = {urn:nbn:de:0030-drops-11798},
doi = {10.4230/OASIcs.ATMOS.2007.1179},
annote = {Keywords: Freight trains, sorting algorithms, train classification, shunting, cargo}
}
Document
12. Robust Algorithms and Price of Robustness in Shunting Problems
Abstract
In this paper we provide efficient robust algorithms for shunting
problems concerning the reordering of train cars over a hump. In
particular, we study algorithms able to cope with small
disruptions, as temporary and local availability and/or
malfunctioning of key resources that can occur and affect planned
operations. To this aim, a definition of robust algorithm is
provided. Performances of the proposed algorithms are measured by
the notion of price of robustness. Various scenarios are
considered, and interesting results are presented.
Cite as
Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, Daniele Frigioni, and Alfredo Navarra. 12. Robust Algorithms and Price of Robustness in Shunting Problems. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 175-190, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{cicerone_et_al:OASIcs.ATMOS.2007.1175,
author = {Cicerone, Serafino and D'Angelo, Gianlorenzo and Di Stefano, Gabriele and Frigioni, Daniele and Navarra, Alfredo},
title = {{12. Robust Algorithms and Price of Robustness in Shunting Problems}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {175--190},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1175},
URN = {urn:nbn:de:0030-drops-11755},
doi = {10.4230/OASIcs.ATMOS.2007.1175},
annote = {Keywords: }
}
Document
13. Approximate dynamic programming for rail operations
Abstract
Approximate dynamic programming offers a new modeling and algorithmic strategy for complex problems such as rail operations. Problems in rail operations are often modeled using classical math programming models defined over space-time networks. Even simplified models can be hard to solve, requiring the use of various heuristics. We show how to combine math programming and simulation in an ADP-framework, producing a strategy that looks like simulation using iterative learning. Instead of solving a single, large optimization problem, we solve sequences of smaller ones that can be solved optimally using commercial solvers. We step forward in time using the same flexible logic used in simulation models. We show that we can still obtain near optimal solutions, while modeling operations at a very high level of detail. We describe how to adapt the strategy to the modeling of freight cars and locomotives.
Cite as
Warren Powell and Belgacem Bouzaiene-Ayari. 13. Approximate dynamic programming for rail operations. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 191-208, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{powell_et_al:OASIcs.ATMOS.2007.1180,
author = {Powell, Warren and Bouzaiene-Ayari, Belgacem},
title = {{13. Approximate dynamic programming for rail operations}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {191--208},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1180},
URN = {urn:nbn:de:0030-drops-11804},
doi = {10.4230/OASIcs.ATMOS.2007.1180},
annote = {Keywords: }
}
Document
14. Experimental Study on Speed-Up Techniques for Timetable Information Systems
Abstract
During the last years, impressive speed-up techniques for Dijkstra's algorithm have been developed. Unfortunately, recent research mainly focused on road networks. However, fast algorithms are also needed for other applications like timetable information systems. Even worse, the adaption of recently developed techniques to timetable information is often more complicated than expected.
In this work, we check whether results from road networks are transferable to timetable information. To this end, we present an extensive experimental study of the most prominent speed-up techniques on different types of inputs. It turns out that recently developed techniques are much slower on graphs derived from timetable information than on road networks. In addition, we gain amazing insights into the behavior of speed-up techniques in general.
Cite as
Reinhard Bauer, Daniel Delling, and Dorothea Wagner. 14. Experimental Study on Speed-Up Techniques for Timetable Information Systems. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 209-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{bauer_et_al:OASIcs.ATMOS.2007.1169,
author = {Bauer, Reinhard and Delling, Daniel and Wagner, Dorothea},
title = {{14. Experimental Study on Speed-Up Techniques for Timetable Information Systems}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {209--225},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1169},
URN = {urn:nbn:de:0030-drops-11695},
doi = {10.4230/OASIcs.ATMOS.2007.1169},
annote = {Keywords: Speed-up techniques, timetable information, shortest path}
}
Document
15. Maintenance of Multi-level Overlay Graphs for Timetable Queries
Abstract
In railways systems the timetable is typically represented as a
weighted digraph on which itinerary queries are answered by
shortest path algorithms, usually running Dijkstra's algorithm.
Due to the continuously growing size of real-world graphs, there
is a constant need for faster algorithms and many techniques have
been devised to heuristically speed up Dijkstra's algorithm. One
of these techniques is the multi-level overlay graph, that
has been recently introduced and shown to be experimentally
efficient, especially when applied to timetable information.
In many practical application major disruptions to the normal
operation cannot be completely avoided because of the complexity
of the underlying systems. Timetable information
update after disruptions is considered one of the weakest points
in current railway systems, and this determines the need for an
effective online redesign and update of the shortest paths
information as a consequence of disruptions.
In this paper, we make a step forward toward this direction by
showing some theoretical properties of multi-level overlay graphs
that lead us to the definition of a new data structure for the
dynamic maintenance of a multi-level overlay graph of a given
graph G while weight decrease or weight increase operations are
performed on G. Our solution is theoretically faster than the
recomputation from scratch and allows fast queries.
Cite as
Francesco Bruera, Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, and Daniele Frigioni. 15. Maintenance of Multi-level Overlay Graphs for Timetable Queries. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 226-242, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{bruera_et_al:OASIcs.ATMOS.2007.1171,
author = {Bruera, Francesco and Cicerone, Serafino and D'Angelo, Gianlorenzo and Di Stefano, Gabriele and Frigioni, Daniele},
title = {{15. Maintenance of Multi-level Overlay Graphs for Timetable Queries}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {226--242},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1171},
URN = {urn:nbn:de:0030-drops-11717},
doi = {10.4230/OASIcs.ATMOS.2007.1171},
annote = {Keywords: Timetable Queries, Speed-up techniques for shortest paths, Dynamic maintenance of shortest paths}
}
Document
16. Improved Search for Night Train Connections
Abstract
The search for attractive night train connections is
fundamentally different from ordinary search:
the primary objective of a costumer of a
night train is to have a reasonably long sleeping period without
interruptions due to train changes. For most passenger it is also
undesired to reach the final destination too early in the morning.
These objectives are in sharp contrast to standard information systems
which focus on minimizing the total travel time.
In this paper we present and compare
two new approaches to support queries for night train
connections. These approaches have been integrated into
the Multi-Objective Traffic Information System (MOTIS)
which is currently developed by our group.
Its purpose is to find all train connections which are attractive from
a costumer point of view.
With a computational study we demonstrate that our specialized algorithms
for night train connections are able to satisfy costumer queries much better
than standard methods. This can be achieved with reasonable computational
costs: a specialized night train search requires only a few seconds of
CPU time.
Cite as
Thorsten Gunkel, Matthias Müller-Hannemann, and Mathias Schnee. 16. Improved Search for Night Train Connections. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 243-258, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{gunkel_et_al:OASIcs.ATMOS.2007.1178,
author = {Gunkel, Thorsten and M\"{u}ller-Hannemann, Matthias and Schnee, Mathias},
title = {{16. Improved Search for Night Train Connections}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {243--258},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1178},
URN = {urn:nbn:de:0030-drops-11781},
doi = {10.4230/OASIcs.ATMOS.2007.1178},
annote = {Keywords: Timetable information system, multi-criteria optimization, night trains, computational study}
}
Document
17. A Simulation/Optimization Framework for Locomotive Planning
Abstract
In this paper, we give an overview of the Locomotive Simulater/Optimizer (LSO)
decision support system developed by us for railroads. This software
is designed to imitate locomotive movement across a rail network,
and it simulates all four major components of the system;
trains, locomotives, terminals, and shops in an integrated framework. It
includes about 20 charts that allow evaluating system performance using
standard measures. LSO can be used by locomotive management to per-
form "what-if" analysis and evaluate system performance for different
input data; it provides a safe environment for experimentation. We have
tested the software on real data and output showed that the software
closely imitates day-to-day operations. We have also performed differ-
ent scenario analysis, and reports illustrate that the software correctly
reflects input data changes.
Cite as
Artyom Nahapetyan, Ravindra K. Ahuja, F. Zeynep Sargut, Andy John, and Kamalesh Somani. 17. A Simulation/Optimization Framework for Locomotive Planning. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 259-276, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
Copy BibTex To Clipboard
@InProceedings{nahapetyan_et_al:OASIcs.ATMOS.2007.1182,
author = {Nahapetyan, Artyom and Ahuja, Ravindra K. and Sargut, F. Zeynep and John, Andy and Somani, Kamalesh},
title = {{17. A Simulation/Optimization Framework for Locomotive Planning}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
pages = {259--276},
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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1182},
URN = {urn:nbn:de:0030-drops-11820},
doi = {10.4230/OASIcs.ATMOS.2007.1182},
annote = {Keywords: Railroad simulation, locomotive engine planning}
}