基于交叉熵法解决随机需求车辆路径问题

Solving Vehicle Routing Problem with Stochastic Demands Based on Cross-Entropy Method

提出一种解决随机需求车辆路径问题(VRPSD)新方法。首先,采用预防性补救措施,建立了VRPSD模型,其次,为提高标准交叉熵(SCE)法性能,对用于更新Markov转移矩阵的路径,设计了根据分位值改变大小的自适应调整方法。仿真结果验证了该算法解决VRPSD的有效性。

A new method is proposed for solving Vehicle Routing Problem with Stochastic Demands（VRPSD）.Firstly,a mathematical model for VRPSD is established by using preventive recourse action.Secondly,in order to improve the performance of Standard Cross-Entropy （SCE）algorithm,an adaptive adjustment scheme is developed for the routes used to update Markov transition matrix in terms of the improvement level of quintiles.Finally,simulation results prove the validity of the proposed method for solving VRPSD.