完全版露天矿生产的车辆安排.docx
《完全版露天矿生产的车辆安排.docx》由会员分享，可在线阅读，更多相关《完全版露天矿生产的车辆安排.docx（40页珍藏版）》请在冰点文库上搜索。
完全版露天矿生产的车辆安排
露天矿生产的车辆安排
摘要
本文阐述了露天矿生产过程中的车辆安排问题。
我们通过对模型的简化，将露天矿生产的车辆安排归结为一个多重目标多重约束的规划问题。
首先我们跟据题给的要求，对原则一和原则二分别建立模型。
然后在实际问题中对相关模型进行求解。
模型一以“总运量最小”和“卡车数最少”为双目标进行规划，利用实际情况中的品位（铁含量）限制，产量要求，电铲和卡车实际总数等为约束条件，从而建立了数学模型。
运用软件lingo对整数规划进行了求解，求出了最优解。
对于卡车的安排，在不改变卸点的情况下，采用贪心法给出了具体车辆的路线安排，同时绘制出了车辆的线路示意图。
在原则一下的结果为：
总运量=85628.62吨公里，出动7台电铲，分别安排在1，2，3，4，8，9，10七个铲位，卡车总数为16辆。
模型二以“产量最大”，“岩石产量最大”和“总运量最小”为目标，根据每个目标的优先顺序，进行多层次的规划（约束条件同模型一）。
根据题目中要求，将此模型分为三个层次，第一次层以“产量最大”为目标，得到了11组最优解，第二层以“岩石产量最大”为目标，在之前的11组解中选出了符合岩石产量最大的5组解，第三层则以“总运量最小”为目标，最终得到了即满足“产量最大”，同时可实现“岩石产量最大”和“总运量最小”的最优解。
在原则二的求解结果为：
最大产量=103026吨，最大岩石产量=49280吨，对应最小运量=167412.63吨公里，出动7台电铲，分别安排在1，2，3，5，7，9，10七个铲位，出动20辆卡车。
在模型改进中，为了使每辆卡车尽可能的发挥其功效，我们认为在一个班次中有大量时间空闲的卡车可以改变卸点。
该方法提高了卡车的平均利用率，减少了运输成本，使模型更加有利于最大限度的实现露天矿的经济效益，为实际情况所运用。
本文的最大特色在于模型求解法过程中，用线性规划与整数规划的相结合思想作为切入点将问题进行层层剖析，使模型一步一步深化，更接近实际。
本文的算法虽然通俗易懂，但计算量较大。
关键字
线性规划整数规划贪心法车辆安排
一、问题的重述
钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。
许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。
提高这些大型设备的利用率是增加露天矿经济效益的首要任务。
露天矿里有若干个每个铲位已预先根据铁含量将石料分成矿石和岩石。
一般来说，平均铁含量不低于25%的为矿石，否则为岩石。
每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。
每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。
露天矿同时有若干卸点，包括卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。
从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%±1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。
从长远看，卸点可以移动，但一个班次内不变。
卡车的平均卸车时间为3分钟。
所用卡车载重量为154吨，平均时速28hkm。
卡车的耗油量很大，每个班次每台车消耗近1吨柴油。
发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。
卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。
电铲和卸点都不能同时为两辆及两辆以上卡车服务。
卡车每次都是满载运输。
每个铲位到每个卸点的道路都是专用的宽60的双向车道，不会出现堵车现象，每段道路的里程都是已知的。
我们需要设计的一个班次的生产计划应该包含以下内容：
出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。
一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：
1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；
2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。
请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。
针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。
某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。
各卸点一个班次的产量要求：
矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。
铲位和卸点位置的二维示意如图一，各铲位和各卸点之间的距离（公里）如下表：
矿位1
矿位2
矿位3
矿位4
矿位5
矿位6
矿位7
矿位8
矿位9
矿位10
矿石漏
5.26
5.19
4.21
4.00
2.95
2.74
2.46
1.90
0.64
1.27
倒装场Ⅰ
1.90
0.99
1.90
1.13
1.27
2.25
1.48
2.04
3.09
3.51
岩场
5.89
5.61
5.61
4.56
3.51
3.65
2.46
2.46
1.06
0.57
岩石漏
0.64
1.76
1.27
1.83
2.74
2.60
4.21
3.72
5.05
6.10
倒装场Ⅱ
4.42
3.86
3.72
3.16
2.25
2.81
0.78
1.62
1.27
0.50
表一
各铲位矿石、岩石数量（万吨）和矿石的平均铁含量如下表：
矿位1
矿位2
矿位3
矿位4
矿位5
矿位6
矿位7
矿位8
矿位9
矿位10
矿石量
0.95
1.05
1.00
1.05
1.10
1.25
1.05
1.30
1.35
1.25
岩石量
1.25
1.10
1.35
1.05
1.15
1.35
1.05
1.15
1.35
1.25
铁含量
30%
28%
29%
32%
31%
33%
32%
31%
33%
31%
表二
二、问题的分析
露天矿具有多个铲点和多个卸点，从而形成了运输的多条通道。
在露天矿的生产中，岩矿石的运输占有很大的部分，运输成本对于露天矿的经济效应影响很大，因此合理的安排岩矿石的运输方案，实现运输成本的最小化，是露天矿优化设计中的一个重要问题。
需要解决问题有:
a.共出动多少辆铲车
b.铲车分配到那些铲位上
c.共出动多少辆卡车，
d.卡车分配在那些路线上
e.卡车在每条路线上的运输次数。
本问题是一个有约束的规划问题，分别以总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小和利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）为目标，利用实际情况中的品位（铁含量）限制，产量要求，电铲和卡车实际总数等为约束条件，从而建立出数学模型，实现运输方案的最优化设计，从而实现经济效益的最大化。
三、符号说明
i:
第i个卸点（1为矿石漏，2为倒装场I，3为岩场,4为岩石漏，5为倒装场II）
j:
第j的铲点（依次对应于示意图中的10个铲位）
：
从第j个铲点到第i个卸点需要跑的趟数
：
第j个铲点到第i个卸点的距离（单位为公里）
:
第i个卸点的最低产量要求（单位为吨）
：
第j个铲位所需最少车辆数
：
第j个铲位的矿石产量（单位为吨）
：
第j个铲位的岩石产量（单位为吨）
：
第j个铲位所需的电铲数目（0表示此铲位没有有电铲，1表示此铲位有电铲）
：
第j个铲位所产矿石的平均铁含量
：
第j个铲位卡车工作的平均时间（单位为小时）
：
卡车时速，为28km/h
：
卡车总运量，最小值为w
C：
单车载重量，为154吨，
四、模型假设
1、电铲和卸点都不能同时为两辆及两辆以上卡车服务；
2、卡车只点火一次，每次都是满载运输，单车载重量为154吨，平均时速28km/h，卡车匀速行驶，在卡车工作过程中无车辆损坏等特殊情况发生；
3、卸点在一个班次内位置不变，平均卸车时间为3分钟；
4、每个铲位至多安置一台电铲，平均装车时间为
分钟；
5、卡车运输过程中不堵车，不发生等待情况；
6、各铲位的车辆分配后即固定，不会行驶到其他铲位，且最终回到原分配铲位；
7、装、卸完货后卡车能立即出发，中间停顿时间忽略不计；
五、模型建立
1、原则一：
“总运量最小”和“卡车数最少”的双目标规划。
目标函数为：
总运量最小
和卡车数最小
约束条件为：
（1）从每个铲位运出的矿石总量不大于此铲位的矿石产量：
（2）从每个铲位运出的矿石总量不大于此铲位的岩石产量：
（3）各个矿石卸点需要的铁含量要达到要求：
（4）一个工作班次周期为8小时，平均装车时间为5分钟，所以最到装车次数为
=96（次），即铲车8小时持续一直工作也最多只能装96辆车：
（5）一个班次8个小时自从第一辆车开始卸货之后一直有车在该卸点卸货，
=160,在一个卸点所卸的货物不能超过该卸点的饱和度:
（6）每个铲点最多有一辆铲车或没有铲车，铲车总数应不大于7：
且
=1或0
（7）各个卸点一个班次的产量需要满足产量要求：
（8）分配到各个铲位的总的车辆数不大于20
2、原则二：
要求利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。
因此考虑目标函数为总产量
，岩石产量
，总运量
，同样为多目标规划问题，约束条件与原则一相同。
3、因此问题的数学模型为：
（1）
原则一：
（2）原则二：
，
，
六、模型求解
1、原则一的模型求解
已知：
某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。
各卸点一个班次的产量要求：
矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。
依据已建立的线性规划模型，利用lingo软件求解得（代码见附录1），
目标一的计算结果为：
总运量=85628.62吨公里
出动7台电铲，分别安排在1，2，3，4，8，9，10七个铲位。
将各条路线所需的卡车数简单加和得，一共需要13辆卡车。
由于不变卸点的约束，卡车数量的简单加和在实际安排时是不可能实现的。
下面我们将给出卡车的实际安排：
得到从第j个铲位到第i个卸点卡车需跑的趟数
为：
从第j个铲位到第i个卸点卡车需跑的趟数
Kij
j=1
j=2
j=3
j=4
j=5
j=6
j=7
j=8
j=9
j=10
i=1
0
13
0
0
0
0
0
54
0
11
i=2
0
42
0
43
0
0
0
0
0
0
i=3
0
0
0
0
0
0
0
0
70
15
i=4
81
0
43
0
0
0
0
0
0
0
i=5
0
13
2
0
0
0
0
0
0
70
表三
一辆卡车在卸点i与铲位j之间往返行驶一次需
分钟，装卸需（3+5）=8分钟，共需8+
分钟，这条线路上一辆卡车一个班次内可往返
（[]表示取整），则该线路需要卡车
辆，卡车总数最多不能超过M=20辆:
得到从第j个铲位到第i个卸点每辆卡车最多可跑的趟数
从第j个铲位到第i个卸点每辆卡车最多可跑的趟数
Cij
j=1
j=2
j=3
j=4
j=5
j=6
j=7
j=8
j=9
j=10
i=1
14
15
17
18
22
23
25
29
44
35
i=2
29
38
29
36
35
26
33
28
21
20
i=3
13
14
14
16
20
19
25
25
37
45
i=4
44
30
35
29
23
24
27
19
15
13
i=5
17
18
19
21
26
23
41
31
35
46
表四
为每辆卡车安排行驶路线及运输次数。
我们采用贪心法。
使每辆卡车发挥最大功效，即当此线路上卡车需跑的总趟数
大于等于此线路上每辆卡车最多可跑的趟数
，则在此线路和安排一辆固定路线的卡车，然后安排改变路线的卡车，通过改变铲位，将其他剩余的趟数跑完。
由表三和表四数据可得：
表五
变铲位的卡车的路线安排：
第一辆：
先在矿石漏—铲位2之间运输13趟，花费时间为（8+
）*13，一个班次内的剩余时间为T—（8+
）*13=87分钟，然后改变铲位为铲位8,87/（8+
）=5趟，剩余班次时间为6.5分钟，时间太短不足以跑一趟，所以此剩余时间忽略，即第一辆车的工作时间结束矿石漏—铲位8还剩余运输次数为20趟。
第二辆：
先在矿石漏—铲位8之间运输20趟，花费时间为（8+
）*20=322.86分钟，一个班次内的剩余时间为T—（8+
）*20=157分钟，然后改变铲位为铲位10,
157/（8+
）=11趟，剩余时间9分钟，因模型假设卡车运输不改变卸点，所以第二辆车的工作时间结束。
第三辆：
先在倒装场I—铲位2之间运输4趟，花费时间为（8+
）*4=48.97分钟，一个班次内的剩余时间为T—（8+
）*4=431分钟，然后改变铲位为铲位4,
运完所剩7趟所需时间为（8+
）*7=89.9分钟，剩余时间341分钟，因模型假设卡车运输不改变卸点，所以第三辆车的工作时间结束。
第四辆：
先在岩场—铲位9之间运输33趟，花费时间为（8+
）*33=413.9分钟，一个班次内的剩余时间为T—（8+
）*33=66分钟，然后改变铲位为铲位10，
66/（8+
）=6趟，剩余时间3.36分钟，时间太短，所以此剩余时间忽略，即第四辆车的工作时间结束时岩场—铲位10还剩余运输次数为9趟。
第五辆：
在岩场—铲位10之间运输9趟，花费时间为（8+
）*9=93.99分钟，一个班次内的剩余时间为T—（8+
）*9=386分钟，因模型假设卡车运输不改变卸点，所以第五辆车的工作时间结束。
第六辆：
先在岩石漏—铲位1之间运输37趟，花费时间为（8+
）*37=397.49分钟，一个班次内的剩余时间为T—（8+
）*37=82.51分钟，然后改变铲位为铲位3，
82.51/（8+
）=6趟，剩余时间1.87分钟，时间太短，所以此剩余时间忽略，第六辆车的工作时间结束，岩石漏—铲位3还剩余运输次数为2趟。
第七辆：
在岩石漏—铲位3之间运输2趟，花费时间为（8+
）*2=26.88分钟，一个班次内的剩余时间为T—（8+
）*2=453.12分钟，因模型假设卡车运输不改变卸点，所以第七辆车的工作时间结束。
第八辆：
先在倒装场II—铲位2之间运输13趟，花费时间为（8+
）*13=319分钟，一个班次内的剩余时间为T—（8+
）*13=161分钟，然后改变铲位为铲位3，运输2趟后剩余161-（8+
）*2=113.12分钟，然后改变铲位为铲位10，113.12/（8+
）=11,剩余时间为1.58分钟，不足以跑一趟，所以此剩余时间忽略，第八辆车的工作时间结束，倒装场II—铲位10还剩余运输次数为13趟。
第九辆：
倒装场II—铲位2之间运输13趟，花费时间为（8+
）*13=131.82分钟，剩余时间为348.18分钟。
因此共出动16两卡车，其中7辆为固定路线，9辆为变铲位路线。
2、原则一的模型计算结果为：
总运量=85628.62吨公里
出动7台电铲，分别安排在1，2，3，4，8，9，10七个铲位。
出动16辆卡车，安排下表：
卡车编号
路线
运输趟数
1
矿石漏——铲位8
29
2
倒装场I——铲位2
38
3
倒装场I——铲位4
36
4
岩场——铲位9
37
5
岩石漏——铲位1
44
6
岩石漏——铲位3
35
7
倒装场II——铲位10
46
8
矿石漏——铲位2
13
矿石漏——铲位8
5
9
矿石漏——铲位8
20
矿石漏——铲位10
11
10
倒装场I——铲位2
4
倒装场I——铲位4
7
11
岩场——铲位9
33
岩场——铲位10
6
12
岩场——铲位10
9
13
岩石漏——铲位1
37
岩石漏——铲位3
6
14
岩石漏——铲位3
2
15
倒装场II——铲位2
13
倒装场II——铲位3
2
倒装场II——铲位10
11
16
倒装场II——铲位10
13
表六
线路示意图如下：
图二（椭圆代表卸点，星号代表铲点）
3、原则二的模型求解
依据已建立的模型，依据已建立的模型，利用lingo软件线性规划（代码见附录1），因为模型二为有优先层次的多目标规划，首先将目标函数定为
（代码见附录3），得到11组符合情况的解，如下表：
第一层各个最优解的岩石产量
序号
P1P2…P10
总产量/吨
岩石产量/吨
17
0110101111
103026
44430.22
22
0111001111
103026
44834.66
27
0111100111
103026
49280
28
0111101011
103026
48972.68
76
1101100111
103026
45612.6
86
1110001111
103026
44021.39
91
1110100111
103026
48724.06
92
1110101011
103026
49280
101
1110001111
103026
49280
102
1111001011
103026
49280
111
1111100011
103026
49280
表七
在此基础上，将目标函数定为
（代码见附录4），得到5组符合情况的解，如下表：
第二层各个最优解的总运量
序号
P1P2…P10
总产量/吨
岩石产量/吨
总运量/吨公里
27
0111100111
103026
49280
172142.74
92
1110101011
103026
49280
167412.63
101
1110001111
103026
49280
170250.08
102
1111001011
103026
49280
174213.424
111
1111100011
103026
49280
177870.308
表八
因原则二要求在产量相同的情况下，取总运量最小的解，所以进一步将
（代码见附录5），定位目标函数，此时可求出原则二的最优解为序号92
4、原则二的模型计算结果
总产量=103026吨；
岩石产量=49280吨；
总运量=167412.63吨公里；
出动7台电铲，分别安排在1，2，3，5，7，9，10七个铲位。
出动20辆卡车，安排下表：
铲位
车辆数
铲位1
3
铲位2
3
铲位3
4
铲位4
0
铲位5
3
铲位6
0
铲位7
3
铲位8
0
铲位9
2
铲位10
2
七、模型评价
优点：
1.用线性规划与整数规划的相结合思想作为切入点将问题进行层层剖析。
使模型一步一步深化，更接近实际模型。
2.考虑到lingo软件本身存在着一定的局限性（模型二中对于目标实际上是有11个符合条件的解，但lingo软件只会就近取其中一种对目标函数的最优解显示出来，因此在有多个层次的优化问题中，利用lingo求得的很有可能不会是最优解），我们采用遍历的方法，通过多个层次的筛选寻得最优解。
缺点：
1.算法的计算量较大，对于卡车的安排问题没有找到切实可行的算法。
2.对该模型复杂的实际问题作了简化。
对其中的一些整数规划问题放宽了条件。
八、模型的改进与推广
在安排变铲位的卡车时，因题目中要求一个班次内卸点不能移动，有些卡车在一个班次内完成所在卸点的运输次数后，仍有很多时间剩余，将一个班次内每辆卡车工作剩余时间统计如下表
卡车编号
所在卸点
一个班次内的剩余时间（分钟）
1
矿石漏
0
2
倒装场I
0
3
倒装场I
0
4
岩场
0
5
岩石漏
0
6
岩石漏
0
7
倒装场II
0
8
矿石漏
6.5
9
矿石漏
9
10
倒装场I
341
11
岩场
3.36
12
岩场
386
13
岩石漏
1.87
14
岩石漏
453.12
15
倒装场II
1.58
16
倒装场II
348.18
由此数据可看出，卡车10、12、14、16在一个班次内的剩余时间都较多，卡车的耗油量很大，每个班次每台车消耗近1吨柴油。
发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。
为了减少卡车的耗油支出，我们考虑可以安排一辆即变卸点又变铲位的卡车，将10、12、14、16这三辆卡车的运输任务由一辆卡车执行完。
路线安排为，此即变卸点又变铲位的卡车在铲位4运输结束后驶向岩场，在岩场执行完运输任务后，从铲位10驶向岩石漏，在岩石漏执行完运输任务后，又从铲位3驶向倒装场ＩＩ。
共花费时间为422.51分钟，可见完全可以由一辆即变卸点又变铲位的卡车代替编号为10、12、14、16的四辆卡车，所以只需出动13辆卡车，大大减少了运输费用，有利于最大限度的实现露天矿的经济效益，为实际情况所运用。
九、参考文献
[1]费培之，数学模型实用教材，成都，四川大学出版社，1998年
[2]卢开澄，单目标、多目标与整数规划，北京，清华大学出版社，1999年
[3]黄光球，桂中岳，露天矿运输系统元胞自动机模糊仿真方法，旷冶，7
（1）：
14-24，1998年
附录：
1.原则一，以运量最大为目标时的代码
model:
sets:
load/1..10/:
a,K_j,R,O,P;
unload/1..5/:
M,K_i;
link（unload,load）:
L,Kmax,K,car,c;
endsets
data:
a=30282932313332313331;
M=1.21.31.31.91.3;
L=5.265.194.214.002.952.742.461.900.641.27
1.900.991.901.131.272.251.482.043.093.51
5.895.615.614.563.513.652.462.461.060.57
0.641.761.271.832.742.604.213.725.056.10
4.423.863.723.162.252.810.781.621.270
升级会员 