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

Abstract

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