使用同步擾動隨機近似演算法最佳化路網號誌

Abstract

市區道路或運輸走廊之號誌連鎖主要藉由控制每個號誌路口的綠燈開始時間（時差）與綠燈長以達成。找出最適號誌連鎖路網可視為一個最佳化問題，目標為最小化負效用。本研究選擇作為目標負效用之延滯的解析式較難取得，因此使用模擬最佳化方法來直接取得目標函數值。本研究使用基於梯度的同步擾動隨機近似演算法（SPSA）作為最佳化器（optimizer），其相比於傳統基於梯度的最陡下降法在N維變數情況下每次迭代至少需N+1次，SPSA在每次迭代只需2次的模擬。本研究使用TRANSYT 17作為模擬器（simulator），希望能得到一個基於梯度的速解法。本研究基於SPSA設計了一個「區別變數型態SPSA」，將決策變數的號誌時差與綠燈長分階段做迭代，考慮了迭代中止條件、階段交替條件，也另外提出綠燈長初始解的搜尋方式與限制式可行域的處理方法。演算法分別在三個不同規模的路網上進行實證，並各選取2、3、5個初始解。小型路網取自既有文獻，故可用來比較先前結果與本研究結果差異；中型路網顯示本研究之演算法在不同隨機擾動下具有收斂性；大型路網中則展示SPSA應於於多幹道路網的實務可行性。同時，小型與中型路網也做了最陡下降法作為比較基準。結果顯示，小型路網可節省58.5%的求解時間；中型路網雖未能改善求解時間，但最佳解可改善7.08%以上；大型路網可在實證下得到與TRANSYT 17 最佳化相似之結果，展現未來應用之潛力。

Traffic signal coordination in urban road networks or transport corridors can be achieved by controlling the green start times (offsets) and green durations at each junction. Designing an effective coordinated network can be viewed as an optimization problem, with the objective of minimizing disutility. Since a closed-form expression for delay, the disutility adopted in this study, is difficult to obtain, a simulation-based optimization framework is employed to evaluate the objective function. This framework consists of an optimizer, which adjusts the decision variables to improve the objective, and a simulator, which provides the function values as feedback to the optimizer. The optimizer is the gradient-based Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm, which requires only two simulations per iteration regardless of the number of variables, in contrast to the steepest descent method that needs at least N+1 simulations for N variables. TRANSYT 17 is adopted as the traffic flow simulator to achieve a gradient-based yet computationally efficient approach. A “variable-type distinguished SPSA” is proposed, in which offsets and green times are updated in separate stages, with termination rules and stage-switching criteria considered. Additional procedures are provided for searching initial green times and handling feasible domains under constraints. The algorithm is tested on three networks of different scales, using two, three, and five initial points respectively. The small network is drawn from prior literature, enabling comparison between prior results and those of this study; the medium network demonstrates convergence of the algorithm under different random perturbations; and the large network illustrates the practical applicability of SPSA to multi-arterial networks. For comparison, the steepest descent method is also applied to the small and medium networks. Results show that in the small network, solution time is reduced by 58.5%; in the medium network, solution time is not reduced but the best solution improves by at least 7.08%; and in the large network, the results are comparable to those produced by the TRANSYT 17 optimizer, demonstrating the potential for future practical applications.