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

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）