Towards the User Equilibrium in Traffic Assignment Using GRASP with Path Relinking

Solving the traffic assignment problem (TAP) is an impor-tant step towards an efficient usage of the traffic infrastruc-ture. A fundamental assignment model is the so-called User Equilibrium (UE), which may turn into a complex optimi-sation problem. In this paper, we present the use of the GRASP metaheuristic to approximate the UE of the TAP. A path relinking mechanism is also employed to promote a higher coverage of the search space. Moreover, we propose a novel performance evaluation function, which measures the number of vehicles that have an incentive to deviate from the routes to which they were assigned. Through experiments, we show that our approach outperforms classical algorithms, providing solutions that are, on average, significantly closer to the UE. Furthermore, when compared to classical meth-ods, the fairness achieved by our assignments is considerably better. These results indicate that our approach is efficient and robust, producing reasonably stable assignments. CCS Concepts •Theory of computation → Optimization with ran-domized search heuristics; Exact and approximate com-putation of equilibria; •Computing methodologies→Ar-tificial intelligence; Search methodologies; Modeling and sim-ulation