3462高教杯数学建模一等奖论文

队号：2103462

露天矿生产的车辆调度的优化设计

摘要

卡车自动化调度系统的优化设计对开采公司经济效益的提高有着十分重要的意义。本文主要研究根据不同的原则建立不同的调度系统的数学模型。为了调度系统的方便表达，我们首先引入Go矩阵和Return矩阵来分别描述从铲位到卸点和从卸点到铲位的卡车的双向调度方案，从而找到了建立模型的突破口，既而根据不同的原则分别建立了不同的数学模型。

根据原则1，我们建立了一个大型的综合规划数学模型（模型1）。在该模型中，我们以总运量和出动卡车的数量最小为目标函数，以品位限制、供求限制、需求限制、铲位和卸点的车辆容量等限制条件为约束。由于直接的求解很困难，所以我们以分步优化，逐层突破的方法求解该模型，并得到满意的解。原则2要求产量最大，同时也要适当考虑岩石的产量优先、总运量较小。据此原则我们建立以产量最大为主要目标的综合规划模型（模型2）。模型2的求解同模型1的求解相似仍采用分步求解法求解。模型1和模型2均是在单原则指导下的数学模型，并不能反映开采公司的综合经济效益，为此我们综合考虑两个原则，建立了综合的双原则数学模型（模型3），该模型是典型的多目标综合规划模型，我们又以平均路程sij为拆合因子，并用偏好性系数加权法将多目标规划问题转化成以

Max

U=w∑∑agijsij (1 w)∑∑agijsij

i=1j=1

i=1j=1

mnmn

为目标函数的单目标规划问题，并用分步优化算法得到不同权值w对应的最优调度方案。应用以上三个模型对实例进行求解，得到如下表中所示的结果（具体的调度方案见正文）。

模型产量岩石量总运量卡车电铲电铲分布

(万吨)(万吨)(吨公里)(辆)(台)编号（铲位号）

模型17.03783.218685272.881371,2,3,4,8,9,10模型210.34884.928148904.142071,2,3,5,8,9,10模型39.88684.928131200.31871,2,3,4,8,9,10

在对以上三个模型求解后，我们又用品位检验法对模型的结果进行检验，并用w法对双原则模型进行了稳定性分析。在对模型进行理论归纳时我们给出了“等待时间均分定理”、“跟从定理”、“理想车辆定理”。针对模型中存在的问题，我们在对模型的进一步讨论中分别对电铲的数量、路线的选择准则、最佳卡车数量的确定展开了讨论。随后我们又对模型进行了优缺点分析，并从几个方面给出了模型的改进方法。最后根据我们在建模中对调度系统的感受，提出了对开采公司的两点建议。

一：问题的提出

钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。

露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。

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

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

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

一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：

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

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

请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。

某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。

铲位和卸点位置的二维示意图如下，各铲位和各卸点之间的距离（公里）如下表：

铲位铲位铲位铲位铲位铲位铲位铲位铲位铲位12345678910

矿石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.46岩石0.641.761.271.832.742.604.213.72漏

倒装4.423.863.723.162.252.810.781.62场Ⅱ

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

铲位铲位铲位铲位铲位铲位铲位铲位12345678

矿石

0．951．051．001．051．101．251．051．30

量岩石

1．251．101．351．051．151．351．051．15

量铁含

30%28%29%32%31%33%32%31%

量

1.065.051.27

0.576.100.50

铲位铲位9101．351．251．351．2533%

31%

二、基本假设与符号说明

1.基本假设

为了便于问题的研究，我们对题目中的不确定因素作一些约定和假设。

1．电铲在一个班次内不改变铲位，也就是说每台电铲在一个班次内只在一个铲位上工作。这主要是因为电铲的转移不方便并且电铲的转移需要站用时间，影响公司的效益。

2．矿石漏和铁路倒装场只是卸矿石的不同地方，它们的开采对露天矿的经济效益无

影响。同样，卸岩石的岩石漏和岩场的属性也不影响开采公司的经济效益。开采公司的经济效益主要与开采量与运输成本有关。

3．卸点的品位是指在一个班次内在卸点内所卸总矿石铁的综合含量，并不要求任

何一部分矿石的铁含量达到品位限制要求。

4．卡车每次运输都按载重量满载运输，并不考虑因颠簸而使岩石或矿石减少的情

况。另外卡车运输始终以28km/h的平均速度行驶，发动和刹车所占用的时间忽略不计。

5．在同一班次内，每辆卡车所走的路线是不定的，即卡车选择哪条路线是随机的。2、符号的说明

gij：表示在一个班次内从j铲位到i卸点单向路径上所通过的总车次；rij：表示在一个班次内从i卸点到j铲位单向路径上所通过的总车次；

n：铲位的总数；m：卸点的总数；

sij：从i卸点到j铲位的路程；t上：装一辆车所需的时间；t下：卸一辆车所需的时间；Q：总运量；

F：总产量；

N：所需卡车的总量；Ki：i号卸点的需求量；Mj：j号铲位的供应量。

注：其他符号依次在文中说明。

三、问题的分析及模型的准备

通过直观的分析可知，本问题是一个较复杂的运输系统调度问题。问题要求分别满足两条运输原则的条件下建立一个班次运输方案安排的数学模型，并且要给出所用电铲的台数，每台电铲的铲位，出动卡车的数量，卡车的具体调度安排等。所以本问题是一个大型的目标规划问题，目标函数是要求的两个原则，即一个是要求总运量最小，同时出动的卡车最少，另一个是要求获得最大的产量。对于开采公司来说，制定的两个原则事实上就是减少成本，增加收入，以提高公司的经济效益。这样我们就可知道研究该问题的方向就是找目标函数，抽象约束条件，建立规划问题的数学模型。

为了建立完善的数学模型，我们还需对问题作进一步的分析。1．运输矩阵的建立

卡车运输路线的选择是双向、随机的，当多辆卡车同时运输时，他们所形成的运输网错综复杂。为了便于描述卡车在一个班次的调动状态，我们先规定了两个运输方向，同人们习惯上的方向相同，我们把从铲位到卸点的方向称为前进（Go）方向，而将从卸点到铲位的方向称为返回(Return)方向。

设有m个卸点，n个铲位，我们构建以下矩阵描述Go方向的运输状态：

g11 gGo= 21

gn1

g12

g22 gn2

g1n

…g2n

…gmn

…

其中gij表示在一个班次内从j铲位到i卸点单向路径上所通过的总车次，

1≤j≤n,1≤i≤m。

同理，我们可得到Return矩阵：

r11 rR= 21

rn1

r12r22

rn2

…

r1n

…r2n

…rmn

其中rij表示在一个班次内从i卸点到j铲位单向路径上所通过的总车次。

我们将Go矩阵和Return矩阵统称为调度矩阵。

2．原则1的数学分析原则1要求总运量最小，同时出动的卡车数量最少，这实际上是要求运输成本最小，所以原则1又可称为成本小原则。这里的总运量我们理解为卡车所装载的货物总质量（吨）与卡车在装载状态下所行的路程之积，其数字表达式为

Q=∑∑agijsij

i=1j=1

mn

其中sij表示从铲位j到卸点i之间的路程，a为卡车满载时的载重。

当卡车从卸点返回时，此时虽然卡车所走的路程不为零，但此时卡车所装载货物的质量为零，所以返回时卡车的运量为零，所以卡车的总运输指的是从铲位到卸点也即Go方向上的总运量。

原则1同时也要求在同一班次内出动卡车的数量最少。卡车最少的运输状态有以下两个特点：

（1）卡车得到最大限度的利用，即卡车几乎没有等待时间（闲置时间）。（2）卡车充分地工作，恰能完成运输问题，或者超额的部分并不多。对于多辆卡车的装、运、卸的时间我们很难确定，但根据特点（1），我们在宏观上很容易找到卡车数量与其他因素之间的关系。

由于所有卡车几乎一直在工作，即对每辆卡车来说在一个班次内都处于装、运、卸三个时间状态，所以我们将所有卡车的工作时拆合成一辆卡车的工作时，便有

NT=∑∑(gij+rij)sij/v+∑∑(gijt上+rijt下)+t

i=1j=1

i=1j=1

mn

[]

mn

其中T为生产周期，即一个班次的时间，t 为在一个班次内所有卡车的总等待时间，于是有

mn mn

N= ∑∑(gij+rij)sij/v+∑∑(gijt上+rijt下)+t /T

i=1j=1 i=1j=1

[]

由于整个运输过程中原则上不应存在等待时间，所以t 的值应近似为零或就是零。3．原则2的数学分析

原则2要求利用现有车辆,获得最大的产量,所以原则2又可称为产量最大原则,这

里的产量指的是矿石和岩石的总产量，其数学表达式为：

F=∑∑agij

i=1j=1

mn

4.等待时间的控制

我们在安排运输方案时,原则上不应存在等待时间,但不排除一定存在等待时间的情况,所以我们安排运输时应尽可能避免出现等待时间的情况。根据参考文献[]，卡车在进行调度时可以根据“最小饱和度”调度准则（MSD），以尽可能地避免发生等待现象。

这一准则的实质，是将卡车调往具有最小“饱和”程度的路线：

min{Dj}choice(i)=j

≤j≤n

min{Di}

choice(j)=i ≤i≤m

式中choice(i)表示处于i卸点的待发车所选择的将去铲位的代号，choice(j)表示处于j铲位的待发车所选择的将去卸点的代号，Dj表示由卸点到j铲位的饱和度，Di表示由铲位到i卸点的饱和度。Dj和Di的具体表达式为：

t′

s+N ij j

D= t上 j

vt上

t′ s+Nij i t Di= 下

vt下

其中t′为估计的剩余时间，Nj表示到第j号铲位的卡车数，包括正装及待装卡车，

Ni表示到i卸点的卡车数，包括正卸及待卸卡车。

四、原则1数学模型（模型1）的建立与求解

1、模型的建立

由上面问题的分析，我们给出了成本的数学表达式，再经过对目标函数约束条件的分析后，我们建立以下双目标线性规划模型：

minQ=∑∑agijsij

i=1j=1

mn mn* minN= ∑∑(gij+γij)sij/v+∑∑(gijt上+γijt下)+t /Ti=1j=1 i=1j=1

mn

n

∑agij≥Ki j=1

n n

∑bjgija/∑gija∈[29.5%±1%]

j=1 j=1

m

∑agij≤Mj i=1 m

T

∑gij≤，1≤j≤n

t i=1上

n

∑rij≤T,1≤i≤ms.t j=1

t下

*

*

T≥0,limT=0 mnmn ∑∑gij=∑∑rij i=1j=1i=1j=1

gij≥0,rij≥0,且gij,rij为整数

choice(i)=jmin{Dj} ≤j≤n

min{Di}

choice(j)=i

≤i≤m

(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)

关于约束条件的说明

1）约束条件（1）是为保障在一个班次内要满足各卸点的需求；

2）条件（2）是对铲位搭配的约束，即在同一班次内所有矿石的卸点都要达到品味

要求的限制；

3）此条件是基于铲位的岩石和矿石的储量都是有限的而进行的约束，即从任何铲

位所输出的产量不应超过该铲位的储量；4）条件（4）（5）是对gij和rij的约束，它们的上限不应超过T/t上，T/t下；5）条件（6）描述了等待时间的情形，说明了可以存在等待时间，但尽量应使等待

时间为0；

6）条件（7）给出了Go和Return矩阵元素之间的逻辑关系；

7）条件（8）是对目标函数中gij和rij的约束，这是由它们的现实意义而定的。8）条件（9）和条件（10）是为了保证尽量避免等待现象而进行的实时调度的约束。2、模型的求解

模型1是典型的大型的双目标线性规划问题，即使在约束条件下对两个目标分别求解，也是困难的，困难在于模型中的变量太多，尤其是模型的约束条件中包含了实时调度的限制，这种限制使模型变成非线性，而且不易控制的复杂的数学模型。因此不易直接由计算机进行搜索求解，只能另辟途径。

（1）模型算法的理论分析

模型的求解要求给出一个班次内出动电铲的台数，电铲分布的铲位，出动卡车的数量及卡车的路线分配。模型的目标函数为总运量最小，同时要求出动的卡车也是最少，但也要满足运输要求，所以我们先不考虑出动卡车的台数，直接以总运量最小为目标，求解模型。求解出运输方案后，卡车数量即可给出。

直接的求解很复杂，为此我们采取分步求解的方法：

第一步：用线性规划的方法求出从每个铲位到每个卸点所发的车次，从而给出了Go矩阵。

第二步：从Go矩阵判断所需出动的电铲的台数和铲位分配。

第三步：依据Go矩阵提供的信息，用线性规划方法求出由每个卸点返回到每个铲位的车次，从而给出了Return矩阵。

第四步：依据Go矩阵和Return矩阵，根据卡车的充分利用条件求出在一个班次内所需卡车的数量。

（2）分步求解的实现Go矩阵的两种方法求解单目标线性规划法：

为求解Go矩阵，我们先要求出从每个铲位到每个卸点的岩石或矿石的运量。为此，我们以总运量最小为目标函数，供应约束、需求约束、品位限制为约束条件，建立如下单目标线性规划数学模型。

minQ=∑∑gijsij

i=1j=15

10

10

∑agij≥Ki j=1 5

∑agij≤Mj i=1

5 5

s.t ∑bjgija/∑gija∈[29.5%±1%]

j=1 j=1

g≥0,且为整数 ij

5 10

∑gij≤160,∑gij≤96

i=1 j=1

我们利用Mathematic中的ConstrainedMin函数可求出一组解，由于该函数求出

的解并非整数，所以我们用手工改动的方法对求出的结果进行优化处理，处理原则是对所得结果进行取整或取整再加1，并在满足限制条件下使目标函数尽可能的大，这样我们便得到G0矩阵：

0130000055010 041044000000 = 000000007015 810430000000 014000000071

G5×10

该矩阵对应的由铲位到卸点的运输方案如表2所示。

满载时（从铲位到卸点）所经过路径车次表

铲位1铲位2铲位3铲位4铲位8铲位9铲位10

矿石漏倒装场Ⅰ岩场岩石漏倒装场Ⅱ合计

8181

14681341

4343

44

55

70

7196

55

44

70

1510

合计78858512485457

由于表格的形式更能直观地表现卡车的调动状态，所以以后我们只以表格的形式反映调动矩阵的信息。并有表中信息可推得：

满载运程：553.72公里；最小总运量：85272.88吨公里

等效虚拟路径法：

由于品位限制,只有铲位1、2、3在最高限制以下，其他均在其上。所以在用到后7个铲位时，必须和前3个搭配。当两者取一定比例总可得到最短的等效路径，即相当于从某一虚拟铲位到目标终点的最短距离。等效函数为：

f(k)=

(pi 30.5%)×Skj

pi pj

+

(pj 30.5%)×Ski

pj pi

k=1，2，3；i=1，2，3；j=4，5， ，10；

由此可得铲位组合分别对矿石漏、倒装场Ⅰ、倒装场Ⅱ的虚拟最短路，如下3个表

格所示：

到矿石漏的最短等效距离表铲位5铲位6铲位7铲位84.10504.84004.56003.58003.32333.96503.48372.44833.26503.65873.33502.4775到倒装场Ⅰ的最短等效距离表铲位5铲位6铲位7铲位81.58501.95831.79501.97001.22331.62001.29621.86501.42752.03121.69002.0050到倒装场Ⅱ的最短等效距离表铲位5铲位6铲位7铲位8

矿石漏

铲位1铲位2铲位3铲位44.94504.44624.1050铲位94.49002.91502.8712铲位103.26501.92332.0050

倒装场Ⅰ铲位1铲位2铲位3铲位41.70751.07751.5150铲位92.09832.04002.3462铲位102.70503.09003.1075

倒装场Ⅱ铲位4铲位9铲位10

铲位1铲位2铲位34.10503.42253.44003.33502.51832.61754.15163.33503.37873.51001.93502.25003.0200

1.99332.14503.89502.56502.80122.46001.06001.3050

根据此表，由于这些组合全符合品位的要求，所以可以去除品位的，直接由最短路径法得到最小总运量。所得结果与线性规划结果相同。

Return矩阵的求解

由于卡车返回时所选的路线是随机的，但它选择的路线应使总路程最短，所以卡车返回时我们仍用线性规划模型求解。卡车返回的路线如下图所示：

此时卡车看成都集中在卸点，我们的任务是给出卡车的从卸点到铲位的最佳分配方案，使总路程最短。此时卸点相当于供求点，铲位相当于需求点，我们可以以总路程最短为目标函数，以卸点的供求限制，铲位的需求限制为约束条件，建立以下单目标线性规划模型：

5

10

minH=∑∑sijrij

i=1j=1

5

5

∑rij=∑gij,j=1,2 10 i=1i=1s.t 10

10

r=gij,i=1,2 5∑ij∑ j=5 j=1

其中H表示所有卡车返回时所走的总路程。

求解此模型可得从卸点到铲位的运输方案：

空载时（从卸点到铲位）的车次安排表：

铲位1铲位2铲位3铲位4铲位8铲位9铲位10矿石漏

8

70

合计78

倒装场Ⅰ6817

851196

858512485457

岩场岩石漏8143倒装场Ⅱ2747合计816843445570并可解得：空载运程：468.39公里；最小车辆数：13辆。

五、原则2数学模型（模型2）的建立与求解

1、模型的建立

在原则2的指导下，我们根据总产量，总运量的优先级问题，建立了以总产量最大为目标的单目标规划问题的数学模型。

maxF=a∑∑gij

i=1j=1m

n

n

∑agij≥Ki,i=1,2 m j=1

m m

∑bjgija/∑gija∈[29.5%±1%]

j=1 j=1

m

∑agij≤Mj,j=1,2 n i=1 m

T

∑gij≤

t上 i=1

n

∑rij≤T t下s.t j=1

mn * mn

T=NT s(g+r)/v+(gt+rt) ∑∑ijijij∑∑ij上ij下 ≥0

i=1j=1 i=1j=1

limT*=0

mn2×gijsijmngij×(5+3)

+∑∑≤20 ∑∑60×8i=1j=1 i=1j=128×8

min{Dj} choice(i)=j ≤j≤n

min{Di}

choice(j)=i≤i≤m

2．模型的求解

对该模型的求解我们仍采用分步求解的方法。先以总产量最大为主目标可求出铲车分别在“1，2，3，7，8，9，10”、“1，2，3，5，8，9，10”、“1，2，3，4，7，9，10”三种方案的铲位安排时，可得到最优的结果，此时得到的最大总产量为10.3488万吨，

最大的岩石总产量为4.928万吨。三种方案的具体安排如表所示。

方案123

总产量（万吨）10.348810.348810.3488

总岩石产量（万吨）4.9284.9284.928

总运量

（吨公里）151782.4151782.4151782.4

7台铲车所对应的铲位号1，2，3，7，8，9，101，2，3，5，8，9，101，2，3，4，7，9，10

然后以总运量最小为主目标，把最大总产量和最大总岩石产量都分别转化为对主目标函数的限制条件，从而建立了下一步方案优化的数学模型：

minF=a∑∑gijsij

i=1j=1m

n

mn

a∑∑gij=10.3488 i=1j=1 4n

a∑∑gij=4.928 i=3j=1 n

∑agij≥Ki,i=1,2 m j=1 mm

∑bjgija/∑gija∈[29.5%±1%] j=1j=1 m

ag≤M,j=1,2 nijj ∑i=1 m

g≤T

ij

∑t上i=1s.t

T n

r≤ ∑ijt

下

j=1

mn mn *

T=NT ∑∑sij(gij+rij)/v+∑∑(gijt上+rijt下) ≥0 i=1j=1 i=1j=1 *

limT=0

nm2×gijsijmngij×(5+3) ∑∑+∑∑≤20

60×8 i=1j=128×8i=1j=1

choice(i)=jmin{Dj} ≤j≤n min{Di}choice(j)=i

≤i≤m

用此模型可求出三个方案的最优具体调度方案，具体结果如下：

方案1：求出最小总运量：149001.16吨公里；所用卡车的数量为：19辆；满载行

车辆满载时（从铲点到卸点）车次运行情况如下表：

铲位1铲位2铲位3铲位7铲位8铲位9铲位10

矿石漏倒装场Ⅰ

15

49

2322

52

68

36

合计78160

岩场28128733160岩石漏812851160倒装场Ⅱ193263114合计96969696969696672由最短路径单目标函数求出其空载时（从卸点到铲点）车次运行情况如下表：

铲位1铲位2铲位3铲位7铲位8铲位9铲位10合计矿石漏倒装场Ⅰ岩场岩石漏倒装场Ⅱ合计

9696

9696

326496

9696

1896

96

96

4632

3264

96

78160160160114672

方案2：求出最小总运量：148904.14吨公里；所需卡车的数量为：20辆；满载行驶路程：966.91公里；空载时行驶路程：794.64公里。

车辆满载时（从铲点到卸点）车次运行情况如下表：

铲位1铲位2铲位3铲位5铲位8铲位9铲位10合计

矿石漏倒装场Ⅰ岩场岩石漏倒装场Ⅱ合计

158196

682896

286332996

41

7171896

124396

87

544296

9

78160160160114672

96

由最短路径单目标函数求出其空载时（从卸点到铲点）车次运行情况如下表：

铲位1铲位2铲位3铲位5铲位8铲位9铲位10合计矿石漏倒装场Ⅰ岩场岩石漏倒装场Ⅱ合计

9696

96

46

96

326496

6496

5096

96

96

32

64

96

32

78160160160114672

方案3：求出最小总运量：151092.48吨公里；所必需用到卡车为：20辆。满载行

车辆满载时（从铲点到卸点）车次运行情况如下表：

铲位1铲位2铲位3铲位4铲位7铲位9铲位10

矿石漏倒装场Ⅰ

29

24

54

68

14

9

40

合计78160

岩场288745160岩石漏72283228160倒装场Ⅱ14355411114合计96969696969696672由最短路径单目标函数求出其空载时（从卸点到铲点）车次运行情况如下表：

铲位1铲位2铲位3铲位4铲位7铲位9铲位10合计矿石漏倒装场Ⅰ岩场岩石漏倒装场Ⅱ合计

9696

96

32

96

6496

1896

9696

96

96

1464

3264

96

78160160160114672

综合比较以上三个方案可见，方案2相对最好，在满足了最大产量10.3488万吨和最多岩石产量4.928万吨的情况下得到了最小总运量为148904.14吨公里。

六、双原则模型的建立与求解

1、模型的建立

我们已经给出了针对每个原则的数学模型，模型1是根据成本最低原则而建立的，模型2主要是根据产量最高原则而建立的。对于公司来说，他要求总的经济效益最大，总的经济效益包括收益与成本，而收益直接与产量挂钩。所以公司要求既要使产量尽可能大，同时又要使成本尽可能小。这样，我们就有必要综合考虑两个原则约束下的最优运输方案。

对于问题中隐藏的约束条件，在考虑双原则下和单原则下几乎相同，建立综合模型的主要困难是如何处理多个目标函数之间的关系，让它们都尽可能的满足最优状态，也就是使运输决策集Go矩阵和Return矩阵能同时满足以下三个目标：

minQ=∑∑agijsij

i=1j=1

mn mn

minN= ∑∑(gij+rij)sij/v+∑∑(gijt上+rijt下)+t* /T

i=1j=1 i=1j=1

m

n

m

n

maxF=a∑∑gij

i=1j=1

约束条件仍为：

（1）供求限制约束（2）需求限制约束

（3）单个铲位装车总量的限制（小于T/t上）（4）单个卸点卸车总量的限制（小于T/t下）

（5）非整数限制

（6）最小饱和度限制2、模型的求解

以上的模型就是典型的多目标规划问题。在多目标规划问题中，目标越多，目标间的矛盾性就越突出，最优化问题的求解就越困难。所以一般求解多目标规划问题时，先确定各目标在决策中的重要性，称为目标排序，或根据各目标间的逻辑关系，将多目标转化成单目标规划问题。常用的目标排序法有多种，如目标规划法、线性加权法、平方和加权法、理想点法、分量乘除法和功效系数法。

简要地分析各个目标间的关系及公司的实际情况可知，对公司来说，出动的卡车的数量是硬性条件。在运输过程中,要求产量最大,运量最小,这两者相互对立又彼此限制，车辆一般由产量和运量决定，所以我们可以先考虑产量和总运量两个目标，最后根据由这两个目标所得的结果求解所需的卡车数量。分析产量和运量的数学表达式我们可以发现这两个参数在数量只差了一个sij因子，所以我们一所有路线的长度的平均值sij为折合因子，利用偏好性系数加权法将双目标规划问题转化为单目标规划的数学模型：

Max

U=w∑∑aijij+(1 w)∑∑asijgij

i=1j=1

i=1j=1

mnmn

n

∑agij≥Ki,i=1,2 m j=1

m m

∑bjgija/∑gija∈[29.5%±1%]

j=1 j=1

m

∑agij≤Mj,j=1,2 n i=1 10

s.t ∑gij≤160,i=1,2,3,4,5; j=1 5

∑gij≤96,j=1,2,3 9,10 i=1

g≥0且g为非负整数

ij

ij

mng×(5+3) nm2×gijsij

ij

+∑∑≤20 ∑∑60×8i=1j=1 i=1j=128×8

其中w是权值，反应了公司对总运量的偏好程度。

我们在求解上述模型时需要考虑电铲数量的限制，现在我们仅有7辆电铲，并且电铲在一个班次内不可移动，则相当于只有几个铲位可供利用。由排列组合知识

7

知，电铲在铲位的分配方案共有C10=120种，.在上述组合及目标函数的约束下，令

w从0到1以0.1的步长进行遍历，利用Mathematica的线性规划程序进行求解，可得到最优的铲位组合。考虑最一般的情况，取w=0.5，此时得到的最优解结果为：

满载运程：851.95公里；空载运程：769.28公里。最小总运量：131200.3吨公里；最小车辆数：18辆。

车辆满载时（从铲点到卸点）车次运行情况如下表：

铲位1铲位2铲位3铲位4铲位8铲位9铲位10

合计

矿石漏2156178倒装场Ⅰ1568968160岩场128761160岩石漏8128456160倒装场Ⅱ21283584合计96969674968896642由最短路径单目标函数求出其空载时（从卸点到铲点）车次运行情况如下表：

铲位1铲位2铲位3铲位4铲位8铲位9铲位10合计矿石漏倒装场Ⅰ岩场岩石漏倒装场Ⅱ合计

54

96

9696

96

643296

64

64

1074

4296

96

24

78160160160

84642

8896

七、模型的检验与分析

a)品位检验

模型的结果必须首先满足矿石卸点的品位限制，所以我们用品位检验法检验模型的2、w分析

在综合考虑开采公司的效益时,由上面双原则模型的求解结果来看,权值对方案有很大的影响,存在W的稳定区间,使最优方案不变,但存在少数的跳变点,在这些临界点附近,目标结果和方案会有较大变化,它主要源于开采公司负责人的心理变化,所以又称这些变化点心理极限点.在两个极限点之间,也就是在方案的稳定区间内变化时,结果不变,所以该模型在不同权重下的W比较稳定。w不同，对应的最优方案的目标值可能不同，但也可能相同。不同权重下的最优方案的各个目标值随w的变化趋势如图2所示，由此

图可见，当0.4≤w≤0.9时，所得的目标值可以满足公司的要求。所以在模型（3）中，我们对w

=0.5展开讨论是有意义的。

图2

八、模型中辅助理论的归纳

定理1（等待时间均分定理）：

对于一定存在等待时间的调度系统，应平均分配等待时间，以使总效益更高。

证明：设系统中有n辆卡车，模型中所需的总等待时间为t'，设周期为T，每辆车在一周期内的等待时间的为ti，i=1,2, ,n，所以有∑ti=t'为定值。对于一个已有确

i=1n

定总等待时间的系统，我们应尽量使每台车都有合适的时间以便于调度的顺利操作，对上面等式两边同除以周期T，ti/T相当于空闲率，那么最适合调度的状态应使所有卡车的空闲率的乘积尽可能大，因为

n

n

ti ti

≤ ∏ ∑Ti=1T

n t'

=

T

上式当且仅当t1=t2= tn时等号才成立。所以该定理成立。

定理2（跟随定理）：

一辆刚满载的卡车一定可以沿着在同一铲位装车的前一辆车的运输路线。

定理2很容易理解，因为装车的时间t上大于卸车的时间，所以先后同一铲位驶向同一卸点的两辆车一定不会发生等待现象（仅存在两辆车的情况）定理3（最理想车辆定理）：

一个最理想的调度方案所需出动的卡车数量刚好满足：

(gijt∑∑ij

=1

=1

nm

上

+rijt下)+∑∑sij(gij+rij)=NT

i=1j=1

nm

此定理在问题的分析中已经提到，也很容易理解，在此也不作证明。

九、模型的进一步讨论

1、电铲的数量对方案的影响

在模型1中，求出的最佳出动电铲的台数刚好是7台，此时电铲的数量对最优方案的得到没有影响。事实上只要理论求出的最佳电铲数目小于等于7台，电铲的数量对最优方案的得到都没有影响。但当产量增加时，电铲的数量也要增大，以满足生产的要求。在模型2中，目标是产量的最大化，我们不考虑电铲台数限制时，最优的开采方案需要出动10台，最少9台的电铲，这显然不能满足要求，所以我们在一个班次内只有7个铲位在开采，此时我们需要求出在这些铲位的组合下的最优开采运输方案，这样得到的解显然受到电铲的影响。

2、卡车路线选择的原则

在动态规划的调度系统中，我们以最小饱和度准则寻找待发的卡车的最优路线，以提高卡车、电铲的效率，从而提高开采公司的经济效益。除了最小饱和度准则外在文献[9]中还介绍了以下几种最优路径的选择准则。

（1）最早装车法（EarliestLoading）：即将卡车派往预计能最早得以装车的

那台电铲去。

（2）最大卡车法（MaxTruck）：即将卡车派往预计其等装时间最小的那台电铲

去。

（3）最大电铲法（MaxShovel）：即将卡车派往预计电铲等车时间最大的那台

电铲去。

在这些准则中，最大卡车法和最早装车法有其相似之处，二者目标都在于尽可能地提高卡车的利用率，因此在卡车紧张的系统中能得到较高的产量。但二者在算法及效果上也存在较大区别。相比之下，最大电铲法突出电铲的重要性，保证电铲效率的发挥，以使各台电铲的的产量较为均衡，因此宜用在电铲相对紧张的系统中。最小饱和度准则由于综合考虑了电铲、卡车两者的效率，因此其效果一直处于较好状态。并且，当系统中卡车数量较少时，MSDTC略优于MSP，随着卡车趋于饱和，两者的效果趋于一致。

由于这些确定的最优路线只能尽可能地使卡车不处于等待状态，并不能保障使卡车一定不处于等待状态，卡车沿某一路线运行是否会出现等待现象存在一个概率问题，所以我们也可以根据等待概率最小准则选择最优路线。

3、卡车的最佳数量

在上面的求解过程中，为了满足生产的要求，我们出动卡车的准则是在满足卡车数量限制的条件，尽可能首先满足运输的需求，而当理论上计算出的卡车数为非整数N′时，我们用以下方法确定卡车数量：

N=[N′]+1

N≤20

其中[N′]表示不超过N′的最大整数。

用这种方法确定卡车的数量，虽能产量可能大，但同时也意味着在系统中进行调度的整个过程中，一定存在若干量卡车在某个时候发生等待现象，也就意味着运输资源，没得以充分的利用。当N′的小数位数比较小时，我们可以直接取N′=[N′]，虽然运量

小些，但可以保障卡车资源得以充分利用，这样可能会使经济效益更优。那么我们如果判断N是取[N′]还是取[N′]+1，这里我们采用λ判据进行判断，具体表达如下：

[N′],N [N′]≤λN=

[N′]+1,N [N′]>λ

其中λ为判据因子，λ的具体值可由实际生产经验给出。根据等待时间的经济效益与出车成本之间的关系，建立以经济效益最大为目标函数的规划模型，解该模型也可求出λ。

十、模型的评价

1模型的优点（1）针对原则1和原则2所建的两个数学模型和双原则模型都将全部的决策

变量融为一体，模型的综合程度很高。

（2）模型中因入了运输Go矩阵和返回Return矩阵，既为问题的研究提供了

方面，有形象的描述了具体的卡车调度方案。

（3）模型的求解采用分步求解，逐层突破的方法，在个别层中又运用了比较

成熟的线性规划模型和求解方法，从而使较为复杂的数学模型通过分层的求解得到满意的解。

（4）在求解模型2中，我们用了枚举法寻找最佳运输方案，从而保障所得到

的方案为最优方案。

（5）在对模型的建立和求解中，我们找出了几个公理，这些理论从大方向上

指导我们建模和模型的求解。

2模型的缺点（1）每个模型的变量太多，不易直接的求解，只能从别的途径寻找最优解。（2）在分步求解模型时，可能使得到的解只是原模型中接近最优解的一个

解，却可能并不是最优解，并且在求解中并不能给出每辆卡车的每时每刻的具体调动方案，只能分别给出了每条路线前往和返回两个方向的车次。

（3）在确定模型2求解所得的多个方案的优劣时，我们用模糊评判的方法，

虽然可以在很大程度上反映了方案的属性，但还是带些主观因素，缺乏很严密的理论指导。

3模型的改进方向

针对模型的缺点，结合露天矿开采卡车调度的实际情况，我们可以从以下几个方向对模型进行改进。

（1）引进卡车的等待概率

由于卡车在实际的调度中，路线选取是根据一定原则随机选取的，并且理论上选取路线的准则只是相对较好，并不能完全保障卡车不处于等待状态，也就是说卡车在每条路线上发生等待的情况都存在一定概率，所以根据现实的情况，我们可把等待概率引入模型中，并根据等待概率最小准则判断卡车所走的路线。（2）对线路赋权

这主要是为了改进根据原则2所建的模型。原则2的主要目标是使产量最大化，但也要尽量使岩石含量较大，使总运量最小。为了直接寻找最优的运输方案，可以对路线进行赋权以控制产量最大，同时使每辆运输的卡车沿路线短的路线运

行。

定义：从i铲位到j卸点路线的权值为eij=

1。sij

以赋权总产量为最大化为目标函数，其数学表达式为：

F=∑∑aeijgij

i=1j=1

mn

（3）综合考虑生产成本

模型中没有考虑电铲、卡车的消耗能源的成本，没有考虑电铲的可服役的总时间，即没有考虑电铲的折旧费用。而事实上这种大型的电铲和卡车消耗能源的成本很大，而且每台电铲的购买费用很高，这样累计起来开采公司的成本也很大。如果我们把这些成本也加入模型中去，对公司的收益的描述更精确更贴近实际情况。

十一、对露天矿开采运输公司的建议

目前对于多数卡车运输的露天矿仍沿用固定搭配方法，即在一个工作班次内将某台卡车固定配往某采掘工作面。这种固定配车制妨碍了采运设备效率的充分发挥。随着信息科学及通讯技术的发展，七十年代以来，各国已陆续出现了一些卡车自动化调度露天矿，如美国、加拿大、西班牙、保加利亚、南非等地的露天矿及金属矿中，已分别建立了十余个自动化程度各不相同的卡车自动化调度系统。露天矿卡车自动化调度技术在国外发展较快，软硬件技术均趋成熟。目前，国外安装使用自动化调度系统的矿山已由20世纪80年代的10余家发展到30多家。国外应用实际表明，凡采用了自动化调度系统的矿山，都能使生产效率提高5%—15%，个别甚至提高了23%之多。所以我们建议如果条件允许，卡车运输的露天矿应尽可能使用自动化调度系统，以提高公司的经济效益。

1.露天矿开采使用调度系统的好处

自动调度系统的成本相对于大的露天矿开采公司来说很小，只需提供必要的软硬件及必备的通讯设备。但系统的产量可以提高5%—15%的产量，由于产量的基数大，所以使用调度系统后提高的那部分产量是很可观的。所以使用调度系统首先可提高开采公司的经济效益。系统的使用可提高设备的利用率，二是提高设备单位成本的利用率。由于电铲和卡车可称为超重设备，它们的功率很大，耗油很大，而且从一开工就不熄火，所以如不充分加以利用，机械及油料的损耗就不能挽回他们对应的经济效益。以上都是从直观上看使用调度系统的好处，使用调度系统的公司还存在潜在的好处：

（1）可塑造公司依靠科技进步，提高生产率的良好形象；（2）增强公司员工的荣誉感；（3）带动公司员工的工作积极性，减少员工在工作过程因发生等待时间而产生的受挫情绪

（4）提高公司在同行业中的地位2．卡车调度系统使用的说明

在整个调度系统中，优化调度是整个卡车调度系统的核心，优化调度的好坏直接影响设备效率的发挥及整个系统的经济效益。调度的具体方案是由系统的数学模型而产生的，所以数学模型的科学性和先进性是优化调度的基础，同时模型的算法优劣也对调度

方案有很大影响，由于此模型的直接求解很难，所以一种可行的算法是分步计算。在实际应用中，如何使各步紧密的衔接起来对快速实现模型的求解有很大的作用。在实际应用时可以使用大型的计算软件或几种软件的有效组合，并且使各步都能相互采集数据，从而使整个模型的求解成为一脉相承的整体，提高运算速度。

在进行实际调度时有两种调度方法，一是预先安排，也就是在工作之前，将所有卡车的运输路线都已分配好，这种安排不易克服工作过程中出现的障碍，适应性弱。另一种是实时安排，当一辆卡车在选择路线前，先向指挥中心发无线电信号并表明现在位置。指挥中心根据现有系统车次的分布状态，经过有效的运算给出该卡车的路线，这种方法虽然麻烦但适用性强。

参考文献

[1][2][3][4][5][6][7][8][9]

朱道元等编著,数学建模案例精选,北京:科学出版社,2003。

丁大正,科学计算强档Mathematica4教程,北京:电子工业出版社,2002。谷源盛等编著,运筹学,重庆:重庆大学出版社,2001。

田国强等编著,现代经济学与金融学前沿发展,北京:商务印书馆,2002。龚六堂,动态经济学方法,北京:北京大学出版社,2002。过秀成等编著,交通工程学,南京:东南大学出版社2000。杨肇夏，计算机模拟及其应用,北京:中国铁道出版社,1999。姜启源，数学模型（第二版），北京：高等教育出版社，1997。张幼蒂，露天矿卡车调度模型，中国矿业学院科技情报室，1984。

本文来源：https://www.bwwdw.com/article/s04j.html