（管理科学与工程专业论文）模糊优化在露天矿车辆调度中的应用.pdf

中文摘要 摘要 在露天矿的开采中，运输成本和能耗占矿山开采成本的绝大部分，车辆优化 调度是降低采运设备非生产时间、提高生产效率、从而降低整个采矿成本的行之 有效的办法。露天矿车辆调度是复杂的优化问题，现有的方法大部分是基于确定 性信息的，不能有效处理调度面临的模糊问题。 本文首先根据露天矿调度工作的任务、目标及系统功能需求，总结了几种常 用的露天矿车辆调度模型。然后以鞍山一矿山企业为例全面分析了车辆调度问题 的约束条件，建立了确定型的露天矿车辆调度模型。接着在露天矿车辆调度确定 型模型的基础上，根据现实中的各种模糊因素分别建立了车辆调度的单目标和多 目标模糊模型，并运用模糊优化算法对其进行了分析，算例表明模糊优化模型能 够更好的满足需要。 本文在对车辆调度模型模糊优化分析的过程中，首先研究了单目标模糊优化 算法，其中对含有模糊系数的模糊线性规划算法进行了详细的研究，当系数为三 角模糊数时，提出了一种新的算法，此种算法的约束更少，更易于求解。然后研 究了经典多目标线性规划问题的折中算法、m a x - m i n 模糊算法及m a x m i n 模型与 平均模型相结合的两阶段模糊算法。最后研究了含模糊数的多目标线性规划的模 糊优化算法。 本文最后分析和设计了露天矿车辆调度模拟系统，并研制了矿山车辆调度优 化应用程序，实现了矿山车辆调度的智能化和自动化，促进了运输部门管理的科 学化、信息化进程。 关键词：模糊优化；车辆调度；多目标规划；露天矿 英文摘要 a p p l i c a t i o no ff u z z yo p t i m i z a t i o nf o rv e h i c l es c h e d u l i n gs y s t e m i n s u r f a c em i n e a b s t r a c t i ns u r f a c em i n i n g , t h ec o s to ft r a n s p o r t a t i o na n de n e r g ya c c o u n t sf o rt h em a j o r i t y o fm i m n gc o s t o p t i m a lv e h i c l ed i s p a t c hi st h em o s te f f e c t i v em e t h o dt or e d u c e n o n - p r o d u c t i o n t i m ea n di m p r o v ep r o d u c t i o ne f f i c i e n c y v e h i d es c h e d u l i n gi sa c o m p l e xo p t i m i z a t i o np r o b l e m , a n dm o s to ft h ee x i s t i n gm e t h o d sa reb a s e do nt h e c e r t a i n t yo fi n f o r m a t i o na n dc a n n o te f f e c t i v e l ys o l v et h i sp r o b l e m f i r s t , s e v e r a lc o m n l o nv e h i c l es c h e d u l i n gm o d e l sa l em e n t i o n e da c c o r d i n g t ot h e m i s s i o n ，t a r g e ta n ds y s t e mf u n c t i o nr e q u i r e m e n to fd i s p a t c hw o r k t h e na n s h a nm i n e c o m p a n yi st a k e nf o re x a m p l e ，t h ev e h i c l es c h e d u l i n gm o d e li se s t a b l i s h e da f t e r c o m p l e t e l ya n a l y z i n ga l lt h ec o n s t r a i n tc o n d i t i o n s b a s e do i lt h i sv e h i c l es c h e d u l i n g m o d e l ，s i n g l eo b j e c t i v ea n dm u l t i o b j e c t i v ev e h i c l es c h e d u l i n gf u z z ym o d e l a le r e s p e c t i v e l ye s t a b l i s h e db ya n a l y z i n gs o m ec r i t i c a lf u z z yf i c t o r sa n dt h e yf i l ea n a l y z e d b yf u z z yo p t i m i z a t i o na l g o r i t h m f u z z yo p t i m i z a t i o n m o d e li sd e m o n s t r a t e db y e x a m p l e s i nt h ep r o c e s so ff u z z yo p t i m i z a t i o na n a l y s i sf o rv e h i c l es c h e d u l i n gm o d e l ，s i n g l e o b j e c t i v ef u z z yo p t i m i z a t i o na l g o r i t h mi sf i r s t l ys t u d i e d f u z z yl i n e a rp r o g r a m m i n g a l g o r i t h mw i t hf u z z yc o e f f i c i e n t si se l a b o r a t e l ys t u d i e d an e wa l g o r i t h mw i t ht r i a n g l e f u z z yc o e f f i c i e n t si si n t r o d u c e db a s e do np r e v i o u sr e s u l t s t h i sa l g o r i t h mh a sf e w e r c o n s t r a i n t sa n dc a nb ee a s i l ys o l v e d t h e nf o rc l a s s i c a lm u l t i - o b j e c t i v e l i n e a r p r o g r a m m i n g , c o m p r o m i s ea l g o r i t h m ，m a x m i nf u z z ya l g o r i t h ma n dt w op h a s e sf u z z y a l g o r i t h ma r es t u d i e d a tl a s t ，f u z z yo p t i m i z a t i o na l g o r i t h mo fm u l t i o b j e c t i v ef u z z y l i n e a rp r o g r a m m i n gw i t hf u z z yn u m b e ri ss t u d i e d i nt h ee n do ft h i sp a p e r , t h ev e h i c l es c h e d u l i n gs y s t e mo fs u r f a c em i n ei sa n a l y z e d a n dd e s i g n e d ，a n dt h ep r o g r a mo fv e h i c l es c h e d u l i n gi sc a r e f u l l yd e v e l o p e d t h e i n t e l l i g e n c ea n da u t o m a t i o no fm i n ev e h i c l es c h e d u l i n gi si m p l e m e n t e da n d t h es c i e n c e a n di n f o r m a t i o np r o c e s so ft r a n s p o r t a t i o nd e p a r t m e n ti sp r o m o t e d k e yw o r d s ：f u z z yo p t i m i z a t i o n ；v e h i c l es c h e d u l i n g ；m u l t i - o b j e c t i v ep r o g r a m m i n g ； s u r f a c em i n e 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写 成博士硕士学位论文竺搓麴馑焦在蘑丞芷奎牺迥廑主趁廑旦：。除论文中已经 注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表 或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：醵襄李、砌，降十月? 日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密睹磊在以上方框内打。 ) 论文作者签名：多臣反杰导师签名： 日期： 加d 孑年争月 谰修， 模糊优化在露天矿车辆调度中的应用 第1 章绪论 1 1 研究背景 采矿业是资源开发与利用的一个重要行业，而在采矿行业中露天矿开采占有 相当的比重，它是各类有价矿产开采的主要方式，1 9 9 1 年我国铁矿石产量1 7 8 2 2 万吨，其中露天矿开采占8 5 以上，露天采掘总量计4 0 0 0 0 万吨。在有色金属矿石 产量中，铝铜等矿石露天开采也占有相当的比重。就世界上的黑色和有色金属露 天矿来说，露天矿的铁路运输比重占5 5 - 6 5 。在跨入2 1 世纪后，对铁矿石和 有色金属矿石的需求会大幅度的增加，所以露天矿对整个采矿业的发展具有举足 轻重的作用。而要保证露天矿的开采产量，重要的一个环节在于其采运系统的合 理选择和科学管理。在露天开采中，采运系统是指由矿岩运输方式及其所决定的 采掘方式构成的系统，其中运输成本占矿山成本的3 5 4 5 ，能耗占矿山总能耗 的4 0 - - 7 0 。由此得出结论，露天矿生产的高效率很大程度上取决于采运设备的高 效率，对采矿生产的控制可转变为对采运设备的控制，卡车优化调度是降低采运 设备非生产时间、提高生产效率、从而降低整个采矿成本的最为行之有效的办法。 因此，在采矿行业中对运输系统的研究具有重要的意义。 车辆调度问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 是对一系列装载点和( 或) 卸载点，组织适当的行车路线，使车辆有序地通过这些点，并满足一定的目标( 如 里程最短，费用最少) 。 自1 9 5 9 年d a n t z i g 和r a m s e r 首次提出该问题以来，就引起了运筹学、应用数 学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计 划的制定者和管理者的高度重视，成为运筹学与组合优化领域的前沿与热点问题。 各学科的科学家对该问题进行了大量的理论研究与实验分析，并取得了很大的进 展，发表了大量的学术论文。但是大部分论文是基于确定性信息条件( 确定的运量， 确定的丌始服务时间，确定的行驶路程等) 并以运输企业的运输成本( 可以是距离、 时间、费用等) 最小化为目标，而对于不确定性信息( 特别是模糊信息) 条件下的研 究非常少。 第1 章绪论 不确定性是决策分析中存在的普遍现象，在1 9 6 5 年z a d e h 提出了模糊集合的 概念，用隶属函数来刻画元素属于集合的程度，将经典集合的二值逻辑 o ，1 推广 到 0 ，1 区间内的连续值逻辑，从而诞生了模糊集合论，提供了对模糊现象进行定 量描述和分析运算的方法。本文运用模糊优化理论来对露天矿车辆调度问题进行 研究。 1 2 车辆优化调度的发展现状 露天矿车辆调度问题是一个非常复杂的数学问题，涉及到很多的约束和变量， 是车辆调度问题( v e h i c l er o u t i n gp r o b l e m ) 的一个应用。车辆优化调度问题最早由 d a n t z i g 和s e r 于1 9 5 9 年首次提出耐2 1 ，自此，很快引起了运筹学，应用数学， 图论和组合数学，计算机应用科学，管理科学，物流科学等领域专家的极大兴趣， 成为运筹学与组合优化领域的一个热点问题。通过各学科专家的不懈努力，进行 了大量的理论研究和试验分析，取得了很大的进展。 国外车辆优化调度研究已广泛应用于生产、生活的各个方面，如报纸投递及 线路的优化、牛奶陪送及送达路线的优化、电话预定货物的车辆载货和线路设计、 垃圾车的线路优化及垃圾站选址优化、连锁商店的送货及线路优化等等。目前， 研究水平已有很大发展，其理论成果除在汽车运输领域外，在水运、航空、通讯、 电力、工业管理、计算机应用等领域也有一定的应用，还用于航空乘务员轮班安 排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产 系统中的计划与控制等多重组合优化问题【3 】。 但是，在国内该问题的系统研究还不多见，尤其是在矿山企业及矿产资源开 发领域的应用研究更不多见。 1 2 1 车辆优化调度问题分类 车辆优化调度问题是根据问题的空间特性和时间特性的相对重要性来分类 的。自货运车辆优化调度( v s p ) 提出后，许多学者对v s p 从不同角度，按不同的标 准进行了分类。车辆优化调度可根据不同性质具体分为一下几类：【4 】 ( 1 ) 按已知信息的特征分，可分为确定性v r p 和不确定性v r p ，其中不确定 模糊优化在露天矿车辆调度中的应用 性v r p 可以进一步分为随机v r p 和模糊v r p 。 ( 2 ) 按约束条件可分为带能力约束的v r p 、带时间约束的v r p 和带时间窗h 约 束的v r p 。 ( 3 ) 按任务的特征分，有纯装问题和纯卸问题以及装卸混合问题。 ( 4 ) 按任务的性质分，有对弧服务问题( 类似中国邮递员问题) 和对点服务问题 ( 类似旅行商问题) 以及混合服务问题( 如交通车路线安排问题) 。 ( 5 ) 按车辆载货情况分，有满载问题和非满载问题( 多项任务共用一车) 。 ( 6 ) 按运输车辆的类型数目分，有单车型问题( 相同容量) 和多车型问题。 ( 7 ) 按运输车辆路线的类型分，有车辆开放问题和车辆封闭问题。 ( 8 ) 按优化的目标数目来分，有单目标优化问题和多目标优化问题。 1 2 2 车辆优化调度问题的基本算法 ， 根据具体的情况，针对不同类型的v r p 问题的算法也有所不同。目前针对车 辆优化调度问题的求解算法可以说是相当丰富，根据对这些算法本质的分类研究， 基本上可以分为精确算法和启发式算法两大类【5 1 。 ( 1 ) 精确算法 对于精确算法，d e s r o c h e r s 6 1 ，k o h la n dm a d s e n 7 1 ，f i s h e r 8 1 等人做过有关的 研究，其中又可以分为分支界定法、割平面法、网络流算法、动态规划法等。精 确算法可以求得模型的精确解，但是，它的计算量一般随问题规模的增大而呈指 数增长，在求解的过程中需要较长的运行时间。由于这两方面的限制，精确算法 难以真正应用，对此的研究也越来越少。 ( 2 ) 启发式算法 启发式算法是指一种基于直观或经验构造的算法，目标是在可接受的花费( 计 算时间、占用空间等) 下得出待解决问题的满意解，而不是最优解。考虑到v r p 是 强n p 难题，而启发式方法能够比较快地得到满意解，这对解决n p 难题来说有着 不可估量的作用。因此大部分文献中，专家们主要是在构造各种高质量的启发式 算法。 第1 章绪论 目前已提出的启发式算法很多，分类也相当多，按r e g oc e s a r 的分类法有以 下几类： 构造算法 根据一些标准，每一次将一个不在线路上的点增加进线路，直到所有的点都 被安排进线路为止。该类算法的每一步，把当前的线路构形( 很可能是不可行的) 跟另外的构形( 也可能是不可行的) 进行比较并加以改进，最后得到一个较好的可 行构形。另外的构形指，或是根据某个判别函数( 例如总费用) 可产出最大限度节 约的构形，或是能以最小代价把一个不在当前构形上的需求对象插入进来的构形 【9 】 o 构造算法是最早提出用来解决旅行商问题( 简称t s p ) 及v s p 的，这些方法一般 速度快，也很灵活，但这类方法有时找到的解和最优解相差很远。 两阶段法 学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进， 为此提出了两阶段法。第l 阶段得到一个可行解，第2 阶段通过对点的调整，在 始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解来 代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止 【1 0 1 。一般第l 阶段常用构造算法，在第2 阶段常用的改进技术有2 - o p t ，3 - o p t 和 o r - o p t 交换法，这是一种在解的领域中搜索，对初始解进行某种程度优化的算法， 以改进初始解。 一些基于数学规划的算法也属于两阶段法，可以把问题直接描述成一个数学 规划问题，根据其模型的特殊构形，应用一定的技术( 如分解) 进行分划，进而求 解已被广泛研究过的子问题【1 1 1 ，包括先聚类后构造路径法，先构造路径后聚类法 等。 两阶段法是目前成果最丰富，应用最多的一类方法。每一种方法讨论的情况 不尽一致，适用范围也不完相同。 不完全优化算法 以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间。 模糊优化在露天矿车辆调度中的应用 改进优化算法 从一个初始解开始，通过对当前解进行反复局部扰动以达到较好的解。主要 包括禁忌搜索算法、遗传算法、模拟退火算法和人工神经网络方法。 禁忌搜索算法这一概念由g l o v e r 在1 9 8 6 年首次提出，进而形成一套完整算 法。为了回避局部领域搜索陷入局部最优的主要不足，禁忌搜索算法用一个禁忌 表记录下已经到达过的局部最优点。在下一次的搜索中，不再或有选择地搜索这 些点，以此来跳出局部最优点；同时遗忘又使得这些禁忌是弱禁忌，即在一定的 时间后这些禁忌将失效，最终达到全局最优的目的。禁忌搜索算法的搜索速度快， 效率高，适用于大规模的优化计算。但它的主要缺陷是对初始解有较强的依赖性 和搜索过程中只能对一个解操作，所以往往需要使用别的启发式方法先获得一个 较好的初始解。国外已经有许多专家用禁忌搜索算法成功求解了v s p 问题，如 m g e n d r e a u 1 2 】等。 遗传算法是7 0 年代由美国j h o l l a n d 教授和他的学生建立发展起来的，其基 本思想是模拟生物进化中“适者生存”的规律。遗传算法通过保持一个潜在解的 种群进行多方向搜索；采用概率转移来选择部分个体，创造新后代，发展成一种 有效的自适应启发式概率迭代式全局搜索方法，适合数值求解那些带有多参数、 多变量的n p 难题。遗传算法对所解的优化问题没有太多的数学假设，如排序 ( s c h e d u l i n g ) 、路线( r o u t i n g ) 问题、布局( 1 a y o u t ) 问题等，对于各种特殊问题可 以提供很大的灵活性来混合构造领域独立的启发式。但是过早收敛和搜索效率低 等问题是它的主要缺陷。目前国内外已有大量文献【1 3 。1 7 】讨论t s u 用遗传算法解决 v s p 问题的方法，主要是在经验基础上，根据具体问题提出各种不同的编码方式、 交叉算子或变异算子，进行应用比较和改进。 模拟退火算法是由n m e t r o p o l i s 在1 9 5 3 年提出的，是局部搜索算法的扩展。 模拟退火算法用于优化问题的出发点是基于物理中物质的退火过程与一般优化过 程的相似性。它通过模拟固体退火过程，综合了统计物理学和局部搜索方法的思 想，采用m e t r o p o l i s 接受准则，并用一组称为冷却进度表的参数控制算法进程， 使算法在多项式时间内给出一个近似最优解。其不同于局部搜索之处是以一定的 第l 章绪论 概率选择领域中费用值大的状态，理论上说，是一个全局最优算法。近年来，也 有不少专家【1 8 。2 0 1 研究发展了模拟退火算法在v r p 问题中的应用，如s a h t t a h i r u 利用3 - o p t 和模拟退火算法结合来求解v r p 问题，获得了满意的结果。 前面提到的禁忌搜索法、模拟退火法、遗传算法等启发式算法，往往过于复 杂，涉及到复杂的领域转换和求解策略，运算量过大，适合于解决大数据量问题， 在实际的露天矿车辆调度中很难实现和应用。目前解决露天矿车辆调度问题，还 是主要通过建立具有严格约束的数学模型，采用精确的求解算法来解决，但是由 于露天矿车辆调度模型的复杂性，很多计算参数很难确定，模型的建立和求解的 结果有时不能符合实际的需求，这也给模糊优化提供了空间。 1 3 本文的研究内容 露天矿车辆调度问题是一项涉及多学科的系统工程，在研究过程中主要涉及 到了矿山系统工程技术、计算机技术、优化理论、管理信息系统理论等多项现代 技术理论。本文在基于鞍山一矿山企业的实际情况的基础上，主要从以下几个方 面展开工作： ( 1 ) 建立了几种常用的露天矿车辆调度模型，并根据鞍山一企业的实际情况建 立了露天矿车辆调度问题的确定型模型。 ( 2 ) 建立了露天矿车辆调度单目标模糊模型，并运用单目标模糊优化算法进行 了分析研究。 ( 3 ) 运用折衷算法，m a x m i n 模糊算法、两阶段模糊算法分析研究了露天矿车 辆调度多目标确定型模型 ( 4 ) 建立了露天矿车辆调度多目标模糊模型，并运用含模糊数的模糊优化算法 对其进行了分析研究。 ( 5 ) 面向实际，分析、设计和开发了露天矿车辆调度模拟系统，并初步应用到 实际工作中。 模糊优化在露大矿车辆调度中的应用 2 1 车辆路径优化 第2 章露天矿车辆调度模型 2 1 1 道路模型的建立 卡车运输露天矿按其路段位置与质量的不同来划分为主干线，半干线和临时 线。主干线是露天矿建设的固定线路，用于连接采点、卸点等，路面质量好，卡 车在该路面上具有较高的运行速度；半干线是建立在采点、卸点端的半固定线路， 随着矿山工程的发展需定期重新修筑，路面质量较好，车速较低；而临时线是建 立在采点、卸点工作平盘上，用于建立工作面与半干线的运输联系，它随着矿山 工程的发展不断移动，路面质量差，卡车运行速度最低。因此，卡车在矿山道路 上运行时，由于区段的路面质量不同，坡度不同，运行速度差异较大，即使区间 距相同，运行时间也不同，所以对运输系统的描述要充分考虑到路段的自然条件， 才能客观地表征全部露天矿线路状况和相互关系，才能较为准确地计算和统计卡 车在任一路段上的运行时间，从而为路径优化、车流规划提供准确的依据。 把露天矿运输线路系统按其路段的属性划分成区段，简化后恰好抽象成一个 网络系统，各区段构成网络的边，区段之间的衔接点即为网络的节点，网络中边 的权可为运行时问或运输距离。根据露天矿运输系统的特征和构成网络系统节点 和边的稳定性的差异，首先要建立一个只与系统布置及状态有关的基本网络，基 本网络主要描述了固定性较强的干线、半干线系统。每班计划中的采掘位置和排 弃位置确定后，把这些收发点作为新节点，与干线基本网络“搭接 后就形成了 本班的实际的网络系统模型。从而可按照最短路径原则，优化确定各采掘点物料 的去向和路径。 运输道路网络是由其节点和路段组成，对露天矿运输系统而言，其中节点包 括采点、卸点、道路交叉点、中问节点等，而路段应根据线路的性质类型，即线 路的坡度、线路的用途进行划分，具有相同属性的部分划分为同一路段，路段之 间以节点分隔，线路交叉点、边坡点等作为自然节点将线路分隔为路段，每条路 第2 章露天矿车辆调度模型 段用其中心线来代替，表示网路的边或弧。图2 1 与图2 2 表示了道路简化过程 与方法，a 、b 、c 、d 为节点。 、i 0 f o 图2 1 原道路 f i g 2 1o r i g i n a lr o a d 图2 2 抽象后的道路 f i g 2 2r o a d a f t e ra b s t r a c t i o n 随着矿山工程的发展，道路网也在随时发生着变化，为了使道路网络数据能 及时准确地反映矿山道路的实际情况，就需对道路网络数据进行实时更新。另外 j 模糊优化在露天矿车辆调度中的应用 卡车在路段上的运行时间主要受到路段质量的影响。所以在道路网络系统中，路 段权值应为该路段上卡车的运行时间，而不是路段的长度。以运行时间为参数， 求出的最短路径才为最优路径。 2 1 2 最优路径的优化计算 通过研究矿山道路网络图，可以发现，这种图形具有如下特点：图中无自环； 并行边少；悬挂边多。所以矿山运输网络图实际上是一种“树 形简图，符合网 络图的一般概念，可用“迭代法 求出任何两点间的最短路，再用“反向追踪法 找出其最短路径。 设矿山运输系统网络g = ( n ，e ，w ) ，其中n ，e 分别为图g 的节点和边的集合，w 为图g 的权。己知图g 的节点个数为n = n ，对于任意节点j 和k ，且 _ ，露；尼，j = 2 ，3 ，甩，则有最短路方程： d = 0 d ：i i l i n 眠+ w 征) q d 式中： 以节点1 至节点k 的最短路距离； w 疆节点i 到k 的路径权值。 求解最优路径时，给出卡车运行的出发点和目的点的节点号( u ps 和t ) ，按照 d i j k s t r a 算法，只要反复使用迭代公式： d ，( k = m i n ( d ；k - , d ，( 。k 一1 + d 孑一1 ) ( 2 2 ) 当姐时，即可以求出s 至t 的最短路，其中d p ，j = 1 , 2 ，玎是原弧长度。 2 2 车流规划 2 2 1 车流规划模型 露天矿车辆调度系统是一种典型的生产管理自动化控制系统，应具有明确的 管理和控制目标，一般来讲，对于电铲一卡车工艺系统，在满足生产计划约束的 第2 章露天矿车辆调度模型 条件下，保证采、运设备得到充分、有效的利用，使在系统产量已定的条件下， 满足出动作业设备数量最少这一目标；或在系统中出动设备数量已定的条件下， 减少车、铲的非生产性时间，使系统获得最大产量这一目标。 露天矿生产系统可以看作是以采掘点为发点，以排卸点为收点的运输网络系 统，在采掘计划、排卸计划确定后，车流规划模型利用装载点与卸载点之间的优 化路径、在满足一定的约束条件下，如产量、剥采比，配矿要求，电铲优先权等， 对发往各卸载点的车流量进行优化分配，其分配结果是生产计划的具体落实，将 作为卡车调度的基础。 在调度中，把规划的道路运输量与要求分派往的卡车最佳地匹配起来，从而 减少采运设备相互牵制时间、以提高设备利用率，实现露天矿最佳的经济效益。 关于露天矿车辆调度问题，许多专家 2 1 - 2 5 】已做了大量的研究工作，其理论基 础是根据装载点地形、道路及生产量，用最优路线和线性规划的方法计算出优化 的运输路线和车流量。只是追求的目标与约束条件不尽相同，以及基本计算参数 不同而已。归纳起来可表示为如下几种类型： ( 1 ) 班产量最大 q = m a x 嘞 ( 2 3 ) i = lj = l 式中： 卜班内总产量； 嘞班内由装载点i 到卸载点j 的货流量； 由i 号挖掘机工作面到j 号卸载点的最短路径； m ，n 班内装载点，卸载点数。 ( 2 ) 班运输费用最小 式中： c = m i n c f ( 2 4 ) 模糊优化在露天矿车辆调度中的应用 c - 哪运输费用： 勺从采掘点i 到卸载点j 的单位费用； 嘞班内由装载点i 到卸载点j 的货流量； m ，n 班内装载点，卸载点数。 ( 3 ) 班内赢利最大 p = m a x p 驴嘞 i = i j = l 式中： 卜班内总赢利值。 幽i 号电铲采出的矿石到j 号卸载点的获利值； 由i 号装载点到j 号卸载点的货流量； m ，n 装载点，卸载点数。 ( 4 ) 运输功最小 z = i i l i n 嘞s 1 = 1j = l 式中： z _ 班内总吨公里数5 嘞由i 号装载点到j 号卸载点的货流量； 由i 号挖掘机工作面到j 号卸载点的最短路径； m ，n 装载点，卸载点数。 ( 5 ) 出动卡车数量最少 式中： n 二一实动卡车数； ( 2 5 ) ( 2 6 ) r t ln n = m i n 罗( t i + t ) x ，+ ( 乃+ z ) 一) ( 2 7 ) i m 户l 第2 章露大矿车辆调度模型 p 从卸载点到装载点的路径总数； ，第i 条路径的空运时间； l ：第i 条路径的电铲装载时间； a ，第i 条路径的空车流量； n 从装载点到卸载点的路径数； 下 上，第j 条路径的重运时间； 1 ，第j 条路径的卸车时间； v 1 ，第j 条路径的重车流量。 上述目标函数中所用系数参数基本上为费用参数，距离参数和时间参数，其 中费用参数并不是基础的参数，该参数往往是历史资料统计的均值，不但获取的 难度大，而且偏差也大，更不能从卡车调度系统的采集数据中直接提取到，实时 性差，所以费用参数难以适应矿山生产条件多变和发挥计算机卡车调度系统的优 点。而距离参数虽然容易得到，但由于路面类型和质量的不同，卡车的运行速度 差异较大，虽然距离相同，但运行时间有很大差别，就不便于预测卡车的调配效 果。 车流规划模型对于车辆调度系统来讲，不是简单的规划一下车流的去向和路 径，而是计算机车辆调度系统中应用软件的重要组成部分，它规划的结果主要体 现在缩短卡车运行时间，减小非作业时间，从而提高设备效率。因此，车流规划 模型的变量系数应用时间参数描述，目标函数应在满足一定约束条件下，完成既 定生产任务追求实动的卡车数量最少，这样的规划模型才更符合卡车调度系统的 要求。其规划模型的最优解是各装、卸点之间的路径上在单位时间获得的车流量， 这就是卡车调度的依据。在调度中不论采用何种调度准则进行车流的调配，其调 度结果应与车流规划的最优解相接近，车流规划得出的目标函数值就是矿山当前 应有的实动卡车数或要求的单位时间内卡车的运输能力。 模糊优化在露天矿车辆调度中的应用 2 2 2 实时调度模型 实时调度模型即是在车流规划的基础上，应用适当的实时调度准则，根据系 统当前的运行情况，对卡车进行实时调度，给出每台卡车优化的运行方向。 调度准则是卡车调度理论的核心。国内外科技工作者根据不同的具体情况， 提出了多种实时调度准则【2 6 - 3 5 1 ，主要有： ( 1 ) 最早装车法( e l ) 将卡车派往预计能最早得以装车的那台电铲去： ( 2 ) 最大卡车法( m t ) 将卡车派往预计其等装时间最小的那台电铲去； ( 3 ) 最大电铲法( m s ) 将卡车派往预计电铲等车时间最长的那台电铲； ( 4 ) 最小饱和度法( m s d 和m s d t c ) m s d 法是将卡车派往具有最小“饱和 程度的电铲，m s d t c 则在此基础上兼顾了卡车运行周期： ( 5 ) 最小比值方差法( b z f c ) 将卡车派往具有“最小比值方差值”的那台电铲 去； ( 6 ) 固定配车法( f i x ) 将卡车固定地派往某台电铲。 已确定了的需车电铲和可供调配的卡车形成了一个车、铲供求系统，在这个 系统中存在如下特点： ( 1 ) 每个卡车k 都被看作是一个具有供应量s k - - 1 的供应节点，l 台卡车就有1 个这样的供应点； ( 2 ) 每台电铲i 被看作是具有需求量d i 0 的需求节点，n 台电铲就有n 个需求 节点； ( 3 ) 每个供车点k 与每个需车点i 相连，每台卡车都可分配给某台电铲，而每 台电铲都可接受分配来的某辆卡车； ( 4 ) 等待时间q t i kn - - j 被看作是从供车点k 到需车点i 的运输费用。 由上述分析可知，卡车的调配实质上是物资调拨中的一个运输问题，只不过 是费用参数被等待时间所代替而已。因此，卡车实时调度问题就转化成了一个运 输问题的实时求解。 为了使每个分配组合( 车、铲) 总的等待时问最小，给出如下的运输问题模型： 目标函数： 第2 章露天矿车辆调度模型 约束条件： fn d t = m i n i q l 以 上= li = l k s i k = l ，2 ，3 ，1 i = i ， 以d i i = 1 , 2 ，3 ，n k = l ( 2 8 ) ( 2 9 ) ( 2 1 0 ) 式中： q 五卡车k 分配给电铲i 时所需的等待时间； 如卡车k 分配给电铲i 的标识，若卡车k 分配给电铲i 时，以= 1 ，否则， 以= o ； 瓯为卡车k 的供应量，s k = l ； d 电铲i 的需求量，即电铲i 当前的需车数； l 可供卡车数； r 需车电铲数。 模型的解就是当前卡车实时调度的决策，当以= 1 时，就把当前请调卡车 k 沿最短路派往电铲i 去装载。该调度决策能使电铲、卡车效率得到最大发挥，是 极小化卡车运行时问和等待时间的必然结果。同时，使用了各电铲线路的累计生 产率与额定值之间偏差的极小化准则，可避免失控生产情况的发生，保证了生产 剥采比、产量及矿石品质指标能维持在车流规划的范围之内。 2 3 案例分析 2 3 1 案例概述 为了研究的方便和不失一般性，本文对鞍山一矿山实际情况进行了简化。矿 山的生产主要是由电动铲车( 以下简称电铲) 装车、电动轮自卸卡车( 以下简称卡车) 模糊优化在露天矿车辆调度中的应用 运输来完成。矿山的首要任务是提高这些大型设备的利用率来增加露天矿经济效 益。 露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已经预 先根据铁含量将石料分成矿石和岩石。平均含量不低于2 5 的为矿石，否则为岩石。 每个铲位的矿石、岩石数量，以及矿石的平均含铁量( 称为品位) 见表2 1 。每个铲 位至多能安置一台电铲，电铲的平均装车时间是5 分钟。 表2 1 铲位数据 t a b 2 1c h a n w e id a t a 铲位1铲位2 铲位3 铲位4铲位5铲位6铲位7 矿石量 6 l 6 8 6 46 88 48 78 1 岩石量8 17 18 76 87 48 78 1 铁含量 3 0 2 8 2 9 3 2 3 1 3 3 3 1 卸货地点( 以下简称卸点) 有卸矿石的矿石漏、2 个铁路倒装场( 以下简称倒装 场) 和卸岩石的岩石漏、岩场，各卸点一个班次的产量要求：矿石漏7 8 车、倒装 场i8 5 车、倒装场1 1 8 5 车、岩场8 5 车、岩石漏1 2 4 车。从保护国家资源的角度 及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量( 要求都为 2 9 5 1 ，称为品位限制) 搭配起来送到卸点，搭配的量在一个班次( 8 小时) 内满足 品位限制即可。从长远看，卸点可以移动，但是一个班次内不变。卡车的平均卸 车时间为3 分钟。 所用卡车的重量为1 5 4 吨，平均时速2 8 k m h 。卡车的耗油量很大，每个班次 每台卡车消耗近1 吨柴油。发动机点火时需要消耗相当多的电瓶能量，在一个班 次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原 则上在安排时不应该发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆 以上的卡车服务。卡车每次都是满载运输。 每个电铲到每个卸点的道路都是专用的宽6 0 m 的双向车道，不会出现堵车现 象，每个电铲到每个卸点的距离见表2 2 。 第2 章露天矿车辆调度模型 表2 2 各铲位和各卸点之间的最短距离 t a b 2 2s h o r t e s td i s t a n c eb e t w e e nl o a dp l a c e sa n du n l o a dp l a c e s 铲位1铲位2铲位3铲位4铲位5铲位6铲位7 矿石漏5 2 65 1 94 2 l4 0 0 1 9 00 6 41 2 7 倒装场i 1 9 00 9 91 9 01 1 32 0 43 0 93 5 l 倒装场i i4 4 23 8 63 7 23 1 61 6 21 2 70 5 0 岩场 5 8 95 6 l5 6 l4 5 62 4 61 0 6o 5 7 岩石漏 0 6 41 7 61 2 71 8 33 7 25 0 56 1 0 首先对模型做如下假设： ( 1 ) 卡车是从卸点出发，最后回到卸点。 ( 2 ) 一个班次，电铲固定在某一铲位上不动，卸点不移动。 ( 3 ) 不存在由于调度不合理以外的因素而造成的等车现象。 ( 4 ) 一个班次中卡车只有在开始工作时点火一次。 ( 5 ) 由于重车比空车所消耗的油料及能量大得多，故在计算总运量时只考虑重 车的运量。 ( 6 ) 一个卡车在一个班次内可以装矿石也可以装岩石，但不可以混装。 ( 7 ) 卸点与卸点之间没有通路或者路径很长，卡车不允许从一卸点直接到另一 卸点。 ( 8 ) 所给的各个卸点产量为产量下限，卸点存储上限不受限制。 ( 9 ) 为了方便起见，规定卸点按矿石漏、倒装场l 、倒装场2 、岩石漏、岩场 秩序编排序号1 、2 、3 、4 、5 ，铲位则按所给铲位号排序。 2 3 2 案例的模型 露天矿生产追求的目标是在完成既定产量的条件下，使出动的设备数量最少， 或在系统中出动设备数量己定的条件下，使系统产量最大，二者并不矛盾，都是 通过减少设备非作业时问，缩短卡车运行时间，提高设备效率而实现的。但实现 规划目标，必须满足露天矿生产实际所受的约束条件的限制，其约束条件要充分 反映生产系统的实际情况以及矿山发展的要求。主要包括生产计划给定的产量任 模糊优化在露天矿车辆调度中的应用 务，剥采比，采运设备的能力，线路通过能力、配矿要求等。具体来讲，对于露 天矿进行车辆调度必须考虑如下约束条件： ( 1 ) 电铲采装能力约束； ( 2 ) 排卸点处理能力约束： ( 3 ) 剥采比约束； ( 4 ) 矿石质量指标约束； ( 5 ) 采掘计划与排卸计划约束； ( 6 ) 卡车运输能力约束等。 本文采用定铲配车与随机配车相结合的方式调度卡车，即铲车固定在铲位， 但卡车不固定搭配某一铲车，卡车在某一路线上完成运输任务后可以到其他路线 上运输而与其他的铲车搭配。案例的模型如下： 目标函数： ( 1 ) 完成任务前提下总运量( 车公里数) 最小 nm + k m i n z ，= 勘 c 扩 ( 2 1 1 ) i = l3 = 1 式中： z l 总运量，车公里。 嘞第i 个装点到第j 个卸点运输量，车； 巳第i 个装点到第j 个卸点的重载运行距离，公罩； ( 2 ) 利用现有车辆运输，获得最大的产量 nm + k 。m a x z ：= 知 ( 2 1 2 ) l = ij = l 式中： z ：最大产量，车； 约束条件： ( 1 ) 总产量约束( 矿与岩) 第2 章露天矿车辆调度模型 日 1 = 1 j = l m + k g ( 2 1 3 ) 式中： 卜当前尚未完成的岩的产量计划，车； g 一当前尚未完成的矿的产量计划，车。 ( 2 ) 每个卸点的产量约束( 上限与下限，通常只需要下限，上限是多余的) 式中： 勤弓 i = l 勤g i = l j = l m + k j = l m + 七 e 第j 个卸点的剩余计划产量上限，车； g 第j 个卸点的剩余计划产量下限，车； l l 卜_ 一卸岩点数量，个； k 卸矿点数量，个。 ( 3 ) 每个装点的产量约束( 矿和岩的资源约束，通常是上限) x i j d f i = 1 ，z j = l m + k 冬c i i = 1 以 j = m + l 式中： d ；第i 台铲车的岩石的剩余计划产量上限，车； e 第i 台铲车的矿石的剩余计划产量上限，车； n 装点数量，个。 ( 4 ) 品位约束 ( 2 1 4 ) ( 2 1 5 ) 模糊优化在露天矿车辆调度中的应用 e t a f e ，x , j - o ，j = m + l ，m + k 扣1 ( 2 1 6 ) z r a 厂a 。】宰x t j 0 f = l 式中： a 。第i 铲处矿石的铁含量，百分比； 岛第j 个卸点的品位下限，百分比： d ，第j 个卸点的品位上限，百分比。 ( 5 ) 剥采比约束 nn