随机多路径车辆路径问题及其算法

摘要

为了更加契合现实的城市配送运作环境，本文对经典的车辆路径问题进行了新的拓展研究，考虑了任意两个物流节点之间存在多条路径且每条路径的通行成本不确定的情况，建立了随机多路径车辆路径问题(stochastic multi-path vehicle routing problem, SMP-VRP)模型，并针对所研究的问题设计了具有较高求解效率的两阶段算法。算法的第一阶段，采用具有约束的K-means算法对客户进行分组，将SMP-VRP问题转化为随机多路径旅行商问题(stochastic multi-path traveling salesman problem, SMP-TSP);算法的第二阶段，将SMP-TSP问题先转化成等价的情景规划问题，再近似成确定型规划问题；通过对SMP-TSP问题的求解，进而得到SMP-VRP问题的解。算例测试表明，相较于采用贪心策略的配送组织方法，本文所提出的两阶段算法可以降低7%左右的平均配送成本，并且表现出良好的稳定性，为物流配送车辆路径优化问题提供了新的研究思路，且具有较强的应用价值。

关键词

城市配送 / 车辆路径问题 / 随机多路径 / 两阶段算法 / K-means算法