速度时变的多中心半开放式车辆路径问题研究

Research on Multi-depot Half-open Vehicle Routing Problem with Time-varying Speed

针对多中心半开放式车辆路径问题,考虑软时间窗约束和车辆速度变化情况,构建了最大化平均客户满意度、最短配送距离和最小配送成本为目标的优化模型,并设计了两阶段求解算法。基于自适应网格密度法和邻域拥挤密度法对多目标粒子群算法的外部档案进行维护及选取全局最优粒子,提高算法的收敛性和后期种群多样性,以获得初始可行解。用变邻域搜索算法优化初始可行解,减小配送距离,降低配送成本。通过仿真实验结果验证了模型的合理性和两阶段算法的有效性。

Aiming at the multi-depot half-open vehicle routing problem and considering the soft time window constraints and vehicle speed changes,an optimization model with the goal of maximizing average customer satisfaction,shortest distribution distance and minimum distribution cost is established and a two-stage solution algorithm is designed.The self-adaptive grid density method and neighborhood crowding density method are used to maintain the external archives and to select the global optimal particles,and the convergence of the multi-objective particle swarm optimization(MOPSO)and the diversity of the later population can be improved to obtain the initial feasible solution.The initial feasible solution is optimized by the variable neighborhood search algorithm(VNS)to reduce the delivery distance and cost.The rationality of the model and the effectiveness of the two-stage algorithm design are verified by the simulation experiments.