基于特定拓扑结构的交通分配算法分析与设计方法

Specific topological structures are defined as some simple network structures with nice topological properties and mathematical properties. They are the minimal topology for flow operations in the traffic assignment algorithms, and can be regarded as elemental blocks to study the traffic assignment algorithms. Experiences from current literatures indicate that employment of specific topological structures and their utilization methods have key effects on the convergence performance of traffic assignment algorithms. Here we emphasize the significance of these specific topological structures in analyzing and designing traffic assignment algorithms, and plan to study traffic assignment algorithms by these specific topological structures. Our research content includes: ①Collect and explore specific topological structures with potential properties for designing traffic assignment algorithms, and build the equality conditions between the traffic assignment problem and the specific topological structures; ②analyze the role of specific topological structures in designing traffic assignment algorithms and summarize well properties of advanced algorithms that can be used for others; ③analyze and compare the impact mechanism of different specific topological structure or their utilization methods on convergence performance of traffic assignment algorithms; ④improve current algorithms or design new algorithms by proper use of specific topological structures. Our research is expected to improve the current state-of-art of traffic assignment algorithms, and provide quick and efficient solutions to the planning, design and management of the urban transportation network.

特定拓扑结构被定义为某些具有良好拓扑特性与数学特性的简单网络结构，是交通分配算法进行流量操作的最小结构，也是研究交通分配算法的基本单元。特定拓扑结构的选择与运用对于交通分配算法的收敛具有关键性作用。本课题强调网络结构的拓扑特性在交通分配算法分析与设计过程中的重要性，拟通过研究某些特定拓扑结构来达到解析与开发交通分配算法的目的。本课题将：①从挖掘和研究构成交通分配算法的特定拓扑结构入手，建立交通分配问题与拓扑结构之间的等价关系；②分析特定拓扑结构在交通分配算法设计过程中承担的作用，总结优秀算法设计过程中存在的规律性特点；③解析不同拓扑结构及运用方法对交通分配算法收敛特性的影响机理；④通过对特定拓扑结构的合理运用为切入点探索现有算法的改进方法和新算法的设计方法。研究成果将提高现有交通分配算法的计算精度，速度和可靠性，为大规模交通网络的规划、设计和管理提供快速准确的解决方案。

面向大规模交通网络上的用户均衡分配问题，本课题提出并研究了基于特定拓扑结构的交通分配算法分析与设计方法。特定拓扑结构可以理解为是对交通网络按照一定规则分解后得到的一些具有良好数学和拓扑特性的子网络，是交通分配子问题定义的载体，也是算法进行流量操作的最小拓扑结构。本课题的研究内容围绕特定拓扑结构展开：首先，我们对文献中的现有算法所采用的特定拓扑结构的拓扑特性，分解方法，子问题定义方法，子问题求解方法和算法的收敛特性进行了深入的分析和对比，总结了不同拓扑结构以及不同处理方法对算法收敛的影响规律 ；其次，我们通过改进某些已有特定拓扑结构的分解、搜集和流量均衡方法来设计新型交通分配算法，提出了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名。