露天矿生产的车辆安排
问题的提出
? 问题的提出,
现代化铁矿是露天开采的，它的生产主要有电动铲车（以下
简称电铲）装车，电动轮自卸卡车（以下简称卡车）运输来完成。
提高这些大型设备的利用率是增加露天矿经济效益的首要任务。
露天矿场里有若干个爆破生成的石料堆，每堆称为一个铲位，
每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，
平均铁含量不低于 25%的为矿石，否则为岩石。每个铲位的矿石、
岩石数量，以及矿石的平均含铁量（称为品位）都是已知的。每
个铲位至多能安置一台电铲，电铲的平均装车时间为 5分钟。
问题的提出
? 问题的提出 (续 ),
卸货地点（以下简称卸点）有卸矿石的矿石漏,2个铁路倒装
场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都
有各自的产量要求。从保护国家资源的角度及矿山的经济效益考
虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都是
29.5% 1%，称为品位限制）搭配起来送到卸点，搭配的量在一
个班次（ 8小时）内满足品位限制即可。从长远来看，卸点可以
移动，但一个班次内不变。卡车的平均卸车时间为 3分钟。
所用卡车载重量为 154吨，平均时速 28。卡车的耗油量很大，
每个班次每台车消耗将近 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
倒装场 I 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
倒装场 II 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%
模型的假设
? 模型的假设,
1,卡车在一个班次中不应发生等待或熄火后再启动的情况 ;
2,在铲位或卸点处由两条路线以上造成的冲突问题面前,我们认
为只要平均时间能完成任务,就认为不冲突,我们不排时地进行讨
论 ;
3,空载与重载的速度 v都是 28km/h,耗油相差却很大 ;
4,卡车可能提前退出系统 ;
5,卡车加油,司机吃饭与上厕所等休息时间忽略不计 ;
符号的说明
? 符号的说明,
1,T(i,j)为 路线的运行周期 ;
2,d(i,j)为 路线的距离 ;
3,为每条路线上可容纳的最大车辆数 ;
4,ME(i,j)为一辆车在相应的路线上运输次数的上界 ;
5,为第 n辆车在 路线上运输的次数 ;
6,为第 n辆车是否被利用的标志数
7,为第 i个铲点是否有铲车的标志数
ijSD?
ijSD?
(,)ij?
(,)nY i j
ijSD?
nc
ih
问题的分析
? 问题的分析,
这是一个多目标组最优化问题。优化目标有两个，最小运输
量和最少卡车数，两个目标在一定程度上是相互影响的，在运输
成本中，总运量是主要决定因素，把总运量作为主要目标，将卡
车数转化为约束条件，使卡车总数不大于 20，得到改进模型。根
据多目标的主要目标法的有效解理论，在此最优解集上求最少卡
车书的有效解或弱有效解。另外，由于电铲和卸点只能同时为一
辆卡车服务，若此时还存在其他卡车在该铲点或卸点需要服务，
就等于出现等待情况，在解决时应避免该情况发生。在装石料时
若一条路线中卡车数超过一定值时，必然会出现等待。
问题的分析
? 问题的分析 (续 ),
为了方便讨论，我们按矿石漏,倒装场 I，倒装场 II，岩石漏，
岩场的顺序将它们依次记作卸点 D1,D2,…,D5,装点 S1，
S2,…,S10 。于是，每条 → → 路线的运行周期为,
T（ i,j） =3+5+ (min)
其中的 d(i,j)为 与 之间的距离（ km）,v为卡车速度
（ km/h）,由于每装一次车的平均时间为 5min（大于卸车时间
3min），那么每条路线上可容纳的最大车辆数为,
=[T(i,j)/5],
此外，每辆车一个班次工作 480min，则一辆车在相应的路线上运
输次数的上界为 ME(i,j)=[480/T(i,j)]。
120 (,)d i j
v
iS
iS iSjD
jD
(,)ij?
模型的建立及求解
? 模型准备,
在模型建立之前，先给出几个必要的命题（证明过程略）和
分析过程。我们用标志数 来刻画第 n辆车是否被利用。当第 n辆
车被利用时 =1，否则 =0。
命题 1,第 n辆车是否被利用的标志数,
,n=1,2,…,20;
其中 是第 n辆车从 到 的运输次数,flag为符号函数。
命题 2,第 i个铲点是否有铲车的标志数,
,i=1,2,…,10;
nc
nc
1 0 5
11
( (,) )nn
ij
c fla g Y i j
??
? ??
(,)nY i j
nc
iS jD
2 0 5
11
( (,) )in
ij
h fl a g Y i j
??
? ??
模型的建立及求解
? 问题一的模型,
对于问题 1和问题 2，都必须满足,
1.各铲点向所有卸点提供的岩石和矿石总量应分别不大于该铲点
矿石数量和岩石数量，即为模型 Ⅰ 中的（ 1）式。
2.有所有铲点向各卸点运输的石料总和应不小于卸点所需石料的
下限，即为模型 Ⅰ 中的（ 2）式。
3.品味限制，在三个矿石卸点，矿石的平均铁含量应在给定范围
内，即为模型 Ⅰ 中的（ 3）式。
4.由于铲车数量为 7，所以要求利用铲点不超过 7个，即为模型 Ⅰ
中的（ 4）式。
5.每个铲点的工作次数不大于 96次，即为模型 Ⅰ 中的（ 5）式。
6.每个卸点的工作次数不大于 160次，即为模型 Ⅰ 中的（ 6）式。
模型的建立及求解
? 问题一的模型 (续 ),
综上所述，可得问题一的基本模型,
模型 Ⅰ,
这里,n=1,2,…,20;
2 0 1 0 5
1 1 1
m i n 1 5 4 ( { (,) (,) }n
n i j
f Y i j d i j
? ? ?
? ???
20
1
min n
n
c
?
?
1 0 5
11
( (,) )nn
ij
c fla g Y i j
??
? ??
模型的建立及求解
? 问题一的模型 (续 ),
s.t,;,i=1,2,…,10; (1)
,j=1,2,…,5; (2)
,j=1,2,3; (3)
1 0 3
11
1 5 4 (,)ni
nj
Y i j k
??
???
2 0 5
11
1 5 4 (,)ni
nj
Y i j y
??
???
2 0 1 0
11
1 5 4 (,)nj
ni
Y i j M D
??
???
20 10
11
20 10
11
(,)
2 8,5 % 3 0,5 %
(,)
ni
ni
n
ni
Y i j
Y i j
?
??
??
??
??
??
模型的建立及求解
? 问题一的模型 (续 ),
,,i=1,2,…,10; (4)
,i=1,2,…,10; (5)
,j=1,2,…,5; (6)
,,i=1,2,…,10,n=1,2,…,20 (7)
,n=1,2,…,20,i=1,2,…,10,j=1,2,…,5 (8)
10
1
7i
i
h
?
??
2 0 5
11
( (,) )in
ij
h fl a g Y i j
??
? ??
2 0 5
11
(,) 9 6n
nj
Y i j
??
???
2 0 1 0
11
(,) 1 6 0n
ni
Y i j
??
???
{0,1}ih ?
(,) { 0 }nY i j N??
{0,1}nc ?
模型的建立及求解
? 模型的求解,
模型 Ⅰ 是双目标规划,运输总量为线性函数，所需卡车数是非
线性的，并且不连续，无法用一般的非线性规划求解。根据多目
标规划中的主要目标法，将运输总量设为主要目标，最少卡车数
设为次要目标，将次要目标转化为约束条件，从而使得模型 Ⅰ 简
化为单目标规划问题。由前面的讨论，将最少卡车数转化为约束
条件后，可以求出最优解。
模型的建立及求解
? 模型的求解 (续 ),
于是，化简后的改进模型为,
模型 Ⅱ,
s.t,(1),(2),(3),(5),(6),(7),(8)同模型 Ⅰ ;
,,i=1,2,…,10; (4)
,,n=1,2,…,20; (9)
2 0 1 0 5
1 1 1
m i n 1 5 4 ( { (,) (,) }n
n i j
f Y i j d i j
? ? ?
??? ? ?
10
1
7i
i
h
?
??
2 0 5
11
( (,) )in
ij
h fl a g Y i j
??
? ??
20
1
20n
n
c
?
??
1 0 5
11
( (,) )nn
ij
c fla g Y i j
??
? ??
模型的建立及求解
? 模型的求解 (续 ),
由于排时计划无效，等待问题很难从基本上解决，我们这里
深入讨论一个班次内所有卡车来回于第 i个铲点和第 j个卸点次数
的上界 M(i,j)，由于每条路线卡车的运行周期是一定的，且相邻
两车间隔不小于 5分钟，因而在整条路线上的车次也是一定的，
加之受到相应铲点岩石和矿石最大产量的限制，可得到,
其中, =,,。
(,) m i n { (,) (,),[ (,) / 1 5 4 ] }M i j i j M E i j p i j???
480(,) [ ]
(,)M E i j T i j?(,)ij?
(,)[]
5
T i j,1,2,3(,)
,4,5
i
i
kjp i j
yj
???
? ?
?
模型的建立及求解
? 模型的求解 (续 ),
经过计算后得到,
于是，,得到最终求解模型。
6 1 6 8 6 4 6 8 7 1 7 2 6 8 8 4 8 7 7 0
6 1 6 8 6 4 6 8 7 0 8 1 6 6 8 4 8 7 8 0
6 1 6 8 6 4 6 8 7 1 8 1 6 8 6 4 7 0 8 1
8 1 7 1 7 0 6 8 7 2 7 5 6 8 7 4 8 0 8 1
8 1 7 1 8 4 6 8 7 4 8 0 6 8 7 4 7 6 8 1
T
M
??
??
?
??
??
1 0 5(,)M i j ??
20
1
(,) (,)n
n
Y i j M i j
?
?? 1,2,...,5i??
模型的建立及求解
? 模型的求解 (续 ),
模型 III,
s.t,(1),(2),…,(9) 同模型 II;
,i=1,2,…,10,j=1,2,…,5 。 (10)
1 0 5 2 0
1 1 1
m i n 1 5 4 ( { ( ) (,) (,) }n
i j n
f Y i j d i j
? ? ?
??? ? ?
20
1
(,) (,)n
n
Y i j M i j
?
??
模型的建立及求解
? 模型的求解 (续 ),
根据以上的改进模型，为了便于求解，暂时不考虑约束条件
（ 9），将 看成一个变量，一共 50个变量。这恰好是
个整数线性规划问题，利用 Microsoft Office Excel软件对其进
行求解，得到最优解,最小运量 =556.03 154=85628.62吨公里。
此时 5,6,7三个铲点没有运输量，恰好满足铲车和铲位数量的
约束，主要目标已经解决。
20
1
(,)n
n
Y i j
?
?
?
模型的建立及求解
? 模型的求解 (续 ),
在此基础上，分析车辆分配方案，使所用卡车数量最少。如
果 成立，则安排一辆卡车在一个班次内就只
行驶 路线。但当 不是 的整数倍时，
必然还要其他卡车将剩余的石料运输完，其车次为,
通过调整卡车在各路线的运输可使卡车最少。
20
1
(,) (,)n
n
Y i j M E i j
?
??
ijSD?
20
1
(,)n
n
Y i j
?
? (,)ME i j
20
1
(,) m o d ( (,),(,) )n
n
Z i j Y i j M E i j
?
? ?
模型的建立及求解
? 模型的求解 (续 ),
这里运用贪心算法，具体算法如下,
1.将剩余车次矩阵 中非零元素对应时间周期矩阵 从大
到小排序；
2.首先尽可能多运输 中最大元素对应的路线，但不能超过
班次总工作时间，如有时间剩余，则转移到 次大元素对应
的路线，选择其中不超过班次总工作时间的最大路线；运输以后
就在 减去已运输的次数；
3.依次策略直至一辆卡车的工作时间排满为止；
4.若 中还存在非零元素就返回 1，按上述方法重复，直至
剩余矩阵 中元素都为零,结束。
10 5Z ? 10 5T?
10 5T?
10 5T?
10 5Z ?
10 5Z ?
10 5Z ?
模型的建立及求解
? 模型的求解 (续 ),
表 1 问题 1一班次的运输方案,
其中,表示第 3辆卡车在铲点 2与卸点 1之间共运输了 13车次，其它类似。
铲点
卸点 1 2 3 4 8 9 10 品位
1 0 0 0 0 30,50%
2 0 0 0 0 0 30,02%
3 0 0 0 0 30,49%
4 0 0 0 0 0 ———
5 0 0 0 0 0 ———
(4) (7)37,44
(3)13
(1) (8)3,39
(5)13 (6)2
(6) (9)8,35
(4) (10)6,37
(1) (11)25,29
(12) (2)38,32
(2) (3)5,6
(6) (12)23,47
(5)15
(3)13
模型的建立及求解
? 模型的求解 (续 ),
经过调整并且考虑到转移时间差，我们得到第一问所需最小
车辆数为 13辆，即以下定理,
定理 1:在该问题中所利用的最少的车辆数为 13辆。
证明,在最优解中，我们将运输周期 和运输计划安排车次
相乘并求和得出在此方案下的理想工作时间总和,
=6038.976分钟
每辆卡车的有效工作时间都是 480分钟，所需卡车数
=12.5813辆，所以所需卡车数必然大于 12辆。而表 1中已给出了
13辆车的可行运输方案，所以命题成立。
10 5T?
10 5N ?
1 0 5
11
(,) (,)
ii
to ta l T i j N i j
??
????
/ 480n total?
模型的建立及求解
? 转移时间差,
在以上的讨论中, 我们均没有考虑当一辆卡车从一条路线转
移到另一条路线上的时间差 。 时间差的产生主要是在运输过程中,
这辆车无需再回到原来的铲点, 而是直接到另一条路线上相应的
铲点, 由于两条路线的不同, 造成了卡车在转移过程中的转移时
间差 。 不妨设 （ i,j） 为一条从 到 的运输路线, 那么当一
辆卡车从路 1线转移到路线 2时, 其转移时间差, iS jD
12
1 1 2 2 2 1 1 1
12
0
,:
( (,) (,) ) (,) (,)
,:
2
if i i
t i j i j T i j T i j
if i i
?
??
?? ? ?
??
?
模型的建立及求解
? 转移时间差 (续 ),
由于原来的理想时间总和并没有考虑到转移时间差, 从而有,
结论：根据最优结果进行分配车次，考虑转移时间差，其时间的
总量必然比原来的理想时间总和 6038.976大。
模型的建立及求解
? 等待问题的讨论,
由于对任何多于两辆车的讨论都可以转化为两辆车的情况,
所以, 在此仅讨论两辆车产生等待的情况 。 根据卡车出现的位置
对等待情况进行分类,
1.在铲点处产生等待 。 如果两辆车在同一条路
线上运行, 那么它们的运行可以用右图表示,
只有当
时, 两车才会在装车点发生等待 。
其中 AB表示装货时间 (5min),CD表示卸货时间 (3min),S1,S2表示
两辆卡车, t1,t2分别表示两辆车开始在 A点装货的时间 。
A
B
D
C
S1 S2
2 1 1 2{ m o d (,),m o d (,) } 5M a x t t T t t T? ? ?
模型的建立及求解
? 等待问题的讨论 (续 ),
如果这两车在不同的路线
上但是在同一铲点装货运
行, 如图二, 则只有当以
下三式,
联立有解的时候, 两车才会产生等待 。
D1
C1
A1
B1
A2
B2
D2
C2
S1
S2
10 m o d (,) 5t t T? ? ?
20 m o d (,) 5t t T? ? ?
12m a x (,) 4 8 0t t t??
模型的建立及求解
? 等待问题的讨论 (续 ),
2.卸点处产生等待 。 类似于 1的
讨论, 可以分为两种情况,
当两辆车在同一条路线上面运行
时, 如右图, 那么必须满足,
A
B
D
C
S1 S2
2 1 1 2{ m o d (,),m o d (,) } 3M a x t t T t t T? ? ?
模型的建立及求解
? 等待问题的讨论 (续 ),
当两辆车在不同一条路
线上运行时, 如右图,
只有当以下三式,
联立有解的时候, 两车才会产生等待 。
其中 表示时间段,T表示一圈所用的时间 。
S1 S2
A1
B1
D1
C1
D2
C2
A2
B2 1 1 1 1m o d (,) 3CCt t t T t? ? ? ?
2 2 2 2m o d (,) 3CCt t t T t? ? ? ?
12m a x (,) 4 8 0t t t??
1(2)Ct 1(2) 1(2)A B C??
模型的建立及求解
? 问题二的模型,
对于问题 2，基于问题 1的约束条件，求最大产量且运输量最小，
可得出模型如下,
模型 Ⅳ,
s.t.(1)…… (9)同模型 Ⅲ
2 0 1 0 5
1 1 1
m a x 1 5 4 (,)n
n i j
p Y i j
? ? ?
? ???
1 0 5 2 0
1 1 1
m i n 1 5 4 ( { ( ) (,) (,) }n
i j n
f Y i j d i j
? ? ?
??? ? ?
模型的建立及求解
? 问题二的模型 (续 ),
采用类似于问题 1的解法，首先不考虑约束条件（ 9），按铲
点分布不同，共分为 个整数线性规划子问题，求出其产量
的最大的解。然后，将最大产量作为一个约束条件，并考虑岩石
产量优先，再利用 Microsoft Office Excel求解最小运量。求得
总产量 671车次,10.3334万吨，总运量为 147792.26吨公里，其
中岩石产量为 320车次,49280吨；矿石产量为 351车次,54054吨；
卡车数量为 20辆。
710 120C ?
模型的建立及求解
? 问题二的模型 (续 ),
类似于问题 1，采用贪心算法，并且考虑转移时间差，求出安排如表 2,
表 2 问题 2一班次的运输方案,
铲点
卸点 1 2 3 4 8 9 10 品位
1 0 0 0 0 30,50%
2 0 0 0 30,06%
3 0 0 0 30,50%
4 0 0 0 ———
5 0 0 0 0 ———
(10)24
(7) (10)
(11)
23 5
44
(6) (7)
(12)
10 10
39
(6)8
(5) (6)19,9
(7) (13)
(19)
4,18
18
(8) (9)3,5
(9)16
(8)32
(3) (14)
(4) (5)
4,37
13,14
(3) (4)27,1
(4) (10)18,2
(15) (18)32,32
(6) (2)1,11
(2)20
(16) (17)38,38
(1)24
(1) (2)
(20)
22 5
45
模型的评价与改进
? 模型的评价与改进,
本文对建立的两个基本模型逐步简化求解，将多目标规划利
用主要目标法转化为单目标规划，非线性规划转化为线性规划，
利用 Microsoft Office Excel软件的整数规划求解，模型简单，
适用性强，容易编程实现求解，并且能够很好的解决问题的整数
约束。由于模型的简单化，就避免不了很多重复操作，将原问题
分成 120个简单的整数规划问题的子问题，为了求得最优解，必
须遍历这 120个问题，求出各个子问题的最优解，在进行比较，
时间开销很大；但是，在求解过程中，我们发觉很多情况其实是
不符合要求的，这样可以将那些对产量上限很不敏感的铲点不予
考虑，作出适当的简化。
问题的提出
? 问题的提出,
现代化铁矿是露天开采的，它的生产主要有电动铲车（以下
简称电铲）装车，电动轮自卸卡车（以下简称卡车）运输来完成。
提高这些大型设备的利用率是增加露天矿经济效益的首要任务。
露天矿场里有若干个爆破生成的石料堆，每堆称为一个铲位，
每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，
平均铁含量不低于 25%的为矿石，否则为岩石。每个铲位的矿石、
岩石数量，以及矿石的平均含铁量（称为品位）都是已知的。每
个铲位至多能安置一台电铲，电铲的平均装车时间为 5分钟。
问题的提出
? 问题的提出 (续 ),
卸货地点（以下简称卸点）有卸矿石的矿石漏,2个铁路倒装
场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都
有各自的产量要求。从保护国家资源的角度及矿山的经济效益考
虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都是
29.5% 1%，称为品位限制）搭配起来送到卸点，搭配的量在一
个班次（ 8小时）内满足品位限制即可。从长远来看，卸点可以
移动，但一个班次内不变。卡车的平均卸车时间为 3分钟。
所用卡车载重量为 154吨，平均时速 28。卡车的耗油量很大，
每个班次每台车消耗将近 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
倒装场 I 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
倒装场 II 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%
模型的假设
? 模型的假设,
1,卡车在一个班次中不应发生等待或熄火后再启动的情况 ;
2,在铲位或卸点处由两条路线以上造成的冲突问题面前,我们认
为只要平均时间能完成任务,就认为不冲突,我们不排时地进行讨
论 ;
3,空载与重载的速度 v都是 28km/h,耗油相差却很大 ;
4,卡车可能提前退出系统 ;
5,卡车加油,司机吃饭与上厕所等休息时间忽略不计 ;
符号的说明
? 符号的说明,
1,T(i,j)为 路线的运行周期 ;
2,d(i,j)为 路线的距离 ;
3,为每条路线上可容纳的最大车辆数 ;
4,ME(i,j)为一辆车在相应的路线上运输次数的上界 ;
5,为第 n辆车在 路线上运输的次数 ;
6,为第 n辆车是否被利用的标志数
7,为第 i个铲点是否有铲车的标志数
ijSD?
ijSD?
(,)ij?
(,)nY i j
ijSD?
nc
ih
问题的分析
? 问题的分析,
这是一个多目标组最优化问题。优化目标有两个，最小运输
量和最少卡车数，两个目标在一定程度上是相互影响的，在运输
成本中，总运量是主要决定因素，把总运量作为主要目标，将卡
车数转化为约束条件，使卡车总数不大于 20，得到改进模型。根
据多目标的主要目标法的有效解理论，在此最优解集上求最少卡
车书的有效解或弱有效解。另外，由于电铲和卸点只能同时为一
辆卡车服务，若此时还存在其他卡车在该铲点或卸点需要服务，
就等于出现等待情况，在解决时应避免该情况发生。在装石料时
若一条路线中卡车数超过一定值时，必然会出现等待。
问题的分析
? 问题的分析 (续 ),
为了方便讨论，我们按矿石漏,倒装场 I，倒装场 II，岩石漏，
岩场的顺序将它们依次记作卸点 D1,D2,…,D5,装点 S1，
S2,…,S10 。于是，每条 → → 路线的运行周期为,
T（ i,j） =3+5+ (min)
其中的 d(i,j)为 与 之间的距离（ km）,v为卡车速度
（ km/h）,由于每装一次车的平均时间为 5min（大于卸车时间
3min），那么每条路线上可容纳的最大车辆数为,
=[T(i,j)/5],
此外，每辆车一个班次工作 480min，则一辆车在相应的路线上运
输次数的上界为 ME(i,j)=[480/T(i,j)]。
120 (,)d i j
v
iS
iS iSjD
jD
(,)ij?
模型的建立及求解
? 模型准备,
在模型建立之前，先给出几个必要的命题（证明过程略）和
分析过程。我们用标志数 来刻画第 n辆车是否被利用。当第 n辆
车被利用时 =1，否则 =0。
命题 1,第 n辆车是否被利用的标志数,
,n=1,2,…,20;
其中 是第 n辆车从 到 的运输次数,flag为符号函数。
命题 2,第 i个铲点是否有铲车的标志数,
,i=1,2,…,10;
nc
nc
1 0 5
11
( (,) )nn
ij
c fla g Y i j
??
? ??
(,)nY i j
nc
iS jD
2 0 5
11
( (,) )in
ij
h fl a g Y i j
??
? ??
模型的建立及求解
? 问题一的模型,
对于问题 1和问题 2，都必须满足,
1.各铲点向所有卸点提供的岩石和矿石总量应分别不大于该铲点
矿石数量和岩石数量，即为模型 Ⅰ 中的（ 1）式。
2.有所有铲点向各卸点运输的石料总和应不小于卸点所需石料的
下限，即为模型 Ⅰ 中的（ 2）式。
3.品味限制，在三个矿石卸点，矿石的平均铁含量应在给定范围
内，即为模型 Ⅰ 中的（ 3）式。
4.由于铲车数量为 7，所以要求利用铲点不超过 7个，即为模型 Ⅰ
中的（ 4）式。
5.每个铲点的工作次数不大于 96次，即为模型 Ⅰ 中的（ 5）式。
6.每个卸点的工作次数不大于 160次，即为模型 Ⅰ 中的（ 6）式。
模型的建立及求解
? 问题一的模型 (续 ),
综上所述，可得问题一的基本模型,
模型 Ⅰ,
这里,n=1,2,…,20;
2 0 1 0 5
1 1 1
m i n 1 5 4 ( { (,) (,) }n
n i j
f Y i j d i j
? ? ?
? ???
20
1
min n
n
c
?
?
1 0 5
11
( (,) )nn
ij
c fla g Y i j
??
? ??
模型的建立及求解
? 问题一的模型 (续 ),
s.t,;,i=1,2,…,10; (1)
,j=1,2,…,5; (2)
,j=1,2,3; (3)
1 0 3
11
1 5 4 (,)ni
nj
Y i j k
??
???
2 0 5
11
1 5 4 (,)ni
nj
Y i j y
??
???
2 0 1 0
11
1 5 4 (,)nj
ni
Y i j M D
??
???
20 10
11
20 10
11
(,)
2 8,5 % 3 0,5 %
(,)
ni
ni
n
ni
Y i j
Y i j
?
??
??
??
??
??
模型的建立及求解
? 问题一的模型 (续 ),
,,i=1,2,…,10; (4)
,i=1,2,…,10; (5)
,j=1,2,…,5; (6)
,,i=1,2,…,10,n=1,2,…,20 (7)
,n=1,2,…,20,i=1,2,…,10,j=1,2,…,5 (8)
10
1
7i
i
h
?
??
2 0 5
11
( (,) )in
ij
h fl a g Y i j
??
? ??
2 0 5
11
(,) 9 6n
nj
Y i j
??
???
2 0 1 0
11
(,) 1 6 0n
ni
Y i j
??
???
{0,1}ih ?
(,) { 0 }nY i j N??
{0,1}nc ?
模型的建立及求解
? 模型的求解,
模型 Ⅰ 是双目标规划,运输总量为线性函数，所需卡车数是非
线性的，并且不连续，无法用一般的非线性规划求解。根据多目
标规划中的主要目标法，将运输总量设为主要目标，最少卡车数
设为次要目标，将次要目标转化为约束条件，从而使得模型 Ⅰ 简
化为单目标规划问题。由前面的讨论，将最少卡车数转化为约束
条件后，可以求出最优解。
模型的建立及求解
? 模型的求解 (续 ),
于是，化简后的改进模型为,
模型 Ⅱ,
s.t,(1),(2),(3),(5),(6),(7),(8)同模型 Ⅰ ;
,,i=1,2,…,10; (4)
,,n=1,2,…,20; (9)
2 0 1 0 5
1 1 1
m i n 1 5 4 ( { (,) (,) }n
n i j
f Y i j d i j
? ? ?
??? ? ?
10
1
7i
i
h
?
??
2 0 5
11
( (,) )in
ij
h fl a g Y i j
??
? ??
20
1
20n
n
c
?
??
1 0 5
11
( (,) )nn
ij
c fla g Y i j
??
? ??
模型的建立及求解
? 模型的求解 (续 ),
由于排时计划无效，等待问题很难从基本上解决，我们这里
深入讨论一个班次内所有卡车来回于第 i个铲点和第 j个卸点次数
的上界 M(i,j)，由于每条路线卡车的运行周期是一定的，且相邻
两车间隔不小于 5分钟，因而在整条路线上的车次也是一定的，
加之受到相应铲点岩石和矿石最大产量的限制，可得到,
其中, =,,。
(,) m i n { (,) (,),[ (,) / 1 5 4 ] }M i j i j M E i j p i j???
480(,) [ ]
(,)M E i j T i j?(,)ij?
(,)[]
5
T i j,1,2,3(,)
,4,5
i
i
kjp i j
yj
???
? ?
?
模型的建立及求解
? 模型的求解 (续 ),
经过计算后得到,
于是，,得到最终求解模型。
6 1 6 8 6 4 6 8 7 1 7 2 6 8 8 4 8 7 7 0
6 1 6 8 6 4 6 8 7 0 8 1 6 6 8 4 8 7 8 0
6 1 6 8 6 4 6 8 7 1 8 1 6 8 6 4 7 0 8 1
8 1 7 1 7 0 6 8 7 2 7 5 6 8 7 4 8 0 8 1
8 1 7 1 8 4 6 8 7 4 8 0 6 8 7 4 7 6 8 1
T
M
??
??
?
??
??
1 0 5(,)M i j ??
20
1
(,) (,)n
n
Y i j M i j
?
?? 1,2,...,5i??
模型的建立及求解
? 模型的求解 (续 ),
模型 III,
s.t,(1),(2),…,(9) 同模型 II;
,i=1,2,…,10,j=1,2,…,5 。 (10)
1 0 5 2 0
1 1 1
m i n 1 5 4 ( { ( ) (,) (,) }n
i j n
f Y i j d i j
? ? ?
??? ? ?
20
1
(,) (,)n
n
Y i j M i j
?
??
模型的建立及求解
? 模型的求解 (续 ),
根据以上的改进模型，为了便于求解，暂时不考虑约束条件
（ 9），将 看成一个变量，一共 50个变量。这恰好是
个整数线性规划问题，利用 Microsoft Office Excel软件对其进
行求解，得到最优解,最小运量 =556.03 154=85628.62吨公里。
此时 5,6,7三个铲点没有运输量，恰好满足铲车和铲位数量的
约束，主要目标已经解决。
20
1
(,)n
n
Y i j
?
?
?
模型的建立及求解
? 模型的求解 (续 ),
在此基础上，分析车辆分配方案，使所用卡车数量最少。如
果 成立，则安排一辆卡车在一个班次内就只
行驶 路线。但当 不是 的整数倍时，
必然还要其他卡车将剩余的石料运输完，其车次为,
通过调整卡车在各路线的运输可使卡车最少。
20
1
(,) (,)n
n
Y i j M E i j
?
??
ijSD?
20
1
(,)n
n
Y i j
?
? (,)ME i j
20
1
(,) m o d ( (,),(,) )n
n
Z i j Y i j M E i j
?
? ?
模型的建立及求解
? 模型的求解 (续 ),
这里运用贪心算法，具体算法如下,
1.将剩余车次矩阵 中非零元素对应时间周期矩阵 从大
到小排序；
2.首先尽可能多运输 中最大元素对应的路线，但不能超过
班次总工作时间，如有时间剩余，则转移到 次大元素对应
的路线，选择其中不超过班次总工作时间的最大路线；运输以后
就在 减去已运输的次数；
3.依次策略直至一辆卡车的工作时间排满为止；
4.若 中还存在非零元素就返回 1，按上述方法重复，直至
剩余矩阵 中元素都为零,结束。
10 5Z ? 10 5T?
10 5T?
10 5T?
10 5Z ?
10 5Z ?
10 5Z ?
模型的建立及求解
? 模型的求解 (续 ),
表 1 问题 1一班次的运输方案,
其中,表示第 3辆卡车在铲点 2与卸点 1之间共运输了 13车次，其它类似。
铲点
卸点 1 2 3 4 8 9 10 品位
1 0 0 0 0 30,50%
2 0 0 0 0 0 30,02%
3 0 0 0 0 30,49%
4 0 0 0 0 0 ———
5 0 0 0 0 0 ———
(4) (7)37,44
(3)13
(1) (8)3,39
(5)13 (6)2
(6) (9)8,35
(4) (10)6,37
(1) (11)25,29
(12) (2)38,32
(2) (3)5,6
(6) (12)23,47
(5)15
(3)13
模型的建立及求解
? 模型的求解 (续 ),
经过调整并且考虑到转移时间差，我们得到第一问所需最小
车辆数为 13辆，即以下定理,
定理 1:在该问题中所利用的最少的车辆数为 13辆。
证明,在最优解中，我们将运输周期 和运输计划安排车次
相乘并求和得出在此方案下的理想工作时间总和,
=6038.976分钟
每辆卡车的有效工作时间都是 480分钟，所需卡车数
=12.5813辆，所以所需卡车数必然大于 12辆。而表 1中已给出了
13辆车的可行运输方案，所以命题成立。
10 5T?
10 5N ?
1 0 5
11
(,) (,)
ii
to ta l T i j N i j
??
????
/ 480n total?
模型的建立及求解
? 转移时间差,
在以上的讨论中, 我们均没有考虑当一辆卡车从一条路线转
移到另一条路线上的时间差 。 时间差的产生主要是在运输过程中,
这辆车无需再回到原来的铲点, 而是直接到另一条路线上相应的
铲点, 由于两条路线的不同, 造成了卡车在转移过程中的转移时
间差 。 不妨设 （ i,j） 为一条从 到 的运输路线, 那么当一
辆卡车从路 1线转移到路线 2时, 其转移时间差, iS jD
12
1 1 2 2 2 1 1 1
12
0
,:
( (,) (,) ) (,) (,)
,:
2
if i i
t i j i j T i j T i j
if i i
?
??
?? ? ?
??
?
模型的建立及求解
? 转移时间差 (续 ),
由于原来的理想时间总和并没有考虑到转移时间差, 从而有,
结论：根据最优结果进行分配车次，考虑转移时间差，其时间的
总量必然比原来的理想时间总和 6038.976大。
模型的建立及求解
? 等待问题的讨论,
由于对任何多于两辆车的讨论都可以转化为两辆车的情况,
所以, 在此仅讨论两辆车产生等待的情况 。 根据卡车出现的位置
对等待情况进行分类,
1.在铲点处产生等待 。 如果两辆车在同一条路
线上运行, 那么它们的运行可以用右图表示,
只有当
时, 两车才会在装车点发生等待 。
其中 AB表示装货时间 (5min),CD表示卸货时间 (3min),S1,S2表示
两辆卡车, t1,t2分别表示两辆车开始在 A点装货的时间 。
A
B
D
C
S1 S2
2 1 1 2{ m o d (,),m o d (,) } 5M a x t t T t t T? ? ?
模型的建立及求解
? 等待问题的讨论 (续 ),
如果这两车在不同的路线
上但是在同一铲点装货运
行, 如图二, 则只有当以
下三式,
联立有解的时候, 两车才会产生等待 。
D1
C1
A1
B1
A2
B2
D2
C2
S1
S2
10 m o d (,) 5t t T? ? ?
20 m o d (,) 5t t T? ? ?
12m a x (,) 4 8 0t t t??
模型的建立及求解
? 等待问题的讨论 (续 ),
2.卸点处产生等待 。 类似于 1的
讨论, 可以分为两种情况,
当两辆车在同一条路线上面运行
时, 如右图, 那么必须满足,
A
B
D
C
S1 S2
2 1 1 2{ m o d (,),m o d (,) } 3M a x t t T t t T? ? ?
模型的建立及求解
? 等待问题的讨论 (续 ),
当两辆车在不同一条路
线上运行时, 如右图,
只有当以下三式,
联立有解的时候, 两车才会产生等待 。
其中 表示时间段,T表示一圈所用的时间 。
S1 S2
A1
B1
D1
C1
D2
C2
A2
B2 1 1 1 1m o d (,) 3CCt t t T t? ? ? ?
2 2 2 2m o d (,) 3CCt t t T t? ? ? ?
12m a x (,) 4 8 0t t t??
1(2)Ct 1(2) 1(2)A B C??
模型的建立及求解
? 问题二的模型,
对于问题 2，基于问题 1的约束条件，求最大产量且运输量最小，
可得出模型如下,
模型 Ⅳ,
s.t.(1)…… (9)同模型 Ⅲ
2 0 1 0 5
1 1 1
m a x 1 5 4 (,)n
n i j
p Y i j
? ? ?
? ???
1 0 5 2 0
1 1 1
m i n 1 5 4 ( { ( ) (,) (,) }n
i j n
f Y i j d i j
? ? ?
??? ? ?
模型的建立及求解
? 问题二的模型 (续 ),
采用类似于问题 1的解法，首先不考虑约束条件（ 9），按铲
点分布不同，共分为 个整数线性规划子问题，求出其产量
的最大的解。然后，将最大产量作为一个约束条件，并考虑岩石
产量优先，再利用 Microsoft Office Excel求解最小运量。求得
总产量 671车次,10.3334万吨，总运量为 147792.26吨公里，其
中岩石产量为 320车次,49280吨；矿石产量为 351车次,54054吨；
卡车数量为 20辆。
710 120C ?
模型的建立及求解
? 问题二的模型 (续 ),
类似于问题 1，采用贪心算法，并且考虑转移时间差，求出安排如表 2,
表 2 问题 2一班次的运输方案,
铲点
卸点 1 2 3 4 8 9 10 品位
1 0 0 0 0 30,50%
2 0 0 0 30,06%
3 0 0 0 30,50%
4 0 0 0 ———
5 0 0 0 0 ———
(10)24
(7) (10)
(11)
23 5
44
(6) (7)
(12)
10 10
39
(6)8
(5) (6)19,9
(7) (13)
(19)
4,18
18
(8) (9)3,5
(9)16
(8)32
(3) (14)
(4) (5)
4,37
13,14
(3) (4)27,1
(4) (10)18,2
(15) (18)32,32
(6) (2)1,11
(2)20
(16) (17)38,38
(1)24
(1) (2)
(20)
22 5
45
模型的评价与改进
? 模型的评价与改进,
本文对建立的两个基本模型逐步简化求解，将多目标规划利
用主要目标法转化为单目标规划，非线性规划转化为线性规划，
利用 Microsoft Office Excel软件的整数规划求解，模型简单，
适用性强，容易编程实现求解，并且能够很好的解决问题的整数
约束。由于模型的简单化，就避免不了很多重复操作，将原问题
分成 120个简单的整数规划问题的子问题，为了求得最优解，必
须遍历这 120个问题，求出各个子问题的最优解，在进行比较，
时间开销很大；但是，在求解过程中，我们发觉很多情况其实是
不符合要求的，这样可以将那些对产量上限很不敏感的铲点不予
考虑，作出适当的简化。
