Equilibrium Solution Search on a Selfish Routing Problem with Multiple Constraints Using the Variable Metric Gradient Projection Method

摘要

The selfish routing problem is a mathematical model to represent the behavior of the selfish players who select a path in a congested network. In the selfish routing problem, Braess's paradox shows that there exists a case that more network resources may cause worse traffic performance contrary to expectations. In the previous studies of the selfish routing problem, the traffic network with a pair or multiple pairs of source sink vertex and the independent normalization constraints has been investigated. This paper introduces a multi-constraint type selfish routing problem. In this problem, a traffic network with multiple source vertices and multiple sink vertices is considered. The total flow from each source vertex is constrained to be constant. The total flow to each sink vertex is also constrained to be constant. This study formulates an optimization problem to obtain the equilibrium solution of the multi-constraint type selfish routing problem. Then, this study considers the meaning of the equilibrium solution through the derivation of the optimality condition. In order to solve the formulated problem, the variable metric gradient projection method is applied. In the numerical experiments, the optimality of the equilibrium solution obtained by the variable metric gradient projection method is verified. Then, the incidence of Braess's paradox in the multi-constraint type selfish routing problem is confirmed.