基于改进最大流最小割算法的露天境界优化及应用

doi:10.11872/j.issn.1005-2518.2018.03.318

黄金科学技术 ›› 2018, Vol. 26 ›› Issue (3): 318-324.doi: 10.11872/j.issn.1005-2518.2018.03.318

基于改进最大流最小割算法的露天境界优化及应用

贾明涛^1,2，涂小腾^1,2,3*，任助理^1,2，陈鑫^1,2，宋华强^1,2

1.中南大学资源与安全工程学院，湖南长沙 410083；
2.中南大学数字矿山研究中心，湖南长沙 410083；
3.北京奥信化工科技发展有限责任公司，北京 100040

收稿日期:2017-01-12 修回日期:2017-10-06 出版日期:2018-06-30 发布日期:2018-07-28
通讯作者: 涂小腾（1992-），男，湖北红安人，硕士研究生，从事数字矿山研究工作。xiaoteng_tu@163.com
作者简介:贾明涛（1973-），男，河南南阳人，博士，副教授，从事数字矿山和岩石力学等研究工作。mingtao_jia@163.com
基金资助:
国家自然科学基金项目“基于深度学习和距离场的复杂金属矿体三维建模技术”（编号：41572317）和中央高校基本科研业务费专项资金“自然崩落法放矿计划优化方法与可视化编制技术研究“（编号：2016zzts450）联合资助

Optimization and Application of Open Pit Boundary Based on Improved Maximum Flow Minimum Cut Algorithm

JIA Mingtao^1,2，TU Xiaoteng ^1,2,3，REN Zhuli^1,2，CHEN Xin ^1,2，SONG Huaqiang^1,2

1.School of Resources and Safety Engineering，Central South University，Changsha 410083，Hunan，China;2.Center of Digital Mine Research，Central South University，Changsha 410083，Hunan，China;3.Beijing Auxin Chemical Technology Ltd.，Beijing 100040，China

Received:2017-01-12 Revised:2017-10-06 Online:2018-06-30 Published:2018-07-28

摘要/Abstract

摘要： 最终境界对露天矿开采效益至关重要，而求解速度慢且结果不准确是最大流最小割算法在露天矿境界优化中的一个固有缺陷。对已有最大流最小割算法进行改进，以净现值（NPV）最大为目标，首先以最大几何境界内的价值块构造有向网络图，通过聚合网络图节点减少弧的复杂度，并在残留网络中对负价值节点增加开采约束，以保证得到的最小割集中正价值块受到负价值块的约束，最终通过C++编程实现该算法对露天矿进行境界优化。经实例验证，该方法科学可行，克服了原算法求解速度慢且结果不准确的弊端，且求解效率提高了近600 s，该算法具有理论上的优越性和实用性。

关键词: 露天矿, 境界优化, 最大流最小割算法, 最大几何境界, 净现值, 几何约束, 网络图, 价值块

Abstract: The ultimate boundary was very important to the benefit of open-pit mining，but the maximum flow minimum cut algorithm easily trapped into solved the problem more slowly，and its result was not accurate in open-pit mine boundary.The existing maximum flow minimum cut algorithm was improved，with the goal of maximizing net present value （NPV），first of all，the vector graph was created by the value blocks in maximize the geometric boundary，by aggregating the network graph nodes to reduce the complexity of the arc，and the negative value was constrained in the residual network nodes to ensure the positive value of the minimum cut set was constrained by the negative value，the algorithm was achieved by C+ + programming in boundary optimization of open-pit mining.The example validation shows that the method is scientific and feasible，it overcomes the drawback that the original algorithm is slow and inaccurate，and the solution efficiency is improved by nearly 600 s，the algorithm has theoretical superiority and practicability.

Key words: Key words：open pit mine, boundary optimization, maximum flow minimum cut algorithm, maximum geome-tric boundary, NPV, geometric constraints, network diagram, value block

中图分类号:

TD854

贾明涛, 涂小腾, 任助理, 陈鑫, 宋华强. 基于改进最大流最小割算法的露天境界优化及应用[J]. 黄金科学技术, 2018, 26(3): 318-324.

JIA Mingtao, TU Xiaoteng, REN Zhuli, CHEN Xin, SONG Huaqiang. Optimization and Application of Open Pit Boundary Based on Improved Maximum Flow Minimum Cut Algorithm[J]. Gold Science and Technology, 2018, 26(3): 318-324.

参考文献［16］

［1］	高永涛，吴顺川，王青，等.露天采矿学[M].长沙：中南大学出版社，2010.<br />
	Gao Yongtao，Wu Shunchuan，Wang Qing，et al.Open Pit Mining[M].Changsha：Central South University Press，2010.<br />
［2］	王青，王智静.露天开采整体优化：理论、模型与算法[M].北京：冶金工业出版社，2000.<br />
	Wang Qing，Wang Zhijing.Holistic Optimization of Open Pit Mining：Theory，Models and Algorithms[M].Beijing： Metallurgical Industry Press，2000.<br />
［3］	Wright E A.The use of dynamic programming for open pit mine design：some practical implications[J].Mining Science & Technology，1987，4（2）：97-104.<br />
［4］	Zhao Y， Kim Y C.A new graph theory algorithm for optimal ultimate design[C]//SME-AIME annual meeting，utab：Proceedings 23rd International APCOM Symposium，1992：423-434.<br />
［5］	Fenech E J，Acrivos A.The application of linear programming to design problems[J].Chemical Engineering Science，1956，5（2）：93-98.<br />
［6］	Hochbaum D S.A new-old algorithm for minimum-cut and maximum-flow in closure graphs[J].Networks，2001，37（4）：171-179.<br />
［7］	Picard J C，Smith B T.Parametric maximum flows and the calculation of optimal intermediate contours in open pit mine design[J].Information，2004，42（2）：143-152.<br />
［8］	Picard J C.Maximal closure of a graph and applications to combinatorial problems[J].Management Science，1976，22（22）：1268.<br />
［9］	Lemieux M J.Moving cone optimizing algorithm[C]//Computer Methods for the 80’s in the Mineral Industry，SME-AIME，1979：329-345.<br />
[10]	Samavati M，Essam D，Nehring M，et al.A local branching heuristic for the open pit mine production scheduling problem[J].European Journal of Operational Research，2017，257（1）：261-271.<br />
［11］	黄俊歆，王李管，毕林，等.改进的露天境界优化几何约束模型及其应用[J].重庆大学学报，2010，33（12）：78-83.<br />
	Huang Junxin，Wang Liguan，Bi Lin，et al.The improved geometrical constraint model of open-pit mine boundary optimum and its application[J].Journal of Chongqing University，2010，33（12）：78-83.<br />
［12］	杨彪，罗周全，陆广，等.复杂多金属露天矿山最终境界动态综合优化[J].矿冶工程，2011，31（1）：1-4.<br />
	Yang Biao，Luo Zhouquan，Lu Guang，et al.Dynamic and comprehensive optimization of ultimate pt limit for complex multi-metal open-pit mine[J].Mining and Metallurgy Engineering，2011，31（1）：1-4.<br />
［13］	杨彪，罗周全，陆广，等.基于经济时间序列预测的露天矿开采境界动态优化[J].煤炭学报，2011，36（1）：29-33.<br />
	Yang Biao，Luo Zhouquan，Lu Guang，et al.Open pit mining limit dynamic optimization based on economic time series forecasting [J].Journal of China Coal Society，2011，36（1）：29-33.<br />
［14］	Choudhury S，Chatterjee S.Pit optimisation and life of mine scheduling for a tenement in the central African copper belt[J].International Journal of Surface Mining Reclamation & Environment，2014，28（3）：200-213.<br />
［15］	季桂树，卢志渊，李庆春.一种求解最小割集问题的新思路[J].计算机工程与应用，2003，39（2）：98-100.<br />
	Ji Guishu，Lu Zhiyuan，Li Qingchun.A new idea for solving the minimal cut set[J].Computer Engineering and Applications，2003，39（2）：98-100.<br />
［16］	刘汝佳，黄亮.算法艺术与信息学竞赛[M].北京：清华大学出版社，2004.<br />
	Liu Rujia，Huang Liang.The Contest of Algorithm Art and Informatics[M].Beijing：Tsinghua University Press，2004.<br />

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	杨明财, 盛建龙, 叶祖洋, 董舒. 基于FlAC3D的露天矿边坡稳定性及影响因素敏感性分析[J]. 黄金科学技术, 2018, 26(2): 179-186.
[2]	张二洋，陈建宏. 基于Surpac矿山设计软件及虚幻引擎实现的矿山虚拟现实漫游系统[J]. 黄金科学技术, 2017, 25(4): 93-98.
[3]	贾明涛，吕青海，陈鑫，宋华强. 聚合分期算法在露天矿中长期生产计划编制中的应用[J]. 黄金科学技术, 2017, 25(4): 58-64.
[4]	文超, 顾清华, 冯居易. 基于GIS的露天矿配矿管理系统研究[J]. J4, 2009, 17(2): 58-62.
[5]	李和平, 王晓亮, 汪洋, 李洪海, 薛田喜. 露天松动爆破技术在河西金矿的试验与应用[J]. J4, 2007, 15(4): 45-50.
[6]	白晓平, 才庆祥. 露天矿半连续运输系统可靠性研究[J]. J4, 2000, 8(2): 40-43.
[7]	狄卫民, 云庆夏. 应用网络流规划编制露天矿最优排土计划[J]. J4, 1999, 7(4~5): 78-81.

基于改进最大流最小割算法的露天境界优化及应用

Optimization and Application of Open Pit Boundary Based on Improved Maximum Flow Minimum Cut Algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献［16］

相关文章 7

Metrics

本文评价

推荐阅读 10

基于改进最大流最小割算法的露天境界优化及应用

Optimization and Application of Open Pit Boundary Based on Improved Maximum Flow Minimum Cut Algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献 ［16］

相关文章 7

Metrics

本文评价

推荐阅读 10

参考文献［16］