行程时间不确定环境下的可靠最短路径算法研究

Link travel times in congested urban road networks are highly stochastic. Many empirical studies have found that travelers on such networks prefer to choose reliable shortest paths for their travel so that they can arrive at destinations with a higher on-time arrival probability. Therefore, it is necessary to investigate the reliable shortest path problem (RSPP) in stochatic stationary networks with travel time uncertainties. Due to its non-additive property, RSPP cannot be solved by traditional shortes path algorithms. To address this non-additive issue, RSPP in this study is formulated as one of multi-criteria shortest path problems. The domiance condition of RSPP is established so as to reduce the number of generated non-dominated paths. Based on the established dominance condition, a hierarhical network approach is proposed to efficently solve RSPP in large-scale road networks. In addition, RSPP is extended into stochastic time-dependent (STD) networks. A new link travel time model with stocahstic-first-in-first out property is proposed. Based on the proposed model, efficient reliable shortest path algorithms are developed for finding reliable shortest path in STD networks. Finally, to demonstrate the applicability of proposed models and algorithms, a prototype route guidance system (RGS) is developed using real-world traffic data. The development of reliable shortest path algorithms can capture travellers' various risk-taking behvarior under travel time uncertainties, so as to enhance the RGS user friendly. It is expected that RGS with reliable shortest path finding functions can not only help travelers to make better route choice decisions, but also improve overall network traffic conditions.

在拥堵的城市网络中，行程时间具有高度的不确定性。大量实证表明：出行者在行程时间不确定的情况下更倾向于选择可靠度高的路径，即可靠最短路径。因此，很有必要研究随机网络中的可靠最短路径问题。由于可靠最短路径具有不可加性(即路径阻抗不等于路段阻抗之和)，不能直接采用传统的最短路径算法求解。针对可靠最短路径的不可加性难题，本项目将可靠最短路径问题表述为多目标优化问题，研究其多目标支配条件。在此基础上，提出一种随机网络的层次模型,减小可靠最短路径计算的规模，高效地查找超大型网络中的可靠最短路径。将问题进一步扩展到动态随机网络中，研究路段时间的随机先进先出特性，提出有效的动态可靠最短路径算法。最后，结合实际交通数据，对理论成果进行综合实验验证和分析。可靠最短路径算法考虑了出行者在行程时间不确定环境下的风险决策行为，可提高导航应用的可靠性，有效地指导公众出行，对缓解交通拥堵具有十分重要的意义。

在拥堵的城市网络中，行程时间具有高度的不确定性。大量实证表明：出行者在行程时间不确定的情况下更倾向于选择可靠度高的路径，即可靠最短路径。本课题针对随机网络中的可靠最短路径问题，主要研究：①基于浮动车数据研究行程时间分布估计方法，定量分析行程时间不确定性；②建立动态随机网络中的多目标支配条件，证明动态随机网络中行程时间的随机先进先出和不可逆特性；③提出多目标A*算法和双阶段搜索算法，高效地求解大规模网络中的正向和逆向可靠最短路径问题；④进一步研究可靠最短路径成果在出行行为分析和物流配送中的应用。项目研究进展顺利，目前已发表论文9篇（其中SCI/SSCI文章8篇，EI论文1篇），授权2项国家专利；培养了毕业博士生1名，硕士生4名；资助成员和学生参加了5个国际/国内会议。通过该项目的研究能够为提高导航应用的可靠性，有效地指导公众出行，提供理论支撑和决策依据。