License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.20
URN: urn:nbn:de:0030-drops-76109
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7610/
Briem, Lars ;
Buck, Sebastian ;
Ebhart, Holger ;
Mallig, Nicolai ;
Strasser, Ben ;
Vortisch, Peter ;
Wagner, Dorothea ;
Zündorf, Tobias
Efficient Traffic Assignment for Public Transit Networks
Abstract
We study the problem of computing traffic assignments for public transit networks: Given a public transit network and a demand (i.e. a list of passengers, each with associated origin, destination, and departure time), the objective is to compute the utilization of every vehicle. Efficient assignment algorithms are a core component of many urban traffic planning tools. In this work, we present a novel algorithm for computing public transit assignments. Our approach is based upon a microscopic Monte Carlo simulation of individual passengers. In order to model realistic passenger behavior, we base all routing decisions on travel time, number of transfers, time spent walking or waiting, and delay robustness. We show how several passengers can be processed during a single scan of the network, based on the Connection Scan Algorithm [Dibbelt et al., LNCS Springer 2013], resulting in a highly efficient algorithm. We conclude with an experimental study, showing that our assignments are comparable in terms of quality to the state-of-the-art. Using the parallelized version of our algorithm, we are able to compute a traffic assignment for more than ten million passengers in well below a minute, which outperforms previous works by more than an order of magnitude.
BibTeX - Entry
@InProceedings{briem_et_al:LIPIcs:2017:7610,
author = {Lars Briem and Sebastian Buck and Holger Ebhart and Nicolai Mallig and Ben Strasser and Peter Vortisch and Dorothea Wagner and Tobias Z{\"u}ndorf},
title = {{Efficient Traffic Assignment for Public Transit Networks}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {20:1--20:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-036-1},
ISSN = {1868-8969},
year = {2017},
volume = {75},
editor = {Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7610},
URN = {urn:nbn:de:0030-drops-76109},
doi = {10.4230/LIPIcs.SEA.2017.20},
annote = {Keywords: Algorithms, Optimization, Route planning, Public transportation}
}
|
Keywords: |
|
Algorithms, Optimization, Route planning, Public transportation |
|
Collection: |
|
16th International Symposium on Experimental Algorithms (SEA 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.08.2017 |
