Line planning with user-optimal route choice

Recently, Marie and me wrote a paper about a new line planning model for public transport.

There are quite a few models around already, which can be broadly categorised using two optimisation objectives: The costs of the line plan on the one hand, and the passenger comfort on the other. Naturally, there are many possibilities to define these properties.

An important concern for passenger comfort is the average time a passenger needs to spend on his or her journey. But how do passengers travel, which path do they take through the public transport network? Previous models assume that “we” (the designer of the line plan) can determine how passengers travel, that is, we tell them the path for each journey in a way that the total travel time of all passengers is as small as possible.

From a passenger’s perspective, however, one would rather use the shortest available route (a user-optimum), than one that ensures the best travel time for other passengers (a system-optimum).

In our paper we derived two models to include this selfish route choice in the line planning process. Not surprisingly, these models become quite large and difficult so solve using an integer programming solver, so we also had to develop heuristic solution algorithms to be able to solve real-world sized problems.

Now, creating meaningful experimental data turned out to be a challenge here, due to the two objective functions travel time and line costs. For our integer programming models, we wanted to use a budget on the costs. But how large should it be chosen? If we set it too small, there might be no feasible solutions, but even if there are some, computation times will be very high (as they are hard to find). On the other hand, if the budget is too large, then the problems are very simple to solve, and computation times are small.

Our solution to this dilemma was to run the heuristic (which produces several, hopefully Pareto efficient solutions), and to use the budgets of these solutions to determine a reasonable budget for the integer programming instances as a compromise.

So, to derive cost budgets for our integer programs, we first had to use a completely different solution algorithm. Makes you wonder what to do when no such “outside view” is available!

This is the abstract:

We consider the problem of designing lines in a public transport system, where we include user-optimal route choice. The model we develop ensures that there is enough capacity present for every passenger to travel on a shortest route. We present two different integer programming formulations for this problem, and discuss exact solution approaches. To solve large-scale line planning instances, we also implemented a genetic solution algorithms.

We test our algorithms in computational experiments using randomly generated instances along realistic data, as well as a realistic instance modeling the German long-distance network. We examine the advantages and disadvantages of using such user-optimal solutions, and show that our algorithms scale with instance size to be used for practical purposes.