第 8卷 第 1期
1 999年 3 月
运 筹 与 管 理
OPERATIONS RESEARCH AND M AN AGEMENT SCIENCE
VoI．8．No．1
M ar．．1 999
露天矿卡车运输系统最佳调度的数学
模型及其数值解法研究
马义飞 李祥仪
(北京科技大学资源工程系，北京，1 00083)
摘 要 文章分析 _r目前卡车调度系统的建模情况 ，应用最佳控制的理论建立 了卡车调度系统的
数学模型 ，并结合 一简例 ，分析了数值解法，给出简例的数值解。通过对数值解的分析，说明数学模
型和数值解法都是正确的 。
关键词 计算机控制；卡车调度；最佳控制 ；数学模型
中图法分类号 TD571：0224
Abstract
A Mathematic Model of Optimal Control
for Truck Dispatch System in Opencast Mining
M a Yifei Li Xiangyi
(Beijing University of Science＆Technology，BeOing，100083 China)
This paper has examined the modelling of truck dispatch system in opencast
mining．W ith the optimal theory，a mathematical model has been constructed． Taking a
simple case as example，the paper has analyzed the computational method of the problem ，
with the method，calculated the simplc case and got good results which proved that the
mathematical model and the solving method are correct．
Key words com puter control；truck dispatch；optimal control；mathematical model
1 当前国内外计算机卡车调度系统的应用情况
国际上流行的计算机卡车调度系统是美国模块公司的 DISPATCH，它是综合监控系统 ，
经过多年的发展，现在达到对设备状态自动监控 ，GPS定位 ，自动派车的阶段。它的软硬件功
能都很强，目前在世界范围内的 50多座矿山成功地应用该系统。但是，它的价格 昂贵 ，一套
DISPATCH需外汇 $3000000；维护困难 ，购买的软件对矿山管理人 员而言是黑箱 ，维护长期
依赖国外 ，非常不便。所以，我国的计算机卡车调度系统 ，要立足国内开发。
国内也积极开发实用计算机卡车调度系统，1990年 由本钢南芬铁矿、马鞍山矿 山研究院、
东北工学院组成的联合课题组开发了南芬铁矿生产调度计算机辅助系统。1994年 ，霍林河矿
收稿 日期：1 998 08—10
马义飞 ，男，1 954年 7月出生，北京科技大学资源 程学院博士研究生；
李祥仪 ，北京科技大学资源工程学院教授，博 导。
维普资讯
54 运 筹 与 管 理 1999年 第 8卷
务局与煤科总院西安分院、中国矿业大学合作，开发完成计算机控制 自动化卡车调度系统。据
文[1 l中计算，该系统在不增加采、掘、运设备的情况下可使产量提高 5％～6％，每年可获 300
多万元收益，建立卡车调度系统的投资在投入使用后 2年内便可收回。
计算机卡车调度系统大体可分为两大部分 ，硬件系统 ，包括中央处理计算机、信号采集、传
输设备等；软件系统，包括信息处理、根据最优准则确定最优派车方案 ，直至 自动发出指令、派
车。本文不研究硬件 ，在硬件设备到位之后，软件及数学模型是发挥系统效果的关键 。
目前的软件通常是分步建模，计算机模拟实现。(见图 1)
更
新
， — -
行
时
间
矿山地形
矿坑配置及约束
系统中的随机情况
图 1 卡车调度过程示意图
Fig．1 Diagram of truck dispatch process
最佳线路的方法和程序已比较成熟，这里不作讨论。车流规划通常用线性规划[2 或多 目标
规划L3 建模。
线性规划建模时分别考虑下列 目标 ：
(1)班费用最小或赢利最大；
(2)产量最大 ；
(3)卡车数量少；
(4)单位运输功最少。
在优化车流分配的基础上，用动态规划调配空车到电铲 ，并考虑电铲的优先权，尽量实现
线性规划的结果。
多目标规划模型的 目标是：
(1)第一优先级 目标 ，系统出动卡车数量少；
(2)第二优先级 目标 ，赢利最大 ；
维普资讯
第 1期 马义 飞等 ：露天矿卡车运输 系统 最佳调度 的数学模型 及其数值 解法研 究 55
(3)第三优先级 目标 ，品位最佳。
从上面的叙述可知，目前的模型车流规划与动态派车是分别处理的，对车流规划的结果只
能“尽量实现”，而卡车调度系统是一个完整的动态控制系统，优化与派车不能分开 。本文试图
用最佳控制的理论建立数学模型，作为卡车调度系统控制的补充。它的优点是 ，所定义的电铲
剩余工作时间实质上是一个综合指标，既考虑了电铲利用率最大，又考虑了卡车等待时间最
短 ；所求出的最优控制就是在一定时期内，按照指标函数所给 目标的派车方案。当然，本文的研
究还是初步的，没有给出其它几种 目标下的指标 函数的数学表述。本文的意义在于把最佳控制
理论第一次引入计算机卡车调度系统。
2 卡车运输系统最佳调度问题的提法 ][ ]
2．1 状态方程
首先，把所研究的时间区间分为 K个时间段 ，第 段简记为 k，并且 ，下面凡出现 (是)的地
方，都表示对时间区间 k而言 ，不再一一重复。
在装载点上设 ：
(1)z (是)第 i台电铲前等待装车的卡车的总容量 ，i===1，2，⋯，m。
一 为电铲数 ，把 m 个电铲等待的卡车的总容量以矢量 X(是)表示；
(2) (是)为 k时间区间内来到电铲 i的卡车总容量，i—l，2，⋯， ，总括起来以矢量 U(k)
表示。而 U(足)往前推一个运行时间就是派往电铲的卡车容量 ，所以，U(是)是可以控制的 ；
(3)ri( )为 k时间区间内电铲 i完成的装载量，i—l，2，⋯，m，总的以矢量 R(是)表示 。
这样 ，装载点的状态转移方程为：
X(是+ 1)===X(是)一 R(是)+ U (是)
它表示 ，电铲前等待的空车容量随装车而减少，随来车而增多。
另外，对控制应有约束：
(是)=nC ，2一l，2，⋯取正整数；C为卡车装载能力，
，2≤N (是) N (是)为 k时刻在派车点等待派出的卡车数。
显然，这个系统是可控的，因为，通过改变 U，可以改变 X的每一个分量。
2．2 目标泛函
先定义电铲的剩余工作时间：
tt===ztfrl
它的意义是 ，目前在电铲 i前等待的卡车，电铲需要多少时间装完。
为充分利用每台电铲的能力，以及使卡车等待时间最少 ，令每台电铲的剩余工作时间基本
相等；
这样 ，有 目标泛函：
r 1、1，Xi-~l( ) z (是)、 min J：：： I ( 一 )l
3 简例及数值解法研究
3．1 系统描述
维普资讯
56 运 筹 与 管 理 1999年 第 8卷
不失一般性 ，设某露天矿有 5台电铲，在某时刻 是在电铲前等待的卡车容量分别为 ：
z1(是)，z2(是)，z3(是)，z4(屉)，z5(是)；
电铲装载速率分别为：r。'r2'r3 ，r ；
派往 电铲的卡车容量分别为 ： (是)， (是)， 。(是)， (是)， (是)。
3．2 最佳控制的数学模型
(1)状态方程
z1(是+ 1)一 z1(是)～ r1+ (是)
z2(是+ 1)一 z2(是)～ 2+ 2(是)
z3(是+ 1)===z3(是)一 3+ 3(是)
(是+ 1)一 z4(是)～ + 4(是)
z5(七+ 1)一 z5(七)～ 5+ 5(七)
(2)目标泛函
J === k-I窭 一 + 一 )]
(3)H 函数和协方程
II：：：
4
( 一 ) + ( 一 )
r t+ I r i r 5 r I
+ 1(是+ 1)(z1(是)一 r1+ 1(是))
+ 2(是+ 1)(z2(是)一 r2+ 2(是))
+ 3(是+ 1)(z3(是)一 3+ 3(是))
+ (是+ 1)( (是)一 + (是))
+ (是+ 1)(z5(是)一 r5+ 5(是))
1(是)一 1(是+ 1)+ 4x1(是)／r1／rl一 2x2(k)／r1／r2～ 2x5(k)／r1／r5
2(是)一 2(是+ 1)+ 4x2(k)／r2／r2— 2x1(k)／r1／r2～ 2x3(是)／r2／r3
3(是)一 3(是+ 1)+ 4x3(k)／r3／r3— 2x2(k)／r2／r3～ 2x4(k)／r3／r4
4(是)一 (是+ 1)+ 4x4(是)／r4／r4— 2x3(是)／r3／r4～ 2x5(是)／r4／r5
(是)一 (是+ 1)+ 4x5(是)／r5／r5— 2x1(是)／r1／r5～ 2x4(是)／r4／r5
3．3 解法
首先对 U 取满足约束的 U。，用状态方程计算对应于 U。的 X。，用协态方程计算 入(矢量)，
用目标泛函计算相应的 J。，接下来求规划问题 ：
minH (U) (把 H 看成是 U 的函数)
满足对 U 的约束，得到新的 U，再计算对应于新 U 的 X， ，J，若新 U 及对应的 X使 J有
所下降，U赋给 U。继续前面的计算 ，否则，U。及 X。为所求。
算法步骤是 ：
第一步 读入原始数据 ；
第二步 取满足约束的 U。
第三步 计算相应的 X， ，J；
第四步 将 J与前一个 J做比较，若有所下降，转向第五步 ，否则转向第七步 ；
第五步 计算规划问题参数；
维普资讯
第 1期 马义飞等：露 天矿卡 车运输 系统最佳调度 的数 学模型 及其数 值解法研 究 57
第六步 解规划问题 ，求得新的 U，返 回到第三步；
第七步 取当前的 U为最优解 ，计算相应的 X，输出，停止。
应该指 出，U，X， 都是 向量，并且是时间的 函数，在程序中要用二维数组表示 ，一维表示
其每个分量 ，另一维表示其在所研究区间内的每个分点。计算是在每个分量及每个分点上进行
的 。
另外 ，程序在迭代中的每一步都尽可能地应用了已有的最新中间结果 ，使收敛速度大大加
快。
3．4 简例的数值解
取卡车载重量为 20t，电铲装载能力都为 4t，初始 X值分别为 8O，2O，6O，O，O，初始时刻为
O，终了时刻为 21，得到结果如下表：
K U(1) U(2) U(3) U(4) U(5)
1 ．OO ．OO ．OO 2O、OO ．OO
2 ．oo 20．oo ．oo ．oo ．oo
3 ．oo ．oo ．oo ．oo 20．oo
4 ．oo ．oo ．oo 20．oo ．oo
5 ．oo 20．oo ．oo ．oo ．oo
6 ．oo ．oo ．oo ．oo 20．oo
7 ．oo ．oo ．oo 20．oo ．oo ．
8 ．OO ．oo ．oo ．oo 20．oo
9 ．OO ．OO ．OO 2O．OO ．OO
1o ．oo 20．oo ．oo ．oo ．oo
11 ．OO ．OO 2O．oo ．oo ．oo
1 2 ．OO ．OO ．OO ．OO 2O．OO
1 3 ．OO ．oo ．oo 20．oo ．oo
14 ．OO ．OO 2O．oo ．oo ．oo
1 5 ．OO 2O．OO ．oo ．oo ．oo
1 6 2O．OO ．OO ．oo ．oo ．oo
1 7 ．OO ．OO ．oo ．oo 20．oo
18 ．OO ．OO ．OO 20．oo ．oo
19 ．OO ．OO 2O．OO ．OO ．OO
20 ．oo 20．oo ．oo ．oo ．oo
X(1)
80．oo
76．oo
72．oo
68．oo
64．oo
60．oo
56．oo
52．oo
48．OO
X(2)
2O．OO
36．OO
32．OO
28．OO
44．OO
40．OO
36．OO
32．OO
28．OO
X(3)
60．OO
56．OO
52．OO
48．OO
44．OO
40．OO
36．OO
32．OO
28．OO
X(4)
． oo
． oo
． oo
1 6．oo
1 2．oo
8．oo
24．oo
20．oo
36．OO
X(5)
． OO
． OO
1 6．00
1 2．OO
8．OO
24．OO
2O．OO
36．OO
32．OO
K 1 2 3 4 5 6 7 8 9
维普资讯
58 运 筹 与 管 理 1999年 第 8卷
10 44．O0 44．O0 24．O0 32．O0 28．O0
11 40．00 40．00 40．00 28．00 24．00
12 36．O0 36．O0 36．O0 24．O0 40．O0
13 32．O0 32．O0 32．O0 40．O0 36．O0
14 28．00 28．00 48．00 36．O0 32．00
1 6 24．O0 44．O0 44．O0 32．O0 28．O0
17 40．00 40．00 40．00 28．00 24．00
18 36．O0 36．O0 36．O0 24．O0 40．O0
1 9 32．O0 32．O0 32．O0 40．O0 36．O0
20 28．00 28．00 48．00 36．00 32．00
3．5 用计算结果指导派车
这一例子的初始状态，可能是 由于未考虑电铲能力的随机派车，或电铲故障等原因造成在
电铲 1，3前面的卡车排队等候 ，经最佳控制的数学模型计算 ，屉<12可采取这样的派车原则；
不给 电铲 1派车，电铲 2在 k=2，5，10，各派 1车；电铲 3在 屉一11派 1车；电铲 4分别在 k一1，
4，7，9，13各派 1车 ；电铲 5分别在 k一3，6，8，各派 1车。屉>12各状态已基本相等，由于这里
电铲能力都一样 ，所以 ，进入均匀派车阶段，按电铲 5，4，3，2，1，5⋯轮换派车。
在表中可看到，到 k一11，各状态已基本相等 ，由于 电铲能力相等，所以，剩余工作时间也
基本相等，这时，就可提高电铲利用率 ，也可使卡车等待时间最短 。
4 结论
(1)露天矿卡车调度系统是一个动态控制系统 ，可以用本文提出的最佳控制的数学模型描
述 ，所求出的 U(屉)就是 k时刻应到达各电铲上的卡车容量，数值 U(屉)／c就是 k时刻应派到
各电铲上的卡车数，再提前一个卡车空车运行时间就应是派车时刻，派车是可控的 ；
(2)电铲剩余工作时间基本相等是一个综合指标 ，可充分利用电铲的能力，也可使卡车等
待时间最少 ；
(3)本文提出的数值解法，将数学规划和迭代结合在一起 ，已证明是成功的；
(4)简例的数值解是符合工程实际的 ，它也说明数学模型和解法是正确的。
参考文献
1 苏靖 ．计算机卡车调度系统在我国露天矿实现的问题研讨 ．露天采煤技术，1 997，(3)：2～5
2 孙庆山等 ．露天矿卡车调度系统的数学模型的建立 ．中国矿业，1 997，(1)：80~82
3 苏靖，刘胜富 ，张幼蒂 ．露天矿计算机控制实时优化调度算法的研究 ．中国矿业 ，1 997，(3)：82~85
4 吴受章 ．应用最优控制 ．西安 ：西安交通大学出版社，1 988．1 22～183
5 张光澄 ．最优控制计算方法 ．成都：成都科技大学出版社，1 991．60~91
维普资讯
