露天矿的生产安排

【摘要】：

本文主要解决的是如何安排生产计划，可以在消耗最少资源的情况下，达到理想的产量要求。由于每辆车的路线不一定固定，文章通过先求出每条路线上的车次数，再对车辆进行分配达到解决问题的目的。

首先解决铲位问题，若任意选出7个铲位，有120种排列组合，计算复杂度较大，基于此，我们采用贪心法，按照卸点的距离、产量、品位等要求依次取得最优、次优…等若干较优铲位。据此方法得到4个铲车安排方案。

全文以车次为决策变量，针对原则一，以总运量最大，总车辆数最少为目标，以各卸点的产量和品位要求，各铲位及卡车的资源，卡车持续工作不等待等作为约束，建立双目标线性规划模型。值得一提的是，我们巧妙的对每条线路上，一辆车从铲位出发到再次回到铲位所用时间内，铲车服务的车辆数进行了约束，以此满足卡车不等待的要求。分别对上述4种安排方案运用2种方法求解，方法一：单纯形法，先不考虑车辆数，保留总运量最大为目标进行求整数解，若有相同解，选择车辆数最少的解。方法二：采用回代搜索的方法，不考虑总运量，以车辆数最少为目标求整数解，然后分别以最少车辆数到20之间的数为车辆数进行回代，求解出总运量最小的解。再从解得的4种结果中选择最优，得到铲车安排方案及每条线路的车次。针对原则二，我们在上述建立的模型基础上，将目标改为总产量最大，约束不变，建立线性规划模型。分别对4种方案求解，再择其最优。

根据每条线路上的车次，本文再次利用贪心法，先安排固定线路的卡车，再根据剩余车次安排需要改变路线的卡车，安排不唯一，文中给出了其中一种安排方案。

利用lingo软件对文中模型求解，得到结果：针对目标一，出动7台铲车，分别安排在1,2,3,4,8,9,10七个铲位，出动13辆卡车，具体方案见表7，按此方案得到总运量约为8.6万吨公里，总产量约为7.0万吨。矿石产量约为3.8万吨，岩石产量约为3,2万吨。针对目标二，铲车安排与目标一相同，出动20辆卡车，具体方案见表8，按此方案得到总运量约为14.7万吨公里，总产量约为10.3万吨。矿石产量约为5.4万吨，岩石产量约为4.9万吨。

最后，本文对模型的优缺点进行了分析，并做了改进与推广。

【关键词】：贪心法 铲位安排 车次 线性规划 

一、问题的重述

某露天矿共有10个铲位、5个卸点，现有铲车7台，卡车20台。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）见表1，每个铲位至多能安排一台电铲，电铲的平均装车时间为5分钟。

卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。

所用卡车载重量为154吨，平均时速28。卡车的耗油量很大，每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。

每个铲位到每个卸点的道路都是专用的宽60的双向车道，不会出现堵车现象，每段道路的里程见表2。

要求按照以下两个原则分别建立数学模型：1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。给出一个班次生产计划的快速算法，并制定一个生产计划，包括出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次，使得在卡车不等待条件下满足产量和品位要求。

表1：各铲位矿石、岩石数量(万吨)和矿石的平均铁含量

该问题实际上是要求得到每辆车的运输方案。由已知，不难求出一辆车一个班次内里在卸点i与铲位j之间可往返的次数，基于此，我们可以通过求出每条路线上的车次数达到解决问题的目的。

无论是对往返次数还是车次数的求解，首先应对7台铲车进行安排。若用排列组合的方法，有120种，计算复杂度太大，结合实际，可用贪心法选择较优的铲位，余下的再进行排列组合，便可确定较优的铲车安排方案。

分析题目可知，目标及各个产量要求、品位要求均为每条线路上车次的一次函数，故可用线性规划求解。分别以两个原则之一为目标，以铲位资源及卸点要求等为约束建立2个线性规划模型，对贪心法筛选过的铲车安排方法分别求出其线性规划的最优解，然后在其中再选出最优者，可得最优的铲车安排和车次。再次利用贪心法，先安排固定路线的卡车，然后安排改变路线的卡车，便可得到每辆车的运输方案。

三、模型的假设

假设1：不考虑意外事故等随机因素对运输过程造成的影响，卡车空载和满载时速度均为28km/h.

假设2：假设电铲和卡车在一个班次内不会出现机器故障等状况，可以不停地工作。

假设3：卡车的路线可以不固定，可以在不同路线上进行调度，且在改变路线时耗费的时间不计。

假设4：各铲位之间与各卸点之间相互。

假设5：在一个班次内，铲车的位置固定不变。

四、符号说明

5.1 铲车的安排

基于分析，采用贪心法对铲位进行选择。贪心法的思想是：每次选择当前最优的点，如不满足条件，再选择次优点，以此类推。通过分析知，铲车应先选择距离卸点最近的铲位，才能以最小的运量获得足够的产量，若此铲位不能满足产量要求，再取次近的铲位，若不能达到品位要求，还需要选择可以平衡品位的点。

由已知各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。根据各铲位和各卸点之间的距离表1，先选择距离矿石漏最近的铲位9，其产量为1.35，铁含量33%，产量可以达到要求但品位超标，再选择可均衡品位的最近的铲位－铲位3。同理，根据倒装场1选择铲位2和铲位4；根据倒装场II选择铲位10和铲位1；根据岩场选择铲位9和铲位3；根据岩石漏选择铲位1和铲位3。由此可确定铲位1、2、3、4、9、10六个铲位，再从剩下的四个点中选取一个即可，经过这种方法筛选后的铲车安排方法为4种．

表3

对于筛选后的铲车安排方法，建立整型线性规划模型逐一求解，再择其最优。将选择的7个铲位的标号重新标为1,2,3…7。

5.2.1针对原则一建立模型：

原则一要求总运量最小，同时出动最少的卡车，从而使得运输成本最小，由此很容易想到建立一个双目标规划模型。

根据总运量最小得到第一个目标函数 

根据出动最少的卡车数得到第二个目标函数 

约束条件：

约束1：各个卸点的产量需要达到要求，即

                                     (1)

约束2：各个卸点的品位需要达到要求，即

下限                            （2）

上限                            （3）

约束3：各个铲位的矿石（岩石）的运出量不能超过该铲位的矿石（岩石）数量，即

矿石                             (4)                                

岩石                               （5）

约束4：由于铲车每次装载需分钟，故一个班次内最多可装载60T／=480／5=96次，即                  (6)

约束5：同理，由于卸点每次卸载需Tb分钟，故一个班次内最多可卸载60T／Tb=480／3=160次，即                   (7)

约束6：由于一辆卡车在卸点i与铲位j之间往返行驶一次需分钟，装卸需分钟，共需分钟，这条线路上一辆卡车一个班次内可往返次，（[ ]表示向0取整），则该线路需要卡车，卡车总数最多不能超过M=20辆，即 

                                               (8)

约束7：每条线路上的车辆在工作期间不出现等待，即

             (9)

约束8：为非负整数               (10)

综上所述，可得到如下所示双目标线性规划模型：

用两种方法将该模型转化成单目标线性规划求解，方法一：首先以总运量最少为目标函数，不考虑使用的卡车数。若求得多组解，则取其中使用卡车数最少的解。方法二：先不考虑总运量，以最少卡车数为目标函数，然后将求得的最少卡车数到20之间的卡车数回代，以总运量为目标逐一求解，并通过比较选取总运量最小的一组解。

5.2.2针对原则二建立模型：

原则二要求利用现有车辆运输，获得最大产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。相对于原则一所建立的模型，主要区别是目标函数不同，其约束条件均相同，只需改变目标函数即可

目标函数：

产量：    

约束条件：同5.2.1中约束1至约束8

如有多组解满足最大产量，依题目要求取，即岩石产量优先，如果岩石产量相同，依题取，即总运量最小的解．

5.3 运输方案的确定

选取最优解中每条路线的车次，即可为每辆卡车安排行驶路线及运输次数．由可知共需要13辆卡车．再次采用贪心法，使每辆卡车发挥最大工效，先安排固定路线的卡车，然后安排改变路线的卡车。以下以模型1得出的运输方案求解过程为例。

对模型1进行求解得到每条路线的车次数如表4

表4

表5

表6

在改变路线的6辆车中：

第一辆：在1-2线路运输13次，剩余时间分钟，可以继续在1-8线路运输次．剩余时间极小，忽略，此时1-8线路剩余车次25-5=20．

第二辆：在1-8线路运输20次，剩余时间分钟，可以继续在1-10线路运输次．剩余时间极小，忽略，此时1-10线路无剩余车次．

第三辆——第六辆的安排方法同上．

按上述方法，即贪心法计算剩余时间，即可得到具体的车辆安排，问题得解．

六、模型的求解

运用lingo软件求解得到如下结果：

目标一

出动7台铲车，分别安排在1,2,3,4,8,9,10七个铲位。总运量85628吨公里8.6万吨公里，总产量70378吨7.0万吨，磁矩石产量38192吨3.8万吨，岩石产量32186吨3.2万吨，出动13辆卡车，分别编号为1,2…13，每辆车的具体安排如下表(不唯一)：

表7

出动7台铲车，分别安排在1，2，3，4，8，9，10七个铲位。总产量103488吨10.3万吨 ，总运量146791吨公里14.7万吨，公里矿石产量54308吨5.4万吨，岩石产量49280吨4.9万吨，出动20辆卡车，分别编号为1,2…20，每辆车的具体安排如下表(不唯一)：

表8

模型优点：

1、运用贪心法快速求得铲车的可能位置，简化了计算，同时与现实生活接近

2、采用线性规划的思想，化整为零，使模型简化，大大减少了模型的复杂度

3、可移植性强，对于类似的露天矿运输安排，该模型均适用

模型缺点：

1、没有考虑卡车改变路线时消耗的时间，使得对改变路线的车次安排不唯一，且求解的产量比实际偏高。

2、若换一个露天矿，运用贪心法选择铲车位置时可能有多余7个较优点，则不能较快的选择，有一定的机遇性。

模型的改进和推广：

1、题目中卸点之间和铲点之间相互，而在实际的运输问题中，经常允许在卸点之间进行运输。于是我们可以求得各卸点之间的距离，对模型1改进后求解。由于时间关系我们没有求出结果。

2、在卸点可移的情况下，每个铲点和卸点之间的距离发生改变，就会产生很多组距离数据。每一组数据都可带进模型1求解，在所有的解中，可选出一组是运输成本最低的解。从而根据卸点的选择来降低运输成本。

参考文献

[1]袁新生，邵大宏，郁时炼．露天矿生产车辆的优化安排．北京：科学出版设2007

[2]于俊泊，肖川，楚玉强．露天矿生产的车辆安排

[3]黄振，黄际洲，黄鑫．露天矿的车辆安排