改进蚁群算法在地下矿山运输路径优化的应用
周科平，翟建波
(中南大学 资源与安全工程学院，湖南省深部金属矿产开发与灾害控制重点实验室，湖南 长沙，410083)
摘要：为提高地下矿山运输的智能化和自动化管理水平，提出以电机车总运输距离为目标函数，矿石接收点和溜井数目为变量的运输路径优化模型，并利用改进的蚁群算法对模型进行求解，以便得到最佳的运输路径，将该模型应用到国内某矿山井下运输系统，取得比较理想的效果，并进行参数选取的敏感性分析研究。研究结果表明：利用该方法可以快速得到运输系统的最佳配送路径以及最短运输距离为4 415.653 m，并通过试验多次测试得出，各参数的最佳取值范围为蚂蚁数目m为14~23，信息素重要程度因子α为0.5~1.5，启发函数重要程度因子β为1~3，信息素挥发因子ρ为0.05~0.20，迭代次数NC为100~130。
关键词：改进蚁群算法；地下矿山运输；路径优化；参数选取
中图分类号：TD529 文献标志码：A 文章编号：1672-7207(2014)01-0256-06
Application of improved ant colony algorithm in route optimization of underground mine’s transportation
ZHOU Keping, ZHAI Jianbo
(Hunan Key Laboratory of Mineral Resources Exploitation and Hazard Control for Deep Metal Mines,
School of Resource and Safety Engineering, Central South University, Changsha 410083, China)
Abstract: In order to improve the intelligent and automated management level of the underground mine’s transportation, its route optimization model was proposed with the total haul distance of electric locomotive as the objective function, the ore receiving point and the orepass number as variables. Then the improved ant colony algorithm was used for solving the model and getting the best transportation route. The model was applied for a underground mine’s transport system, and an ideal effect was gotten. Besides, the sensitivity analysis of parameter selection was studied. The results show that the best distribution route of the transport system is quickly gotten by using this method and the shortest distance is 4 415.653 m. In addition, the best values for each parameter are obtained by testing with ant number m being 14-23, pheromone important degree factor α being 0.5-1.5, heuristic function important degree factor β being 1-3, pheromone evaporation factor ρ being 0.05-0.20, and iteration NC being 100-130.
Key words: improved ant colony algorithm; underground mine’s transportation; route optimization; parameter determination
矿山智能化与数字化将会是未来矿山发展的模式，采矿学业将变成多学科交叉形成的一门崭新学科[1]。在地下矿山的生产中，运输是其中非常重要的环节，传统的经验运输模式会随着矿山生产量以及矿山规模增加而使得管理更加困难，如何对运输路径进行合理优化与智能管理就变得尤为重要。物流配送路径优化问题已经发展的越来越趋于成熟，近些年，在路径优化中开始普遍引进智能优化算法进行研究并取得了不错的效果[2]。李智[3]在煤炭运输上进行了蚁群算法的应用研究，华臻等[4]也提到蚁群算法在矿井中的一些简单应用，但还没有形成一套详细的应用于地下矿山运输路径优化的理论体系。鉴于此，本文作者通过改进的蚁群算法对地下矿山运输路径优化问题进行了深入的研究，然后建立了地下矿山运输路径优化模型，最后将该模型应用到井下运输系统中，取得了比较满意的结果。
1 蚁群算法
1.1 基本蚁群算法
蚁群算法是20世纪90年代由Dorigo等[5]提出的一种模拟蚂蚁群体行为方式的仿生优化算法。该算法引入正反馈并行机制，具有较强的鲁棒性、优良的分布式计算机制、易于其他方法相结合等优点。
基本蚁群算法的介绍是从TSP问题开始，TSP的简单形象描述为：给定n个城市有1个旅行商从某一城市出发，访问各城市1次且仅有1次后再回到原出发城市，要求寻找出一条最短的巡回路径。假设城市集合
，城市之间的旅行路径长短
，最短路径表示如下式所示。
(1)
蚁群算法中的基本变量和常数有：n，TSP问题中的城市个数；m，蚁群中蚂蚁的总数目；dij，城市i和j之间的距离，其中
；
，表示t时刻路径(i, j)上的残留信息量。初始时刻各条路径上信息量相等，设
(const为常数)。
蚂蚁k(k=1, 2, …, m)在运动过程中，根据各条路径上的信息量决定其转移方向。
表示t时刻蚂蚁k由城市i转移到城市j的状态转移概率，如下式所示。
(2)
式中：
表示t时刻下一步蚂蚁k允许选择的城市；tabuk(k=1, 2, …, m)表示禁忌表，记录蚂蚁k当前已访问过的城市；
表示信息启发式因子；
表示期望启发式因子；
表示该算法的先验知识，其值如下式所示。
(3)
蚁群算法必须进行信息素的定时更新来避免淹没启发信息，定义经过n个时刻，蚂蚁对所有n个城市都完成1次遍历后，对残留信息素进行更新处理。路径(i, j)上的信息量根据式(4)和(5)进行调整。
(4)
(5)
式中：
为信息素挥发系数，用
表示信息残留系数；
为本次循环中路径(i, j)上的信息素增量，初始时刻
；
表示第k只蚂蚁在本次循环中留在路径(i, j)上的信息量。
Dorigo等[5]提出了蚁周、蚁量和蚁密3种信息素更新模型。其中蚁周模型的使用比较广泛，如下式所示。
(6)
大量的试验得出蚁周模型的最好实验参数选取范围为0≤≤5，0≤≤5，0.1≤
≤0.99，10≤Q≤ 10 000。
1.2 改进蚁群算法
蚁群算法的运用已经吸引了国际以及国内学术界的普遍关注，但基本蚁群算法也存在如下不足：(1) 每次解构造过程的计算量比较大，算法搜索时间长；(2) 算法容易出现停滞现象；(3) 基本蚁群算法是离散 的，也需要向连续优化问题方面进行应用。许多学者针对上述缺陷，做了大量蚁群算法的改进研究工作，主要集中在改善其全局收敛性和应用于连续域问题两点[6-10]。
最大-最小蚁群系统(MAX-MIN Ant System，MMAS)的基本思想是为了避免算法过早收敛于非全局最优解，将各条路径上的信息量限制在区间
之内，超出该范围则限制为信息量允许的上下限，从而使算法不在扩散，加快收敛速度。
修改后的更新规则如下：
(7)
(8)
其中：
表示迭代最优解或全局最优解，在MMAS中常使用迭代最优解。
2 地下矿山运输路径优化问题及模型
2.1 问题描述
设地下矿山某运输水平(即一个中段)内有n个溜井Ai(i=1, 2, …, n)，溜井的储存待运矿量分别为ai；m个矿石接收点Bj(j=1, 2, …, m)，接收到的矿石量分别为bj，从溜井点A i到矿石接收点Bj的距离为dij，xij表示从溜井点Ai到矿石接收点Bj的矿石量，则x ij需要满足
(i=1, 2, …, n)和
(j=1, 2, …, m)；此外，矿石接收点总接收矿石量一定等于溜井总运出矿量，即
；矿石的总运输距离为
。如何在满足运矿需求的基础上，使得总运输距离最低一直是地下矿山运输追求的目标。
2.2 蚁群模型实现
设m个矿石接收点分别有kh(h=1, 2, …, m)辆电机车，分别为Ch个溜井服务，若1台电机车的载重量为Q，则m个矿石接收点的需矿量也就等于电机车个数与载重量的乘积，即khQ；通过m个接收点派出电机车为各溜井卸矿点A1, A2, …, An服务，矿石的溜井总数为n，1辆电机车最大行驶距离为L。
表示第h个矿石接收点第k台车负责服务的溜井数，
分别表示第h个矿石接收点的第k条路径，其中：第i个元素rhki表示溜井rhki在第h个矿石接收点服务区域内的路径k中的顺序为i，若rhki=0，则表示电机车处在矿石的第h个接收点处。qrhki表示第h个矿石接收点服务区域内第k条路径中溜井rhki的卸矿量
, h=1, 2, …, m，表示第h个矿石接收点派出的第k辆电机车的路径上第i个溜井到第i-1个溜井的距离，其中第0个溜井即为矿石接收点，若以运输距离最短为目标函数，即如式(9)所示。
(9)
约束条件：
(10)
(11)
(12)
(13)
(14)
式(11)保证每条路径上各溜井的卸矿量之和不超过电机车的最大允许荷载；式(12)保证1辆电机车的运输距离不超过其最大运输距离L；式(13)保证所有路径上的溜井数之和等于总溜井数，同时保证每个溜井都能够得到装矿的服务；式(14)表示了每条路径的溜井组成；式(15)限制1个溜井只能有1列电机车来服务[11-15]。
本文以单矿石接收点路径优化问题为例求解的蚁群算法实现步骤为。
(1) 初始化参数，读取溜井点和矿石接收点坐标以及溜井卸矿量，设置最大信息素和最小信息素参数，并计算各点之间的距离。
(2) 设置迭代计数器NC=0，将m只蚂蚁置于配送中心，分别为各蚂蚁建立禁忌表。
(3) 对于每只蚂蚁i，在待访问溜井列表中找出所有未走过的溜井点，并在这些节点中按照转移概率公式选择蚂蚁的下一个溜井点j。
(4) 考虑i和j连接后线路上的载矿量q，若q小于车辆最大容量，则继续下步，否则将j点重新加入待访问溜井列表A中，并随机在A表中选择一点作为起点，转步骤(3)。
(5) 对每只蚂蚁在选择下一点之后对其所走过的路径进行局部信息素更新及信息素增量更新。
(6) 求k只蚂蚁搜索的最佳路径长度和路线，并全局更新该条路线边上的信息素，每次更新完信息素都进行边界检查，将信息量控制在区间之内。
(7) 将本次迭代最优解与全局最优解比较，若本次迭代最优解更好，则进行2-OPT优化[16]，并更新全局最优解及全局最优路径表。
(8) 判断NC是否等于最大迭代次数，若是，则结束；否则清空禁忌表，跳回步骤(2)，重复进行上述步骤。
3 实例计算与参数敏感性分析
3.1 实例计算与结果分析
本文以云南省某锡矿山1650运输水平为例，进行地下矿山运输车辆配送路径优化的研究，其运输系统见图1。从图1可知：该运输水平内有1个主溜井B0，可以看作路径优化问题中的矿石接收中心，有13个采场溜井A1，A2，…，A13，可以看作路径优化问题中的需求点；需要从主溜井通过电机车派送去装载矿石，即电机车从每个采场溜井获得矿石；每个采场溜井的卸矿量是一定的。
图1 井下运输系统网络图
Fig. 1 Network diagram of underground transportation system
通过现场数据的收集，可以得到主溜井的坐标以及各个采场溜井的坐标和卸矿量，如表1所示。
表1 溜井坐标及卸矿量
Table 1 Orepass coordinate and discharging ore number
设置算法参数如下：蚂蚁的数目m=21，最大迭代次数NC=100[10]，信息素重要程度因子
，启发函数重要程度因子
，信息素挥发因子
，信息素的最大最小值开始的时候设置多大无所谓，在第1次搜索完成会生成1个最优解，然后利用这个解可以重新生成最大最小值；设置每辆电机车的载矿量均为50 t，由运行结果可知最佳配送路线的配送距离为4 415.653 m，最佳配送路线见表2。
表2 最佳配送路径
Table 2 Best distribution route
3.2 参数选取的敏感性分析
为了探究各参数对本次实验结果的影响，对比10组不同参数对应的最优路径情况。每组运行10次，得出最大值、最小值和平均值，蚂蚁数目对3组值的影响情况如图2所示。
图2 蚂蚁数目对路径的影响
Fig. 2 Influence of ant number on route
由图2可知：在本例中蚂蚁数目是问题规模的1.0~1.5倍，既能找到最优解，算法也相对稳定，运行时间也是相对最少。
信息素重要程度因子对3组值的影响情况如图3所示。
由图3可知：在本例中信息素重要程度因子α在0.5~1.5内，算法的综合求解性能最好。
启发函数重要程度因子β对3组值的影响情况如图4所示。
由图4可知：在本例中启发函数重要程度因子β在1~3内，算法的综合求解性能最好。
信息素挥发因子ρ对3组值的影响情况如图5所示。
图3 信息素重要程度因子α对路径的影响
Fig. 3 Influence of pheromone important degree factor α on route
图4 启发函数重要程度因子β对路径的影响
Fig. 4 Influence of heuristic function important degree factor β on route
图5 信息素挥发因子ρ对路径的影响
Fig. 5 Influence of pheromone evaporation factor ρ on route
由图5可知：在本例中信息素挥发因子ρ的值在0.05~0.20内，算法的综合求解性能最好。
迭代次数NC对3组值的影响情况如图6所示。
图6 迭代次数NC对路径的影响
Fig. 6 Influence of iteration number NC on route
由图6可知：本例中当迭代次数大于40后，路径的变化开始趋于稳定，迭代次数在100~130之间路径的平均值趋于最小，说明算法寻找到最优解的性能最好。
4 结论
(1) 本文提出了地下矿山运输的路径优化模型，并利用改进蚁群算法对路径优化模型进行求解，以得到最优路径。
(2) 通过对某矿山井下运输系统的应用，得到最佳配送路径以及最短运输距离为4 415.653 m，
(3) 通过对参数选取的敏感性分析，得出本例中各参数的最佳取值为蚂蚁数目m为14~23，信息素重要程度因子为 0.5~1.5，启发函数重要程度因子为1~3，信息素挥发因子为0.05~0.20，迭代次数NC为100~130。
参考文献：
[1] 古德生. 地下金属矿采矿科学技术的发展趋势[J]. 黄金, 2004, 25(1): 18-22.
GU Desheng. The development tendency of mining science and technology of underground metal mine[J]. Gold, 2004, 25(1): 18-22.
[2] 吴隽. 基于改进蚁群算法的物流配送路径优化研究[D]. 武汉: 武汉理工大学计算机科学与技术学院, 2009: 10-22.
WU Juan. Research on logistics distribution routing problem based on improved ant colony algorithm[D]. Wuhan: Wuhan University of Technology. School of Computer Science and Technology, 2009: 10-22.
[3] 李智. 基于蚁群算法的煤炭运输优化方法[J]. 中国铁道科学, 2004, 25(3): 126-129.
LI Zhi. Optimization model of coal transportation based on ant colony algorithm[J]. China Railway Science, 2004, 25(3): 126-129.
[4] 华臻, 王振翀. 蚁群优化算法在矿井中的应用[J]. 煤炭学报, 2008, 33(3): 353-356.
HUA Zhen, WANG Zhenchong. Application of ant colony algorithm to mine[J]. Journal of China Coal Society, 2008, 33(3): 353-356.
[5] Dorigo M, Caro G D, Gambardella L M. Ant algorithms for discrete[J]. Artificial Life, 1999(5): 137-172.
[6] 郑松, 侯迪波, 周泽魁. 动态调整选择策略的改进蚁群算法[J]. 控制与决策, 2008, 23(2): 225-228.
ZHENG Song, HOU Dibo, ZHOU Zekui. Ant colony algorithm with dynamic transition probability[J]. Control and Decision, 2008, 23(2): 225-228.
[7] 夏鸿斌, 须文波, 刘渊. 自适应并行机制的改进蚁群算法[J]. 系统工程与电子技术, 2009, 31(12): 2973-2976.
XIA Hongbin, XU Wenbo, LIU Yuan. Ant colony algorithm with adaptive parallel mechanism[J]. Systems Engineering and Electronics, 2009, 31(12): 2973-2976.
[8] 宋雪梅. 蚁群算法的改进及应用研究[D]. 唐山: 河北理工大学计量与自动控制学院, 2005: 18-27.
SONG Xuemei. Improvement and applications of ant colony optimization[D]. Tangshan: Hebei Polytechnic University. School of Computer and Automatic Control, 2005: 18-27.
[9] Holland J H. Adaptation in natural and artificial systems[M]. Ann Arbor: University of Michigan Press, 1975: 22-55.
[10] 段海滨. 蚁群算法原理及其应用[M]. 北京: 科学出版社, 2005: 42-97.
DUAN Haibin. Ant colony algorithm and its application[M]. Beijing: Science Press, 2005: 42-97.
[11] 孙莹, 连民杰. 基于改进蚁群算法的地下矿车辆生产调度路径优化研究[J]. 金属矿山, 2010(2): 51-54.
SUN Ying, LIAN Minjie. Research on vehicle routing and scheduling problems based on improved ACA in underground mine[J]. Metal Mine, 2010(2): 51-54.
[12] 戴树贵, 陈文兰, 潘荫荣, 等. 多配送中心车辆路径安排问题混合蚁群算法[J]. 四川大学学报(工程科学版), 2008, 40(6): 154-158.
DAI Shugui, CHEN Wenlan, PAN Yinrong, et al. A hybrid ant colony algorithm for multiple depot vehicle routing problem[J]. Journal of Sichuan University (Engineering Science Edition), 2008, 40(6): 154-158.
[13] 陈美军, 张志胜, 史金飞. 多约束下多车场车辆路径问题的蚁群算法研究[J]. 中国机械工程, 2008, 19(16): 1939-1944.
CHEN Meijun, ZHANG Zhisheng, SHI Jinfei. Study on ant colony algorithm for multi-depots vehicle routing problem with multiple constraints[J]. China Mechanical Engineering, 2008, 19(16): 1939-1944.
[14] 陈美军, 张志胜, 史金飞. 基于自适应多态蚁群算法的多约束车辆路径问题[J]. 东南大学学报(自然科学版), 2008, 38(1): 37-42.
CHEN Meijun, ZHANG Zhisheng, SHI Jinfei. Vehicle routing problem with multiple constraints using adaptive and polymorphic ant colony algorithm[J]. Journal of Southeast University (Natural Science Edition), 2008, 38(1): 37-42.
[15] 陈美军, 张志胜, 陈春咏, 等. 多车场车辆路径问题的新型聚类蚁群算法[J]. 企业管理与信息化, 2008, 37(11): 1-5.
CHEN Meijun, ZHANG Zhisheng, CHEN Chunyong, et al. Study on a novel clustering ant colony algorithms for multi- depots vehicle routing problem[J]. Manufacture Information Engineering of China, 2008, 37(11): 1-5.
[16] 祝崇隽, 刘民, 吴澄, 等. 针对模糊需求的VRP的两种2-OPT算法[J]. 电子学报, 2001, 29(8): 1-3.
ZHU Chongjuan, LIU Min, WU Cheng, et al. Two kinds of 2-OPT algorithm for VRP with fuzzy demand[J]. Acta Electronica Sinica, 2001, 29(8): 1-3.
(编辑 杨幼平)
收稿日期：2012-12-24；修回日期：2013-03-21
基金项目：国家自然科学基金资助项目(51274253)；国家自然科学基金重大资助项目(50934006)
通信作者：周科平(1964-)，男，湖南衡阳人，教授，博士生导师，从事深部采矿和矿山岩石力学研究；电话：0731-88879965；E-mail: kpzhou@vip.163.com
