以非線性反應函數求解雙層路網設計問題

Abstract

Stackelberg 賽局問題廣泛的應用在各個學術領域上。在交通領域 上，網路設計問題就是一個典型的Stackelberg 賽局，參賽者分別為政府 （負責設計號誌時制）以及用路人（執行路徑選擇）。此均衡網路設計問 題包含尋找一網路改善之最佳配置，即使用者路徑選擇為均衡情況下求得 系統最佳之配置。由於Stackelberg 賽局計算較複雜，過去學者提出了幾 種演算法，包含有迭代法（Iterative Method）、懲罰法（Penalty Method） 以及敏感性分析法（Sensitivity Approach）。其中敏感性分析法又分為梯度 法（Gradient Method）與線性反應函數估計法（Linear Reaction Function Approximation）：其中以線性反應函數估計法效率較高。然其反應函數之 假設為線性，不一定能反應真實之狀態，故本研究嘗試建立高階之非線性 反應函數，期能加速演算效率並改進解之品質。 在本研究第一年的工作中，將專注於發展高階敏感性分析，使此理 論更一般化，增廣其應用範圍。 計畫第二年將延續第一年的高階敏感性分析方法，用此敏感性資訊 建立一非線性之反應函數，將其用以求解領導—跟隨雙層問題。發展一合 適之演算法，且探討其收斂性。 於計畫第三年，本研究將擴展原有可微之雙層Stackelberg 賽局問題 至不可微之問題。並嘗試透過次梯度（sub-gradient）方式進行求解。

The Stackelberg game problem is widely applied to different research areas. In the transportation area, the network design problem is one typical Stackelberg game example with two players, the government designing signal controls and the users choosing routes, respectively. This equilibrium network design problem includes searching an optimal setting of network improvements, that is, to obtain the optimal setting under the user equilibrium condition. Because the Stackelberg game requires complicated computing, some researchers proposed several algorithms including the iterative method, the penalty method and the sensitivity approach. Two methods of the sensitivity approach are the gradient method and the linear reaction function approximation, and the latter is more efficient. However, the method above has the assumption that the reaction function is linear, which may not reflect the real situation. This research tries to establish nonlinear reaction function to improve the computing efficiency and quality of the solution. In the first year, we will focus on the nonlinear sensitivity analysis approach to generalize the theory and expand the application. In the second year, we will continue the research to solve the leader-follower bilevel problem, develop an algorithm and discuss its convergence. In the final year, we will expand the algorithm from differentiable objective function to non-differentiable one and try to solve the problem by applying the sub-gradient method.