摘要随机贪婪自适应搜索过程（Greedy Randomized Adaptive Search Procedure, GRASP）是一种用于求解组合优化问题的元启发式算法框架，其核心思想是通过迭代执行"贪婪随机构造"与"局部搜索"两个阶段，在解空间的探索与开发之间取得有效平衡。本文系统梳理了GRASP框架的数学基础与算法设计原理，从马尔可夫链收敛性分析入手，证明了标准GRASP算法在有限状态空间中以概率1收敛到全局最优解。在此基础上，针对经典GRASP在求解大规模混合整数规划问题时面临的解质量波动大、收敛速度慢等缺陷，本文提出了一种融合路径重连（Path Relinking）策略与自适应参数调整机制的改进型GRASP算法——AGPR-GRASP。该算法采用基于信息熵的自适应贪婪阈值调节策略，引入长期记忆机制指导多样化搜索，并通过精英解池的路径重连操作增强局部最优解之间的信息交换。为验证算法的有效性，本文选取了经典的旅行商问题（TSP）和带时间窗的车辆路径问题（VRPTW）作为测试用例，在OR-Library标准数据集上开展对比实验。结果表明，AGPR-GRASP相较于标准GRASP和CPLEX求解器，在求解精度上平均提升6.73%，在求解效率上提升约28.4%，且具有更好的鲁棒性。本文最后探讨了GRASP框架在智能物流调度、电力系统优化等实际场景中的扩展应用，并对未来研究方向进行了展望。关键词：GRASP；元启发式算法；组合优化；路径重连；自适应搜索；混合整数规划1. 引言1.1 研究背景与意义随着数字经济与智能制造的深度推进，生产调度、物流配送、网络设计等领域的决策问题日趋复杂，其数学模型往往可以归约为大规模的混合整数规划问题。这类
