Volume
OASIcs, Volume 59
17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Event
ATMOS 2017, September 7-8, 2017, Vienna, AustriaEditors
Publication Details
- published at: 2017-09-04
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-042-2
- DBLP: db/conf/atmos/atmos2017
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 59, ATMOS'17, Complete Volume
Abstract
OASIcs, Volume 59, ATMOS'17, Complete Volume
Cite as
17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@Proceedings{dangelo_et_al:OASIcs.ATMOS.2017,
title = {{OASIcs, Volume 59, ATMOS'17, Complete Volume}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017},
URN = {urn:nbn:de:0030-drops-79109},
doi = {10.4230/OASIcs.ATMOS.2017},
annote = {Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Combinatorics, Graph Theory, Applications}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Organization
Abstract
Front Matter, Table of Contents, Preface, Organization
Cite as
17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{dangelo_et_al:OASIcs.ATMOS.2017.0,
author = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
title = {{Front Matter, Table of Contents, Preface, Organization}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {0:i--0:x},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.0},
URN = {urn:nbn:de:0030-drops-78872},
doi = {10.4230/OASIcs.ATMOS.2017.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Organization}
}
Document
Revenue Maximization in Online Dial-A-Ride
Abstract
We study a variation of the Online-Dial-a-Ride Problem where each request comes with not only a source, destination and release time, but also has an associated revenue. The server's goal is to maximize its total revenue within a given time limit, T. We show that the competitive ratio is unbounded for any deterministic online algorithm for the problem. We then provide a 3-competitive algorithm for the problem in a uniform metric space and a 6-competitive algorithm for the general case of weighted graphs (under reasonable assumptions about the input instance). We conclude with an experimental evaluation of our algorithm in simulated settings inspired by real-world Dial-a-Ride data. Experimental results show that our algorithm performs well when compared to an offline version of the algorithm and a greedy algorithm.
Cite as
Ananya Christman, Christine Chung, Nicholas Jaczko, Marina Milan, Anna Vasilchenko, and Scott Westvold. Revenue Maximization in Online Dial-A-Ride. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{christman_et_al:OASIcs.ATMOS.2017.1,
author = {Christman, Ananya and Chung, Christine and Jaczko, Nicholas and Milan, Marina and Vasilchenko, Anna and Westvold, Scott},
title = {{Revenue Maximization in Online Dial-A-Ride}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {1:1--1:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.1},
URN = {urn:nbn:de:0030-drops-78886},
doi = {10.4230/OASIcs.ATMOS.2017.1},
annote = {Keywords: online algorithms, dial-a-ride, competitive analysis, vehicle routing, metric space}
}
Document
Truthful Mechanisms for Delivery with Agents
Abstract
We study the game-theoretic task of selecting mobile agents to deliver multiple items on a network. An instance is given by $m$ packages (physical objects) which have to be transported between specified source-target pairs in an undirected graph, and $k$ mobile heterogeneous agents, each being able to transport one package at a time. Following a recent model [Baertschi et al. 2017], each agent i has a different rate of energy consumption per unit distance traveled, i.e., its weight. We are interested in optimizing or approximating the total energy consumption over all selected agents.
Unlike previous research, we assume the weights to be private values known only to the respective agents. We present three different mechanisms which select, route and pay the agents in a truthful way that guarantees voluntary participation of the agents, while approximating the optimum energy consumption by a constant factor. To this end, we analyze a previous structural result and an approximation algorithm given in [Baertschi et al. 2017]. Finally, we show that for some instances in the case of a single package, the sum of the payments can be bounded in terms of the optimum.
Cite as
Andreas Bärtschi, Daniel Graf, and Paolo Penna. Truthful Mechanisms for Delivery with Agents. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{bartschi_et_al:OASIcs.ATMOS.2017.2,
author = {B\"{a}rtschi, Andreas and Graf, Daniel and Penna, Paolo},
title = {{Truthful Mechanisms for Delivery with Agents}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {2:1--2:17},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.2},
URN = {urn:nbn:de:0030-drops-78891},
doi = {10.4230/OASIcs.ATMOS.2017.2},
annote = {Keywords: delivery, agent, energy optimization, approximation mechanism, frugality}
}
Document
Dynamic Time-Dependent Routing in Road Networks Through Sampling
Abstract
We study the earliest arrival and profile problems in road networks with time-dependent functions as arc weights and dynamic updates. We present and experimentally evaluate simple, sampling-based, heuristic algorithms. Our evaluation is performed on large, current, production-grade road graph data with time-dependent arc weights. It clearly shows that the proposed algorithms are fast and compute paths with a sufficiently small error for most practical applications. We experimentally compare our algorithm against the current state-of-the-art. Our experiments reveal, that the memory consumption of existing algorithms is prohibitive on large instances. Our approach does not suffer from this limitation. Further, our algorithm is the only competitor able to answer profile queries on all test instances below 50ms. As our algorithm is simple to implement, we believe that it is a good fit for many realworld applications.
Cite as
Ben Strasser. Dynamic Time-Dependent Routing in Road Networks Through Sampling. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{strasser:OASIcs.ATMOS.2017.3,
author = {Strasser, Ben},
title = {{Dynamic Time-Dependent Routing in Road Networks Through Sampling}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {3:1--3:17},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.3},
URN = {urn:nbn:de:0030-drops-78972},
doi = {10.4230/OASIcs.ATMOS.2017.3},
annote = {Keywords: shortest path, time-dependent, road graphs, preprocessing}
}
Document
Improved Oracles for Time-Dependent Road Networks
Abstract
A novel landmark-based oracle (CFLAT) is presented, which provides earliest-arrival-time route plans in time-dependent road networks. To our knowledge, this is the first oracle that preprocesses combinatorial structures (collections of time-stamped min-travel-time-path trees) rather than travel-time functions. The preprocessed data structure is exploited by a new query algorithm (CFCA) which also computes (and pays for it) the actual connecting path that preserves the theoretical approximation guarantees. To make it practical and tackle the main burden of landmark-based oracles (the large preprocessing requirements), CFLAT is extensively engineered. A thorough experimental evaluation on two real-world benchmark instances shows that CFLAT achieves a significant improvement on preprocessing, approximation guarantees and query-times, in comparison to previous landmark-based oracles. It also achieves competitive query-time performance compared to state-of-art speedup heuristics for time-dependent road networks, whose query-times in most cases do not account for path construction.
Cite as
Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis. Improved Oracles for Time-Dependent Road Networks. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2017.4,
author = {Kontogiannis, Spyros and Papastavrou, Georgia and Paraskevopoulos, Andreas and Wagner, Dorothea and Zaroliagis, Christos},
title = {{Improved Oracles for Time-Dependent Road Networks}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {4:1--4:17},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.4},
URN = {urn:nbn:de:0030-drops-78954},
doi = {10.4230/OASIcs.ATMOS.2017.4},
annote = {Keywords: Time-dependent shortest paths, FIFO property, Distance oracles}
}
Document
Integrating Passengers' Assignment in Cost-Optimal Line Planning
Abstract
Finding a line plan with corresponding frequencies is an mportant stage of planning a public transport system. A line plan should permit all passengers to travel with an appropriate quality at appropriate costs for the public transport operator. Traditional line planning procedures proceed sequentially: In a first step a traffic assignment allocates passengers to routes in the network, often by means of a shortest path assignment. The resulting traffic loads are used in a second step to determine a cost-optimal line concept. It is well known that travel time of the resulting line concept depends on the traffic assignment. In this paper we investigate the impact of the assignment on the operating costs of the line concept.
We show that the traffic assignment has significant influence on the costs even if all passengers are routed on shortest paths. We formulate an integrated model and analyze the error we can make by using the traditional approach and solve it sequentially. We give bounds on the error in special cases. We furthermore investigate and enhance three heuristics for finding an initial passengers’ assignment and compare the resulting line concepts in terms of operating costs and passengers’ travel time. It turns out that the costs of a line concept can be reduced significantly if passengers are not necessarily routed on shortest paths and that it is beneficial for the travel time and the costs to include knowledge on the line pool already in the assignment step.
Cite as
Markus Friedrich, Maximilian Hartl, Alexander Schiewe, and Anita Schöbel. Integrating Passengers' Assignment in Cost-Optimal Line Planning. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{friedrich_et_al:OASIcs.ATMOS.2017.5,
author = {Friedrich, Markus and Hartl, Maximilian and Schiewe, Alexander and Sch\"{o}bel, Anita},
title = {{Integrating Passengers' Assignment in Cost-Optimal Line Planning}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {5:1--5:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.5},
URN = {urn:nbn:de:0030-drops-79015},
doi = {10.4230/OASIcs.ATMOS.2017.5},
annote = {Keywords: Line Planning, Integrated Public Transport Planning, Integer Programming, Passengers' Routes}
}
Document
Robustness Tests for Public Transport Planning
Abstract
The classical planning process in public transport planning focuses on the two criteria operating costs and quality for passengers. Quality mostly considers quantities like average travel time and number of transfers. Since public transport often suffers from delays caused by random disturbances, we are interested in adding a third dimension: robustness. We propose passenger-oriented robustness indicators for public transport networks and timetables. These robustness indicators are evaluated for several public transport plans which have been created for an artificial urban network with the same demand. The study shows that these indicators are suitable to measure the robustness of a line plan and a timetable. We explore different trade-offs between operating costs, quality (average travel time of passengers), and robustness against delays. Our results show that the proposed robustness indicators give reasonable results.
Cite as
Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Robustness Tests for Public Transport Planning. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{friedrich_et_al:OASIcs.ATMOS.2017.6,
author = {Friedrich, Markus and M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schiewe, Alexander and Sch\"{o}bel, Anita},
title = {{Robustness Tests for Public Transport Planning}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {6:1--6:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.6},
URN = {urn:nbn:de:0030-drops-78904},
doi = {10.4230/OASIcs.ATMOS.2017.6},
annote = {Keywords: robustness measure, timetabling, line planning, delays, passenger-orientation}
}
Document
Public Transit Routing with Unrestricted Walking
Abstract
We study the problem of answering profile queries in public transportation networks that allow unrestricted walking. That is, finding all Pareto-optimal journeys regarding travel time and number of transfers in a given time interval. We introduce a novel algorithm that, unlike most state-of-the-art algorithms, can compute profiles efficiently in a setting that allows arbitrary walking. Using our algorithm, we show in an extensive experimental study that allowing unrestricted walking, significantly reduces travel times, compared to settings where walking is restricted. Beyond that, we publish the transportation networks of Switzerland that we used in our study, in order to encourage further research on this topic.
Cite as
Dorothea Wagner and Tobias Zündorf. Public Transit Routing with Unrestricted Walking. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{wagner_et_al:OASIcs.ATMOS.2017.7,
author = {Wagner, Dorothea and Z\"{u}ndorf, Tobias},
title = {{Public Transit Routing with Unrestricted Walking}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {7:1--7:14},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.7},
URN = {urn:nbn:de:0030-drops-78914},
doi = {10.4230/OASIcs.ATMOS.2017.7},
annote = {Keywords: Algorithms, Optimization, Route planning, Public transportation}
}
Document
Faster Transit Routing by Hyper Partitioning
Abstract
We present a preprocessing-based acceleration technique for computing bi-criteria Pareto-optimal journeys in public transit networks, based on the well-known RAPTOR algorithm [Delling et al 2015]. Our key idea is to first partition a hypergraph into cells, in which vertices correspond to routes (e.g., bus lines) and hyperedges to stops, and to then mark routes sufficient for optimal travel across cells. The query can then be restricted to marked routes and those in the source and target cells. This results in a practical approach, suitable for networks that are too large to be efficiently handled by the basic RAPTOR algorithm.
Cite as
Daniel Delling, Julian Dibbelt, Thomas Pajor, and Tobias Zündorf. Faster Transit Routing by Hyper Partitioning. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{delling_et_al:OASIcs.ATMOS.2017.8,
author = {Delling, Daniel and Dibbelt, Julian and Pajor, Thomas and Z\"{u}ndorf, Tobias},
title = {{Faster Transit Routing by Hyper Partitioning}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {8:1--8:14},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.8},
URN = {urn:nbn:de:0030-drops-78962},
doi = {10.4230/OASIcs.ATMOS.2017.8},
annote = {Keywords: Routing, speed-up techniques, public transport, partitioning}
}
Document
Optimizing Traffic Signal Settings for Public Transport Priority
Abstract
In order to promote public transport many municipalities use traffic signal control with a priority for buses or trams. In this paper, we address the problem of finding optimal passive transit signal priority settings. Building on a cyclically time-expanded network model for the combined traffic assignment traffic signal coordination problem, we introduce a suitable queuing model and several modifications to model public transport vehicles appropriately. We evaluate the applicability of this approach by computing and analyzing optimal solutions for several instances of a real-world scenario.
Cite as
Robert Scheffler and Martin Strehler. Optimizing Traffic Signal Settings for Public Transport Priority. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{scheffler_et_al:OASIcs.ATMOS.2017.9,
author = {Scheffler, Robert and Strehler, Martin},
title = {{Optimizing Traffic Signal Settings for Public Transport Priority}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {9:1--9:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.9},
URN = {urn:nbn:de:0030-drops-79005},
doi = {10.4230/OASIcs.ATMOS.2017.9},
annote = {Keywords: transit signal priority, traffic flow, traffic signal optimization, cyclically time-expanded network, public transport}
}
Document
Analysis of Strengths and Weaknesses of a MILP Model for Revising Railway Traffic Timetables
Abstract
A railway timetable is typically planned one year in advance, but may be revised several times prior to the time of operation in order to accommodate on-demand slot requests for inserting additional trains and network maintenance. Revising timetables is a computationally demanding task, given the many dependencies and details to consider. In this paper, we focus on the potential of using optimization-based scheduling approach for revising train timetables during short term planning, from one week to few hours before the actual operation. The approach relies on a MILP (Mixed Integer Linear Program) model which is solved by using the commercial solver Gurobi.
In a previous experimental study, the MILP approach was used to revise a significant part of the annual timetable for a sub-network in Southern Sweden to insert additional trains and allocate time slots for urgent maintenance. The results showed that the proposed MILP approach in many cases generates feasible, good solutions rather fast. However, proving optimality was in several cases time-consuming, especially for larger problems. Thus, there is a need to investigate and develop strategies to improve the computational performance. In this paper, we present results from a study, where a number of valid inequalities has been selected and applied to the MILP model with the aim to reduce the computation time. The experimental evaluation of the selected valid inequalities showed that although they can provide a slight improvement with respect to computation time, they are also weakening the LP relaxation of the model.
Cite as
Fahimeh Khoshniyat and Johanna Törnquist Krasemann. Analysis of Strengths and Weaknesses of a MILP Model for Revising Railway Traffic Timetables. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{khoshniyat_et_al:OASIcs.ATMOS.2017.10,
author = {Khoshniyat, Fahimeh and T\"{o}rnquist Krasemann, Johanna},
title = {{Analysis of Strengths and Weaknesses of a MILP Model for Revising Railway Traffic Timetables}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {10:1--10:17},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.10},
URN = {urn:nbn:de:0030-drops-78995},
doi = {10.4230/OASIcs.ATMOS.2017.10},
annote = {Keywords: Railway, Timetable, Short term planning, Boosting Methods, Valid inequalities}
}
Document
Strong Relaxations for the Train Timetabling Problem Using Connected Configurations
Abstract
The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral.
Cite as
Frank Fischer and Thomas Schlechte. Strong Relaxations for the Train Timetabling Problem Using Connected Configurations. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{fischer_et_al:OASIcs.ATMOS.2017.11,
author = {Fischer, Frank and Schlechte, Thomas},
title = {{Strong Relaxations for the Train Timetabling Problem Using Connected Configurations}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {11:1--11:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.11},
URN = {urn:nbn:de:0030-drops-79021},
doi = {10.4230/OASIcs.ATMOS.2017.11},
annote = {Keywords: combinatorial optimization, train timetabling, Lagrangian relaxation, connected configurations}
}
Document
An Improved Algorithm for the Periodic Timetabling Problem
Abstract
We consider the computation of periodic timetables, which is a key task in the service design process of public transportation companies. We propose a new approach for solving the periodic timetable optimisation problem. It consists of a (partially) heuristic network aggregation to reduce the problem size and make it accessible to standard mixed-integer programming (MIP) solvers. We alternate the invocation of a MIP solver with the well-known problem specific modulo network simplex heuristic (ModSim). This iterative approach helps the ModSim-method to overcome local minima efficiently, and provides the MIP solver with better initial solutions.
Our computational experiments are based on the 16 railway instances of the PESPlib, which is the only currently available collection of periodic event scheduling problem instances. For each of these instances, we are able to reduce the objective values of previously best known solutions by at least 10.0%, and up to 22.8% with our iterative combined method.
Cite as
Marc Goerigk and Christian Liebchen. An Improved Algorithm for the Periodic Timetabling Problem. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{goerigk_et_al:OASIcs.ATMOS.2017.12,
author = {Goerigk, Marc and Liebchen, Christian},
title = {{An Improved Algorithm for the Periodic Timetabling Problem}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {12:1--12:14},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.12},
URN = {urn:nbn:de:0030-drops-78924},
doi = {10.4230/OASIcs.ATMOS.2017.12},
annote = {Keywords: periodic timetabling, railway optimisation, modulo network simplex, periodic event scheduling problem}
}
Document
Optimizing Train Stopping Patterns for Congestion Management
Abstract
In this paper, we optimize train stopping patterns during morning rush hour in Japan. Since trains are extremely crowded, we need to determine stopping patterns based not only on travel time but also on congestion rates of trains. We exploit a Wardrop equilibrium model to compute passenger flows subject to congestion phenomena and present an efficient local search algorithm to optimize stopping patterns which iteratively computes a Wardrop equilibrium. We apply our algorithm to railway lines in Tokyo including Keio Line with six types of trains and succeed in relaxing congestion with a small effect on travel time.
Cite as
Tatsuki Yamauchi, Mizuyo Takamatsu, and Shinji Imahori. Optimizing Train Stopping Patterns for Congestion Management. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{yamauchi_et_al:OASIcs.ATMOS.2017.13,
author = {Yamauchi, Tatsuki and Takamatsu, Mizuyo and Imahori, Shinji},
title = {{Optimizing Train Stopping Patterns for Congestion Management}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {13:1--13:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.13},
URN = {urn:nbn:de:0030-drops-78988},
doi = {10.4230/OASIcs.ATMOS.2017.13},
annote = {Keywords: Train stopping pattern, Wardrop equilibrium, Congestion management, Local search algorithm, Event-activity network}
}
Document
Flight Planning in Free Route Airspaces
Abstract
We consider the problem of finding cheapest flight routes through free route airspaces in a 2D setting. We subdivide the airspace into regions determined by a Voronoi subdivision around the points from a weather forecast. This gives rise to a regular grid of rectangular regions (quads) with every quad having an associated vector-weight that represents the wind magnitude and direction. Finding a cheapest path in this setting corresponds to finding a piece-wise linear path determined by points on the boundaries of the quads. In our solution approach, we discretize such boundaries by introducing border points and only consider segments connecting border points belonging to the same quad. While classic shortest path graph algorithms are available and applicable to the graphs originating from these border points, we design an algorithm that exploits the geometric structure of our scenario and show that this algorithm is more efficient in practice than classic graph-based algorithms. In particular, it scales better with the number of quads in the subdivision of the airspace, making it possible to find more accurate routes or to solve larger problems.
Cite as
Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen. Flight Planning in Free Route Airspaces. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{jensen_et_al:OASIcs.ATMOS.2017.14,
author = {Jensen, Casper Kehlet and Chiarandini, Marco and Larsen, Kim S.},
title = {{Flight Planning in Free Route Airspaces}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {14:1--14:14},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.14},
URN = {urn:nbn:de:0030-drops-79047},
doi = {10.4230/OASIcs.ATMOS.2017.14},
annote = {Keywords: Flight planning, Geometric shortest path, Free route airspace, Vector weighted paths, Vector weighted planar subdivisions}
}
Document
Cost Projection Methods for the Shortest Path Problem with Crossing Costs
Abstract
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem.
Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that transforms crossing costs into shadow costs on individual arcs, thus approximating the SPPCC by a standard shortest path problem. We evaluate all algorithms' performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
Cite as
Marco Blanco, Ralf Borndörfer, Nam Dung Hoàng, Anton Kaier, Pedro M. Casas, Thomas Schlechte, and Swen Schlobach. Cost Projection Methods for the Shortest Path Problem with Crossing Costs. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{blanco_et_al:OASIcs.ATMOS.2017.15,
author = {Blanco, Marco and Bornd\"{o}rfer, Ralf and Dung Ho\`{a}ng, Nam and Kaier, Anton and Casas, Pedro M. and Schlechte, Thomas and Schlobach, Swen},
title = {{Cost Projection Methods for the Shortest Path Problem with Crossing Costs}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {15:1--15:14},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.15},
URN = {urn:nbn:de:0030-drops-78939},
doi = {10.4230/OASIcs.ATMOS.2017.15},
annote = {Keywords: shortest path problem, resource constrained shortest path, crossing costs, flight trajectory optimization, overflight fees, cost projection}
}
Document
An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems
Abstract
Through the development of efficient algorithms, data structures and preprocessing techniques, real-world shortest path problems in street networks are now very fast to solve. But in reality, the exact travel times along each arc in the network may not be known. This led to the development of robust shortest path problems, where all possible arc travel times are contained in a so-called uncertainty set of possible outcomes.
Research in robust shortest path problems typically assumes this set to be given, and provides complexity results as well as algorithms depending on its shape. However, what can actually be observed in real-world problems are only discrete raw data points. The shape of the uncertainty is already a modelling assumption. In this paper we test several of the most widely used assumptions on the uncertainty set using real-world traffic measurements provided by the City of Chicago. We calculate the resulting different robust solutions, and evaluate which uncertainty approach is actually reasonable for our data. This anchors theoretical research in a real-world application and gives an indicator which robust models should be the future focus of algorithmic development.
Cite as
Trivikram Dokka and Marc Goerigk. An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{dokka_et_al:OASIcs.ATMOS.2017.16,
author = {Dokka, Trivikram and Goerigk, Marc},
title = {{An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {16:1--16:13},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.16},
URN = {urn:nbn:de:0030-drops-79035},
doi = {10.4230/OASIcs.ATMOS.2017.16},
annote = {Keywords: robust shortest paths, uncertainty sets, real-world data, experimental study}
}
Document
Look-Ahead Approaches for Integrated Planning in Public Transportation
Abstract
In this paper we deal with three consecutive planning stages in public transportation: Line planning (including line pool generation), timetabling, and vehicle scheduling. These three steps are traditionally performed one after another in a sequential way often leading to high costs in the (last) vehicle scheduling stage. In this paper we propose three different ways to "look ahead", i.e., to include aspects of vehicle scheduling already earlier in the sequential process: an adapted line pool generation algorithm, a new cost structure for line planning, and a reordering of the sequential planning stages. We analyze these enhancements experimentally and show that they can be used to decrease the costs significantly.
Cite as
Julius Pätzold, Alexander Schiewe, Philine Schiewe, and Anita Schöbel. Look-Ahead Approaches for Integrated Planning in Public Transportation. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
Copy BibTex To Clipboard
@InProceedings{patzold_et_al:OASIcs.ATMOS.2017.17,
author = {P\"{a}tzold, Julius and Schiewe, Alexander and Schiewe, Philine and Sch\"{o}bel, Anita},
title = {{Look-Ahead Approaches for Integrated Planning in Public Transportation}},
booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
pages = {17:1--17:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-042-2},
ISSN = {2190-6807},
year = {2017},
volume = {59},
editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.17},
URN = {urn:nbn:de:0030-drops-78944},
doi = {10.4230/OASIcs.ATMOS.2017.17},
annote = {Keywords: line pool generation, line planning, vehicle scheduling, integrated planning, public transport}
}