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

High-Order Sensitivity Analysis of Equilibrium Network Flows

黃友恆(You-Heng Huang)

指導教授 ： 卓訓榮 ； 方述誠

國立交通大學/管理學院/運輸與物流管理學系/博士(2014年)

https://doi.org/10.6842/NCTU.2014.01157

摘要

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.

並列關鍵字

Sensitivity analysis ； Signal control problem ； Network design problem

參考文獻

[1] Aashtiani, H.Z. and Magnanti T.L., “Equilibria on a congested transportation network,” SIAM J. Algebraic and Discrete Methods 2, pp. 213-226, 1981.

[2] Abdulaal, M. and L.J. LeBlanc, “Continuous equilibrium network design models,” Transportation Research 13B, pp. 19-32, 1979.

[3] Allsop, R.E., “Some possibilities for using traffic control to influence trip distribution and route choice,” Proceedings of the 6th International Symposium on Transportation and Traffic Theory, pp. 345-373, 1974.

[5] Baskan, O., “Determining Optimal Link Capacity Expansions in Road Networks Using Cuckoo Search Algorithm with L#westeur042#vy Flights,” Journal of Applied Mathematics, Vol. 2013, Article ID 718015, 11 pages, 2013.

[6] Beckmann, M., C. McGuire and C. Winsten, Studies in the Economics of Transportation, CT: Yale University Press, 1956.