考虑时空相关随机行驶时间的车辆路径问题模型与算法

本文对一类在真实道路网络中考虑时空相关的随机行驶时间的车辆路径问题进行了研究. 首先我们建立了该问题的两阶段随机规划模型. 然后我们将用于候选解寻优的智能优化算法与用于产生评价解的随机场景的情景生成技术相结合，提出一种智能随机优化方法求解该问题. 为了有效地进行解的寻优，本文结合可变邻域下降算法提出了一种混合粒子群优化算法.最后通过一系列基于北京市区道路网络的算例实验，我们验证了所提出的混合粒子群优化算法的有效性.实验结果还表明，考虑实际交通环境中道路网络上车辆行驶时间的时空相关性，会影响最优车辆路径决策方案.

Model and algorithm for vehicle routing problem with spatial-temporal correlated stochastic travel times

This paper studies a version of vehicle routing problem with spatial temporal correlated stochastic travel times in real road networks. First,a two stage stochastic optimization model is established for this problem. An intelligent stochastic optimization method is then proposed to solve the model, in which an efficient intelligent optimization algorithm is developed to find candidate solutions, and the scenario generation technology is adopted to generate spatial temporal correlated stochastic travel time scenarios to evaluate the solutions. This paper proposes a hybrid particle swarm optimization algorithm combined with a variable neighbourhood descent algorithm to perform effective optimization. Finally, a series of testing instances are established based on the road network of Beijing to verify the effectiveness of the hybrid particle swarm optimization algorithm. The experimental results show that considering the spatial temporal correlation of stochastic vehicle travel times in real traffic environment will affect the best vehicle routing decisions.