License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2010.156
URN: urn:nbn:de:0030-drops-27575
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2757/
Go to the corresponding OASIcs Volume Portal

Schmidt, Marie ; Schöbel, Anita

The Complexity of Integrating Routing Decisions in Public Transportation Models

pdf-format:
13.pdf (0.3 MB)

Abstract

To model and solve optimization problems arising in public
transportation, data about the passengers is necessary and has to be
included in the models in any phase of the planning process. Many
approaches assume a two-step procedure: in a first step, the data
about the passengers is distributed over the public transportation
network using traffic-assignment procedures. In a second step, the
actual planning of lines, timetables, etc. takes place. This approach
ignores that for most passengers there are many possible ways to reach
their destinations in the public transportation network, thus the
actual connections the passengers will take depend strongly on the
decisions made during the planning phase. In this paper we
investigate the influence of integrating the traffic assignment
procedure in the optimization process on the complexity of line
planning and aperiodic timetabling. In both problems, our objective is
to maximize the passengers' benefit, namely to minimize the overall
travel time of the passengers in the network. We present new models,
analyze NP-hardness results arising from the integration of the routing
decisions in the traditional models, and derive polynomial algorithms
for special cases.

BibTeX - Entry

@InProceedings{schmidt_et_al:OASIcs:2010:2757,
  author =	{Marie Schmidt and Anita Sch{\"o}bel},
  title =	{{The Complexity of Integrating Routing Decisions in Public Transportation Models}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{156--169},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Thomas Erlebach and Marco L{\"u}bbecke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2757},
  URN =		{urn:nbn:de:0030-drops-27575},
  doi =		{10.4230/OASIcs.ATMOS.2010.156},
  annote =	{Keywords: Line Planning, Timetabling, Routing}
}

Keywords: Line Planning, Timetabling, Routing
Collection: 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)
Issue Date: 2010
Date of publication: 01.09.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI