Volume
OASIcs, Volume 33
13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Event
ATMOS 2013, September 5, 2013, Sophia Antipolis, FranceEditors
Publication Details
- published at: 2013-09-05
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-939897-58-3
- DBLP: db/conf/atmos/atmos2013
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 33, ATMOS'13, Complete Volume
Abstract
OASIcs, Volume 33, ATMOS'13, Complete Volume
Cite as
13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@Proceedings{frigioni_et_al:OASIcs.ATMOS.2013,
title = {{OASIcs, Volume 33, ATMOS'13, Complete Volume}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013},
URN = {urn:nbn:de:0030-drops-42535},
doi = {10.4230/OASIcs.ATMOS.2013},
annote = {Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
Front Matter
Frontmatter, Table of Contents, Preface, Workshop Organization
Abstract
Frontmatter, Table of Contents, Preface, Workshop Organization
Cite as
13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. i-xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{frigioni_et_al:OASIcs.ATMOS.2013.i,
author = {Frigioni, Daniele and Stiller, Sebastian},
title = {{Frontmatter, Table of Contents, Preface, Workshop Organization}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {i--xii},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.i},
URN = {urn:nbn:de:0030-drops-42391},
doi = {10.4230/OASIcs.ATMOS.2013.i},
annote = {Keywords: Frontmatter, Table of Contents, Preface, Workshop Organization}
}
Document
Recoverable Robust Timetable Information
Abstract
Timetable information is the process of determining a suitable travel route for a passenger. Due to delays in the original timetable, in practice it often happens that the travel route cannot be used as originally planned. For a passenger being already en route, it would hence be useful to know about alternatives that ensure that his/her destination can be reached.
In this work we propose a recoverable robust approach to timetable information; i.e., we aim at finding travel routes that can easily be updated when delays occur during the journey. We present polynomial-time algorithms for this problem and evaluate the performance of the routes obtained this way on schedule data of the German train network of 2013 and simulated delay scenarios.
Cite as
Marc Goerigk, Sacha Heße, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel. Recoverable Robust Timetable Information. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{goerigk_et_al:OASIcs.ATMOS.2013.1,
author = {Goerigk, Marc and He{\ss}e, Sacha and M\"{u}ller-Hannemann, Matthias and Schmidt, Marie and Sch\"{o}bel, Anita},
title = {{Recoverable Robust Timetable Information}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {1--14},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.1},
URN = {urn:nbn:de:0030-drops-42407},
doi = {10.4230/OASIcs.ATMOS.2013.1},
annote = {Keywords: timetable information, recoverable robustness, delay scenarios}
}
Document
Is Timetabling Routing Always Reliable for Public Transport?
Abstract
Current route planning algorithms for public transport networks are mostly based on timetable information only, i.e., they compute shortest routes under the assumption that all transit vehicles (e.g., buses, subway trains) will incur in no delays throughout their trips. Unfortunately, unavoidable and unexpected delays often prevent transit vehicles to respect their originally planned schedule. In this paper, we try to measure empirically the quality of the solutions offered by timetabling routing in a real public transport network, where unpredictable delays may happen with a certain frequency, such as the public transport network of the metropolitan area of Rome. To accomplish this task, we take the time estimates required for trips provided by a timetabling-based route planner (such as Google Transit) and compare them against the times taken by the trips according to the actual tracking of transit vehicles in the transport network, measured through the GPS data made available by the transit agency. In our experiments, the movement of transit vehicles was only mildly correlated to the timetable, giving strong evidence that in such a case timetabled routing may fail to deliver optimal or even high-quality solutions.
Cite as
Donatella Firmani, Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni. Is Timetabling Routing Always Reliable for Public Transport?. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 15-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{firmani_et_al:OASIcs.ATMOS.2013.15,
author = {Firmani, Donatella and Italiano, Giuseppe F. and Laura, Luigi and Santaroni, Federico},
title = {{Is Timetabling Routing Always Reliable for Public Transport?}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {15--26},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.15},
URN = {urn:nbn:de:0030-drops-42415},
doi = {10.4230/OASIcs.ATMOS.2013.15},
annote = {Keywords: Shortest Path Problems, Route Planning, Timetable-based Routing, Public Transport Networks}
}
Document
Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations
Abstract
We study the problem of robust routing in urban public transportation
networks. In order to propose solutions that are robust for typical delays, we assume that we have past observations of real traffic situations available. In particular, we assume that we have "daily records" containing the observed travel times in the whole network for a few past days. We introduce a new concept to express a solution
that is feasible in any record of a given public transportation network. We adapt the method of Buhmann et al. [Buhmann et al., ITCS 2013] for optimization under uncertainty, and develop algorithms that allow its application for finding a robust journey from a given source to a given destination. The performance of the algorithms and the quality of the predicted journey are evaluated in a preliminary
experimental study. We furthermore introduce a measure of reliability of a given journey, and develop algorithms for its computation. The robust routing concepts presented in this work are suited specially for public transportation networks of large cities that lack clear hierarchical structure and contain services that run with high frequencies.
Cite as
Katerina Böhmová, Matús Mihalák, Tobias Pröger, Rastislav Srámek, and Peter Widmayer. Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 27-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{bohmova_et_al:OASIcs.ATMOS.2013.27,
author = {B\"{o}hmov\'{a}, Katerina and Mihal\'{a}k, Mat\'{u}s and Pr\"{o}ger, Tobias and Sr\'{a}mek, Rastislav and Widmayer, Peter},
title = {{Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {27--41},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.27},
URN = {urn:nbn:de:0030-drops-42428},
doi = {10.4230/OASIcs.ATMOS.2013.27},
annote = {Keywords: Algorithms, Optimization, Robustness, Route planning, Public transportation}
}
Document
Delay-Robustness of Transfer Patterns in Public Transportation Route Planning
Abstract
Transfer pattern routing is a state-of-the-art speed-up technique for finding optimal paths which minimize multiple cost criteria in public transportation networks. It precomputes sequences of transfer stations
along optimal paths. At query time, the optimal paths are searched among the stored transfer patterns, which allows for very fast response times even on very large networks. On the other hand, even a minor change to the timetables may affect many optimal paths,
so that, in principle, a new computation of all optimal transfer patterns becomes necessary. In this paper, we examine the robustness of transfer pattern routing towards delay, which is the most common source of such updates. The intuition is that the deviating paths caused by typical updates are already covered by original
transfer patterns. We perform experiments which show that the transfer patterns are remarkably robust even to large and many delays, which underlines the applicability and reliability of transfer pattern routing in realistic routing applications.
Cite as
Hannah Bast, Jonas Sternisko, and Sabine Storandt. Delay-Robustness of Transfer Patterns in Public Transportation Route Planning. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 42-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{bast_et_al:OASIcs.ATMOS.2013.42,
author = {Bast, Hannah and Sternisko, Jonas and Storandt, Sabine},
title = {{Delay-Robustness of Transfer Patterns in Public Transportation Route Planning}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {42--54},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.42},
URN = {urn:nbn:de:0030-drops-42434},
doi = {10.4230/OASIcs.ATMOS.2013.42},
annote = {Keywords: Route planning, public transportation, transfer patterns, delay, robustness}
}
Document
Solving a Freight Railcar Flow Problem Arising in Russia
Abstract
We consider a variant of the freight railcar flow problem. In this
problem, we need 1) to choose a set of transportation demands between
stations in a railroad network, and 2) to fulfill these demands by
appropriately routing the set of available railcars, while
maximizing the total profit. We formulate this problem as a
multi-commodity flow problem in a large space-time graph. Three
approaches are proposed to solve the Linear Programming relaxation
of this formulation: direct solution by an LP solver, a column
generation approach based on the path reformulation, and a ``column
generation for extended formulations'' approach. In the latter, the
multi-commodity flow formulation is solved iteratively by dynamic
generation of arc flow variables. Three approaches have been tested
on a set of real-life instances provided by one of the largest
freight rail transportation companies in Russia. Instances with up
to 10 millions of arc flow variables were solved within minutes of
computational time.
Cite as
Ruslan Sadykov, Alexander A. Lazarev, Vitaliy Shiryaev, and Alexey Stratonnikov. Solving a Freight Railcar Flow Problem Arising in Russia. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 55-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{sadykov_et_al:OASIcs.ATMOS.2013.55,
author = {Sadykov, Ruslan and Lazarev, Alexander A. and Shiryaev, Vitaliy and Stratonnikov, Alexey},
title = {{Solving a Freight Railcar Flow Problem Arising in Russia}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {55--67},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.55},
URN = {urn:nbn:de:0030-drops-42448},
doi = {10.4230/OASIcs.ATMOS.2013.55},
annote = {Keywords: Freight routing, multi-commodity flow, column generation}
}
Document
A Configuration Model for the Line Planning Problem
Abstract
We propose a novel extended formulation for the line planning
problem in public transport. It is based on a new concept of
frequency configurations that account for all possible
options to provide a required transportation capacity on an
infrastructure edge. We show that this model yields a strong LP
relaxation. It implies, in particular, general classes of facet
defining inequalities for the standard model.
Cite as
Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. A Configuration Model for the Line Planning Problem. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 68-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2013.68,
author = {Bornd\"{o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika},
title = {{A Configuration Model for the Line Planning Problem}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {68--79},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.68},
URN = {urn:nbn:de:0030-drops-42451},
doi = {10.4230/OASIcs.ATMOS.2013.68},
annote = {Keywords: Combinatorial optimization, polyhedral combinatorics, line planning}
}
Document
The Stop Location Problem with Realistic Traveling Time
Abstract
In this paper we consider the location of stops along the edges of
an already existing public transportation network. This can be the
introduction of bus stops along some given bus routes, or of railway
stations along the tracks in a railway network. The positive effect of new stops is given by the better access of the customers to the public transport network, while the traveling time increases due to the additional stopping activities of the trains which is a negative effect for the customers.
Our goal is to locate new stops minimizing a realistic traveling time
which takes acceleration and deceleration of the vehicles into account. We distinguish two variants: in the first (academic) version we locate $p$ stops, in the second (real-world applicable) version the goal is to cover all demand points with a minimal amount of realistic traveling time. As in other works on stop location, covering may be defined with respect to an arbitrary norm. For the first version, we present a polynomial approach while the latter
version is NP-hard. We derive a finite candidate set and an IP formulation. We discuss the differences to the model neglecting the realistic traveling time and provide a case study showing that our procedures are applicable in practice and do save in average more than 3% of traveling time for the passengers.
Cite as
Emilio Carrizosa, Jonas Harbering, and Anita Schöbel. The Stop Location Problem with Realistic Traveling Time. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 80-93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{carrizosa_et_al:OASIcs.ATMOS.2013.80,
author = {Carrizosa, Emilio and Harbering, Jonas and Sch\"{o}bel, Anita},
title = {{The Stop Location Problem with Realistic Traveling Time}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {80--93},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.80},
URN = {urn:nbn:de:0030-drops-42467},
doi = {10.4230/OASIcs.ATMOS.2013.80},
annote = {Keywords: Stop Location, Realistic Traveling Time, IP Formulation}
}
Document
Evolution and Evaluation of the Penalty Method for Alternative Graphs
Abstract
Computing meaningful alternative routes in a road network is a complex problem -- already giving a clear definition of a best alternative seems to be impossible. Still, multiple methods describe how to compute reasonable alternative routes, each according to their own quality criteria. Among these methods, the penalty method has received much less attention than the via-node or plateaux based approaches. A mayor cause for the lack of interest might be the unavailability of an efficient implementation. In this paper, we
take a closer look at the penalty method and extend upon its ideas. We provide the first viable implementation --suitable for interactive use-- using dynamic runtime adjustments to perform up to multiple orders of magnitude faster queries than previous implementations. Using our new implementation, we thoroughly evaluate the penalty method for its flaws and benefits.
Cite as
Moritz Kobitzsch, Marcel Radermacher, and Dennis Schieferdecker. Evolution and Evaluation of the Penalty Method for Alternative Graphs. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 94-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{kobitzsch_et_al:OASIcs.ATMOS.2013.94,
author = {Kobitzsch, Moritz and Radermacher, Marcel and Schieferdecker, Dennis},
title = {{Evolution and Evaluation of the Penalty Method for Alternative Graphs}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {94--107},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.94},
URN = {urn:nbn:de:0030-drops-42474},
doi = {10.4230/OASIcs.ATMOS.2013.94},
annote = {Keywords: Alternatives, Routing, Shortest Paths, Penalties, Parallelization}
}
Document
Improved Alternative Route Planning
Abstract
We present improved methods for computing a set of alternative source-to-destination routes in road networks in the form of an alternative graph. The resulting alternative graphs are characterized by minimum path overlap, small stretch factor, as well as low size and complexity. Our approach improves upon a previous one by introducing a new pruning stage preceding any other heuristic method and by introducing a new filtering and fine-tuning of two existing methods. Our accompanying experimental study shows that the entire alternative graph can be computed pretty fast even in continental size networks.
Cite as
Andreas Paraskevopoulos and Christos Zaroliagis. Improved Alternative Route Planning. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 108-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{paraskevopoulos_et_al:OASIcs.ATMOS.2013.108,
author = {Paraskevopoulos, Andreas and Zaroliagis, Christos},
title = {{Improved Alternative Route Planning}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {108--122},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.108},
URN = {urn:nbn:de:0030-drops-42485},
doi = {10.4230/OASIcs.ATMOS.2013.108},
annote = {Keywords: Alternative route, stretch factor, shortest path, non-overlapping path, penalty, plateau}
}
Document
Result Diversity for Multi-Modal Route Planning
Abstract
We study multi-modal route planning allowing arbitrary (meaningful)
combinations of public transportation, walking, and taking a car / taxi. In the straightforward model, the number of Pareto-optimal solutions explodes. It turns out that many of them are similar to each other or unreasonable. We introduce a new filtering procedure, Types aNd Thresholds (TNT), which leads to a small yet representative subset of the reasonable paths. We consider metropolitan areas like New York, where a fast computation of the paths is difficult. To reduce the high computation times, optimality-preserving and heuristic
approaches are introduced. We experimentally evaluate our approach with respect to result quality and query time. The experiments confirm that our result sets are indeed small (around 5 results per query) and representative (among the reasonable Pareto-optimal paths), and with average query times of about one second or less.
Cite as
Hannah Bast, Mirko Brodesser, and Sabine Storandt. Result Diversity for Multi-Modal Route Planning. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 123-136, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{bast_et_al:OASIcs.ATMOS.2013.123,
author = {Bast, Hannah and Brodesser, Mirko and Storandt, Sabine},
title = {{Result Diversity for Multi-Modal Route Planning}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {123--136},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.123},
URN = {urn:nbn:de:0030-drops-42494},
doi = {10.4230/OASIcs.ATMOS.2013.123},
annote = {Keywords: Route Planning, Multi-Modal, Result Diversity}
}
Document
Column Generation for Bi-Objective Vehicle Routing Problems with a Min-Max Objective
Abstract
Column generation has been very useful in solving single objective
vehicle routing problems (VRPs). Its role in a branch-and-price algorithm is to compute a lower bound which is then used in a branch-and-bound framework to guide the search for integer solutions. In spite of the success of the method, only a few papers treat its application to multi-objective problems and this paper seeks to contribute in this respect. We study how good lower bounds
for bi-objective VRPs in which one objective is a min-max function can be computed by column generation. A way to model these problems as well as a strategy to effectively search for columns are presented. We apply the ideas to two VRPs and our results show that strong lower bounds for this class of problems can be obtained in "reasonable" times if columns are intelligently managed. Moreover, the quality of the bounds obtained from the proposed model
are significantly better than those obtained from the corresponding
"standard" approach.
Cite as
Boadu Mensah Sarpong, Christian Artigues, and Nicolas Jozefowiez. Column Generation for Bi-Objective Vehicle Routing Problems with a Min-Max Objective. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 137-149, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{sarpong_et_al:OASIcs.ATMOS.2013.137,
author = {Sarpong, Boadu Mensah and Artigues, Christian and Jozefowiez, Nicolas},
title = {{Column Generation for Bi-Objective Vehicle Routing Problems with a Min-Max Objective}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {137--149},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.137},
URN = {urn:nbn:de:0030-drops-42500},
doi = {10.4230/OASIcs.ATMOS.2013.137},
annote = {Keywords: Multi-objective optimization, column generation, integer programming, vehicle routing}
}
Document
Carpooling: the 2 Synchronization Points Shortest Paths Problem
Abstract
Carpooling is an appropriate solution to address traffic congestion and to reduce the ecological footprint of the car use. In this paper, we address an essential problem for providing dynamic carpooling: how to compute the shortest driver's and passenger's paths. Indeed, those two paths are synchronized in the sense that they have a common subpath between two points: the location where the passenger is picked up and the one where he is dropped off the car. The passenger path may include time-dependent public transportation parts before or after the common subpath.
This defines the 2 Synchronization Points Shortest Path Problem (2SPSPP). We show that the 2SPSPP has a polynomial worst-case complexity. However, despite this polynomial complexity, one needs efficient algorithms to solve it in realistic transportation networks.
We focus on efficient computation of optimal itineraries for solving the 2SPSPP, i.e. determining the (optimal) pick-up and drop-off points and the two synchronized paths that minimize the total traveling time. We also define restriction areas for reasonable pick-up and drop-off points and use them to guide the algorithms using heuristics based on landmarks. Experiments are conducted on real transportation networks. The results show the efficiency of the proposed algorithms and the interest of restriction areas for pick-up or drop-off points in terms of CPU time, in addition to its application interest.
Cite as
Arthur Bit-Monnot, Christian Artigues, Marie-José Huguet, and Marc-Olivier Killijian. Carpooling: the 2 Synchronization Points Shortest Paths Problem. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 150-163, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{bitmonnot_et_al:OASIcs.ATMOS.2013.150,
author = {Bit-Monnot, Arthur and Artigues, Christian and Huguet, Marie-Jos\'{e} and Killijian, Marc-Olivier},
title = {{Carpooling: the 2 Synchronization Points Shortest Paths Problem}},
booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {150--163},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-939897-58-3},
ISSN = {2190-6807},
year = {2013},
volume = {33},
editor = {Frigioni, Daniele and Stiller, Sebastian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.150},
URN = {urn:nbn:de:0030-drops-42517},
doi = {10.4230/OASIcs.ATMOS.2013.150},
annote = {Keywords: Dynamic Carpooling, Shortest Path Problem, Synchronized Paths}
}