Page 132 - 2025年第56卷第8期

TSP 作为传统非确定性多项式难题（NP-hard），多年来各界学者已提供多种寻优方法，例如人工
群算法 ［10］ 、元启发法 ［11］ 、深度强化学习 ［12］ 等一系列工具手段。而早年由 John H. Holland 及课题团队提
［13］
出的遗传算法 （Genetic Algorithm，GA）凭借自身较强的鲁棒性、并行性、高效性、广泛适用性以及
可结合性等多种优点在 TSP 问题上有着较为不错的寻优效果。但传统遗传算法在解决复杂条件的问题
时有着易陷入局部最优以及早熟的现象，对此国内外学者进行了长时间的研究并给出了多种解决办
法。其中李茂军等 ［14］ 在 1998 年提出单亲遗传算法（Partheno-Genetic Algorithm，PGA），主张不使用传
统遗传算法常用的交叉算子，而是通过基因换位算子隐含交叉算子的功能来实现进化操作。PGA 有着
操作简单、不易陷入早熟收敛等特点，除此之外还可解决传统交叉算子无法适用于特定高约束的路径
规划问题。
路径规划与任务分配一直是国内外学者持续关注和探讨的问题。杨杰等 ［15］ 根据混凝土配送行为特
征，建立以多个施工工地中断浇筑和等待浇筑的运输车辆协同配送为目标的数学模型，运用改进的双
层算子编码形式遗传算法对模型进行求解，有效降低了车辆和施工工地的等待时间，提高了施工效
率。Chen 等 ［16］ 提出一种电动预拌混凝土车的作业调度优化方法，开发了改进的基于模型的强化学习
方法，称为并行掩码衰减蒙特卡罗树搜索，以有效地解决电动预拌混凝土车调度问题，实验表明该
算法在最小化成本或延迟方面优于其他基准测试。Xu 等 ［17］ 基于数字孪生，对挖沟机器人的作业路径
进行了重新规划，为油茶林挖沟作业的智能化提供了新的思路。Karthik 等 ［18］ 针对无人机的覆盖路径
规划问题，提出了一种基于改进绿蟒蛇优化算法（Improved Green Anaconda Optimization，IGAO）的覆
盖路径规划机制，其在偏差比、任务完成时间和执行时间等方面较优。Liu 等 ［19］ 提出了一种集成编
码方法并与基于关键路径邻域搜索策略的改进遗传算法相结合，之后实验证明了其改进方法的有效
性。Tian 等 ［20］ 以建立混合整数线性规划模型为基础，提出了一种具有可变邻域搜索的遗传算法，在
4 组不同尺度的实例上进行了数值实验后，证明了其在分布式装配作业车间调度寻优问题上优越的
稳定性。Sun 等 ［21］ 使用改进单亲遗传算法，针对无人水面舰艇工作过程获得通信区域内的最优路径点
进行改进，实验结果表明该方法能够有效解决多艘无人艇在有障碍海域的路径规划问题。崔博等 ［22］
通过建立基于元胞自动机的填筑仓面信息模型，以及基于强化学习的碾压作业路径规划模型，解决
了碾压机数量变化的路径分配问题，并耦合上述两种模型，实现了堆石坝填筑仓面碾压作业动态路
径规划。
本文研究内容为多辆运输车协同合作，在任务量一定的条件下将常态混凝土、骨料以及施工渣料
运输到指定位置的调度优化研究，其区别传统调度问题的要点在于，关键点位排序需要遵循严格的实
际施工逻辑，而使用常规遗传算法时无法有效解决本文所涉及的高约束遗传算子问题。为此，本文在
前人研究的基础上提出适应高约束遗传算子的模型方案及优化算法。首先，构建混凝土坝施工水平运
输多目标优化调度数学模型；其次，以单亲遗传算法（PGA）为主体优化手段，其中交叉过程针对本文
研究内容采取特殊的单亲自交叉基因重组。通过引入哈密顿回路来筛选初始路径，使用 Logistic 混沌
映射来确认算法过程中的变异区间，从而解决因特殊问题而导致的主体算法提前收敛和陷入局部最优

的问题。在单亲遗传算法的基础上结合本文研究对象特点提出高约束单亲遗传算法（High Constraint
Partheno-Genetic Algorithm，HC-PGA）并计算出最佳调度方案。最后，依托我国西南某航电枢纽工程
混凝土闸坝施工水平运输开展工程应用研究，从成本与效率两方面与常规遗传算法调度方案及传统人
工调度手段进行对比分析。

2 成本-效率多目标调度优化模型

2.1 数学模型 针对运输车辆所在场景提取运输路径时，应符合以下规则：①根据工程布置图提取真
实路径；②所提取路径要保证全面性，即包含所有必要路径；③每条被提取路径的距离要根据布置图
注释进行记录以保证初始数据真实性，但其之间的路径以及数量以实际研究对象为准。

— 1096 —