Volume
OASIcs, Volume 12
9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)
Event
ATMOS 2009, September 10, 2009, Copenhagen, DenmarkEditors
Publication Details
- published at: 2009-11-25
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-939897-11-8
- DBLP: db/conf/atmos/atmos2009
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 12, ATMOS'09, Complete Volume
Abstract
OASIcs, Volume 12, ATMOS'09, Complete Volume
Cite as
9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
Copy BibTex To Clipboard
@Proceedings{clausen_et_al:OASIcs.ATMOS.2009,
title = {{OASIcs, Volume 12, ATMOS'09, Complete Volume}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2012},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009},
URN = {urn:nbn:de:0030-drops-35741},
doi = {10.4230/OASIcs.ATMOS.2009},
annote = {Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
Front Matter
ATMOS 2009 Preface -- 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems
Abstract
The 9th ATMOS workshop was held in Copenhagen, September 10, 2008,
within ALGO, an annual meeting combining European algorithms conferences
and workshops. ATMOS focuses specifically on models, algorithms and methods for optimization problems in transportation systems.
Cite as
9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. i-iii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{clausen_et_al:OASIcs.ATMOS.2009.2294,
author = {Clausen, Jens and Di Stefano, Gabriele},
title = {{ATMOS 2009 Preface -- 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
pages = {i--iii},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2294},
URN = {urn:nbn:de:0030-drops-22943},
doi = {10.4230/OASIcs.ATMOS.2009.2294},
annote = {Keywords: Combinatorial optimization, transportation, scheduling, infrastructure planning, timetables}
}
Document
Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected
Abstract
Speeding up multi-criteria search in real timetable information systems
remains a challenge in spite of impressive progress achieved in recent years
for related problems in road networks.
Our goal is to perform multi-criteria range queries, that is, to find all
Pareto-optimal connections with respect to travel time and number of transfers
within a given start time interval. This problem can be modeled as a path
search problem in a time- and event-dependent graph. In this paper, we investigate two key speed-up techniques for a multi-criteria variant of \textsc{Dijkstra}'s algorithm --- arc flags and contraction --- which seem to be strong candidates for railway networks, too.
We describe in detail how these two techniques have to be adapted for a multi-criteria scenario and explain why we can expect only marginal speed-ups (compared to observations in road networks) from a direct implementation. Based on these insights we extend traditional arc-flags to \emph{time-period flags} and introduce \emph{route contraction} as a substitute for node contraction.
A computational study on real queries demonstrates that these techniques
combined with goal-directed search lead to a speed-up of factor 13.08 over the baseline variant for range queries for a full day.
Cite as
Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller-Hannemann. Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{berger_et_al:OASIcs.ATMOS.2009.2148,
author = {Berger, Annabell and Delling, Daniel and Gebhardt, Andreas and M\"{u}ller-Hannemann, Matthias},
title = {{Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
pages = {1--21},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2148},
URN = {urn:nbn:de:0030-drops-21481},
doi = {10.4230/OASIcs.ATMOS.2009.2148},
annote = {Keywords: Timetable information, multi-criteria search, time-dependent networks, arc flags, contraction Timetable information, multi-criteria search, time-dependent networks, arc flags, contraction}
}
Document
An Improved Train Classification Procedure for the Hump Yard Lausanne Triage
Abstract
In this paper we combine an integer programming approach
and a computer simulation tool to successfully develop and verify an
improved classification schedule for a real-world train classification instance.
First, we derive an integer program for computing train classification
schedules based on an earlier developed bitstring representation of
such schedules. We show how to incorporate various practical restrictions
in this model. Secondly, we apply the model to one day of traffic data
of the Swiss classification yard Lausanne Triage. We incorporate all the
operational and infrastructural restrictions of this yard instance in our
integer program. Even with this high number of restrictions, we are able
to compute a schedule that saves a full sorting step and one track compared
to the currently applied procedure. We finally show this improved
schedule is applicable in practice by a thorough computer simulation.
Cite as
Peter Márton, Jens Maue, and Marc Nunkesser. An Improved Train Classification Procedure for the Hump Yard Lausanne Triage. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{marton_et_al:OASIcs.ATMOS.2009.2142,
author = {M\'{a}rton, Peter and Maue, Jens and Nunkesser, Marc},
title = {{An Improved Train Classification Procedure for the Hump Yard Lausanne Triage}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
pages = {1--15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2142},
URN = {urn:nbn:de:0030-drops-21427},
doi = {10.4230/OASIcs.ATMOS.2009.2142},
annote = {Keywords: Train classification, shunting of rolling stock, simulation tools for transport operations, infrastructure planning, freight trains Train classification, shunting of rolling stock, simulation tools for transport operations, infrastructure planning, freight trains}
}
Document
Arc-Flags in Dynamic Graphs
Abstract
Computation of quickest paths has undergoing a rapid development in recent
years. It turns out that many high-performance route planning algorithms are
made up of several basic ingredients. However, not all of those ingredients have
been analyzed in a \emph{dynamic} scenario where edge weights change after
preprocessing. In this work, we present how one of those ingredients, i.e.,
Arc-Flags can be applied in dynamic scenarios
Cite as
Emanuele Berrettini, Gianlorenzo D'Angelo, and Daniel Delling. Arc-Flags in Dynamic Graphs. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{berrettini_et_al:OASIcs.ATMOS.2009.2149,
author = {Berrettini, Emanuele and D'Angelo, Gianlorenzo and Delling, Daniel},
title = {{Arc-Flags in Dynamic Graphs}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
pages = {1--18},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2149},
URN = {urn:nbn:de:0030-drops-21490},
doi = {10.4230/OASIcs.ATMOS.2009.2149},
annote = {Keywords: Shortest Path, Speed-Up Technique, Dynamic Graph Algorithm Shortest Path, Speed-Up Technique, Dynamic Graph Algorithm}
}
Document
Delay Management with Re-Routing of Passengers
Abstract
Trains often arrive delayed at stations where passengers have to change to other trains. The question of delay management is whether these trains should wait for the original train or depart on time. In traditional delay management models passengers always take their originally planned route. This means, they are in case of a missed connection always delayed with the cycle time of the timetable. In this paper, we propose a model where re-routing of passengers is incorporated. \\
To describe the problem we represent it as an event-activity network similar to the one used in traditional delay management, with some additional events to incorporate origin and destination of the passengers. We prove NP-hardness of this problem, and we present an integer programming formulation for which we report the first numerical results. Furthermore, we discuss the variant in which we assume fixed costs for maintaining transfers and we present a polynomial algorithm for the special case of only one origin-destination pair.
Cite as
Twan Dollevoet, Dennis Huisman, Marie Schmidt, and Anita Schoebel. Delay Management with Re-Routing of Passengers. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{dollevoet_et_al:OASIcs.ATMOS.2009.2143,
author = {Dollevoet, Twan and Huisman, Dennis and Schmidt, Marie and Schoebel, Anita},
title = {{Delay Management with Re-Routing of Passengers}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
pages = {1--17},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2143},
URN = {urn:nbn:de:0030-drops-21433},
doi = {10.4230/OASIcs.ATMOS.2009.2143},
annote = {Keywords: Transportation, Delay Management, Re-Routing, OD-pairs Transportation, Delay Management, Re-Routing, OD-pairs}
}
Document
Edges as Nodes - a New Approach to Timetable Information
Abstract
In this paper we suggest a new approach to timetable information by
introducing the ``edge-converted graph'' of a timetable.
Using this model we present simple algorithms that solve the
earliest arrival problem (EAP) and the minimum number of transfers problem
(MNTP).
For constant-degree graphs this yields linear-time algorithms for EAP and
MNTP which improves upon the known \emph{Dijkstra}-based approaches.
We also test the performance of our algorithms against the classical
algorithms for EAP and MNTP in the time-expanded model.
Cite as
Olaf Beyersdorff and Yevgen Nebesov. Edges as Nodes - a New Approach to Timetable Information. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{beyersdorff_et_al:OASIcs.ATMOS.2009.2147,
author = {Beyersdorff, Olaf and Nebesov, Yevgen},
title = {{Edges as Nodes - a New Approach to Timetable Information}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
pages = {1--12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2147},
URN = {urn:nbn:de:0030-drops-21478},
doi = {10.4230/OASIcs.ATMOS.2009.2147},
annote = {Keywords: Timetable infomation, earliest arrival problem, minimum number of transfers problem, time-expanded model Timetable infomation, earliest arrival problem, minimum number of transfers problem, time-expanded model}
}
Document
Efficient Route Planning in Flight Networks
Abstract
We present a set of three new time-dependent models with increasing flexibility for realistic route planning in flight networks. By these means, we obtain small graph sizes while modeling airport procedures in a realistic way. With these graphs, we are able to efficiently compute a set of best connections with multiple criteria over a full day. It even turns out that due to the very limited graph sizes it is feasible to precompute full distance tables between all
airports. As a result, best connections can be retrieved in a few microseconds on real world data.
Cite as
Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis. Efficient Route Planning in Flight Networks. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{delling_et_al:OASIcs.ATMOS.2009.2145,
author = {Delling, Daniel and Pajor, Thomas and Wagner, Dorothea and Zaroliagis, Christos},
title = {{Efficient Route Planning in Flight Networks}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
pages = {1--17},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2145},
URN = {urn:nbn:de:0030-drops-21450},
doi = {10.4230/OASIcs.ATMOS.2009.2145},
annote = {Keywords: Timetable information, flight modeling, shortest paths, multi criteria, table lookups Timetable information, flight modeling, shortest paths, multi criteria, table lookups}
}
Document
MILP formulations of cumulative constraints for railway scheduling - A comparative study
Abstract
This paper introduces two Mixed Integer Linear Programming (MILP)
models for railway traffic planning using a cumulative scheduling
constraint and associated pre-processing filters. We compare standard
solver performance for these models on three sets of problems from
the railway domain and for two of them, where tasks have unitary resource
consumption, we also compare them with two more conventional models.
In the experiments, the solver performance of one of the cumulative
models is clearly the best and is also shown to scale very well for
a large scale practical railway scheduling problem.
Cite as
Martin Aronsson, Markus Bohlin, and Per Kreuger. MILP formulations of cumulative constraints for railway scheduling - A comparative study. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{aronsson_et_al:OASIcs.ATMOS.2009.2141,
author = {Aronsson, Martin and Bohlin, Markus and Kreuger, Per},
title = {{MILP formulations of cumulative constraints for railway scheduling - A comparative study}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
pages = {1--13},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2141},
URN = {urn:nbn:de:0030-drops-21413},
doi = {10.4230/OASIcs.ATMOS.2009.2141},
annote = {Keywords: Railway transport scheduling, Cumulative scheduling, Mixed Integer Linear Programming (MILP) modelling and pre-processing Railway transport scheduling, Cumulative scheduling, Mixed Integer Linear Programming (MILP) modelling and pre-processing}
}
Document
On Assessing Robustness in Transportation Planning
Abstract
We consider a fundamental problem, called \emph{QoS-aware Multicommodity Flow},
for assessing robustness in transportation planning. It constitutes a
natural generalization of the weighted multicommodity flow problem, where
the demands and commodity values are elastic to the Quality-of-Service (QoS)
characteristics of the underlying network. The problem is also fundamental in
other domains beyond transportation planning. In this work, we provide an
extensive experimental study of two FPTAS for the QoS-aware Multicommodity
Flow Problem enhanced with several heuristics, and show the superiority of
a new heuristic we introduce here.
Cite as
Apostolos Bessas and Christos Zaroliagis. On Assessing Robustness in Transportation Planning. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{bessas_et_al:OASIcs.ATMOS.2009.2146,
author = {Bessas, Apostolos and Zaroliagis, Christos},
title = {{On Assessing Robustness in Transportation Planning}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
pages = {1--16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2146},
URN = {urn:nbn:de:0030-drops-21469},
doi = {10.4230/OASIcs.ATMOS.2009.2146},
annote = {Keywords: QoS-ware Multicommodity Flow, Robust Planning, Demand Elasticity, Packing LP QoS-ware Multicommodity Flow, Robust Planning, Demand Elasticity, Packing LP}
}
Document
Scheduling Aircraft to Reduce Controller Workload
Abstract
We address a problem in air traffic management: scheduling flights
in order to minimize the maximum number of aircraft that
simultaneously lie within a single air traffic control sector at
any time $t$. Since the problem is a generalization of the NP-hard
no-wait job-shop scheduling, we resort to heuristics. We report
experimental results for real-world flight data.
Cite as
Joondong Kim, Alexander Kroeller, and Joseph Mitchell. Scheduling Aircraft to Reduce Controller Workload. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. -12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{kim_et_al:OASIcs.ATMOS.2009.2144,
author = {Kim, Joondong and Kroeller, Alexander and Mitchell, Joseph},
title = {{Scheduling Aircraft to Reduce Controller Workload}},
booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-11-8},
ISSN = {2190-6807},
year = {2009},
volume = {12},
editor = {Clausen, Jens and Di Stefano, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2144},
URN = {urn:nbn:de:0030-drops-21443},
doi = {10.4230/OASIcs.ATMOS.2009.2144},
annote = {Keywords: Air Traffic Management, trajectory scheduling, flight plan scheduling, no-wait job shop Air Traffic Management, trajectory scheduling, flight plan scheduling, no-wait job shop}
}