基于填挖匹配与智能优化算法的土石方调配优化

文思巧巧, 于 静, 郭嘉伟

(1.长沙理工大学 交通运输工程学院，湖南 长沙 410014； 2.公路养护技术国家工程研究中心，湖南 长沙 410014)

0 引言

土石方调配通常包括不同区域的挖掘、装载、搬运、卸载和压实作业，普遍存在于道路、土石坝、大型场平等工程建设项目中[1-2]，是建筑工程的基本组成部分。土石方调配可分为填挖匹配和运输路径规划两个阶段，旨在通过合理优化填挖匹配方案与运输路径规划方案，提高工程效率、降低施工成本。在实际土石方调运过程中需要综合考虑运输路径、运输工具选择、调运时间安排等多个因素，而传统的土石方调配设计常基于经验和直觉，缺乏科学分析和优化方法，易导致不必要的资源浪费与施工周期延长[3-4]。

填挖匹配问题常采用线性规划模型、自动生成模型[5-6]、多目标决策模型[7]等确定其填挖匹配方案。如以工程总调配费用最小为目标[8]，以多个土石方填挖区间的物料和进度协调关系为约束规则[9]，建立填挖匹配问题的可行性规划模型[10]。上述研究虽然能很快获取填挖匹配方案，但施工机械的运输路径与施工顺序方案无法确定。

由于土石方工程中土石方调运量往往较大[11]，且土石方材料从一个地点运输到另一个地点一般费用较高[12-15]，为了降低施工成本、提高土石方施工的智能化调度水平，学者对土石方运输路径规划进行了研究[16-20]。土石方运输路径规划问题实质上是车辆路径问题的一个扩展应用，属于NP-Hard问题[3]，即无法在多项式时间内获取问题解决方案。当任务规模很大时，传统的精确算法无法在有限时间内获取调度方案，需采取有效的启发式算法进行求解。土石方运输路径规划问题通常是一个连续且可重复的迭代优化过程，因此可通过有效的求解方法来优化土石方调配路径，如最短路径Floyd[21]、Dijkstra改进算法[22]、遗传算法[23]、粒子群算法[24]等。

以土石方调配中的填挖匹配问题和运输路径规划问题为研究对象，分别对土石方调配的两阶段问题进行模型构建与算法求解，获得了最优填挖匹配方案与机械运输路径方案。

1 土石方两阶段调配模型

本文的土石方两阶段调配模型包括填挖匹配模型与运输路径规划模型。填挖匹配模型是以填挖对(土石方等量划分后，可进行土石方调运的一个填方区与对应的挖方区)间的运输成本、机械人工费用为最小成本为目标，匹配填挖对，获取最小施工费用下的填挖匹配方案。由于填挖匹配方案只明确了土石方的调运数量与调运关系，未对项目的具体施工顺序及机械运输路径进行统一规划，本文在填挖匹配方案基础上，同时求解了最小机械转运距离下的机械运输路径方案。

1.1 填挖匹配模型

设某土石方调配项目有m个挖方区，对应的挖方量集合记为E={E1,E2,…,Em},Ei表示第i个挖方区的挖方量;设有n个填方区,对应的填方量集合记为F={F1,F2,…,Fn},Fj表示第j个填方区的填方量。记C=(Cij)nm为挖方区与填方区间的施工费用矩阵,Cij表示第i个挖方区与第j个填方区间的总施工费用,主要由填挖对之间人工与机械费用确定。记Xij为第i个挖方区的土方运输到第j个填方区的决策变量,其中,Xij=1表示第i个挖方区的土方运输到第j个填方区,Xij=0表示第i个挖方区的土方没有运输到第j个填方区。

根据上述土石方填挖匹配问题的数学描述，本阶段的数学模型为：

(1)

(2)

(3)

(4)

式 (1)为土石方调配的目标函数，即以最小施工成本为目标对土石方填挖进行匹配；式 (2)为填挖区的填挖平衡条件，即挖方区总量与填方区总量相同；式 (3)为挖方区约束条件，1个挖方区最多被服务1次；式 (4)为填方区约束条件，表示每个填方区最多被服务1次。式(1)～(4)为土石方填挖匹配问题的线性规划模型。

1.2 土石方运输路径规划算法模型

对于土石方运输路径规划问题，为了尽可能访问到所有填挖对，要求路径规划模型需有较强的随机搜索能力。因此，结合土石方调运问题特点，本文选用随机搜索能力较强的禁忌搜索(Tabu Search,TS)算法与模拟退火优化(Simulated Annealing, SA)算法模型求解土石方调运的运输路径规划问题。

1.2.1模拟退火算法

SA算法是一种模拟物理退火的过程而设计的优化算法，即模拟物体先加热后冷却的退火过程。SA基于蒙特卡洛迭代求解策略，模拟热能在下降并趋于稳定的过程中允许跳出局部最优解的机制，从而可获取全局较优的可行解。

SA算法首先选择一个可行的填挖区路径调度方案作为初始解，并设置算法的初始温度与终止温度，在SA实例中初始温度设为T0=1 000 ℃，终止温度为Tf=10-3℃；其次，基于邻域交换规则产生新解，并依据Metropolis接受准则确定当前解；最后，判定热平衡条件，继续降温寻优，直至输出当前最优解。

SA算法土石方运输路径规划算法流程如图1所示。

1.2.2禁忌搜索算法

TS算法是一种元启发式随机搜索算法，其特点是采用了一种灵活的“记忆”技术--禁忌表。禁忌表用于记录已经访问过的解，防止重复搜索，以此来避免陷入局部最优解。

TS算法在填挖区的路径调度方案中可以高效安排好车辆的运输路径，模仿人类的“记忆”功能，使用禁忌表记录已搜索局部最优解的历史信息，赦免禁忌区域中的优良状态，不断迭代更新从而获得全局最优解。

TS算法土石方运输路径规划算法流程如图2所示。

图2 禁忌搜索算法流程

2 实例求解

以某高速公路路段的土石方调配问题为例进行土石方调运方案设计。本项目土石填方区调运量为675599m3，考虑土石方挖填平衡，需要借土超过4万m3。本项目土石方的借方区与挖方区位置如图3所示。以15000m3作为1个填挖对等量划分标准，将原有挖、填方区划分为等土方量的填、挖方子集。

图3 填挖方区域分布

2.1 土石方调配数据准备

1)运距计算。填方与挖方区域之间的距离是主干道运距与便道运距之和。

2)自卸车数量。自卸汽车数量根据挖-填方之间的填挖效率决定。即在施工期间以挖掘机不间断施工作为自卸车数量优化选择的标准，选择满足条件下最小数量的自卸车。

3)施工费用计算。土石方调配成本主要包括施工期间内机械费用与人工费用，其中施工机械主要包括挖掘机、压路机、自卸汽车。根据2018公路工程预算定额，相关的施工机械费用、施工机械、人员安排如表1所示。

表1 机械费用、施工机械安排、人员安排机械名称单价(元·台班-1)数量/台(人)挖掘机1 195.011自卸汽车841.461振动压路机903.681推土机2 355.271人工105.495 注:人工包含观察员1名,挖掘机、自卸汽车、压路机、推土机驾驶员各1名。

2.2 土石方两阶段优化调配算法求解

为验证土石方两阶段优化调配算法的可行性与有效性，采用Matlab软件对实例进行算法求解。经过多次实验与分析统计，确定了SA算法的相关参数：初始温度T0=1 000 ℃，终止温度Tend=10-3℃，各温度层的链长L=125次，降温率q=0.98；禁忌搜索算法的禁忌长度为45次。为避免实验结果赘述，只列出在迭代步数500下，SA算法、TS算法当前最优解的变化与算法求解效率情况。

图4为SA算法与TS算法在迭代次数为500时，土石方调运冗余路径当前最优解的变化情况，2种求解算法都可在迭代200次内达到当前的最优解。

图4 SA的当前最优解变化情况

为了验证迭代次数对SA、TS算法的影响，选取迭代次数分别为200、400、500、600、700、800次时进行实验验证。图5为不同迭代次数下SA算法与TS的实验结果。整体上，SA算法与TS算法都可以实现5 s内获取当前最优解，2种算法的求解效率都很高。相较于TS算法，SA算法的求解效率更高，但其求解稳定性稍差一些。TS算法的求解效率虽稍逊于SA算法，但TS算法可在迭代次数200次条件下100%获取当前最优解，SA算法在迭代次数200次条件下获取当前最优解的准确率约为95%。

图5 不同迭代次数下的算法求解时间

2.3 填挖匹配方案

以最小土石方调运成本为目标，在确定施工机械与人员安排以及实际测算填挖对间运距的情况下，基于填挖匹配模型与2种求解算法，采用Matlab编程获取的最优填挖匹配方案如表2所示。

表2 最优填挖匹配方案1.5×104 m3填方挖方1～34567～91011-1213141516171819202122～23242526272829303132333435～45总数1112～12111113111411151116～172218～20332111221123112411251126～2833

续表2 最优填挖匹配方案1.5×104 m3填方挖方291130111～34567～91011～1213141516171819202122～23242526272829303132333435～45总数311132113311341135113611371138113911401141114211431144～4522总数311131211111111121111111111111 注: 1个填挖对的土方量为15 000 m3,表中数值为填挖对的个数。

2.4 土石方调运方案

为了对项目具体施工顺序及机械运输路径进行统一规划，基于土石方最优填挖匹配方案与土石方路径规划模型，以机械转运最短运距为目标函数，以项目实际的机械转运规则为约束，采用Matlab对SA算法进行求解，获取土石方调运方案，包括施工机械转运方案与自卸车路径转运方案。

SA算法求解的自卸汽车转运方案如式(5)所示。其中，Ci代表第i个挖方区，Fj代表第j个填方区。

C6→F23→C1～3→F26～28→C18→F38→C21→F40→C22～23→F44～45→C26→F30→C28→F36→C25→F33→C20→F14→C14→F35→C31→F34→C11～12→F16～17→C27→F42→C34→F31→C7～9→F18～20→C35～45→F2～12→C5→F25→C19→F43→C33→F37→C32→F32→C30→F29→C29→F41→C4→F39→C10→F1→C2～4→F21

(5)

3 结语

本文对土石方调配中填挖匹配和运输路径规划两个阶段的问题进行了模型构建与算法研发。具体在考虑运输路径、运输工具选择、调运时间安排等多个实际场景下，以填挖对间的运输成本、机械人工费用最小为优化目标，获取以最小施工费用的填挖匹配方案；对项目具体施工顺序及机械运输路径进行统一规划，以最小机械转运距离为目标，基于最优填挖匹配方案与土石方路径规划模型，采用模拟退火算法、禁忌搜索算法求解了带有施工顺序的土石方调运方案；最后，以某高速公路路段的土石方调配问题为例，对土石方两阶段调配模型与模拟退火算法进行验证。研究成果如下：

1)构建了土石方调运填挖匹配的线性规划模型与求解算法，获取了土石方调运的最优填挖匹配方案。

2)基于模拟退火算法构建了土石方运输路径规划模型。基于最小施工费用的最优填挖匹配方案，获得了最小机械转运距离下带有施工顺序的土石方调运方案。

通过实例求解，验证了模拟退火算法、禁忌搜索算法求解土石方调配问题的可行性与有效性。SA算法的求解效率更高，SA算法的求解稳定性更高。两种求解算法对包含45对填挖区的某高速公路某路段的土石方调运问题进行求解，在5 s内可获取较优的土石方调运方案。

本研究还存在以下不足：

1)由于实际土石方调运问题中填挖区往往不能根据土方量进行等量划分子填挖方，故本文中的土石方调运填挖匹配模型还需进一步考虑实际调运过程中的非线性因素。

2)本文采用的模拟退火算法稳定性方面还存在改进空间，接下来尝试研究混合式的SA-TS算法，以此提高传统SA算法的稳定性。