论文部分内容阅读
车辆路径问题作为车辆调度的重要环节,是目前优化领域的难点问题之一。经过国内外学者的不断研究已取得了丰富的研究成果和经验,并广泛运用于在工业生产、计算机科学等领域。根据车辆路径问题的问题特性和数学模型,怎样用科学算法在合理的时间内搜索到问题的最优路径依然是最优化问题的研究重点,突出了重要的理论价值和现实意义。由于精确算法在求解最优化问题时,时间会根据问题规模的大小逐级变长的重大缺陷,众多学者提出了人工智能算法,这为解决车辆路径问题提供了良好的选择空间和无限发散思维。虽然蚁群算法和禁忌搜索算法在求解车辆路径优化问题中的应用兴起已久,但其潜力还有待进一步挖掘,以下是本文的主要研究内容:(1)对基本禁忌搜索算法精度和效率差的问题提出了改进策略。考虑到基本禁忌搜索算法精度差,本文提出了两点改良:优化算法结构和丰富邻域搜索函数。改进算法在判断该候选解是否优于公告板中最优值这一过程做出调整。当然,改进算法是在保留了基本TS算法思想的基础上做出了修改。改进后的禁忌搜索算法使用多种邻域操作算子,极大地丰富了邻域函数。其次,针对禁忌搜索算法效率差这一劣势,本文合理设计禁忌表结构和选择禁忌对象。对比Solomon标准数据库中的算例数据,改进后的禁忌搜索算法与基本算法不论是在效率还是精度上都有明显的改善,说明禁忌搜索算法有很好的理论研究价值和意义;与其他算法对比的结果也显示了改进后的禁忌搜索算法也有较强的优势。(2)在众多智能优化算法中,蚁群算法拥有良好的全局搜索性能,但是局部搜索能力又很弱且整体搜索效率低,纵观其他算法,发现禁忌搜索算法刚好可以弥补蚁群算法这一缺点。然而禁忌搜索算法对初解有较强的敏感度,好的初始解能使算法快速收敛到最优解。因此有必要设法提出一种混合智能优化算法,使其相辅相成,实现更好的求解结果。蚁群算法研究进程已久,不管是理论研究还是实际应用上都取得了重大突破。在混合算法中蚁群算法使用自适应的期望启发因子,能够使信息素合理的迭代。此外,为了降低禁忌搜索对初始解的依耐性,本文先使用蚁群算法迭代出具有一定差异度的若干较优解,作为改进禁忌搜索算法的初始解,并保留信息素的信息来指导禁忌搜索算法快速迭代。混合算法有效利用了禁忌搜索算法较强的局部搜索能力和蚁群算法并行的全局搜索能力,力求在避免局部收敛到最优值和算法的收敛性能上有较大改善。对比单一蚁群算法和禁忌搜索算法以及其他人工智能算法,混合后算法在精度上有了提升,说明禁忌搜索算法和蚁群算法是有竞争力的;而且与标准数据库的已知最优解的差距缩小,说明混合算法在求解车辆路径问题上是有优势的。