论文部分内容阅读
车辆路径规划问题(VRP)是物流配送过程中的关键问题之一，对车辆路径规划问题的研究尤其是对带时间窗的车辆路径规划问题(VRPTW)的研究，有助于提高物流经济效益，实现物流科学化。带时间窗的车辆路径规划问题是组合优化问题中的带多个约束条件的NP-完全问题，早期作为单目标优化问题被广泛研究。近年来，随着进化多目标优化算法的发展，许多研究者开始使用进化多目标优化的方法对该问题进行多目标优化，在优化目标方面则普遍采用了传统的车辆数和总行车距离两个目标建立优化模型。然而，有研究表明，车辆数和总行车距离两个目标之间冲突性并不强，并且车辆数为离散目标函数，因此目前基于车辆数-总行车距离模型的多目标优化算法均未能得到包含丰富非支配解的代表性Pareto前端。另外，单纯的进化优化方法在求解组合优化问题时也存在效率不高，收敛慢的问题。本文基于当前研究现状的不足，提出了一种新颖的连续多目标优化模型，并且将LK启发式局部搜索同非支配领域免疫算法(NNIA)相结合设计了求解该模型的新的Memetic算法。本文的主要工作有：(1)针对带时间窗的车辆路径优化问题，建立了服务质量-服务代价两目标车辆路径优化模型MOM-CQ(Continuous Multi-objective Vehicle Routing Model Based onService Cost and Quality)，具体又包括严格考虑约束的MOM-CQC和将约束转化为目标函数的MOM-CQUC两个模型，通过车辆到达时间的早晚衡量服务质量，建立服务质量目标函数，沿用车辆总行驶距离衡量服务代价。两种模型目标函数均为连续目标函数，通过构造求解VRPTW的NNIA算法对两个模型进行了求解，实验结果表明MOM-CQC模型具有普遍强烈的冲突性，非常适合连续多目标优化并且较MOM-CQUC模型适用性更强。(2)针对提出的MOM-CQC模型，利用车辆路径优化问题同旅行商问题天然的相似性，在NNIA的框架下引入Lin-Kernighan(LK)启发式搜索算法，并重新设计了已有的进化算子，构造了密母免疫多目标车辆路径优化算法(MIA)。算法对优势种群使用LK作局部搜索，提高了优势种群的质量，加快了算法收敛速度，克服了NNIA稳定性不足的缺点，并且提升了算法最终得到的解的路径质量，提高了算法最终得到的Pareto前端收敛程度。