Abstract: Accidents, bad weather and traffic congestion contribute to the uncertainties of travel times in real-life transportation networks, which greatly impact the quality of individual's life and the reliability of transportation systems. In this context, this paper proposes a robust optimization approach which addresses the optimal routing problem in transportation networks with dynamic stochastic link travel times. Specifically, taking the reliability of travel times into consideration, the indicator of robust schedule delay is used as the criterion of optimality to evaluate the candidate paths. The objective function is defined as minimizing the largest cost between the actual arriving time and the desired arrival time in such a road environment. Then, under the stochastic consistent condition, a mathematical proof is given to simplify the model, and it is converted into solving an optimal path problem in a deterministic dynamic network. In the end, a modified Dijkstra's algorithm is applied to solving the problem in a sampled network. The computation complexity of the algorithm is polynomial-time, and the proposed approach is not probability-based. Thus, it has an potential of an application to a large-scale network.

Key words: urban traffic, optimal path, robust optimization, stochastic and time-dependent network, priori data

摘要： 交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。

关键词: 城市交通, 最优路径, 鲁棒优化, 随机时变网络, 先验数据