NP问题是自然界中普遍存在的一类问题,由于其目标解的搜索空间随着规模的增加而呈现指数级的增长,所以该问题已经成为当今计算机科学,人工智能等领域的瓶颈问题和热点问题。目前,传统的基于最优解的精确优化方法在求解大规模的NP完全上表现的无能为力,而与在可接受的条件限制(如时间)内找到问题的满意解的启发式算法成为解决该问题的一个有力工具,从而也成为科学界应用界研究的热点。蚁群优化算法作为一种群智能启发式算法,凭借其自身的正向反馈(能保证快速找到好的解),蚂蚁间的耦合性小(适合分布式计算并可以逃避过早的收敛)和基于贪婪的启发式搜索(帮助算法在早期阶段找到可行解)等特性,在求解NP问题上得到了广泛的应用,并且有较为完善的理论基础。另一方面,本文所重点研究的车辆路径问题是一类典型的NP问题。实际生活中的很多问题都可以被抽象为车辆路径问题,如快递发货问题,飞机、铁路列车、水运船舶及公共汽车的调度问题,物流配送问题,工作排班等问题。因此,研究车辆路径问题的启发式算法有着极为重要的理论意义和现实价值。经过几十年的发展,该问题也取得了喜人的成果,在理论和应用上都表现了很大的可行性。本课题研究了混合启发式蚁群优化算法(结合改进的蚁群优化算法结合邻域搜索算法)及其在车辆路径问题中的应用,结合启发式算法善于发现可能存在最优解的区域和局部搜索算法善于在某个区域中找到更好的解的各自优势,提出了混合启发式算法,解决了带容量约束的车辆路径问题和在学术界提出不久的双层车辆路径问题,并且在公开测试样例表现出了一定的优越性,说明了算法的有效性。本课题主要取得的成果主要有以下几个方面：第一,在原有基础蚁群优化算法(ACO)基础上,对该元启发式算法根据车辆路径问题的特点进行了改进,并在性能和效率上取得更好的结果；第二,在领域下降搜索算法的基础上提出了一种局部搜索能力更强的多领域下降搜索法；第三,在大规模的双层路径问题中,提出了一种效率更高的局部搜索算法：基于阈值的领域搜索；第四,结合贪婪算法,蚁群优化算法和各种领域搜索算法,本文提出了一种基于阈值的混合启发式算法,用于求解双层车辆路径问题。利用传统启发式算法的快速性,蚁群优化算法的搜索多样性以及局部搜索算法较强的局部寻优能力,提高求解质量,加速算法的收敛性。总的来说,本论文对蚁群优化算法和车辆路径问题,特别是运量限制的车辆路径问题和双层路径问题进行了实验性的研究,且已实际的车辆路径问题相结合,取得了实际应用价值。