随着现代生活中的科技和工业的进步,组合优化问题作为一组经典又实用的问题越发被广泛关注。旅行商问题(Traveling Salesman Problem,TSP)是组合优化中一个经典的问题,也是一个NP-Hard问题,在计算机、数学和运筹学等领域中是热点研究领域,且TSP具有极高的理论和应用价值。在问题规模随着城市规模扩大时,时间和空间复杂度会呈现出指数级的增长,大多数算法都不能够求出一个令人满意的解,所以成为在此专业领域中被研究者们特重视的问题之一。TSP因时代的发展,类似技术的不断进步,如人工智能、计算机技术等,为该问题带来越拉越多的解决方法。启发式算法用于求解TSP时,运行时间较短,但普遍结果不够精确。如今在求解TSP时,多用混合算法,各取其长,提高求解TSP的效率。在本文中,通过对多种求解TSP的算法进行分析后,着重研究了贪婪随机自适应搜索算法(Greedy Randomized Adaptive Search Procedures,GRASP),并将其与其他算法相结合为混合算法。GRASP算法是一个经常用于求解组合优化问题的算法,它是一个二次迭代的过程,该算法在求解TSP时,若所得解陷入了局部最优的情况,是由于其构造阶段的贪婪随机性。针对该算法在求解TSP时对其进行改进,根据其二次迭代的特性,在第一阶段构造通过控制候选表的长度,构造一个可行的贪婪随机初始解。在第二阶段引入群智能算法灰狼优化算法(GreyWolf Optimizer,GWO),对其进行重新编码,能够用于求解TSP这类离散型问题。然而原始的GWO的初始解是随机生成的,它的好坏极大程度上影响了整体的求解,故将构造阶段所得解作为GWO的初始解,利用GWO较强的全局搜索特性,对其进行逼近搜索,从而避免陷入局部最优的情况。对TSPLIB中的多个数据运用改进的算法对其进行大规模的算法性能实验测试,分别对多个参数进行多次调整,多方面对结果进行分析。混合算法在第二阶段搜索后能改善初始解,并且几乎达到全局最优,验证了该算法解的质量有大幅度的提升。大多数实例能够求得最优解,规模较大的实例所求解误差较小,较其他算法在规模较大的实例下仍然能对其进行求解。最后本文将生活中常见的物流配送路径规划问题作为应用场景,该问题可以抽象为TSP的拓展问题,多旅行商问题。物流配送要求多位司机以尽短的路程快速完成配送,首先用K-means对各车辆配送的站点进行划分,再通过使用改进的算法优化配送路径。验证该算法能够运用在实际问题中,提高司机的配送效率,简短配送路程,节省所需时间,从而保证及时完成任务,减少对公司造成的损失。