交通規劃中的廣義納什均衡問題的理論與算法研究

《交通規劃中的廣義納什均衡問題的理論與算法研究》是依託南京師範大學，由徐玲玲擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：交通規劃中的廣義納什均衡問題的理論與算法研究
• 項目類別：青年科學基金項目
• 項目負責人：徐玲玲
• 依託單位：南京師範大學

項目摘要

廣義納什均衡問題是最佳化領域近年研究的一個熱點問題．該問題來源於經濟學，目前作為模型廣泛地用於交通、環境科學、通訊、計算機科學等領域．然而針對該問題的理論和數值方法研究仍處於初始階段．本項目擬根據廣義納什均衡問題自身的特殊結構，以最佳化算法為基礎，對交通領域出現的幾類問題進行理論和算法研究．首先，通過引入光滑的精確罰函式，將廣義納什均衡問題轉化為納什均衡問題,再對納什均衡問題設計高效算法，在適當的條件下證明算法的收斂性． 針對交通領域中出現的選址等問題，我們引入帶0-1變數的廣義納什均衡這一特殊的問題，對於這類複雜的問題，我們將對連續變數與整數變數進行合理的分解，套用交替方向法設計有效的數值求解方法． 最後我們還將廣義納什均衡問題作為模型，解決路徑選擇、公共資源合理分配等交通問題．這些研究結果將特定的廣義納什均衡問題與數值最佳化相結合，對其它領域的廣義納什均衡問題的研究將有重要的啟示作用．

結題摘要

本項目主要研究交通規劃問題中的廣義納什均衡問題的算法及套用，研究了在交通尖峰時段隨機因素導致的擁堵對出行的影響；研究了用交替方向法求解帶有耦合項的凸規劃問題；研究了一類特殊的帶有整數約束的二次規劃問題的求解；構造了一類光滑的罰函式求解廣義納什均衡問題；研究了帶有不等式約束的可分離的凸規劃問題的求解，用於解決交通規劃問題中帶容量約束及交通流量分配等問題。首先研究了交通規劃中的尖峰時段隨機因素導致的擁堵問題對出行的影響，這個結果可以為尖峰時段出行者提供一個出行時間的參考。我們研究了帶二次耦合項的凸規劃問題的算法，該算法能夠有效地求解特殊的廣義納什均衡問題；突破了交替方向法適用於求解可分離結構的最佳化問題這一限制。非線性整數規劃問題是非常難的一類問題，我們研究了帶一類特殊的整數約束的二次規劃問題，給出了最優解的必要條件，並以此設計了一個算法。 我們考慮了廣義納什均衡問題的罰函式算法，構造了一類光滑的精確罰函式，理論上能夠保證算法產生的點列收斂到解，以往文獻中求解廣義納什均衡問題的罰函式方法一般採用非光滑精確罰函式，在具體計算時需要先進行光滑化處理， 我們的數值實驗表明該方法求解一些廣義納什均衡問題優於非光滑精確罰函式。 另外還考慮了帶不等式約束的可分離最佳化問題， 這類問題通常的解決方法是引入新的變數，將不等式約束變成等式約束，這樣增加了問題的規模，降低了計算效率， 我們將乘子進行投影，利用問題的特殊結構，引入的變數具有顯式表達形式，直接求解帶有線性不等式的可分離問題，並將算法用於求解交通規劃中的流量配置問題及帶有容量約束等問題。