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

来源：计算机测量与控制杂志2014年第11期北京时间：

作者：祝毅鸣,刘莹

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

关键词：车辆路径;交叉熵;规划;蒙特卡罗 

基金资助：河南省科技厅科技攻关项目(112102310482)。