Abstract: In order to solve the Vehicle Routing Problem with Simultaneous Pickup and Delivery（VRPSPD） with soft windows, a optimization model is developed for minimizing the total cost, which includes the vehicle dispatching cost, driving cost and penalty for time window. The hybrid particle swarm optimization algorithm is proposed to solve this problem, the algorithm is combined with variable neighborhood down search as the main body of the adaptive disturbance mechanism, using adaptive neighborhood strategy choice, and applying a variable number of cycles in each neighborhood search to improve the detection capability and search efficiency of the solution space. The Adaptive Perturbation Mechanism, which is based on the descending search of variable neighborhoods, adapts to the selection of neighborhood strategy and applies a variable number of cycles in each neighborhood search to improve the detection capability and search efficiency of the solution space. Numerical experiments show that the algorithm is feasible and effective.

Key words: soft time window, vehicle routing problem with simultaneous pickup and delivery, particle swarm optimization, variable neighborhood descent

摘要： 针对带软时间窗的同时集配货车辆路径问题（VRPSPD），建立了以车辆派遣成本、行驶成本和时间窗惩罚成本之和最小为目标的车辆路径优化模型；设计混合粒子群算法进行求解，该算法结合以变邻域下降搜索为主体的适应性扰动机制，采用适应性选择邻域策略，并在每个邻域搜索中应用可变的循环次数，以此提高对解空间的探测能力和搜索效率。数值实验结果表明了该算法的可行性和有效性。

关键词: 软时间窗, 同时集配货车辆路径, 粒子群算法, 变邻域下降搜索