随着互联网经济和贸易的发展,物流业的规模与日俱增,物流配送对经济活动的影响越来越显著。车辆路径优化问题(VRP)是配送优化的关键问题。对配送车辆路线进行优化能够有效降低配送成本,减少配送时间,提升用户满意度,因此研究该问题具有重要的现实意义。车辆路径问题是一类NP完全问题,传统的精确算法难以在合理时间内进行求解,用启发式算法求解近似解是人们研究该问题的一个重要方向。蚁群算法(ACO)是模拟自然界中蚁群觅食行为而提出的一种启发式算法。该算法在求解车辆路径问题等组合优化问题时具有不错的效果,同时蚁群算法具有本质并行性,易于和其他算法结合等优点。但蚁群算法存在容易陷入局部最优等缺陷。本文主要研究了蚁群算法在车辆路径优化问题中的应用,并针对该算法存在的缺陷提出了一种新的混合蚁群算法。算法的执行效率也是评估一个算法性能的重要指标。为了提高蚁群算法的执行效率,使之能够在更短时间内求解问题,本文提出了两种方法。一种是将车辆路径问题分解成几个子问题,每个子问题采用多线程方式单独求解;另一种是根据蚁群算法的本质并行性,利用OpenCL的异构并行框架,实现运行于GPU的并行蚁群算法。文本主要的工作和研究成果如下:1.提出新的混合蚁群算法(SACO)。传统蚁群算法收敛速度快,能在较短时间内获得不错的可行解,但容易陷入局部最优。而模拟退火算法(SA)能够通过邻域搜索在可行解附近持续搜索更优解,但是解的质量和收敛速度很依赖初始可行解。SACO整合了蚁群算法和模拟退火算法的优点。该算法首先采用蚁群算法搜索可行解,当蚁群算法陷入局部最优解后,启动模拟退火算法搜索更优解,并将蚁群算法获得的解作为模拟退火算法初始可行解。为了进一步避免蚁群算法因信息素停滞而陷入局部最优的情况,引入了新的信息素扰动策略。2.为了算法提高执行效率,提出了分解的混合蚁群算法(DSACO)。首先利用SACO算法用少量的迭代求解整个问题并获得至今最优解;然后根据至今最优解将整个问题拆分成几个规模较小子问题,每个子问题再分别用SACO求解;再根据子问题的获得更优解更新整体问题的当前最优解,并重复上述迭代过程。由于每个子问题是独立的,因此DSACO算法采用多线程方式并发求解每个子问题。3.为了充分利用蚁群算法的本质并行性,提出了基于OpenCL的并行蚁群算法(OCL-ACO)。该算法将蚁群算法的主要计算部分设计成并行执行的OpenCL内核,宿主主机只负责管理和调度内核。OCL-ACO对蚁群算法解的构建、信息素更新等过程采用了数据并行化的实现方式,极大地提高了算法并行性。