2014-12-03
The line planning routing game
Publication
Publication
ERIM report series research in management Erasmus Research Institute of Management
In this paper, we propose a novel algorithmic approach to solve line planning problems. To this end, we model the line planning problem as a game where the passengers are players which aim at minimizing individual objective functions composed of travel time, transfer penalties, and a share of the overall cost of the solution. To find equilibria of this routing game, we use a best-response algorithm. We investigate, under which conditions on the line planning model a passenger’s best-response can be calculated efficiently and which properties are needed to guarantee convergence of the best-response algorithm. Furthermore, we determine the price of anarchy which bounds the objective value of an equilibrium with respect to a system- optimal solution of the line planning problem. For problems where best-responses cannot be found efficiently, we propose heuristic methods. We demonstrate our findings on some small computational examples.
| Additional Metadata | |
|---|---|
| , , , , | |
| hdl.handle.net/1765/77431 | |
| ERIM Report Series Research in Management | |
| ERIM report series research in management Erasmus Research Institute of Management | |
| Organisation | Erasmus Research Institute of Management |
|
Gattermann, P., Schiewe, A., & Schmidt, M. (2014). The line planning routing game (No. ERS-2014-017-LIS). ERIM report series research in management Erasmus Research Institute of Management. Retrieved from http://hdl.handle.net/1765/77431 |
|
