Title: The efficiency of greedy best response algorithm in road traffic assignment

Authors: Lahna Idres; Mohammed Said Radjef

Addresses: Research Unit LaMOS, Department of Operational Research, Exact Sciences Faculty, Bejaia University, 06000, Algeria ' Research Unit LaMOS, Department of Operational Research, Exact Sciences Faculty, Bejaia University, 06000, Algeria

Abstract: In this work, we investigate the problem of the integer road traffic assignment. So, we model the interaction among the road users sharing the same origin-destination pair, as a symmetric network congestion game. We focus on Rosenthal's results to guarantee the existence of a pure Nash equilibrium (PNE). Then, we study the behaviour of an algorithm based on greedy best response (GBR) in finding PNE. In previous studies, the efficiency of GBR to compute a PNE of a symmetric network congestion game in series-parallel networks is proved. In our work, another approach is used to demonstrate its efficiency in more general networks. It is shown that the non-series parallel networks can be classed into two types. The conditions that make GBR succeeds for each type is then drawn. The advantage of GBR-algorithm is that provides a better approximation of the equilibrate assignment, since it is integer.

Keywords: road traffic assignment; congestion game; Nash equilibrium; GBR algorithm.

DOI: 10.1504/IJMOR.2019.102077

International Journal of Mathematics in Operational Research, 2019 Vol.15 No.3, pp.338 - 363

Accepted: 28 Apr 2018
Published online: 06 Sep 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article