交通仿真系统的并行计算、智能优化和混杂模型研究

论文摘要

智能交通系统（Intelligent Transportation System，ITS）是当前解决交通问题的主要方法和手段。作为ITS的重要组成部分，交通仿真系统是进行交通管理、控制和诱导决策的重要实验手段和工具。在交通仿真系统中，交通流模型运算速度的问题一直阻碍着交通仿真系统在解决大规模路网问题上的进一步发展，特别是在采用微观交通流模型的交通仿真系统中。随着ITS技术的深入发展，交通控制系统需要应用于复杂的交通场景中，对其实时性的要求也越来越高，作为交通控制系统核心的交通优化算法，同样存在运算速度的问题。快速发展的并行计算技术是提高运算速度的有效手段，而并行计算的引入，给交通仿真系统和交通控制系统中的优化算法提出了新的研究课题。针对这一研究课题，从三个方面进行了研究：一是建立了适合微观交通流模型并行计算的框架。二是在微观交通流模型并行计算框架研究的启发下，提出了一种适合并行计算的混杂交通流模型——并行混杂交通流（Parallel Hybrid Traffic Flow，PHTF）模型。三是提出了一种适合并行计算的蚁群优化（Ant Colony Optimization，ACO）算法——基于层状解构造图拆分的蚁群优化（Parallel ACO based on Layered Construction GraphDecomposition，PACO-LCGD）算法。此外，由于交通路网模型是交通仿真系统的基础，建立一个灵活的、能够细致描述实际微观交通路网，并将微观交通路网和宏观交通路网统一在同一框架下的路网模型仍然值得作进一步的研究。从这点出发，提出了基于车道的混杂交通路网模型，并将该模型在浙江大学智能交通研究中心自主研发的城市混合交通仿真与分析系统（Simulation and Analysis System for Urban Mixed Traffic，SASUMT）最新版本中加以了实现。本文还论述了SASUMT最新的研究成果，讨论了城市交通仿真系统与交通控制系统中的优化算法并行化软、硬件实现的一些关键技术。主要的研究成果总结如下：1、提出了一套适合微观交通流模型并行计算的框架。该框架参考了元胞（Cellar Automatic，CA）模型并行计算的框架，包括基于网格的区域分解方法、边界缓冲模型和改进的同步机制三个部分。其中基于网格的区域分解方法和边界缓冲模型分别用来实现任务的分解和提供仿真计算时所需的交互数据；改进的同步机制参考了CA模型并行计算的同步机制，根据在集群环境内消息能够并行传递的特征，通过同步栅来实现同步。针对该框架，设计了一个大规模路网进行实验验证，并采用LogGP模型进行了理论分析。理论分析和实验结果表明，应用这一框架可以方便地实现微观交通流模型的并行计算，提高微观交通流模型运算的速度，从而满足ITS中大规模交通路网实时、高效和动态仿真的需求。2、提出了一种适合并行计算的混杂交通流模型——并行混杂交通流模型。该模型根据尽量降低消息大小的思路，在微观交通流模型并行计算的基础上，采用混杂交通流模型建模的方法。PHTF模型并行计算时仍使用微观交通流模型并行计算的框架，在每台从机中依然采用微观交通流模型进行仿真计算。不同之处在于所传送的消息不再是每个车辆的信息，而是边界缓冲区内的宏观统计特性，当另一台计算机接收到这些宏观统计特性的数据后，会根据这些数据产生新的车辆。与微观交通流模型并行计算相比，并行混杂交通流模型减少了所传送消息的大小，具有更高的并行效率和可扩展性。3、提出了一种适合并行计算的蚁群算法——基于层状解构造图拆分的并行蚁群算法。由于应用蚁群优化算法求解复杂大规模多阶段决策问题时，其计算量会随着阶段数和各阶段离散化容许决策集合规模的增加成指数增长，造成无法在单台计算机中进行计算的现象，PACO-LCGD算法可以较好的解决这一问题。该算法通过应用并行计算技术，将解构造图拆分成若干块，把每一块的计算任务放置在不同的计算机上并行执行，互相合作完成整个计算任务。经实验验证和LogP模型的理论分析，表明这种算法可以快速有效地进行问题的求解。4、提出了一种新的路网模型——基于车道的混杂交通流模型。基于车道的混杂交通流模型采用基于特征的建模理论进行建模，将车道作为建模的基本单位，用车道／节点的拓扑关系表示交通网络的拓扑关系。车道之间的拓扑关系通过基于特征的建模方法进行描述。对于交叉路口，将其表述为一个由若干条车道组成的具有面几何形状的特征。基于车道的混杂交通流模型不仅能够有效的描述宏观交通路网，而且能够细致的描述微观交通路网，将宏观交通路网和微观交通路网统一在同一个框架之下，具有较强的扩展性。在SASUMT最新版本中，针对该模型进行了实现。5、论述了SASUMT最新的研究成果，并对并行化的城市交通仿真系统与优化算法的软件实现进行了初步探讨。讨论了交通流模型并行计算和PACO-LCGD算法的软硬件实现方法，并加以了实现。另外给出了并行化的城市交通仿真与优化系统硬件实现的一个初步框架。6、对全文的研究工作进行了总结，并对相关领域未来的研究方向进行了展望。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 交通仿真系统
• 1.2.1 系统仿真的概念
• 1.2.2 交通系统仿真
• 1.2.3 交通流模型
• 1.2.4 国内外交通仿真系统软件研究
• 1.3 交通控制系统
• 1.3.1 交通控制系统的发展历史
• 1.3.2 交通控制系统的分类
• 1.3.3 交通控制系统研究的进展
• 1.4 并行计算基本理论
• 1.4.1 并行计算平台
• 1.4.2 并行程序的开发
• 1.4.3 并行算法概述
• 1.4.4 并行计算模型
• 1.4.5 并行算法的性能度量
• 1.5 研究内容与成果
• 1.5.1 需要研究的问题
• 1.5.2 研究内容与成果
• 1.5.3 名词定义
• 第2章 微观交通流模型的并行计算
• 2.1 引言
• 2.2 区域分解
• 2.3 CA模型和其他交通流模型并行计算研究概况
• 2.4 微观交通流模型的并行计算
• 2.4.1 基于网格的区域分解
• 2.4.2 边界缓冲模型
• 2.4.3 同步机制
• 2.5 并行计算框架的验证
• 2.6 算法性能分析
• 2.7 小结
• 第3章 混杂交通流模型及其并行计算
• 3.1 引言
• 3.2 混杂交通流模型
• 3.3 混杂交通流模型的并行计算
• 3.4 并行混杂交通流模型
• 3.4.1 建模思路
• 3.4.2 模型分析
• 3.4.3 模型验证
• 3.5 小结
• 第4章 并行蚁群优化算法及其在交通控制系统中的应用
• 4.1 引言
• 4.2 蚁群优化算法
• 4.3 基于层状解构造图的蚁群优化算法
• 4.4 并行蚁群优化算法
• 4.5 基于层状解构造图拆分的并行蚁群优化算法
• 4.5.1 解构造图的拆分
• 4.5.2 并行蚁群优化算法
• 4.6 实验验证
• 4.7 算法性能分析
• 4.8 PACO-LCGD算法在信号灯配时参数协调优化中的应用
• 4.9 小结
• 第5章 城市交通并行仿真与优化系统
• 5.1 引言
• 5.2 城市交通仿真与分析系统
• 5.3 基于车道的路网模型
• 5.3.1 基于车道的路网模型研究概述
• 5.3.2 基于车道的混杂路网模型
• 5.3.3 基于车道的混杂路网模型的软件实现
• 5.4 城市交通并行仿真与优化系统的设计
• 5.5 小结
• 第6章 结论与展望
• 6.1 主要研究成果
• 6.2 未来研究方向
• 参考文献
• 附录一 交通仿真软件网址
• 附录二 MPI简介
• 附录三 自然区域编码系统
• 附录四 E-R图和UML图简介
• 作者简介及攻读博士期间完成的论文
• 致谢