Page 134 - 2025年第56卷第8期

3 基于高约束单亲遗传算法（HC-PGA）的调度优化

高约束单亲遗传算法（HC-PGA）模型分为
需求层、数据层、分析层以及输出层。常规遗
传算法提供了混凝土坝施工水平运输方案优化
的底层逻辑，进一步根据本研究特点确定以其
引申改进的单亲遗传算法作为主要寻优手段，
然后针对单亲遗传算法在本研究应用中的缺点
做出优化而确定本研究最终的模型构建。具体
构建思路见图 1。
3.1 初始染色体生成 传统 TSP 问题在生成初
始解时一般采用对城市随机排列的方式，其中
排列过程除保证首尾城市相同外并无其他限制
要求 ［24］ 。作为算法构建基础，初始调度方案的
合理生成直接影响后续寻优过程的科学性与先
进性。本研究在生成初始调度方案时有着以下
特点：①节点间体现出严谨的逻辑关系。②各
节点在一条染色体上不只出现一次，而出现次
图 1 高约束单亲遗传算法构建思路
数与实际施工强度和运输车工作强度有关。③多
辆车协同作业，节点分配时需增加边界条件。
由此可知本研究的染色体生成以及后续遗传算子的生成都有着高程度复杂性和显著约束性，这也
是提出高约束单亲遗传算法的原因所在。
用数字表示节点，如 000122333444 为结合实际施工场景后得出的完整节点序列，其中 0 表示停车
场节点。对此序列进行排列时须遵循工程紧前紧后关系，而且由于运输车辆应符合从停车点位出发最
终回到停车点位的实际情况，生成的染色体首尾且必须为 0。因此，由最终得出的染色体 032413043240，
可将其表示为 0324130/043240，两条序列分别表示两辆运输车的调度信息。
车辆一：0→3→2→4→1→3→0
车辆二：0→4→3→2→4→0
具体应用时可根据实际情况调整运输车的数量，最大限度保证整个运输调度的科学性、合理性与
先进性。然而，在面对动态调度问题时，任务的再分配需要基于当前运输车辆的实时位置进行调整。
这要求染色体编码必须以车辆的当前位置作为起点，而终点依然是一个停车点位（0）。这种动态编码
策略允许算法灵活地适应环境变化和任务调整，从而更有效地优化运输路径和降低调度成本。
3.2 哈密顿回路筛选策略 哈密顿回路 ［25］ 是由爱尔兰数学家 Hamilton 提出的，以一个正十二面体的
20 个顶点代表 20 个城市，要求从一个城市出发，沿着棱恰好经过每个城市各一次，最后回到起点。
与 TSP 一样同属于 NP 问题。对于哈密顿回路问题没有特定的解法，可针对具体问题对其进行求解。
由于本研究问题的复杂性以及染色体的高约束性，引进哈密顿回路求解对单亲遗传算法的初始解
进行筛选。具体方法如下：a）每个点位都有与其对应的一个或多个紧后点位，而距离最近的紧后点位
定义为“最优紧后节点”；b）将每个初始解看作为一条哈密顿回路，随机确定除首位和末位的一节点
P，P 的紧后点位为 M；c）检查节点 P 紧后点位 M 是否为最优紧后节点 Q，如果是则不予改动，否则进
行最优搜索；d）最优搜索的具体手段为找到随机节点 P 后最近的停车点位 N ，搜索 N 后首次出现的最
1 1
优紧后节点 Q，整条哈密顿回路末尾停车点为 N ；e）若 N 后没有出现最优紧后节点 Q，则不予该路径
2 1
进行改动，反之将片段 MN 与片段 QN 进行互换，节点 N 与 Q 之间的片段保持不变。有研究表明可通
1 2 1
— 1098 —