Template-Type: ReDIF-Paper 1.0
Author-Name: Gattermann, P.
Author-Name-Last: Gattermann
Author-Name-First: Philine
Author-Name: Schiewe, A.
Author-Name-Last: Schiewe
Author-Name-First: Alexander
Author-Name: Schmidt, M.E.
Author-Name-Last: Schmidt
Author-Name-First: Marie
Title: The line planning routing game
Abstract: 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.
Length: 30
Creation-Date: 2014-12-03
File-URL: https://repub.eur.nl/pub/77431/ERS-2014-017-LIS.pdf
File-Format: application/pdf
Series: RePEc:ems:eureri
Number: ERS-2014-017-LIS
Keywords: transportation, game theory, routing, line planning, routing game
Handle: RePEc:ems:eureri:77431