基於特定拓撲結構的交通分配算法分析與設計方法

《基於特定拓撲結構的交通分配算法分析與設計方法》是依託西南交通大學，由謝軍擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：基於特定拓撲結構的交通分配算法分析與設計方法
• 項目類別：青年科學基金項目
• 項目負責人：謝軍
• 依託單位：西南交通大學

項目摘要

特定拓撲結構被定義為某些具有良好拓撲特性與數學特性的簡單網路結構，是交通分配算法進行流量操作的最小結構，也是研究交通分配算法的基本單元。特定拓撲結構的選擇與運用對於交通分配算法的收斂具有關鍵性作用。本課題強調網路結構的拓撲特性在交通分配算法分析與設計過程中的重要性，擬通過研究某些特定拓撲結構來達到解析與開發交通分配算法的目的。本課題將：①從挖掘和研究構成交通分配算法的特定拓撲結構入手，建立交通分配問題與拓撲結構之間的等價關係；②分析特定拓撲結構在交通分配算法設計過程中承擔的作用，總結優秀算法設計過程中存在的規律性特點；③解析不同拓撲結構及運用方法對交通分配算法收斂特性的影響機理；④通過對特定拓撲結構的合理運用為切入點探索現有算法的改進方法和新算法的設計方法。研究成果將提高現有交通分配算法的計算精度，速度和可靠性，為大規模交通網路的規劃、設計和管理提供快速準確的解決方案。

結題摘要

面向大規模交通網路上的用戶均衡分配問題，本課題提出並研究了基於特定拓撲結構的交通分配算法分析與設計方法。特定拓撲結構可以理解為是對交通網路按照一定規則分解後得到的一些具有良好數學和拓撲特性的子網路，是交通分配子問題定義的載體，也是算法進行流量操作的最小拓撲結構。本課題的研究內容圍繞特定拓撲結構展開：首先，我們對文獻中的現有算法所採用的特定拓撲結構的拓撲特性，分解方法，子問題定義方法，子問題求解方法和算法的收斂特性進行了深入的分析和對比，總結了不同拓撲結構以及不同處理方法對算法收斂的影響規律 ；其次，我們通過改進某些已有特定拓撲結構的分解、蒐集和流量均衡方法來設計新型交通分配算法，提出了iTAPAS（improved Traffic Assignment by Paired Alternative Segments）算法和Greedy算法。前者較TAPAS算法更加簡單，而且收斂效率提高了一倍；而後者作為一個基於路徑的算法，比目前所有的基於起點或者bush的算法都要快。第三，我們通過構造新的特定拓撲結構來設計新型的交通分配算法，提出了用於求解路徑流量的EMARB（Entropy Maximization through Alternative Representation of Bushes）算法。在該算法中我們構建了一種新型的bush結構，即node-based arrival bush；進而將交通分配原問題進行了兩類分解，一是根據origin-based bush分解，二是根據node-based arrival bush分解；通過將路徑流量在這兩類bush上來回疊代實現了算法的收斂。本項目提出了一種全新的交通分配算法設計思路，並且在這種思路的指導下成功開發了三個高效的交通分配算法，顯著提高了大規模交通分配問題的計算效率和精度。項目的研究成果包括：發表（含一篇出版中（In Press））4篇SCI/SSCI期刊論文，其中1篇發表在《Transportation Science》，2篇發表在《Transportation Research Part B》，1篇發表在《Transportation Research Record》；在國際國內會議上匯報成果7次，培養博士研究生2名，碩士研究生3名。