Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Schmidt, Marie; Sch÷bel, Anita http://www.dagstuhl.de/oasics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-27575
URL:

;

The Complexity of Integrating Routing Decisions in Public Transportation Models

pdf-format:


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 =		{http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.156},
  annote =	{Keywords: Line Planning, Timetabling, Routing}
}

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


DROPS-Home | Fulltext Search | Imprint Published by LZI