以電路模擬演算法決定非線性成本函數之交通指派問題

Determing the Traffic Assignment Problem with Non-linear Cost Functions by Circuit Simulation Algorithm

鄭兆哲(Chao-Che Cheng)

指導教授 ： 黃寬丞

國立交通大學/管理學院/運輸科技與管理學系/碩士(2009年)

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

摘要

交通指派問題是運輸規劃的一項重要工作，其決定各起訖點旅行者的路徑選擇以及交通路網系統的流量。在使用者均衡的條件下，任何一起訖點對所使用路徑的旅行成本皆相同。使用者均衡流量與一般電路有許多相似的特性，像是電流值可視為交通流量，而電壓值則可被比擬為旅行成本。基於「讓電子來模擬旅行者」的構想，本研究藉由純電阻電路問題的遞回運算來求解交通指派問題。然而路段的成本函數多為非線性，而純電阻所適用的歐姆定律則是線性，這兩者之間的關係則為本研究之重點之一。本研究以三個路網為測試例題，結果顯示就遞回次數與目標值電路模擬演算法的結果都較優於Frank-Wolfe演算法。因此電路模擬演算法應可作為一個基礎來達成本研究終極的目標－在積體電路內構建一系統來模擬實際的大型交通路網。

關鍵字

交通指派問題 ； 使用者均衡 ； 電路模擬

並列摘要

As a key process for urban transportation planning, the traffic assignment problem (TAP) determines the route choice of the travelers for each origin-destination pair and the traffic flow of the network system. Under the user equilibrium condition, the travel costs of the chosen routes are identical for each origin-destination pair. The resulted user equilibrium flow bears significant resemblance to an electronic circuit. In particular, if electrical current is viewed as traffic volume, voltage drop can be thought as travel cost. Based on the basic idea “let the electrons simulate the travelers,” this study establishes a solution algorithm for TAP by iteratively solving the associated pure-resistance circuit problem. However, most of link cost functions are non-linear, but Ohm’s law applicable to pure-resistance components, is a linear relation between current and voltage. How to correlate this two is a key question of this study. The results in the numerical experiment with test networks show that the developed algorithm is better than Frank-Wolfe Algorithm in terms of the number of iterations and the objective function value. Thus, the circuit-simulation approach can be used as a building block to achieve the ultimate goal, building a system in an integrated circuit to simulate the actual large-scale traffic networks.

並列關鍵字

traffic assignment problem ； user equilibrium ； circuit simulation

參考文獻

Huang, K., Cheng, C. and Chuang, T. (2007) Determining the user equilibrium flow of the traffic assignment problem by circuit simulation, Proceedings of the 2nd International Conference on Transportation Logistics, Shenzhen, China.

Bar-Gera, H. (2002) Origin-based algorithm for the traffic assignment problem, Transportation Science, 36, pp. 398-417.

Boyce, D. (2007) Future research on urban transportation network modeling, Regional Science and Urban Economics, 37, pp. 472-481.

Dial, R. B. (2006) A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration, Transportation Research Part B, 40, pp. 917-936.

Florian, M. (1984) Transportation Planning Models (New York, the U.S.A.: North-Holland).