露天矿生产的车辆安排模型

B题 露天矿生产的车辆安排

摘要: 本问题要求对露天矿的矿石和岩石的运输进行优化安排，该问题可归结为一个带约

束的组合优化问题，是NP难题。首先，我们建立在卡车不等待条件下满足产量和品位需求的一个班次生产计划，使总运量最小，同时出动最少的卡车的数学模型。并设计了求各条线路优化车次的快速启发式算法，贪婪算法，并用该算法进行求解得到如下结果：分别在铲位1、2、3、4、9、10出动6辆铲车并出动14辆卡车按下表方案进行运输，其总运量为8.3836万吨公里。我们还将建立的优化模型，转化为多个整数线性规划问题，利用lindo和matlab等数学工具进行了求解，其结果没有贪婪算法优，也没有贪婪算法快。根据得到的车次来推算下表的各条路线上所需卡车数及安排的时候，我们创造性的使用了自己发明的“一笔画”方法使问题的复杂度大大的得到了降低。

（数字为卡车编号，括号内数字为其对应的运输次数） 矿石漏 铲位1 铲位2 铲位3 3(18)，4(18) 9(13) 铲位4 13(23) 14(9) 铲位9 9(29) 铲位10 倒装场Ⅰ 2（39）,13（14） 7(47)，11(22) 12(1) 10(19), 11(7) 倒装场Ⅱ 12 (15) 6 (38)，9 (5) 10(16) 岩场 1（44）， 5(35)，8(7) 岩石漏 8(37) 9(1) 对于题目要求的第二个原则，我们建立了一个两步模型，第一步，产量最大, 岩石产量优先。第二步，将第一步得到的最大产量作为已知，再来安排运输，使总运量最小。 我们也设计了相应的快速算法，求得最大产量为9.4556万吨。 关键字： 混合约束 线性规划 露天矿开采 贪婪算法

一 问题的重述

许多现代化铁矿通常采用露天开采的形式，它的生产主要是由电动铲车装车、电动轮自卸卡车运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。

卸货地点有卸矿石的矿石漏、2个铁路倒装场和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。把矿石按矿石卸点需要的铁含量（假设要求都为29.5%?1%，称为品位

限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。

所用卡车载重量为154吨，平均时速28kmh。卡车的耗油量很大，故一个班次中只在开始工作时点火一次。原则上在安排时不应发生卡车等待的情况。

一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：

1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；

2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。

本题要求根据这两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。

二 模型的假设

1、 在一个班次内，卸点不可以移动。

2、 电铲和卸点都不能同时为两辆及两辆以上卡车服务。

3、 在一个班次中卡车只在开始工作时点火一次，在运输过程中原则上不应发生等待， 4、 在每个铲位到每个卸点的途中，不会出现堵车现象。 5、 每个铲位至多能安置一台电铲。 6、 卡车每次都是满载运输。

三 符号说明

xij：决策变量，从铲位i到卸点j所需的运输车次，i?1,2,...10dij：铲位 i到卸点j的距离，i?1,2,...10j?1,2,...5

j?1,2,...5

ai： 铲位i的矿石数量，i?1，2，...，10

bi： 铲位i的岩石数量 i?1，2，...，10

cj： 卸位j的产量需求。j?1，2，3分别表示矿石漏，倒装场Ⅰ，倒装场Ⅱ，即3

个卸矿点；j?4,5时分别表示岩石漏和岩场，即两个卸岩点

- -

1

?i: 铲位i矿石的铁含量，i?1，2，...，10

p1 ：品位下限，为28.5% p2 ：品位上限，为30.5%

V: 卡车平均时速，为28kmh

?1x?0 sign?x?： 表示x的符号函数，即sign?x????0x?0floor(x): 表示x的整数部分

ceil(x)： 表示大于或等于x的最小整数

四 问题的分析及模型的建立

问题1分析

本问题要求建立在卡车不等待条件下满足产量和品位需求的一个班次生产计划，使总运量最小，同时出动最少的卡车的数学模型。该问题可以归结为一个带约束的组合优化问题。由于当总运量越小，卡车的工作量也越小，从而需要的卡车也越少（当不考虑卡车空驶的时间时）。因此，我们首先确定使总运力（公里吨）最小的各线路运输流量方案，再安排卡车。

由于卡车都满载运输，且其载重量相等，因此将决策变量从铲位i运往卸点j 的矿石或岩石量xij的单位视为车皮，xij为非负整数。为书写方便，我们以10个铲位，5个卸点为例来分析该问题的目标函数和约束条件。实例改变，数字随之变化。

目标函数：总运力??dijxij

j?1i?1510 约束条件：

1． 卡车不等待应满足的约束 （1） 各铲位的装车能力约束

一辆车的平均装车时间为5分钟，则一个班次（8小时）最多能装8?60/5=96趟车，要车辆在铲位不等待，则

5?xj?1ij?8?60/5i?1,2,...,10

（2） 各卸点的卸货能力约束

- -

2

一辆车的平均卸货时间为3分钟，则一个班次（8小时）最多能卸8?60/3=160趟车，要车辆在卸点不等待，则

10?xi?1ij?8?60/3j?1,2,...,5

（3） 各运输线路的运输能力约束

当车辆在一条线路上来回不停地行驶时，由于路线的长度有限，为使车辆在装卸点不等待，则两车之间的时间间隔至少是5，因此同时在一条线上的车辆数不超过(2dij/v?60+3+5)/5,因此，一个班次一条线上的车次数应满足

xij?8?60/(120dij/v?8)?floor[(120dij/v?8)/5],i?1,2,?,10j?1,2,?5

2． 供需约束 （1）铲位i的限矿量

从铲位i运往各矿石卸点的矿石总量不能超过该点能提供的限量，即有

j?1,2,5?xij?floor(ai) i?1，2，...，10 154 （2）铲点i的限岩量

从铲位i运往各岩石卸点的岩石总量不能超过该点能提供的限量，即有

4?xij?floor(j?3bi) i?1，2，...，10 154（3）各卸点的产量需求

从各铲位运往矿石或岩石卸点j的总量应满足该点的需求，即有

cj154?xij?ceil(i?110) j?1，2，...，5

3． 品位约束

p1??xi?110i?110ij?i?p2 （可化为线性约束）

?xij4． 车辆数约束

（1） 每辆车在一个班次能行驶的总路程为8v, 又因只能提供20辆卡车，

因此

??dceil(i?1j?1105ijxij)?20

- -

3

4v