Abstract: This paper concerns on the split delivery vehicle routing problem with stochastic demands. A stochastic program with recourse is formulated. An PSO based heuristic combined with local search is proposed, in which an integer code method and an decoding method based on the Bellman’s equation is presented. This paper also proposes several ways to deal with the difference between the number of the nonzero elements in the vectors including the velocity, the personal best position, the local best position and the global best position. Extensive experiments are carried on the modified Solomon test instance set and the modified Christiansen and Lysgaard test instance set, better parameters are chosen, including the size of the population, the probability of the local search and the number of iteration. The results also been compared with existing results, and 16 improved solution are obtained out of 26 test instances, with the gap between the solution of the other 10 instances and the existing best solutions less than 1%.

Key words: stochastic demands, split delivery, Vehicle Routing Problem（VRP）, Particle Swarm Optimization（PSO）

摘要： 对需求随机的分批配送车辆路径问题进行研究，建立带修正的随机规划模型。设计与局部搜索算法相结合的粒子群算法进行求解，算法使用整数编码和基于Bellman方程的允许分割需求的解码方法。并针对允许分批配送时导致的粒子速度、粒子自身最优位置、局部最优位置及全局最优位置等向量非零元素个数不同的问题，设计可行的统一向量长度的方法。算法在调整的Solomon算例测试集和调整的Christiansen和Lysgaard算例测试集上进行测算，测试有效参数、速度长度及速度更新方程。同时与现有结果进行对比，虽然计算效率较低，但在测试的26个算例中，有14个算例的最优解得到更新，剩余的算例最优解与现有最优解相差小于1%。

关键词: 随机需求, 分批配送, 车辆路径问题, 粒子群算法