论文部分内容阅读
大多数组合优化类问题均属于NP-Hard问题，用传统算法进行求解所需的计算时间会随问题规模的增大而成指数级的增长。因此，该类问题的求解几乎用现代启发式方法。万有引力算法GSA是在2009年提出的一种对物理学中的万有引力定律进行模拟的优化算法，其通过种群中各个体之间存在的万有引力相互作用，引导搜索，具有全局搜索、操作简单、隐并行性等特点。车辆路径问题是组合优化和运筹学领域研究的热点问题之一，主要研究如何设计合理的车辆运输路线以降低运输成本，经过半个多世纪发展，其已广泛存在于最短路、网络布局及工业管理等领域。随着电子商务的发展，车辆路径问题还在大型商场、配送中心及快递中有着广泛的应用。因此对车辆路径问题的深入研究有重要的应用价值。 本文研究内容包括GSA算法搜索能力的验证、算法的改进以及算法在车辆路径问题中的应用。主要工作如下： 1.提出了一种融合粒子群算法的混合万有引力算法（HGSA），通过三类经典测试函数对HGSA进行测试，并与万有引力算法GSA进行对比分析，验证了HGSA的可行性与有效性。 2.首先建立了多时间窗车辆路径优化问题的双层数学规划模型。其次为提高GSA求解速度和最优解的质量，提出了一种与小生境技术和遗传算法交叉算子融合的改进万有引力算法（IGSA）。最后通过数值实验，验证了所设计模型和IGSA的有效性和实用性。