路網均衡流量之高階敏感度分析

Abstract

Sensitivity analysis of equilibrium network flows is useful in various fields, such as bilevel network design problems, road pricing and origin-destination matrix estimation problems. The problems mentioned above can be formulated as a Stackelberg game where the upper level problem aims to find the optimal strategy which maximizes the system performance, and the lower level problem aims to solve the user equilibrium problem, respectively. The reaction function of the lower level problem is the key to solving the Stackelberg game. Due to the characteristics of user equilibria, the lower level problem does not have an explicit reaction function. Usually, the reaction function is approximated by the sensitivity information of equilibrium network flows. By performing such sensitivity analysis, one can predict the directions of variation in the equilibrium patterns when the parameters of cost and demand functions are changed. With this information, the linear approximation of the reaction function can be obtained and applied to solve Stackelberg the game using a sensitivity analysis-based algorithm. The models involved usually exhibit a user equilibrium constraint to form a difficult nonlinear, nonconvex optimization problem. Due to the computational difficulties, a nonlinear approximation of the reaction function is incorporated for solving the problem more efficiently. This research tries to establish the theory of higher-order sensitivity analysis of network equilibrium flows in order to solve the problem with a nonlinear approximation of the reaction function. This research is also going to extend the applicability of directional derivative-based sensitivity analysis method. To generalize the directional derivative-based sensitivity analysis, the continuous differentiability assumption on the cost function is relaxed to be piecewise linear functions. Building on the original directional derivative-based method, an extended model will be studied for providing the required sensitivity information using piecewise linear cost functions.

Sensitivity analysis of equilibrium network flows is useful in various fields, such as bilevel network design problems, road pricing and origin-destination matrix estimation problems. The problems mentioned above can be formulated as a Stackelberg game where the upper level problem aims to find the optimal strategy which maximizes the system performance, and the lower level problem aims to solve the user equilibrium problem, respectively. The reaction function of the lower level problem is the key to solving the Stackelberg game. Due to the characteristics of user equilibria, the lower level problem does not have an explicit reaction function. Usually, the reaction function is approximated by the sensitivity information of equilibrium network flows. By performing such sensitivity analysis, one can predict the directions of variation in the equilibrium patterns when the parameters of cost and demand functions are changed. With this information, the linear approximation of the reaction function can be obtained and applied to solve Stackelberg the game using a sensitivity analysis-based algorithm. The models involved usually exhibit a user equilibrium constraint to form a difficult nonlinear, nonconvex optimization problem. Due to the computational difficulties, a nonlinear approximation of the reaction function is incorporated for solving the problem more efficiently. This research tries to establish the theory of higher-order sensitivity analysis of network equilibrium flows in order to solve the problem with a nonlinear approximation of the reaction function. This research is also going to extend the applicability of directional derivative-based sensitivity analysis method. To generalize the directional derivative-based sensitivity analysis, the continuous differentiability assumption on the cost function is relaxed to be piecewise linear functions. Building on the original directional derivative-based method, an extended model will be studied for providing the required sensitivity information using piecewise linear cost functions.