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

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