基于蚁群算法的高速公路混凝土搅拌站选址研究

李 伟

(中国十九冶集团有限公司，四川 成都 610031)

我国高速公路建设起步相对较晚，在国家积极财政政策的推动下，整体发展较快.从1988 年修建第一条沪嘉高速公路以来，我国高速公路建设经历了三个发展阶段①：第一个阶段为起步阶段（1988—1992 年），年均高速公路通车里程在50—250 公里之间；第二个阶段为高潮阶段（1993—1997 年），年均通车里程保持在450—1 400 公里之间；第三个阶段为大发展阶段（1998 年至今）.根据交通运输部统计，2015—2019 年，我国高速公路建设投资额基本保持逐年上升趋势，2019 年，全国高速公路建设完成投资额为11 504 亿元①参见：2020 年中国高速公路行业发展现状及发展趋势分析[EB/OL].[2021-01-19].http://www.its114.com/html/news/survey/2021_01_113966.html..

作为高速公路建设重要的临时设施之一，混凝土搅拌站是高速公路建设中工程成本控制的关键点，也是混凝土供应链中最重要的环节之一.混凝土搅拌站选址合适与否，会直接影响高速公路施工的质量和混凝土的输送效率，关系到整个高速公路建设的运输成本.

目前，对于高速公路建设中混凝土搅拌站选址问题的研究大多数是基于指标准则下的定性分析，如考虑建设成本、拆除及生态恢复成本、运输距离等因素的混凝土搅拌站优化选址遗传算法模型[1]，考虑距离、交通运输、电力供应、用地面积、自然条件环境保护等因素的混凝土搅拌站选址AHP-FUZZY 模型[2]，考虑目标市场容量、土地成本、环境污染程度、交通便利性等因素的双层规划模型和模糊综合评价模型相结合的搅拌站选址模型[3]等.本文基于定量指标，将蚁群算法引入到混凝土搅拌站选址研究中，从不同混凝土待供点位置出发，建立起基于蚁群算法的混凝土选址的数学模型，旨在降低高速公路建设的运输成本.

1 蚁群算法

蚁群算法（Ant Colony Algorithm，ACA）的基本原理来源于自然界蚂蚁觅食的最短路径原理[4].蚂蚁在寻找食物源过程中，会在其走过的路径上释放一种蚂蚁特有的分泌物（我们称之为信息素），这使得一定范围内的其他蚂蚁能够察觉到并由此影响其以后的行为.当一些路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，以致于信息素强度增大（短时间内不会减弱），蚂蚁选择这些路径的概率也会提高，这种选择过程被称为蚂蚁的自我催化行为.

从1991 年Dorigo 首次提出蚁群算法以来，各国学者对蚁群算法的研究从未停止过，这期间出现了许多改进的蚁群算法，包括蚁群聚类算法等[5].本文主要采用最基本的蚁群算法进行混凝土选址研究.为更好地对蚁群算法进行描述，这里给出蚁群算法计算不同混凝土待供点位置之间最短距离的大致步骤：

1）对不同混凝土供应点位置坐标进行数据处理；

2）计算不同混凝土待供点位置距离矩阵；

3）初始化参数；

4）迭代寻找最佳路径；

5）结果显示.

下面对蚁群算法步骤中所涉及的一些理论、公式以及实现等进行详细说明.

1.1 蚁群算法所涉及的公式

假设蚂蚁数量为m，不同混凝土待供点位置数量（以下简称待供点）为n，待供点i与待供点j之间的距离为d ij(i,j= 1,2, …,n)，t时刻待供点i与待供点j连接路径上的信息素浓度为τij(t).初始时刻，蚂蚁被放置在不同的待供点上，且各待供点间连接路径上的信息素浓度相同，不妨设τij(0)=τ0.然后蚂蚁将按照一定概率选择路线，设pi kj(t)为t时刻蚂蚁k从待供点i转移到待供点j的概率.现定义蚂蚁释放的信息素浓度如下：

其中，ui j(t)为启发函数，表示蚂蚁从待供点i转移到待供点j的期望程度，j∈ allowk，allowk(k= 1,2, …,m)为蚂蚁k的待访问待供点集合，开始时，allowk中有n- 1个元素，即包括除了蚂蚁k出发待供点的其他多个城市，随着时间推移，allowk中的元素越来越少，直到为0；α为信息素重要程度因子（也称信息素因子，其值大小代表信息素强度影响大小）；β为启发函数重要程度因子（也称启发函数因子，其值大小代表启发函数影响大小）.

在蚂蚁经过全部待供点的过程中，蚂蚁释放信息素的同时，各个待供点间连接路径上信息素的强度也在通过挥发慢慢消失.为了描述这一现象，不妨设ρ( 0 ＜ρ＜ 1)表示信息素的挥发程度.因此，当所有蚂蚁完整走完一遍所有待供点后，各个待供点间连接路径上的信息浓度为：

式中，Q为信息素常数，表示蚂蚁循环一次所释放的信息素总量，kL为第k只蚂蚁经过路径的总长度.

1.2 蚁群算法流程

用蚁群算法求解混凝土搅拌站到不同混凝土待供点之间最短距离问题的算法流程如图1 所示.具体步骤如下：

图1 蚁群算法基本流程图

1）对相关参数进行初始化，如蚁群规模、信息素因子、启发函数因子、信息素挥发因子、最大迭代次数等，对数据进行基本处理；

2）随机将蚂蚁放于不同的出发点，对每只蚂蚁计算其下一个访问的待供点，直至所有蚂蚁访问完所有待供点；

3）计算各个蚂蚁经过的路径长度kL，记录当前迭代次数中的最优解，同时对各个待供点连接路径上的信息素浓度进行更新；

4）判断是否达到最大迭代次数，如果是则返回至步骤2），否则终止程序；

5）输出结果.

2 工程算例

贵州省某高速公路全长约50 公里，包括桥梁26 座和隧道8 座，桥隧占比37%，该高速公路采用双向4 车道标准建设，设计时速达到80 公里.该高速公路起自三穗县屏树，起点和三黎高速公路顺接后与沪昆高速形成十字交叉，经三穗县至柏杨坪与思剑高速交叉后，经施秉县甘溪，于施秉县城南与余凯高速施秉连接线顺接.该高速公路全线简图见图2.

图2 某高速公路全线简图

该高速公路地处云贵高原东部斜坡地带（局部地形概貌如图3），地表森林植被茂密，地质条件复杂多样，给桥隧施工增加了一定难度，同时也给混凝土供应与混凝土搅拌站选址增加了难度.经过前期沿线初步勘察，并结合两阶段施工蓝图，测得该高速公路主要大供应量混凝土待供点的位置坐标如表1 所示.利用MATLAB 软件，得到各待供点之间最短路径线路图如图4 所示，蚁群算法收敛轨迹图如图5 所示.

表1 待供点位置坐标

图3 某高速公路局部地形概貌

图4 各待供点之间最短路径线路图

图5 蚁群算法收敛轨迹图

以下给出蚁群算法的MATLAB 实现过程，并由伪代码形式进行表达：

1）clear all；导入表1 中的原始数据；

7）逐个蚂蚁、待供点计算；

8）输出结果.

3 结果分析

根据MATLAB 计算得到了最优路径和收敛轨迹.从图4 可知，采用蚁群算法得到各待供点之间的最短距离为29 736.681 6 m，起始点为第57 待供点，终点为第59 待供点，说明从第57 待供点起至第59 待供点止，60 个待供点之间直线距离为29 736.681 6 m.从图5 可知，采用蚁群算法计算各待供点之间最短距离，迭代至88 次就完成了收敛.

由于工程上各待供点之间的运输路径不可能全部为直线，因此，须结合定性指标综合选定混凝土搅拌站位置.根据本项目两阶段施工蓝图和现场实际情况，选取自然环境、交通运输、电力供应等定性指标，考察60 个待供点的建站周边环境、交通运输便利性、电力供应充足性，同时，选取建设成本、用地面积、原材料运输距离等定量指标，考察60 个待供点建站的建设成本、用地面积、材料运输距离，得到各待供点定性与定量指标参数，如表2 所示.

表2 各待供点定性与定量指标参数

（接下表）

（接上表）

待供点编号 自然环境 交通运输 电力供应 建设成本/万 用地面积/m2 材料运输距离/m 31 优 便利 充足 211 4 000 428 32 良 便利 充足 212 4 000 578 33 良 便利 充足 210 4 000 1 147 34 良 不便利 不充足 210 4 000 704 35 良 便利 充足 210 4 000 689 36 良 便利 充足 204 4 000 681 37 差 便利 充足 203 4 000 773 38 良 便利 充足 202 4 000 800 39 良 便利 充足 205 4 000 7 027 40 良 便利 不充足 205 4 000 735 41 良 便利 充足 206 4 000 436 42 优 不便利 充足 213 4 000 347 43 良 便利 充足 215 4 000 420 44 优 便利 充足 180 4 000 120 45 良 便利 充足 213 4 000 220 46 良 便利 充足 195 4 000 831 47 良 不便利 充足 194 4 000 1 136 48 良 便利 充足 204 4 000 816 49 良 便利 充足 199 4 000 624 50 良 便利 充足 212 4 000 545 51 良 不便利 充足 206 4 000 1 349 52 优 便利 充足 197 4 000 1 732 53 良 便利 不充足 209 4 000 596 54 良 便利 充足 190 4 000 4 054 55 差 便利 充足 197 4 000 2 926 56 良 便利 充足 199 4 000 3 367 57 良 不便利 充足 211 4 000 6 857 58 优 便利 充足 232 4 000 9 504 59 良 便利 充足 212 4 000 5 034 60 良 便利 充足 218 4 000 7 885

从表2 可知，60 个待供点无论从自然环境、交通运输、电力供应等定性指标考虑，还是从建设成本、用地面积、材料运输距离等定量指标考虑，第44 个待供点都具有优势.另外，由图4可知，各待供点主要集中在第44 个待供点附近，因此可以考虑选择第44 个待供点作为该高速公路混凝土搅拌站的选址位置.从现场实际情况来看，该高速公路混凝土搅拌站的选址位置位于第44 个待供点附近236 m 左右，与实际混凝土搅拌站建设位置基本符合，说明蚁群算法可以应用于高速公路混凝土搅拌站的选址.

4 结 论

高速公路混凝土搅拌站的选址问题一直以来都是一个综合性问题，不能仅仅只依靠某单一因素就确定混凝土搅拌站的选址位置.根据“距离越短，运输成本越低”原则，可将混凝土待供点之间的最短距离作为选取混凝土搅拌站首要考虑的因素，同时结合该高速公路自然环境、交通运输、电力供应等定性指标以及建设成本、用地面积、材料运输距离等定量指标，综合考虑确定混凝土搅拌站选址位置.本文引入蚁群算法，统筹考虑高速公路全线各混凝土待供点，较好地计算出了不同混凝土待供点之间的最短距离，在一定程度上较好地解决了运输成本问题，不失为一种可借鉴的方法.当然，对于高速公路混凝土搅拌站选址的多因素研究还需进一步深入.