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

Vehicle routing problem with stochastic customers and demands based on the cross-entropy method

提出一种解决随机用户和需求车辆路径问题(VRPSCD)的方法.针对目标函数的复杂性,设计一种基于Monte-Carlo抽样求解路径期望费用的有效方法;为提高标准交叉熵(CE)法性能,针对用于更新Markov转移矩阵关键路径,根据分位值改变大小,设计了自适应调整方法.计算结果验证了采用该方法解决此问题的鲁棒性和有效性.

A method is proposed to the vehicle routing problem with stochastic customers and demands. Due to the complexity of its objective function, an effective algorithm is designed to obtain the expected cost of routes by using Monte-Carlo sampling. In order to improve the performance of standard cross-entropy method, an adaptive adjustment scheme is developed for the crucial routes used to update Markov transition matrix in terms of the improvement level of quintiles. Computational results show the robustness and the validity of the proposed approach for solving such problems.