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

Abstract

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