Reliable Shortest Path Problems in Stochastic Time-Dependent Networks

This study investigates the time-dependent reliable shortest path problem (TD-RSPP), which is commonly encountered in congested urban road networks. Two variants of TD-RSPP are considered in this study. The first variant is to determine the earliest arrival time and associated reliable shortest path for a given departure time, referred to as the “forward” TD-RSPP. The second problem is to determine the latest departure time and associated reliable shortest path for a given preferred arrival time, referred as the “backward” TD-RSPP. It is shown in this article that TD-RSPP is not reversible. The backward TD-RSPP cannot be solved by the algorithms designed for the forward problem using the reverse search from destination to origin. In this study, two efficient solution algorithms are proposed to solve the forward and backward TD-RSPP exactly and the optimality of proposed algorithms is rigorously proved. The proposed solution algorithms have potential applications in both advanced traveler information systems and stochastic dynamic traffic assignment models.     

交通网络最短路径并行算法研究综述

首先回顾了最短路径并行算法的国内外研究进展,对当前的最短路径并行算法进行分类。接着讨论了交通网络分析中最短路径并行算法常用的两种实现策略以及各自的优缺点;分析了影响网络分割策略并行算法性能的3个主要因素:最短路径算法选择、网络分割及终止检测方法。最后就实际交通网络中最短路径并行算法需进一步研究的问题给出了建议。     

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

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

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

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

灾后公路交通应急救援通道选择模型

基于灾后路段可通行性、救援时效性及安全性的分析,提出了灾后最优应急救援通道定义。结合历史重大自然灾害救援时间与存活率统计资料,提出了时效性与安全性的最优应急救援通道评价原则,建立了包括路径行驶时间与行车风险的最优应急救援通道评价指标。对评价指标进行标准0～1变化后,构建了应急救援通道的目标函数。按照灾后道路破坏导致的路网交通功能受损情况将其划分为正常运营状态及破坏状态,其中针对路网正常运营的状态提出了行程时间最短、行车安全性最高的最优救援通道搜索算法;对交通中断的路网破坏状态,构建了基于路段破坏位置、抢通耗时、抢险机械设备及人员配备的最优救援通道修复算法。研究结果表明:提高路段抗灾能力、路网冗余度、优化抢险保通技术力量及机械设备储备,是提高灾后应急救援工作的重要途径。     

震后应急救援路径选择研究

阐述了应急救援系统建立的必要性及其研究现状。从震后路段的阻抗、交通需求、多源点受灾和救援、交通管制等方面来考虑震后最优救援路径选择模型的构建及其相应算法,以确保震后应急救援行动高效安全地进行。最后在分析存在问题的基础上提出了研究方向。     

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

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

城市道路固定型交通检测器布局优化模型

交通信息采集是智能交通系统的重要基础,准确、可靠的数据是动态交通管理、控制的重要保障。分析影响检测器布局的因素,主要包括交通流的特性、道路交通环境、居民出行路径的选择等,提出基于检测器利用率最优的规划模型。探讨模型参数的计算方法,根据观测样本的均值和方差计算交通量波动系数,用最短路径法计算路段客观重要度。阐述模型的求解过程,通过比较几种传统优化算法的优缺点,设计改进隐枚举算法,并给出具体步骤。     

基于时间依赖网络的城市交通紧急疏散线路研究

研究时间依赖网络的城市紧急疏散交通线路问题.在对考虑疏散过程中交叉口延误和通行能力、紧急疏散网络防堵塞改造已有研究的基础上,对紧急疏散时城市交通网络的时变特性进行分析,提出了动态路阻交通紧急疏散线路的思想.考虑到紧急疏散时不一定满足FIFO要求的特性,将研究对象转化为时间依赖非FIFO网络交通紧急疏散线路的确定问题,建...     

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

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

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

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

观测路径出行时间下随机网络交通需求估计

道路网络起讫点(OD)需求是城市决策长期交通规划和短期交通管理中的基础参数,准确的交通需求更是实施交通拥堵控制、限行限速、路径诱导等措施的先决条件.综合运用观测的轨迹已知和未知路径出行时间,建立随机网络交通需求估计双层规划模型.上层广义最小二乘模型最小化历史交通需求与待估交通需求、观测路径出行时间与待估路径出行时间之间...     

Lane assignment problem using a genetic algorithm in the Automated Highway Systems

This paper deals with the lane assignment problem in the Automated Highway Systems (AHS). The purpose of lane assignment strategies is to increase throughput on multi-lane highways with many entry and exit points, based on the itineraries of vehicles using the highway (point of entry, time of entry and exit point) and the effects of maneuvers. Using partitioned lane assignment strategies, the lane assignment problem is formulated as an optimization problem to find the proper positions of partitions. Then the optimal problem is solved using a Genetic Algorithm (GA). The proposed algorithm has been validated by comparing its solution with that of an all-cases algorithm for a simple case. Moreover, a traffic simulator with a realistic car-following model as well as lane change logic has been developed. The simulation results show the efficiency of the proposed genetic algorithm, compared with random assignment algorithms.     

基于定向树搜索的博弈配流模型

通过将交通路网中路径搜索的定向式启发策略与深度优先的树搜索算法相结合,提出了一种有效路径的定向树搜索算法。该算法利用节点坐标划定有效搜索区,使搜索范围缩小。在具体的求解过程中一是利用已求出的节点位势确定下一步搜索的邻接节点范围,二是利用一个简单的节点估价函数确定进一步要选择的节点。通过给每一个节点一个搜索标记号来记录搜索树的分杈情况,可以顺利的实现有效路径的连续搜索,并结合博弈理论建立了新的交通流分配模型,给出了博弈配流的步骤。新模型合理反映了交通路网中出行者的出行路径决策行为,提供了唯一的路径流量解,因此便于在交通网络的灵敏度分析和优化设计中应用。最后,用一个简单算例说明了该方法的有效性。     

受限路网中汽车行驶最优路径算法及优化实现

实际交通网络不仅包含路网的拓扑关系，还存在大量交通禁行限制。考虑了交通连通性约束所建立的受限路网模型能够更精确地反映实际交通网络。文中提出一种能够在受限路网中寻路的最优路径算法，并具体讨论了算法的优化实现。应用表明该算法可靠高效，可用于实际受限交通网络最优路径规划。     

交通规划中基于遗传算法的最短路交通分配法应用研究

对交通分配中的最短路径和遗传算法进行分析,提出一种适合在不考虑各条出行路径路况和用户出行行驶速度情况下基于遗传来搜索最短路径的分配方法.介绍交通分配的最短路法原理以及遗传算法的概念和过程,给出基于遗传算法的搜索最短路算法过程设计,并用简例对其进行说明.     

基于群决策理论和双层规划模型的交通信号控制优化

基于干道延误时间最小和路段行程速度最大的设计理念,利用智能优化算法和群决策理论,建立了一种双层规划模型下的城市干道交通信号控制方法。算法结合了智能优化策略中的遗传算法和丰富的群体专家意见,并采用模糊数的描述方式实现对不同控制目标的分析评价,给出了一套完善的干道交通信号配时优化方案,使交通问题的分析得以更加客观和实际。最后给出一个实际主干道问题的算例分析,运用MATLAB和Visual C++编程计算对控制方案进行模拟。仿真结果表明,这一方法能有效地改善延误和路段行程速度。     

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.     

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

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

随机交通网络中依赖信息的路径优化问题研究

针对交通网络中路径通行时间具有与时间相关的随机分布特性，将研究在此类交通网络上依赖信息的路径选择问题。在路径选择过程中引入交通信息，在随机交通网络上最优路径选择原则为下一节点的选择将依赖于已实现的路段时间及当前节点的出发时间，通过期望最小值方法，按照路径通行时间期望值最小原则，建立一种通过所获得交通信息来进行路径选择的优化模型，给出了模型的求解算法。并在简单交通网络上对模型进行实现。