TY - JOUR

T1 - An efficient algorithm for dynamic traffic equilibrium assignment with queues

AU - Akamatsu, Takashi

PY - 2001/11

Y1 - 2001/11

N2 - This paper presents an efficient algorithm for solving the dynamic user equilibrium (DUE) traffic assignment with a one-to-many origin-destination (OD) pattern. To achieve the efficiency of the algorithm, we employ the following three strategies. First, we exploit the decomposition property of the DUE assignment with respect to the departure time from an origin; we consider the algorithm that solves each of the decomposed DUE assignments sequentially. Second, we represent the decomposed DUE assignment by an arc-node formulation, not by using path variables. Third, we take advantage of the fact that the decomposed DUE assignment reduces to (finite dimensional) nonlinear complementarity problems (NCPs); we develop the algorithm based on the globally convergent Newton's method for general NCPs. These strategies, together with graph theoretic devices, enable us to design a new algorithm which does not require path enumeration and is capable of dealing with very large-scale networks. Numerical experiments disclose that the proposed algorithm solves the DUE assignment very rapidly, even in large-scale networks with some thousands of links and nodes where conventional heuristic algorithms do not converge to the accurate equilibrium solution.

AB - This paper presents an efficient algorithm for solving the dynamic user equilibrium (DUE) traffic assignment with a one-to-many origin-destination (OD) pattern. To achieve the efficiency of the algorithm, we employ the following three strategies. First, we exploit the decomposition property of the DUE assignment with respect to the departure time from an origin; we consider the algorithm that solves each of the decomposed DUE assignments sequentially. Second, we represent the decomposed DUE assignment by an arc-node formulation, not by using path variables. Third, we take advantage of the fact that the decomposed DUE assignment reduces to (finite dimensional) nonlinear complementarity problems (NCPs); we develop the algorithm based on the globally convergent Newton's method for general NCPs. These strategies, together with graph theoretic devices, enable us to design a new algorithm which does not require path enumeration and is capable of dealing with very large-scale networks. Numerical experiments disclose that the proposed algorithm solves the DUE assignment very rapidly, even in large-scale networks with some thousands of links and nodes where conventional heuristic algorithms do not converge to the accurate equilibrium solution.

UR - http://www.scopus.com/inward/record.url?scp=0035520360&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035520360&partnerID=8YFLogxK

U2 - 10.1287/trsc.35.4.389.10435

DO - 10.1287/trsc.35.4.389.10435

M3 - Article

AN - SCOPUS:0035520360

SN - 0041-1655

VL - 35

SP - 389

EP - 404

JO - Transportation Science

JF - Transportation Science

IS - 4

ER -