The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems

作者:Long, JC (Long, Jiancheng)^{[ 1 ]} ; Szeto, WY (Szeto, W. Y.)^{[ 2 ]} ; Gao, ZY (Gao, Ziyou)^{[ 3 ]} ; Huang, HJ (Huang, Hai-Jun)^{[ 4 ]} ; Shi, Q (Shi, Qin)^{[ 1 ]} 

Dynamic user optimal simultaneous route and departure time choice (DUO-SRDTC) problems are usually formulated as variational inequality (VI) problems whose solution algorithms generally require continuous and monotone route travel cost functions to guarantee convergence. However, the monotonicity of the route travel cost functions cannot be ensured even if the route travel time functions are monotone. In contrast to traditional formulations, this paper formulates a DUO-SRDTC problem (that can have fixed or elastic demand) as a system of nonlinear equations. The system of nonlinear equations is a function of generalized origin-destination (OD) travel costs rather than route flows and includes a dynamic user optimal (DUO) route choice subproblem with perfectly elastic demand and a quadratic programming (QP) subproblem under certain assumptions. This study also proposes a solution method based on the backtracking inexact Broyden-Fletcher-Goldfarb-Shanno (BFGS) method, the extragradient algorithm, and the Frank-Wolfe algorithm. The BFGS method, the extragradient algorithm, and the Frank-Wolfe algorithm are used to solve the system of nonlinear equations, the DUO route choice subproblem, and the QP subproblem, respectively. The proposed formulation and solution method can avoid the requirement of monotonicity of the route travel cost functions to obtain a convergent solution and provide a new approach with which to solve DUO-SRDTC problems. Finally, numeric examples are used to demonstrate the performance of the proposed solution method. (C) 2015 Elsevier Ltd. All rights reserved.