基于改进交叉熵算法的随机需求车辆路径设计方法

Design Method for Vehicle Routing Based on Improved Cross Entropy with Random Demand

摘要:

传统的车辆路径规划方法无法有效地应对实时在线客户需求量随机变化的情形且收敛速度过慢,为了克服其缺点,设计了一种基于蒙特卡罗和重要性采样的交叉熵车辆路径规划方法；首先对随机动态车辆路径规划问题进行了数学建模,然后,描述了蒙特卡罗和交叉熵算法实现稀有事件概率估计的原理,并引入Tsallis熵实现对传统交叉熵的改进,采用蒙特卡罗多次采样获得的费用期望作为路径真实费用的估计值,通过交叉熵算法对重要性概率密度函数和分位数进行不断更新,以增加重要样本获取的概率,从而实现最优路径的获取；最后定义了具体的基于Tsallis熵的随机动态车辆路径规划方法；在MATLAB仿真工具下进行试验,结果表明文中方法能有效地解决随机动态车辆路径问题,与其它方法相比,具有收敛速度快和收敛精度高的优点,是一种有效的随机动态车辆路径规划方法。

Abstract:

Traditional vehicle routing problem can not effectively sovle the in time online and random chaning custeromer demands and the slow convergence rate, in order to conquer the defects, a design method based on monte-carlo and importance sample cross entroy is proposed. Firstly, the vehicle routing problem is modeled mathematically, then the prnciples of monte-carlo and cross entropy algorithm for estimating the spare event appearance probability is described, the cross entropy is improved by add Tsallis entropy, using the monte carlo to estimate the total fee for the path as the real fee, the cross entropy is used to renew the imporatance probability function and partition position to improve the probality of important sample to realize the opitimal path. Finally, the random dynamic route planning method based on Tsallis entropy is defined. The simulation is implemented in the MATLAB, the simlulation result shows the method in this paper can solve the vehicle routing problem effectively, compared with the other methods, it has the rapid convergence rate and convergence precision, therefore, it is an effective random dynamic vehicle routing method with big priority.