Paper Info
Title
An Acceleration Method for Equilibrium Solution Search in Multiple OD Selfish Routing Games
Abstract
A traffic flow allocation has been studied by many researches. This problem is studied by both urban planning research and game theoretical approaches. We stand on game theory to consider the traffic flow allocation problem by treating a class of congestion games on the network. The traffic flow allocation is called, in context the congestion game, a routing game. Our goal is to find an equilibria of choice of the players. However, it is known that the equilibrium searching problem is difficult. In this paper, we propose a solving method for a multi OD selfish routing game, and a method for solving standard routing games and its high speeding method. Our algorithm employs a replicator dynamics which is one of iterative optimization techniques. In the solution based on the replicator dynamics, the calculation time is very large, since the calculation is also performed for all paths. Therefore, as a preprocessing of solving by replicator dynamics, the policy of the proposed method is to make computation time faster by deleting unused paths. This paper evaluates the algorithm by numerical experiment.
Year
DOI
Venue
2018
10.1109/IIAI-AAI.2018.00116
2018 7th International Congress on Advanced Applied Informatics (IIAI-AAI)
Keywords
Field
DocType
selfish routing game,replicator dynamics,multiple OD model
Mathematical optimization,Congestion game,Traffic flow,Computer science,Replicator equation,Preprocessor,Urban planning,Acceleration,Game theory,Computation
Conference
ISBN
Citations 
PageRank 
978-1-5386-7447-5
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Guu Kofujita100.34
Satoshi Takahashi224.09