最小延时问题是旅行商问题的变体,目的是求解路线中所有客户的累计等待时间,最小延时问题相比于旅行商问题更难以解决。目前的求解方法,只能在客户数量较小时具有较高的性能,当客户数量变大时算法很难兼顾运行时间与求解质量。基于上述问题,对如何在较短时间内获得大数据量最小延时问题的优质解这一问题进行以下研究。1.对于大数据量的最小延时问题,目前主要使用元启发式算法求解,在此基础上提出一种混合元启发式算法。将遗传算法与变邻域搜索算法细粒度结合,在遗传算法的框架内实现变邻域搜索。当算法陷入局部最优解时,可以在遗传算法的交叉过程中改变子代染色体的邻域结构;并对遗传算法的变异过程进行改进,子代染色体可以在增加多样性的同时有较大概率发生优化。然后对算法进行数据预处理,通过为每个染色体构建基因节点索引列表,降低生成子代染色体的时间复杂度。2.为了进一步加快算法运行,使用GPU实现算法的并行化,并根据GPU运行特点对并行算法做出改进。将并行算法的交叉与变异过程以线程束为单位分开同步运行,每个线程具有固定的染色体选取位置与生成位置。算法整体上以线程块为单位并行运行,以保证并行算法避免产生线程发散问题并且减少线程通信开销,同时实现染色体的动态选择。此外将算法与扰动机制相结合,增强并行算法全局搜索能力,并使用多重改进方式生成最终解。通过上述方法进一步提升算法性能。为验证算法的实际运行情况,对算法进行对比实验,测试数据的节点个数从51到10150不等。实验结果表明,提出的算法在CPU环境中,相对于其它元启发式算法,可以在较短的时间内取得优质解;在CPU-GPU环境中,当数据规模较大时,并行算法可以取得明显的加速效果,数据规模越大,加速效果越明显。并且该并行算法相较于实验中其它的并行算法,具有更好的性能。因此,对于大数据量的最小延时问题,并行混合元启发式算法可以在相对较短的时间内获得优质解。