行驶时间随机的分批配送车辆路径问题模型与算法

Model and algorithm for split delivery vehicle routing problem with stochastic travel time

为研究分批配送和等待时间对行驶时间随机的车辆路径问题(VRP)的影响,针对行驶时间随机的分批配送车辆路径问题,在软时间窗下考虑等待时间,建立带修正的随机规划模型;同时设计改进的粒子群优化(PSO)算法进行求解:使用需求点可多次出现的整数编码,设计改进的相对位置索引算法进行解码以解决粒子中出现分批需求点问题;将自适应选择用于速度更新以解决各向量长度不同的问题;将路径重连算法用于位置更新过程以解决粒子在离散空间和连续空间转换时信息丢失的问题,适应允许分批配送的特点。通过对调整的Solomon算例测试,考虑等待时间将造成总费用平均增加约3%,且更倾向于分批配送。分批配送能有效降低总费用(2%)和减少使用的车辆数(0.6);在部分算例,特别是R2类算例中,分批配送能有效降低等待时间,平均降低0.78%。

To evaluate the effect of split delivery and waiting time on Vehicle Routing Problem( VRP) with stochastic travel time, by considering the waiting time under soft time window, a stochastic programming model with correction was formulated to solve the Split Delivery VRP( SDVRP) with stochastic travel time. Meanwhile, an improved Particle Swarm Optimization( PSO) was proposed for this problem. At first, an improved relative position index method was used to decode the integer type code in which some customers( the split customers) may appear more than once. Then, an adaptive selection process was used to update the velocity in which the length of the involved vectors are different from each other besause of the split delivery. At last, the path relinking method was used to update the position of the swarm to deal with the information loss caused by the transformation between the continuous space and the discrete space. The experimental results on modified Solomon's instances show that the all-in cost is averagely increased by about 3%, and customers tend to choose split delivery when considering the waiting time. The use of split delivery can effectively reduce the all-in cost( 2%) and the use of vehicles( 0. 6); in addition, in some instances, especially in the R2 instances, the waiting time can be reduced by about 0. 78%.