面向出行时间可靠性的最优路径规划

目前城市道路交通普遍存在交通拥挤、交通出行困难等问题。尤其是一些大城市,交通拥挤问题已成为制约城市进一步发展的重要问题。因此,提高出行者的出行效率和可靠性对解决交通拥挤问题具有重大意义。城市道路交通网络是一个典型的动态随机网络,网络中弧和节点的耗费是随机的,且随时间变化。其最优路径问题可以转化为图论网络中的最短路径问题。提出一种基于蒙特卡罗模拟和遗传算法的动态随机网络最短路径算法来解决城市道路交通网络的最优路径问题,并提出基于出行时长95%可靠性的最优路径选择方法来保证出行时间的可靠性。实验表明该算法可以很好地解决城市道路交通网络出行时间可靠性的问题,可以很好地运用到交通出行的路径规划中去。     

微观交通分布式并行仿真系统设计与效益分析

为了提高交通网络仿真的速度和效率,从挖掘交通网络仿真的并行性出发,设计了分布式并行仿真系统的结构和仿真算法,通过比较选择PVM(Parallel Virtual Machine)作为并行计算的编程环境,提出基于车辆数的网络分割算法和数据时钟同步的通讯方式,使并行仿真达到负载平衡。用程序执行时间、加速比、并行效率和可扩展性4个测度指标来评价算法的并行效益,并以24个交叉口组成的交通网络为例,应用设计的并行算法在不同处理器数目下进行仿真。试验结果显示并行仿真速度比串行仿真提高了3.5倍,因此,这种并行算法提高了交通网络仿真的速度和效率,为实现更大规模的交通仿真奠定了基础。     

基于蚂蚁算法的公交网络最短路径问题研究

通过改进的蚂蚁算法来解决公交网络信息系统中的最短路径问题。提出以换乘次数最少、出行距离最短为目标的路径求解算法，并给出了算法流程。分析了基于蚂蚁算法的城市公交网络的选择策略：选择某条路径即给该路径赋以一定的信息素，信息素愈大的路径，成为最短路径的可能性愈大。并利用改进的蚂蚁算法实现了公交网络乘客信息查询。     

蓄意攻击下城市轨道交通网络抗毁性分析

为分析蓄意攻击策略下的城市轨道交通网络抗毁性,考虑复杂网络理论中最大连通子图相对大小、相对网络效率等因素,提出一种面向蓄意攻击下的城市轨道交通网络抗毁性分析方法。首先,选取城市轨道交通抗毁性指标,对网络蓄意攻击策略进行分析;其次,采用Space L法构建城市轨道交通网络的拓扑结构图,从点度、度分布、平均路径长度、聚集系数、网络效率等统计特性指标,定量分析蓄意攻击下的城市轨道交通网络抗毁性;最后,以北京市城市轨道交通网络为例,分析其2015年至2018年的变化,并对蓄意攻击下城市轨道交通网络抗毁性进行验证。结果表明:BURT_2015和BURT_2018这2个网络的度分布及度相关的参数基本相同;BURT_2018局部连接有所改善,但网络全局效率下降13%;在抗毁性方面,攻击相同的比例节点(或连边)时,BURT_2018和BURT_2015具有相似的抗毁性,但BURT_2018需要为攻击做出更多努力,攻击相同数量的节点(或连边)时,BURT_2018抗毁性更卓越。研究结果进一步丰富了城市轨道交通网络特性的抗毁性分析方法,为城市轨道交通网络的运营管理和规划设计提供了有益借鉴。     

道路交通网络最短路径关键转向研究

研究道路网络中的最短路径关键转向问题,以便于分析某些交叉口转向一旦被限制或由于严重堵塞无法通行时,对OD间最佳行驶路线的影响。将城市道路网抽象为节点具有方向性权重的有向赋权网络,给出了该类网络中最短路径关键转向的定义,对经典Dijkstra算法进行改进,采用给弧标号的方式,设计了在该类网络中寻找最短路径及其关键转向的有效算法。最后通过一个实例进行了分析。     

交通状态模式识别研究

在网络层次上进行区域交通信号控制、交通分配和路径诱导是缓解交通堵塞的有效途径之一。大量的实践经验表明，无论是在城市交通网络，还是在高速公路网络中，网络的状态可分为数量有限且不同类型的模式，并且这些模式不断重复出现。而针对不同的交通网络状态模式，可以通过理论分析或仿真研究等途径，求解用于进行区域信号控制、交通分配及路径诱导的优化控制参数及控制策略。当系统识别出网络处于某种模式时，就可参照事先确定的优化参数及策略进行交通控制和诱导，以缓解交通拥塞，提高交通系统的运行效率。本文基于对交通网络状态模式识别问题及其应用的重要性的认识，应用模式识别的理论和方法，对交通网络状态模式识别问题进行了一些初步研究。     

基于K最短路的流量分配算法研究

结合国内城市轨道交通无缝换乘的运营特点,充分考虑影响城市轨道交通网络客流分配的主要因素及轨道交通网络的特有属性,用运行时间、换乘时间、拥挤附加时间构造城市轨道交通网络广义费用函数,分析乘客在城市轨道交通网络中的路径选择行为;在此基础上,基于图的理论和随机用户平衡原则提出城市轨道交通网络客流分配数学优化模型,设计基于费用约束的K最短路算法进行求解,得出更符合实际的有效路径集合,并通过一组数据对模型和算法进行了验证。     

基于网络对偶均衡的交通流分配模型

利用交通网络中交通流量与阻抗的对偶均衡关系,提出一个基于节点-路段的交通流分配变分不等式模型。分析网络中流量与阻抗间的对偶关系,将交通流量与出行阻抗看作一对对偶均衡变量。利用这种对偶均衡关系,通过不断调整网络中局部组成元素的平衡关系式,最终得到网络均衡状态。对上述网络流与网络阻抗的制约平衡特征加以抽象,不仅得到一个新的交通流分配模型,而且得到一个模拟出行者行为的启发式模型求解算法。新的模型算法有两个突出优点,一是进行流量分配过程中可避免反复求解联接起讫点对的最短路径,二是可以根据流量分配结果方便的求出任意起讫点间的有效路径集,并明确路径流量。     

城市混合交通网络系统优化模型及其算法

针对中国城市混合交通网络的特点,考虑影响出行者交通选择的主要因素,分析了城市混合交通网络中出行者的交通选择行为(包括交通方式选择和路径选择);从交通需求的角度出发,基于BPR公式构造了城市混合交通网络的路段阻抗函数,提出了城市混合交通网络流量分离及分配的变分不等式模型.在此基础上,以城市交通网络系统总阻抗最小为目标,以城市交通管理的政策为手段,采用双层规划方法构造了城市混合交通网络的系统优化模型,并设计了其求解算法.最后通过数值算例,分析了不同交通需求条件下,各种出行方式的流量变化情况以及应采取的系统优化策略.计算结果表明:无论在拥挤条件下还是在非拥挤条件下,优先发展公共交通都是降低网络总费用的有效手段.     

通行能力约束下的弹性需求交通投影动态演化模型

利用投影动态系统理论建立了具有路段通行能力约束的弹性需求交通网络动态演化模型.通过分析节点路段处交通流量与出行阻抗关系,揭示了出行者在网络局部对出行路线进行调整的决策过程,并分别建立了有通行能力约束的路段流量更新方程和弹性交通需求下的节点最短行程时间估计方程.通过在整个网络上整合上述两类方程,得到最终的交通网络投影动态...     

基于层次策略的路径规划算法对比研究

为比较路径规划中基于层次策略的分层算法的计算效率和规划结果的合理性,选取基于预计算的分层算法和基于道路等级的分层分区算法这2类典型的分层路径规划算法,通过对2类算法基本原理的分析,并引入新分区算法和＂虚拟边＂等方法改进现有基于道路等级的分层分区算法以适应实际路网下的路径规划。选取广东省路网数据进行大规模测试,通过寻找＂最短路＂和＂最快路＂进行算法效率和路径规划结果的比较分析。测试结果表明改进的基于道路等级的分层分区算法计算效率更高,规划结果更符合出行偏好。     

基于可视图和A~＊算法的连续模型路径搜索

针对交通枢纽仿真领域中行人最短路径搜索环境建模难的问题,提出一种基于可视图的连续拓扑模型最短路径搜索策略,通过在连续模型下建立可视图并使用A*算法搜索出一条适合行人通行的最短路径,将改进的可视图算法和A*算法结合,降低连续模型中自动选择路径复杂度和扩展结点数目.将该算法应用于城市综合客运枢纽功能与结构数值实验系统对行人对象进行路径搜索导航,实验结果证明此算法可行且具有更高的效率和通用性.     

A Variable Time-Discretization Strategies-Based,Time-Dependent Shortest Path Algorithm for Dynamic Traffic Assignment

Within the simulation-based dynamic traffic assignment (SBDTA) model, the time-dependent shortest path (TDSP) algorithm plays a crucial role in the path-set update procedure by solving for the current optimal auxiliary solution (shortest path). Common types of TDSP algorithms require temporal discretization of link/node time/cost data, and the discretization could affect the solution quality of TDSP and of the overall SBDTA as well. This article introduces two variable time-discretization strategies applicable to TDSP algorithms. The strategies are aimed at determining the optimal time discretization for time-dependent links/nodes travel time data. The first proposed strategy produces a specific discretization interval for each link. The second proposed strategy generates time-varying intervals for the same link over the analysis period. The proposed strategies are implemented in a link-based time-dependent A* algorithm in a SBDTA model DynusT and tested with two numerical experiments on two traffic networks. The results show that the proposed discretization methods achieve the research goal—to flexibly and scalably balance the memory usage and run time for SBDTA without degrading the convergence. This property is rather important when dealing with a large real-world network with a long analysis period.     

基于GIS的地面网络最短路实现在机场飞行区应急救援系统的应用研究

航空安全是空中交通运输系统正常运行的基础,快度、高效的处理航空安全事故对恢复空中交通系统的正常运行具有重要意义。文章从机场航空安全角度出发,通过分析机场飞行区地面网络结构图,创建了节点、弧段关系数据库以描述机场飞行区的网络拓扑结构,运用Dijkstra算法实现了快速最短路径搜索。在此基础上利用地理信息系统（GIS）二次开发工具MapX组件,以国内某机场为例,在Visusal Basic环境下实现了机场飞行区应急救援信息管理系统,为机场应急救援管理决策的可视化、便捷化提供了支持。同时拓展了MapX开发应用型地理信息系统的空间分析能力。     

綠色節能最佳化運輸路徑之規劃

隨著經濟發展,自然環境惡化程度持續加深,肇因為小客車數量日益增加,於是近年來綠色交通概念被大力提倡,如能以最佳節能路徑為運輸進行改造,將能為綠色環保盡一份心力。以最短路徑演算法（Dijkastra＇s Algorithm）為基礎,撰寫出最佳節能路徑之演算法,即每台車皆能以最低油耗知目標行駛,並將其與最短距離和最少旅行之路徑進行結果比較,結果發現該最佳節能路徑相較另兩條目標路徑時最能節省燃油消耗,此成果可提供小客車車主進行最佳節能路徑之規劃。另外也以路網均衡之概念進行交通量指派,使用者均衡和系統均衡分別於時間成本和油耗成本目標下之比較。     

终端区进场流的路径选择研究

在实际运行中,通常依据管制员的经验对进场航班流的路径进行管理,缺乏科学性.针对终端区进场流的路径选择与进场排序的流量管理问题,以进场航班的总完成时间最短为目标,建立基于时间窗与位置约束的路径选择与排序的数学模型.采用先选择路径再排序的循环寻优的方法进行求解,将禁忌搜索(TS)与排序算法相结合,设计了 TS-FCFS 与 TS-DP 两种算法,着重建立了基于关键路径的邻域结构,并加入有效的重置(RESTAR)策略,使算法快速有效的收敛至最优解.最后借助SIMMOD 仿真平台验证算法的可行性.以北京首都机场21架航班为例,仿真结果显示,TS-FCFS 与TS-DP 两种方法较原计划的进场路径总完成时间分别节约了149 s 与175 s.该路径选择算法降低了进场时间,提高了终端区进场效率.通过合理优化进场航班流的路径选择与进场排序,平衡了跑道负荷,减少了航空器间潜在的冲突,同时为管制员调配进场航班流提供了合理有效的路径选择建议.      

随机路网的最短路径问题研究

主要研究随机路网中的最短路径问题,首先给出随机路网的定义,建立了随机路网的模型,假定路段的费用是满足正态分布的随机变量,并给出从历史数据中得到此变量的均值和方差的统计学方法;然后得出路径出行费用的均值及方差的递推公式,将费用的方差当作一个限制条件,从而在Dijkstra算法的基础上,提出了带单一限制条件的最短路径算法,同时给出了算法的具体流程;最后用一个简单例子演示了算法的具体步骤,并在南京路网中验证了此算法的实用性。     

基于GIS的城市公交路网最优路线算法研究

利用GIS地理分析的特性,提出了一种较为简单的公交路网的描述方法。同时,设计了合乎乘客心理的最优路线判断标准,并在此基础上,设计了基于公交路线的双向搜索最短路算法,该算法与现有的基于公交站点最短路算法相比,大大地减少了计算时间。     

区域高速公路网络交通事件传感器布设方法研究

针对如何使用有限的传感器而获得最大的事件检测效益的问题,依据区域高速公路网络拓扑特点,充分利用匝道以及出入口的重要特性,以常规的最短路径算法为基础研究了一种交通事件传感器的优化布设方法,以高速公路网络行程时间标准差作为优化目标,在充分利用现有资源前提下,分别布设和优化路段和出入口事件检测器,形成两层结构的事件检测传感器网络体系。并以上海市高速公路网为例进行了实例应用分析。结果表明,依据合适的优化方法可以确定传感器最佳布设位置和数量,同时结合高效的交通事件检测算法,可以全面提升交通事件检测技术。     

Robust traffic assignment model: Formulation,solution algorithms and empirical application

ABSTRACT

The deterministic traffic assignment problem based on Wardrop's first criterion of traffic network utilization has been widely studied in the literature. However, the assumption of deterministic travel times in these models is restrictive, given the large degree of uncertainty prevalent in urban transportation networks. In this context, this paper proposes a robust traffic assignment model that generalizes Wardrop's principle of traffic network equilibrium to networks with stochastic and correlated link travel times and incorporates the aversion of commuters to unreliable routes.

The user response to travel time uncertainty is modeled using the robust cost (RC) measure (defined as a weighted combination of the mean and standard deviation of path travel time) and the corresponding robust user equilibrium (UE) conditions are defined. The robust traffic assignment problem (RTAP) is subsequently formulated as a Variational Inequality problem. To solve the RTAP, a Gradient Projection algorithm is proposed, which involves solving a series of minimum RC path sub-problems that are theoretically and practically harder than deterministic shortest path problems. In addition, an origin-based heuristic is proposed to enhance computational performance on large networks. Numerical experiments examine the computational performance and convergence characteristics of the exact algorithm and establish the accuracy and efficiency of the origin-based heuristic on various real-world networks. Finally, the proposed RTA model is applied to the Chennai road network using empirical data, and its benefits as a normative benchmark are quantified through comparisons against the standard UE and System Optimum (SO) models.