论文部分内容阅读
车辆路径问题(Vehicle Routing Problem,VRP)是组合优化问题领域非常具有挑战性的问题之一,是解决物流配送等实际的路径优化应用中常见的问题。本文研究的是多目标带时间窗的车辆路径问题(Multi-objective Vehicle Routing Problem with Time Window,多目标VRPTW),以车辆数最少和车辆行驶路程最短为目标,求解出一个Pareto最优解以供决策者根据解集自行做出决策支持。求解VRP及其相关变体问题通常会选择不同的算法,而多目标VRPTW被证实为NP-Hard问题,当问题规模比较大时,智能优化算法将是解决这类问题的不二之选。大部分智能优化算法本身具有较强的全局搜索能力,很多相关算法现已被用于解决VRP及其变体问题。本文研究的是解决多目标VRPTW的和声搜索算法(Harmony Search Algorithm,HSA)的计算性能,主要做了以下工作:(1)对于求解该类型的组合优化问题,本文首先选择的是使用改进的多目标和声搜索算法(Multi-Objective Improved Harmony Search Algorithm,MOIHSA)。MOIHSA具有很强的多目标寻优的特性,很适用于求解多目标VRPTW。在算法中,首先设计好一个多目标和声记忆库(Multi-objective Harmony Memory,MOHM)的结构,用于保存一组寻优过程中不断进化的和声。其次,对原始HS算法中新的和声生成过程做了改进,通过引入和声模板概念以及多重邻域搜索的方式从HM内或者和声搜索范围内进行音调的选取,并且通过动态和声带宽对选自HM中的音调进行微调扰动。最后,对于和声记忆库保留概率(Harmony Memory Considering Rate,HMCR)以及微调扰动概率(Pitch Adjusting Rate,PAR)等关键参数,使用参数的动态调优方式,根据算法执行过程的寻优特点进行动态干扰算法寻优的深度和广度。通过实验仿真结果可以看出,使用MOIHSA求解多目标VRPTW是可行的、有效的。(2)根据上述实验结果,能够看出MOIHSA存在一些不足之处,比如很大程度地依赖初始解,表现为算法多次搜索结果差异比较大,另外算法的前期寻优能力不强、产生新解分量随机性太大。针对这些缺点,本文提出一种混合了遗传算法(GA)的改进多目标HS算法(GA-MOIHSA)来求解多目标VRPTW。在该混合智能算法中,首先利用GA的高度并发特性以及算法迭代初期强大的改善解的优点,生成HM中和声的候选集。也就是通过GA不断地进行选择、交叉和变异等操作,迭代一定的次数后,从种群中选择最好的一组解集作为HM中的和声候选集即MOIHSA的初始解。而GA也有自己的不足之处,比如对种群的多样性要求高,后期收敛速度比较慢,通过与IHSA进行混合,可以互相取长补短。根据实验仿真结果以及对比实验结果可以看出,GA-MOIHSA能够很好地弥补MOIHSA的缺点,提高了MOIHSA的性能。