露天矿生产的车辆安排模型大学论文

露天矿生产的车辆安排模型摘要本文成功引入了车次的概念。

在对时间进行合理假设之后，在约束条件下建立了对车次的全局最优的整数线性规划，利用lindo软件迅速解出全局最优的任务分配。

进一步，利用效率优先原则，对铲点进行优化，并根据物件可分的等容积装箱模型，最终得到了满足要求的计划安排。

根据原则一建立模型的解为：铲位：1、2、3、4、8、9、10，卡车数：13，总运量：8.56万吨·千米，车辆安排计划见表9；根据原则二建立模型的解为：铲位：1、2、3、4、8、9、10，卡车数：20，最大产量：10.35万吨，岩石量：4.93万吨，在最大产量下的最小运量：14.69万吨·千米车辆安排计划见表14。

一、问题的重述露天矿里有若干个爆破的铲位，已预先根据铁含量被分成矿石和岩石两种不同的石料。

每个铲位至多配备一台电动铲车进行装车，并由电动轮自卸卡车将矿石和岩石分别运送至各自的卸货地点，满足各卸点的产量和品位要求（29.5% 1%）。

卡车有其本身的平均速度，随机的装卸时间和载重。

根据所给定的条件，根据以下两条原则分别建立数学模型，并给出一个班次生产计划的快速算法，原则上在安排时不应发生卡车等待的情况。

1、总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；2、利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。

二、问题分析1、本题是一个有约束条件的组合优化问题，涉及到单车型多货种送货满载车辆的优化调度，因而属于NP难题（文献[1]），随着系统规模的扩大，问题的求解难度也大大增加，求解时间呈几何级数上升。

2、本问题最先应着重解决的是车辆的等待问题。

车辆在铲位和卸点的等待主要由三方面引起：(1) 随机因素造成运输和装卸时间不精确从而形成等待；(2) 由于车辆在不同道路上循环的周期不同所偶尔出现的在时间上的重叠。

这种交叉的可能性伴随着道路承载车辆数目的增加而增加，但也可以通过车辆自身的调整而加以避免，例如：改变路线、改变速度等；(3) 若车辆的密度超过了道路、铲点或卸点所能容纳的最大限，则在任意一个周期内都会出现的等待现象。

在本题的条件下，第一种情况中的随机装卸和运输时间概率分布方差无法确定，故此时我们只能将其近似视为恒定，从而解决了随机时间所造成的等待。

第二种情况的等待是可以预期的，但在速度恒定的前提下，只有通过临时改变路线的方法才可避免，将使问题的复杂性显著提高，而在一个班次的短暂时间内形成的影响却并不是很大，为了严格达到要求却引进了庞大的计算量，显然是很不可取的。

第三种情况是我们唯一也必须要考虑的。

车辆平均速度相同，且道路足够宽，则车辆在路上不会拥塞，只有在装卸点才会发生等待，如果与同一装卸点相连的车辆过多，则出现等待不可避免，这是无法容忍的。

因此，在我们的模型中，着重避免的是第三种类型的等待。

3、车辆所要完成的任务只有量的要求而已，即只要考虑在规定时间内运了多少次货即可，不需要再拘泥于该线路上运作车辆的数目。

因此为了更好的表述这个概念，我们在模型中引入了一个在生活中常用的概念——车次。

它的定义为：所有车辆经过铲点或卸点的次数。

它与运量直接相关，满足以下关系式：产量 = 车次×载重引入车次的概念后，完成相同数目的车次任务，可以用多辆车同时在短时间内完成，也可用少量车在长时间内完成。

但一个固定路线（包含多个单一路线）的车次必然决定了其所需的最少车数，满足以下关系式：最少车数×班次时间 = Σ（车次×路线周期）在上式中，最少车数可以取小数，表示在某一固定路线的任务完成过程中，某一车可以在完成自己任务后，换至其他路线，从而实现车辆的最大利用。

本模型最终要得到的是对车辆的安排计划。

根据上式，加上应有的约束条件后，求得车数就可求得最大车次，相反，求得各路线车次后即可求得所需的最少车数。

这样，问题就转化为对车次的最优化问题。

三、模型的条件和假设题目中重要条件的重述： 1、卡车每次满载运输；2、一个铲位至多只有一部电铲；3、卸点和铲位在一个班次内固定不变；4、由于随机因素影响，装卸时间与运输时间都不精确，排时计划无效。

5、矿石漏、倒装场只卸矿石，对矿石有品位限制；岩石漏、岩场只卸岩石，没有品位限制。

模型基本假设：1、车辆的等待主要由车辆的密度超过了道路、铲点或卸点所能容纳的最大限额所引起。

2、卡车在转换线路时不计时间损耗3、卡车的速度，等待时间记恒量，为其平均值。

四、名词和符号的约定名词约定：铲位：露天矿里爆破生成的石料堆，每堆称为一个铲位 铲点：有电铲工作的铲位 卸点：卸下矿石或岩石的地方 品位：矿石的含铁量原题中涉及到的常量： 卡车满载重量：154W t = 卡车平均速度：28/V km h = 平均装车时间：5min up t = 平均卸车时间：3min down t = 一个班次： 8480min T h == 品位限制： []28.5%,30.5%Q ∈自定义变量：总产量： E 总运量： G 总车数： P 矿中铲点的数目： m 矿石卸点的数目： 1n ， 岩石卸点的数目： 2n铲位中矿石产量： ,1,2,i M i m =… t铲位中岩石产量： ,1,2,,i S i m =… t各铲位矿石含铁量： %i ρ铲位i 到卸点j 的距离： ,1,2,,ij D i m =… 1,2,,j n =… km 铲位i 到卸点j 的运输次数： ij N 卸点一个班次产量要求： j C 各运输线上的卡车数： ij n 各运输线上卡车循环时间： ij T 单线单车一个班次内的车次： ij R五、模型的建立和求解首先将各铲点、卸点抽象成二分图中的结点，运输道路的路径抽象成边，并以彼此间距离定义边的权重矩阵×m n D 。

1、考虑第一条原则时的模型即在满足各卸点产量和品位的前提下，使运输成本最小化。

(1) 铲点数目满额时的模型(即铲点数＝铲位数) 原问题可抽象成对运输成本的多目标规划模型：121212111111min ()min n n m ijij i j n n m ij n n m i j ij i j G W ND P P K T +==++=====⎡⎤⎢⎥⎢⎥=+⎢⎥⎢⎥⎢⎥∑∑∑∑∑∑ ..S t11n iijj M N W =≤∑ 保证运走的矿石不会超过铲点的供给量； (1) 1211n n iij j n S N W +=+≤∑保证运走的岩石不会超过铲点的供给量； (2) 1mj iji C NW=≥∑保证满足各卸点的产量要求；(3)1128.5%m ijii miji NNρ==≥∑∑保证满足各卸点的品位要求； (4)1130.5%mijii m iji NNρ==≤∑∑保证满足各卸点的品位要求； (5)1mij i downT N t =≤∑ 保证满足所有铲点在一个班次内可容纳的车次 (6)121n n ij j upTN t +=≤∑保证满足所有卸点在一个班次内可容纳的车次 (7)定理：达到总运量最小时所用的车数即为最少应派遣的车数。

证明：由各运输线上要求的总运行车数和每车的循环时间，可求得在该线上卡车运作的总时间为：ij ij ij ij N T TK P =+ 其中2()60ijup down ij D t t T V +=+，ij K 为始终在该运输线上运作的车数，ij P 为需要额外调用的车时。

则矿场中总共所需的车数为：1212121211111111()n n n n m m ij ij ij ij n n n n m m i j i j ij ij i j i j P N T TK P K K T T ++++========⎡⎤⎡⎤-⎢⎥⎢⎥⎢⎥⎢⎥=+=+⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥∑∑∑∑∑∑∑∑ 1211n n m ij ij i j N T T +==⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥∑∑12112()()60n n m ij ij ij up down i j N D N t t TV T +==⎡⎤+=+⎢⎥⎢⎥∑∑ 由于T 、up t 和down t 可看作常数，而在总产量固定的，111n mij i j EN W===∑∑也为一个常数，则总运量D 最小即可保证派遣的车数最少。

据此定理，原题中的双目标规划问题便可简化为单目标规划，只需对总运量进行规划。

则该模型即可转化为一个标准的整数规划模型，可用lindo 等软件进行求解，当矿场规模不是很庞大的时候，可以以较快的速度寻取全局最优解。

(2) 铲点数目受限时的模型根据前一个模型的求解结果，可以算出每一台电铲的利用率，并根据利用率优先原则进行排序，每次剔除一个铲点，直至铲点数目满足要求。

电铲利用率可用以下算式定义（文献[2]）：1F f T=-其中F 为一个班次内累积电铲总空闲时间。

该模型的求解与铲点数目满额的模型求解完全一样，每减少一个铲点即在二分图上删去对应的结点和关联的边，确定新的权重矩阵。

但是对于该模型的求解还可以再提出两条简化方法：1、若算出某一电铲的利用率为0时，则可以在舍弃后不必对模型重新求解，直接进行下一步骤的计算。

因为利用率为0的铲点一定不与任一卸点相联，故一定是孤立点。

将其从二分图中删去时不会对其求解结果造成影响。

2、根据在问题分析中提及的车次的概念，可以将电铲利用率f 的求解转化为简单的整数求和。

电铲利用率的高低即为与该铲点相连的所有运输道路的车次之和，不需要再利用以上算式进行复杂计算。

2、考虑第二条原则时的模型即在车辆数目给定地前提下，使产量最大化。

该模型和基于第一条原则建立的模型结构类似，约束条件(1)，(2)，(4)，(5)，(6)，(7)可仍然予以保留。

目标函数更改为：211maxn jj n C=+∑ 121maxn n jj C+=∑双目标规划添加约束条件： 20P ≤当岩石卸点达到满负荷时，即岩石产量达到最大时，则可以去掉211maxn jj n C=+∑这个目标函数，使得多目标规划问题简化为单目标规划。

其求解方法与第一问类似。

六、对实际问题的求解和结果分析针对题目中所给出的实例进行求解。

1、考虑第一条原则时的求解 (1) 铲点数目满额时的模型求解经由lindo 软件求解，得到各运输道路上的车次ij N 。

(相关程序见附录1)算得总运量121185607n n m ij ij i j G W N D tkm +====∑∑卸点目标车次的求取：j C W ⎡⎤⎢⎥⎢⎥铲点约束车次的求取：i M W ⎢⎥⎢⎥⎣⎦ —— 矿石产量约束 i S W ⎢⎥⎢⎥⎣⎦—— 岩石产量约束此方法优化效果非常好：1．到达卸点的实际车次与需要的车次吻合； 2．到达铲点的实际车次小于或等于约束车次；3．满足品位要求，由表可见已趋于满足极限要求，即部分已到达30。