论文部分内容阅读
车辆路径问题具有重要的现实意义同时有着高度的复杂性,是现代物流管理的核心问题,应用领域涵盖超市配送物品、工业垃圾收集、校车路线、安全巡逻服务和城市报纸分发等,而变体多车型带时间窗车辆路径问题更符合当下的研究,不仅满足了客户特殊的时间窗口要求,同时便于配送中心采用多元配送方式,实现配送资源的合理调配。由于多车型带时间窗车辆路径问题的NP-hard特性,同时为克服单一算法的弊端,采用混合多种算法或者策略的混合进化算法的方式成为解决该问题的有效途径,对其的研究具有积极得理论和实际研究价值。本研究提出了一种混合进化算法用于解决多车型带时间窗的车辆路径问题。首先针对单一车型情况下带时间窗的车辆路径问题构建数学模型。混合进化算法中包含了基于快速采样策略的全局搜索策略以及基于路线序列差异的局部搜索策略。基于快速采样策略的全局搜索策略可以实现算法快速收敛至Pareto前沿面,基于路线序列差异的局部搜索策略用于进一步提升算法的搜索能力。在Solomon基准问题上进行了一系列的实验结果表明所提出的方法与策略在收敛性上有更好的表现,同时拥有充足的分布性能。其次,针对多车型情况下带时间窗车辆路径问题完善了数学模型,采用了双染色体的形式表达个体,设计了合理的交叉算子和变异算子,用于双染色体的基因重组。将混合算法拆分为多个阶段,调整了基于路线序列差异局部搜索的使用时机。实验结果表明,在算法的不同阶段使用合适的优化策略不仅可以节省算法的计算时间,更能进一步提高算法的求解能力,对比起NSGA-II,SPEA2以及MOEA/D等优化算法,所提出的方法在求解多车型带时间窗的车辆路径问题上更加优秀。本研究所提出的混合进化算法,融合了基于快速采样策略的全局搜索策略以及基于问题相关的局部搜索策略,能够很好地平衡算法的搜索和探索能力,同时将算法拆分为多个不同阶段,精准得使用优化策略能够进一步提高算法的效力和效率,本研究所提出的方法与策略能够较好地处理多车型带时间窗的车辆路径问题,同时对于混合进化算法解决其他复杂多目标优化问题提供了有益的借鉴和参考。