The Complexity of integrating passenger routing decisions in public transportation models

To model and solve optimization problems arising in public transportation, data about the passengers are necessary and have 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 are distributed over the public transportation network (PTN) using traffic-assignment procedures. In a second step, the actual planning of lines, timetables, and so forth takes place. This approach ignores that, assuming that the network is sufficiently dense, for most passengers, there are many possible ways to reach their destinations in the PTN, thus the actual connections the passengers will take strongly depend on the decisions made during the planning phase. In this article, we investigate the influence of integrating the traffic assignment procedure in the optimization process on the complexity of the line planning problem. 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 and systematically analyze their complexities. Exploiting a relation to the resource-constrained shortest path problem, we are able to derive pseudopolynomial and polynomial algorithms for special cases.