论文部分内容阅读
车辆路径规划问题是物流配送管理和城市交通改善等现实应用中普遍存在的问题。根据优化目标和约束条件的不同，车辆路径规划问题可分为多种类型，本文主要求解时间窗约束的多目标车辆路径规划问题（MO-VRPTW），同时最小化运输车辆数和车辆行驶总路程两个目标。MO-VRPTW问题属于NP-Hard组合优化问题，现有的启发式方法难以获得问题的全局最优解。进化算法凭借其良好的全局搜索能力，越来越多的被应用于求解MO-VRPTW问题。本文将基于分解策略的进化多目标优化算法MOEA/D与传统的启发式局部搜索策略相结合，设计求解MO-VRPTW问题的有效方法。具体的研究工作如下：MOEA/D算法的全局搜索能力已经被越来越多的研究成果证明。本文在MOEA/D的框架下，将swap、lambda interchange和2-opt三种经典局部搜索机制引入其中，构造兼顾全局和局部搜索能力的Memetic算法M-MOEA/D求解MO-VRPTW问题。三种搜索算子具有不同的搜索行为，相互合作，有效提高了算法的搜索效率。对Solomon的56个标准测试数据集的仿真实验结果验证了M-MOEA/D算法的有效性。进一步在M-MOEA/D算法的基础上，针对MO-VRPTW问题的特点对算法的子问题邻域构建策略和选择机制进行了改进。MOEA/D利用目标函数的连续性假设构造单目标优化子问题的邻居列表，交叉操作的父代个体只能在邻居列表内子问题的最优解中选择，产生的子代个体只能更新邻居列表中子问题的最优解。然而，这种连续性假设并不适用于MO-VRPTW问题。因为该问题的决策空间和目标空间均为离散空间，目标函数值相近的两个解在决策空间上未必接近。针对这一问题，本文根据子问题最优解在决策空间上的相似性定义子问题之间的距离，提出了一种新的邻域构建策略，并基于新的邻域构建策略设计了适合MO-VRPTW问题的选择算子。仿真实验结果表明，改进后的M-MOEA/D算法在求解质量和收敛速度上取得了良好的折中。在Solomon数据集的多数测试问题上求得了较高质量的解。