基于多目标遗传算法的露天矿卡车调度优化研究_张明.pdf

基于多目标遗传算法的露天矿卡车调度优化研究 张明 1 顾清华 1 李发本 1， 2 闫宝霞 3 刘迪 1 （1. 西安建筑科技大学管理学院， 陕西 西安 710055； 2. 洛阳栾川钼业集团有限责任公司， 河南 洛阳 471000； 3. 西安有色冶金设计研究院有限公司， 陕西 西安 710055） 摘要为合理调配露天矿卡车运输， 实现矿山企业降本增效， 解决卡车运输调度管理的多目标需求， 以卡车 运输成本最低和等待时间最少为目标， 以车铲生产能力、 矿石品位以及生产原则为约束， 构建了多目标卡车调度模 型。模型采用优选因子分配车辆， 使用多目标遗传算法进行求解， 进而优化露天矿卡车的动态调配。针对某露天 矿卡车调度进行多目标优化， 研究结果表明 此方法可提供合理的优化调度方案， 得到具体的卡车运输路线和运行 时刻表， 大大降低卡车运输成本， 提高设备使用效率， 从而为矿山的卡车调度提供具体合理的决策依据。 关键词露天矿调度模型优化调度多目标遗传算法 中图分类号TD672文献标志码A文章编号1001-1250 （2019） -06-157-06 DOI10.19614/ki.jsks.201906028 Research of Open-pit Mine Truck Dispatching Optimization Based on Multi-objective Genetic Algorithm Zhang Ming1Gu Qinghua1Li Faben1， 2Yan Baoxia3Liu Di12 （1. School of Management， Xian University of Architecture and Technology， Xian 710055， China； 2. Luoyang Luanchuan Molybdenum Group Co.， Ltd.， Luoyang 471000， China； 3. Xian Engineering and Research Institute of Nonferrous Metallurgy Limited Company， Xian 710055， China） AbstractIn order to rationally allocate truck transportation in open-pit mines， realize cost reduction and efficiency in- crease for mining enterprises， and meet the multi-objective demand of truck transportation dispatching management， a multi- objective truck dispatching model is constructed with the aims at minimizing truck transportation cost and waiting time，with truck shovel production capacity，grade constraints and production principles as constraints. This model adopts the optimal factor to dispatch the vehicles， and the multi-objective genetic algorithm to make solution， so as to optimize the dynamic allo- cation of trucks in open-pit mines. The multi-objective optimization practice of truck dispatching in an open pit mine shows that this can provide a reasonable optimal dispatching scheme to obtain a specific truck transportation route and opera- tion schedule. It can greatly reduce the cost of truck transportation and improve the efficiency of equipment， thus providing a specific reasonable decision-making basis for truck dispatching in mines. KeywordsOpen-pit mine， Dispatch model， Optimal dispatch， Multi-objective genetic algorithm 收稿日期2019-04-08 基金项目国家自然科学基金项目 （编号 51774228， 51404182） ， 陕西省自然科学基金项目 （编号 2017JM5043） ， 陕西省教育厅专项科研计划 项目 （编号 17JK0425） 。 作者简介张明 （1993） ， 男， 硕士研究生。通讯作者顾清华 （1981） ， 男， 副教授， 博士， 硕士研究生导师。 总第 516 期 2019 年第 6 期 金属矿山 METAL MINE Series No. 516 June 2019 随着我国工业化、 信息化的不断发展， 矿业智能 化、 数字化成为矿山的发展趋势 ［1-4］。系统优化是矿 山智能化建设的一部分， 面对不断变化的市场形式， 优化生产流程、 降低企业成本是每个矿山企业亟需 解决的关键问题。露天矿运输费用约占矿山运营成 本的50～60， 故而优化卡车调度是减少矿山企业 生产成本， 提高企业效益最为行之有效的途径 ［5-8］， 其 实质是合理分配车辆， 确保生产计划高效运行 ［9-10］。 纵观国内外露天矿卡车调度研究， 起初采用计 算机控制露天矿卡车调度优化， 此后采用线性规划、 动态规划、 整数规划等方法完成车辆的派发， 采用 LINGO （Linear Interactive and General Optimizer） 来进 行车流规划从而为调度提供决策依据 ［11］。随着智能 算法的发展， 智能优化算法也在卡车调度中发展起 157 ChaoXing 金属矿山2019年第6期总第516期 来。Godoy等 ［12］基于模拟退火算法， 开发组合优化算 法， 解决了卡车调度决策问题；Souza等 ［13］提出了一 种混合式启发算法， 结合贪心随机自适应搜索程序 和一般变量邻域搜索， 优化了卡车调度中的最少派 车问题。尽管国内外对矿山卡车调度的研究已较成 熟， 但这些研究大多以单个经济指标实现矿山卡车 的分配。矿山卡车调度作为复杂的系统工程， 只考 虑单一的目标， 难以凸显卡车动态分配和优化效 果。对于这一问题， 随着多目标优化的发展， Coelho 等 ［14］提出了3种多目标启发式算法即2PPLS-VNS、 MOVNS、 NSGA-II， 可以应用到露天矿开采作业的动 态卡车分配问题上； Mendes等 ［15］提出了一个多目标 进化算法， 可应用在露天矿卡车动态调度中， 并验证 大多数情况下为所有调度情况提供了良好的解， 但 其多目标研究只给出了适应于卡车调度的多目标优 化算法， 并未给出具体的调度方案。 综上所述， 露天矿卡车调度已由单目标优化转 向多目标优化， 因此本研究以露天矿运输成本最低， 卡车等待时间最少为目标函数， 构建了露天矿卡车 调度的多目标优化模型， 提出了基于多目标遗传算 法的露天矿卡车调度模型求解方法， 并通过MATLAB 软件进行数值求解， 从而得出露天矿生产调度的最 佳方案， 为露天矿卡车调度提供决策依据。 1露天矿卡车调度多目标优化模型 1. 1目标函数 多目标优化是一种考虑多种指标的寻优策略， 更符合于实际问题的多种决策需求 ［16-17］。露天矿卡 车调度是一个复杂系统工程， 实际问题经常涉及多 个目标， 这些目标往往是复杂冲突的， 因此采用多目 标优化卡车调度更能反映实际状况。露天矿卡车调 度涉及到的优化目标有 总运量最小、 产量最大、 设 备利用率最高等。而目前矿山企业比较关心的是运 输成本， 以及设备的利用率。本研究综合考虑矿山 卡车调度的诸多因素， 基于矿山企业关心的问题， 以 运输成本最小， 卡车总的等待时间最小为目标构建 了多目标优化调度模型。 露天矿卡车调度模型概述如下 某露天矿实际 开采中， 有n个装载点Ai（i1， 2， ...，n） ，m个卸载点Bj （j1， 2， ...，m） 和 k辆工作的卡车， 装载点装载率和卸 载点的卸载率已知。每个装载点Ai到每个卸载点Bj 的距离为dij（i1， 2， ...，n；j1， 2， ...，m） ， 其单位为km； 卡车的重载、 空载和维修费用分别为c1、c2、c3， 其中c1、 c2的单位为元/km，c3的单位为元/h。卡车的容量为c， 卡车往返于装载点与卸载点之间。 模型的每一个优化目标由一个函数表示， 所有 的调度参数统称为S， 构建的多目标优化目标函数如 下 FSMin[F1S,F2S].（1） 目标函数F1S为总运输成本，F2S为卡车总的等待时 间 F1S∑ r1 k ∑ i1 n ∑ j1 m dijc1xij∑ i1 n ∑ j1 m dijc2yij∑ r1 k ΔTrc3,（2） F2S∑ r1 k Tlimit-∑ i1 n ∑ j1 m zrijxij-∑ i1 n ∑ j1 m qrijyij-xr,（3） 式中，xij为第r辆卡车从第i个装载点到第j个卸载点的 次数；yij为第r辆卡车从第j个卸载点到第i个装载点的 次数；ΔTr为第r辆卡车的维修时间；Tlimit为班工作时 间或单次优化时间；zrij为第r辆卡车从第i个装载点到 第j个卸载点的重车运行时间；qrij为第r辆卡车从第j 个卸载点到第i个装载点的空车运行时间；xr为第r辆 卡车的空闲时间。 1. 2约束条件 模型约束条件如下 （1） 产量应满足每个卸载点的要求 θ1x∑ r1 k ∑ i1 n cxij-fj≥0，（4） 式中，fj为卸载点j产量要求。 （2） 第i个装载点运输出去的总量不能大于该装 载点的总量 θ2x∑ j1 n cxij-gi≤0， ∀i ；（5） 式中，gi为装载点i的总量。 （3） 装载点∀i； 所装车次小于1个班次内装载点 至多装车数 θ3x∑ j1 m xij-Bc≤0， ∀i ；（6） 式中，Bc为1个班次内装载点至多装车数。 （4） 第j个卸载点卸载的总量不能大于该卸载点 的卸载最大值 θ3x∑ i1 m cxij-qj≤0， ∀i ；（7） 式中，qj为卸载点j的卸载最大值。 （5） 卸点矿石的品位需满足限制要求 θ4x | | | | | || | | | | | | | | || | | | c∑ i1 n xijai c∑ i1 n xij -e -α＜0， ∀i ；（8） 式中，e为品位限制；α为品位允许误差；ai为装载点i的 158 ChaoXing 张明等 基于多目标遗传算法的露天矿卡车调度优化研究2019年第6期 品位。 （6） 每个线路上的运输次数要求 xij,yij∈{}0,1,2,3... .（9） 结合露天矿的生产实际过程， 从以上模型可以 看出 如果降低卡车的运输成本， 就会促使卡车的等 待时间增大， 影响设备使用效率， 其两者之间是相互 冲突的， 一者变优则导致另一者变差。针对以上构 建的多目标模型， 本研究引入多目标遗传算法进行 求解。 2露天矿卡车调度多目标遗传算法 2. 1多目标遗传算法 遗传算法是由Holland （1962） 提出的一种基于生 物进化规律转变而来的随机化搜索算法， 对搜索最 优解具有良好的时效性能。多年来， 在多目标问题 的求解上， 遗传算法相对于其他算法较有优势， 相继 出现多种多目标遗传算法， 例如MOGA、 NSGA、 NS- GA-II、 SPEA2等。 多目标遗传算法引入Pareto最优性理论， 求解之 后可得到优化问题的近似Pareto最优解， 解集中的每 一个解不存在相互支配关系， 优化者可以根据具体 优化问题的偏好信息在该解集中寻求最终的满意 解。 本研究针对露天矿卡车调度问题， 采用多目标 遗传算法NSGA-II的适值分配、 保持种群多样性和防 止优秀个体流失等优点， 在MATLAB平台构建符合 于卡车调度的多目标求解算法， 在解决露天矿卡车 调度问题的同时保证Pareto最优解的可靠性和准确 性。 2. 2算法设计 （1） 输入参数， 产生初始群体p0。针对露天矿卡 车调度的特殊性， 本算法采用偏好因子lfactor满足露天 矿运输中对岩石量的运输要求， 通过式 （10） 实现动 态调整。染色体采用字符编码， 装载点使用大写字 母， 卸载点使用小写字母， 卡车的运行路线使用字符 串表示， 例如 ［AaBbCc］ 表示一辆卡车的运行路线， 与此同时， 记录卡车的运行时刻 ［8］ 。初始种群的产生 满足一定的假设条件， 只有当卡车在规定的时间内 不能再跑一趟或者无处可调度时， 此卡车停止， 除此 之外卡车一直在工作。 ifxrand＜lfactor, ncrock; ifxrand＞lfactor, ncrand;（10） 式中，xrand为选择卸载点因子；crock为岩石卸载点对应 的号；crand为随机产生的可去卸载点的号。 （2） 对种群p0进行排序、 选择、 交叉、 变异、 产生子 代种群Q0， 设置参数t0， 混合当前子父代产生新群 体， 即Rtpt⋃Qt。 （3） 对Rt进行快速无支配排序和拥挤度距离计 算， 然后取出Rt前N优良个体作为下一父代pt1。 （4） 对pt1进行选择、 交叉、 变异产生新代Qt1。 选择时采用二元竞标赛选择法， 交叉时采用单点交 叉产生新染色体。 （5）tt1； 判断是否满足终止条件， 若不满足返 回步骤 （2） 。 （6） 输出得到的Pareto最优解集。 2. 3约束处理 面对智能算法中约束条件难以处理的问题， 通 过引入惩罚函数， 把模型转化为无约束优化。用约 束条件构建目标函数通常是在目标函数中加入惩罚 约束函数， 从而对不可行解进行过滤， 处理形式 viox∑ j1 J λmin or max0,θjxω，（11） 式中，λ，ω为惩罚因子；θjx为约束条件。 2. 4测试函数验证 采用测试函数验证此算法核心思想的寻优性， 以保证应用时的有效性。测试函数选择常被用作检 测算法搜索能力的多目标带约束函数 ［18］ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ minf1xx1 minf2xx2 s.t x2 1x 2 2-1-0.1cos16arctan x1 x2≥0 x1-0.52x2-0.52≤0.5 0≤x1≤π 0≤x2≤π .（12） 算法设置200个初始种群， 1 000代迭代次数， 求 解后优化结果如图1所示。从图1可以看出Pareto最 优解分布均匀， 可得到良好的分布前沿， 说明此方法 对于求解多目标有约束规划问题是有效的。 3实例应用 河南省某露天矿的采区有4个卸载点， 6个装载 点， 运量为40 t的卡车20台。由GPS监测系统得到各 159 ChaoXing 金属矿山2019年第6期总第516期 装载点与卸载点之间的距离如表1所示， 各装载点的 铲位量如表2所示。矿山实行3班制， 破碎站运输产 量1个班的要求依次为0.2万t、 0.2万t、 0.15万t， 渣场 的要求为0.50万t。经现场实际调研， 卡车的重空载运 输费用分别为60元/km、 50元/km， 维修费用1.5元/h。 卡车的重空载平均运行速度分别为15 km/h、 20 km/h。 破碎站品位限制要求为0.12～0.13， 现场每班工 作的运输费用约为82 500元， 卡车的等待时间平均 约为1.75 h。 因露天矿在运输过程中要先以运送岩石量为优 先， 故优化时加入岩石优先选择因子， 以保证运输方 案在矿山的可实施性。在matlab平台上编制多目标 遗传算法进行优化求解， 得到优化方案的Pareto最优 解集如图2所示。 从图2可以看出， 多目标遗传算法求解得到了问 题的多个优解， 比起常规单目标优化得到的单个解 的选择空间更大， 决策者可根据各矿山实际运行等 条件， 选择合理的派车方案进行生产， 在满足运输费 用最小的同时， 达到充分利用卡车的目的。以卡车 总等待时间最小优化方案为例， 本研究得到的卡车 运行路线如表3所示 （以卡车1～5号为例） ， 卡车的 运行时刻如表4所示 （以卡车1为例） ， 卡车的运输次 数如表5所示。为直观表述卡车的运行路线， 图3给 出了卡车1部分时间的运行图。 研究中得到的卡车运行路线与时刻表可为矿山 提供完整具体的调度方案， 比起LINGO求解的车流 规划 ［11］ ， 本方案更加具体， 矿山调度更加精准。选取 求解结果中的3种优化方案与现场固定派车方案④ 作对比。各方案指标如表6所示。对比结果如图4 所示。从表6可以看出， 总等待时间反映着产量的变 化， 总等待时间减小， 卡车使用率提高， 产量增大， 运 输成本增加； 反之， 总等待时间增大， 卡车使用率减 小， 产量减少， 运输成本减少。 根据Pareto最优理论， 由图4可以看出优化方案 均优于现场固定派车方案， 优化方案均是在同一条 160 ChaoXing ［1］ ［2］ ［3］ ［4］ ［5］ ［6］ ［7］ ［8］ ［9］ ［10］ ［11］ ［12］ ［13］ ［14］ 件下的最优解， 不受别的解支配。在多种的决策需 求之下可选择合理的方案满足矿山生产， 若要使满 足生产时班运输成本最低， 可选择方案①， 此方案相 比于现场固定派车方案成本降低了7.46， 产量增加 了1.11。若要充分发挥设备使用率， 使产量最大化 的同时成本最低， 可选择方案③， 此方案相比于现场 固定派车方案虽然成本增加了6.2， 但其产量增加 了17.4。 综上所述， 本研究在满足矿山需求的情况下， 给 出全面的、 优良的决策空间， 帮助企业减少运输成 本， 提高设备使用率， 是一种适用于露天矿卡车调度 的方法。 4结论 （1） 基于多目标优化理论， 综合考虑矿山卡车调 度的诸多影响因素， 以运输成本最小， 卡车总的等待 时间最小为目标函数构建了多目标优化调度模型。 该模型反映了矿山的多种优化需求， 较完整地描述 了卡车动态分配的过程和目的。 （2） 采用多目标遗传算法对模型求解， 得到了 Pareto最优解集， 求解时针对矿山的岩石量优先原 则， 采用偏好因子促使种群更加合理， 成功解决了露 天矿卡车调度问题。 （3） 本研究可为露天矿卡车调度提供具体合理 的优化调度方案以及调度决策依据， 大大降低卡车 运输成本， 提高设备使用率， 是一种适用于露天矿卡 车调度的方法。 参 考 文 献 古德生.智能采矿触摸矿业的未来 ［J］ . 矿业装备， 2014 （1） 24- 26. Gu Desheng. Intelligent mining touches the future of mining［J］ . Mining Equipment， 2014 （1） 24-26. 顾清华， 卢才武， 江松， 等.采矿系统工程研究进展及发展趋势 ［J］ .金属矿山， 2016 （7） 26-33. Gu Qinghua，Lu Caiwu，Jiang Song，et al. Technical progress and development trends of mining systems engineering［J］ . Metal Mine， 2016 （7） 26-33. 马兄， 连民杰， 卢才武， 等.数字矿山信息集成概念模型 ［J］ .金 属矿山， 2014 （7） 135-140. Ma Xiong， Lian Minjie， Lu Caiwu， et al. Conceptual model of digi- tal mine ination integration［J］ . Metal Mine，2014（7） 135- 140. 白春妮， 卢才武， 顾清华.基于GIS/BDS/GPRS的露天矿爆堆数据 管理系统 ［J］ .金属矿山， 2015 （3） 148-151. Bai Chunni，Lu Caiwu，Gu Qinghua. Open pit muckpiles data management system based on GIS /BDS /GPRS［J］ . Metal Mine， 2015 （3） 148-151. 李军才， 蔡美峰.金属露天矿山汽车自动调度系统及其应用 ［J］ . 中国矿业， 2003， 12 （1） 35-38. Li Juncai， Cai Meifeng. Development and application of truck auto- matic dispatching system in open pit mine ［J］ . China Mining Maga- zine， 2003， 12 （1） 35-38. 陈晓青.金属矿床露天开采 ［M］ .北京 冶金工业出版社， 2013. Chen Xiaoqing. Open- pit Mining of Metal Deposits［M］ .Beijing Metallurgical Industry Press， 2013. Alarie S， Gamache M. Overview of solution strategies used in truck dispatching systems for open pit mines ［J］ . International Journal of Surface Mining， 2002， 16 （1） 59-76. Cetin N. Open-pit Truck/Shovel Haulage System Simulation ［D］ .Is- tanbul， TurkeyMiddle East Technical University， 2004. Zhang L， Xia X．An integer programming approach for truck-shov- el dispatching problem in open- pit mines［J］ .Energy Procedia， 2015， 75 1779-1784． Bastos G S. Decision making applied to shift change in stochastic open-pit mining truck dispatching ［J］ .IFAC Proceedings Volumes， 2013， 46 （16） 34-39． 孙效玉， 田凤亮， 张航， 等.兼顾固定配车需要的露天矿车流规 划模型 ［J］ .煤炭学报， 2016， 41 （S2） 583-588. Sun Xiaoyu， Tian Fengliang， Zhang Hang， et al. Traffic flow mod- el in open pit mine for needs of fixed assignment of truck ［J］ . Jour- nal of China Coal Society， 2016， 41 （S2） 583-588. Godoy M，Dimitrakopoulos R. Managing risk and waste mining in long-term production scheduling of open-pit mines ［J］ . SME Trans- actions ， 2004， 9 （9） 43-50. Souza M J F，Coelho I M，Ribas S，et al. A hybrid heuristic algo- rithm for the open-pit-mining operational planning problem ［J］ . Eu- ropean Journal of Operational Research，2010， 207（2） 1041- 1051. Coelho V N，Souza M J F ，Coelho I M，et al. Multi-objective ap- 2019年第6期张明等 基于多目标遗传算法的露天矿卡车调度优化研究 161 ChaoXing ［15］ ［16］ ［17］ ［18］ proaches for the open-pit mining operational planning problem ［J］ . Discrete Mathematics， 2012， 39 （2） 233-240. Mendes J B， D Angelo M F S V， Maia N A ， et al. A hybrid multi- objective evolutionary algorithm for truck dispatching in open-pit- mining［J］ .IEEE Latin America Transactions， 2016， 14（3） 1329- 1334. 李宁， 叶海旺， 吴浩， 等.基于混合粒子群优化算法的矿山生 产配矿 ［J］ .矿冶工程， 2017， 37 （5） 126-130. Li Ning，Ye Haiwang，Wu Hao，et al. Ore blending for mine pro- duction based on hybrid particle swarm optimization algorithm ［J］ . Mining and Metallurgical Engineering， 2017， 37 （5） 126-130. 李瑞， 胡乃联， 李国清， 等.基于多目标0-1规划的采掘作业计 划优化 ［J］ .金属矿山， 2017 （2） 102-108. Li Rui，Hu Nailian，Li Guoqing，et al. Optimization of mining op- eration plan based on multi-objective 0-1 programming ［J］ . Metal Mine， 2017 （2） 102-108. 黄冀卓， 王湛， 马人乐.一种新的求解约束多目标优化问题的 遗传算法 ［J］ ．计算机工程与应用， 2006， 42 （23） 47-51． Huang Jizhuo， Wang Zhan， Ma Renle. A new genetic algorithm for constrained multiobjective optimization problems ［J］ . Computer En- gineering and Applications， 2006， 42 （23） 47-51． （责任编辑石海林） 金属矿山2019年第6期总第516期 162 ChaoXing