基于动态行程时间可靠性的单车辆路径选择算法研究

Study on Single Vehicle Routing Algorithm Based on Dynamic Travel Time Reliability

为了提高出行者的路径选择效率,从微观层面对随机动态路网条件下的单车辆路径选择问题进行深入研究。随机动态路网条件下,作为车辆路径构成单元的路段,不同时刻车辆在其上的行程时间具有明显的动态变化特征,若使用传统的最短路算法进行车辆路径选择,将某一时点的路段行程时间作为路段权值不能反映路段行程时间动态变化产生的影响,车辆路径选择结果容易造成误判。为解决此问题,按照集散波理论对于路段车辆运行状态的划分方式,首先以路段下游信号转换时刻目标车辆与排队车流队尾的相对位置关系为切入点,对路段行程时间进行分状态分类随机动态预测,然后建立对应可接受水平下的路段行程时间可靠性计算模型,最终分别针对简单网络和复杂网络的单车辆路径选择问题提出使用行程时间可靠性作为关键控制变量的三阶段车辆路径选择模型和权值异化的Dijkstra车辆路径选择算法。通过案例及对比分析表明,在出行者面临的简单网络中使用行程时间可靠性进行车辆路径选择可纠正仅仅按照单一行程时间进行车辆路径选择造成的选择误判,在复杂网络中使用行程时间可靠性作为路段权值异化的Dijkstra算法可迅速求出最可靠路径,有效解决了随机动态路网环境下的单车辆路径选择问题,是对路径选择问题研究的深入拓展。

In order to improve the routing efficiency of traveler,the routing problem of single vehicle under the condition of random dynamic road network is studied from micro level. Road section is a vehicle routing unit,the travel time on it has obvious dynamic change characteristics under random dynamic road network condition. If using the traditional shortest path algorithm to solve routing problem and using the instantaneous section travel time as the section weight value cannot reflect the influence of dynamic change of section travel time,the result of vehicle routing may be misjudged easily. In order to solve this problem,a new method is created. According to the division mode of vehicle running status in the theory of gather-disperse wave,first,the relative position relationship between the target vehicle and the tail of the queue in the signal conversion time on downstream section is analyzed,and the road travel time is predicted by states randomly and dynamically. Then, a calculation model about section travel time reliability under acceptable level is established. Finally,2 algorithms for single vehicle routing problem using the travel time reliability as the keycontrol variable are set： one is a 3-stage routing model,the other is a weight dissimilated Dijkstra routing algorithm for single and complex road networks respectively. Through case analysis and comparison,it is found that（ 1） when the traveler is facing a simple network,the vehicle routing using travel time reliability can correct the misjudgment that is only according to the single travel time;（ 2） the dissimilated Dijkstra algorithm,which uses travel time reliability as the section weight value in the complex network,can quickly find the most reliable path. The two algorithms can effectively solve the single vehicle routing problem in random dynamic network environment. The research is the further development of routing problem.