论文部分内容阅读
车辆路径问题(Vehicle Routing Problems，简称VRP)是近几十年来运筹学、应用数学、网络分析、图论、计算机应用及交通运输等学科研究的一个热点问题，是企业供应链管理中的一个重要环节.带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows，简称VRPTW)，是VRP问题的一个重要扩展，其目标是在不违背约束条件的前提下，以最小的成本价格，寻求一个最优的车辆配置方案.
禁忌搜索(Tabu Search，简称TS)算法是一种新的智能优化算法，为求解VRPTW问题提供了新的工具，具有很强的爬山能力，广泛应用于求解大规模组合优化问题.
本文在前人成果及前期工作的基础上，提出了新的混合禁忌搜索算法，并把其应用于VRPTW，取得了较好的结果和收敛速度.主要研究工作如下：
(1)在系统研究带时间窗车辆路径问题的基础上，提出了一种更为合理的VRPTW问题的数学模型.
(2)通过对已有禁忌搜索算法的分析，提出了一种新的禁忌搜索算法，并结合2-opt优化算法，形成混合算法，为更有效的求解VRPTW问题提出了一种新的途径.特别地将Rego求解VRP的弹出链思想推广到了VRPTW问题，提出了新的路径改进策略.
(3)通过对混合禁忌搜索算法原理的分析，讨论了其收敛性和时间复杂度.
(4)用面向对象的思想对构造的混合算法加以实现，且以一系列Solomon基准实例对算法进行测试，计算结果与相关算法的计算结果进行比较，结果表明，混合算法在求解VRPTW上是有效的和可行的.