论文部分内容阅读
本文主要研究的带时间窗车辆路径问题(Vehicle Routing Problems with Time Windows,VRPTW),存在于物流运输和供应链等诸多领域,以使用车辆数最少和总行驶路程最小为目标,车辆路径规划为自变量,求解出一个由非支配解组成的Pareto集合,为决策者提供决策支持。VRPTW是经典的NP-Hard问题,其问题规模通常超出精确算法等算法的适用范围。智能优化算法以其优秀的全局搜索能力和较快的收敛速度等特点,成为解决此类问题的常用算法。本文研究了求解多目标VRPTW的基于分解的多目标进化算法及膜优化,主要做了以下工作:(1)针对多目标VRPTW,本文首先选择了收敛速度快的基于分解的多目标进化算法(A Multi-objective Evolutionary Algorithm Based on Decomposition,MOEA/D),并在其全局搜索能力强的基础上加入合适的局部搜索算子,弥补其局部搜索能力的不足。首先,将解的存储结构设置为链式存储和顺序存储两种,分别配合启发式车辆数优化算子和启发式路程优化算子在邻域内采用切比雪夫法进行进化操作。然后,加入邻域间的进化操作,减少局部最优的情况的出现。(2)通过对改进MOEA/D的实验分析,可以看出它仍存在所求Pareto前沿面的边界不是最优的缺点,单维度上的解还有优化空间,有必要探索其Pareto前沿面的边界。针对此缺点,本文提出了一种求解多目标VRPTW的基于MOEA/D和组织型P系统的膜算法(T-MOEA/D),利用单目标求解以及P系统的并行性,在优化边界的同时提高计算能力不增加时间代价。在该算法中,构建了具有4个膜的组织型P系统,把对本文双目标问题的两种单目标求解、改进MOEA/D的操作以及外部种群的自搜索分别设定成各膜中的反应规则,使用细胞通讯规则对该系统中的对象进行信息传递和共享,确保并行进化的稳定运行。通过仿真实验和数据对比,可以验证改进MOEA/D具有可行性和有效性,其精确度在同类进化算法中有一定的竞争力。在此基础上,T-MOEA/D膜算法进一步优化了Pareto解集的分布。