The Complexity of Integrating Routing Decisions in Public Transportation Models

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.