一种解决地下矿山车队管理问题的最短路径算法讲课讲稿

1、Good is good, but better carries it.精益求精，善益求善。一种解决地下矿山车队管理问题的最短路径算法-Ashortest-pathalgorithmforsolvingthefleetmanagementprobleminundergroundminesMichelGamache,RenaudGrimard,PaulCohenEuropeanJournalofOperationalResearch,2004,166(2005):497506一种解决地下矿山车队管理问题的最短路径算法翻译：二一三年十月摘要：本文通过对地下矿山铲运机（LHD）车队管理问题的研究，基

2、于最短路径算法，解决了车辆新任务调度、路径选择和行程安排等问题。每一决策，须考虑矿山现状、运输网络中所有单线双向路段的交通现状和实际运行中的制约因素。如无论铲运机前进或后退，都须保证铲斗能在灵活装卸。关键词：车队管理，调度，路径选择，行程安排，地下开采1引言在地下开采中，一个主要的基础设施成本涉及巷道开拓的挖掘工程。巷道构成了运输网络的基础，是采矿作业必不可少的条件。因此，在规划阶段，采矿工程师设法尽可能多的减少巷道开拓，从而创造出几乎仅由单线双向路段构成的紧凑运输网络。此外，为了限制额外空间的需要，地下矿井往往选择铲运机型车队来完成在装载点和卸载点之间的装载、运输和倾倒矿石、废石及回填材料的

3、工作。在这种有限的网络中，铲运机必须共用路段。这种情况导致一个有效的车队管理系统的必要性。在由车队管理系统做出的决定中，一个就是每次都能为基本上已装载或倾倒完物料的铲运机选择一个新的目的地从而形成一个新的有效的任务。该调度决策基于一个预先确定的标准：最大限度减少周期时间，最大限度减少等待时间或空闲时间等。此外，调度决策必须考虑到交通，即网络上运行的其他铲运机，从而全局性地改善车辆的机动性和隐性地提高整个作业效率。因此，这项任务不仅包括从起点到终点的车辆调度，还包括为这些车辆寻找路径，以避免在装载点或卸载点发生碰撞，排队等候以及死锁条件。由于这些困难与运输网络的性质有关，目前几乎所有的地下矿山，

4、铲运机是在起点或终点的转变开始时预先分配的。起点与终点之间的路径总是相同的，车辆在路口的优先权是以操作者管理的一系列规则为基础（例如先进，先出）和/或由交通信号灯管理。这样的操作条件较简单，但并不适用于所有由环境决定的潜在情况。鉴于铲运机必须在一些装载点和交叉路口等待而其他一些装载点此时正好可以使用，可见生产率是可以提高的。基于上述考虑，地下矿山车队管理决策包括三个主要组成部分：调度，路径选择和行程安排。该行程安排的目的是为一辆或多辆铲运机选择一个新的目的地（装载或卸载点）。路径选择包括在起点到终点之间选择最佳路线（路段）。最后，调度包括决定车辆在运输区段上的运行速度和轮候时间，以避免车辆之间

5、的冲突。为了实现最优决策，在一个特定的问题中这三个组成部分必须同时解决。本文依据露天矿山调度和自行搬运车（AGV）管理系统的开发思想提出了一种同时处理这三个组成部分的一体化解决方案。文章第2节介绍已出版的前人的著作。第3节详细介绍所提方案的内容。最后，第4节介绍该方法的扩展延伸。2前人工作露天矿已经使用调度系统近30年。由于监测系统的可用性以及露天矿调度问题的每个决策不需要考虑路径选择和行程安排的事实而使这种系统的使用变得简单。Munirathinam和Yingling在1994年提出了露天矿山调度系统的调查研究。他们的结论之一是调度系统应以计划驱动策略为基础。计划驱动系统由两部分组成。其中之

6、一是通过求解一个线性或非线性的数学模型来设立一个最优生产计划。该计划表明，对于每一种类型的材料，在来源地和目的地之间的运输都应该保证生产能力最大化或运输成本最小化。它还需遵守调配和容量方面的限制。计划驱动系统的第二个组成部分是如何调度卡车驶向铲装设备，以尽量减少实际生产率与第一个组成部分所确立的生产计划之间的偏差。为了有效率，计划驱动系统必须经常更新，因为开采状况随着轮班持续变化。计划驱动策略也应是地下矿井调度系统的一部分。只有少数文章涉及地下开采运输车队管理系统的问题。其中，NikosVagenas于1991年曾从事半自动铲运机（RAL，即自动运行但必需人工装载和倾倒）的管理。该系统采用最短

7、路径算法来选择起点到终点的最优路线，并采用不同的算法来控制网络冲突。由Vagenas提出的这个分配方法非常适合在地下矿山使用。该方法考虑到网络上的车辆之间的关系，以两个模块为基础。第一个，关于半自动铲运机的运输路径选择，依据四个算法：一是从起点到终点寻找允许使用的最短路径，二是用于在车辆必须减速时的监测，三是为解决双向冲突，四是穿越交通分区。第二个模块，即调度模块，采用启发式程序为半自动铲运机确定目的地。车辆定位是提到的一个问题，但没有提供如何解决的资料。地下矿山车队管理呈现出与制造业背景的自行搬运车管理的相似性。Kim和Tanchoco于1991年提出一种似乎特别适合地下矿山车队管理需要的方

8、法。他们提出了一个有效的算法来为在由双向路段组成的运输网络中运行的自行搬运车寻找无冲突最短时间路线。路由和调度方面的问题同时解决，但车辆的目的地是首先选择好的。这种解决方案包括在时间窗口图上寻找一条最短路径，该图则是根据网络中当前和未来的交通情况而确定，即需要知道网络中其他车辆的路线以及在何时哪些路口是可以通过的。在图中，一个节点代表运输网络的一个交叉路口而一个时窗则显示在此时相应的路口是空闲的。弧集表示空闲时窗之间的可行链接。在创建图表时，对每一个可行的弧线进行测试，以避免路段上的追尾和迎面冲突。在从一个原点到目的地的任何路径上节点代表一个无冲突点。最优可行路线是通过Dijkstra最短路径

9、算法找出的。为了避免在涉及找寻可行弧时不必要的计算，时间窗口图不显式构造，而是在主程序执行时隐含考虑。这种方法是对冲突检测的一个重大改进。双向路段的使用，使该方法比之前提出的任何方法更切合实际，更适合地下矿井。然而，制造业和采矿环境之间依然存在重要差别。首先，地下矿井周期的变化不能像制造业一样比较容易地允许作业执行计划。装载时间显示了最广泛的不同特点，由于这样的事实，即在铲运机前的散状物料需要多次调整前斗进行装载。搬运和倾倒时间的不同则明显减少。为使该方法适用于地下矿山环境，则要求根据操作进度来适时调整时间窗口图。这个问题在第4节讨论。第二个重要的区别是有关在两种环境下使用的车辆类型。铲运机可

10、以前进，后退，但在装载和倾倒阶段其铲斗只能位于车体前方。自行搬运车则不存在这个问题。然而，对于铲运机来说，预先计划从起点到目的地的轮流运行秩序，以确保车辆能准确到达，是车队管理系统的一个本质特征。此问题的解决方法在第3节中讨论。Krishnamurthy等人于1993年依据一系列解决自行搬运车管理问题的生产技术提出了一种方法。他们的解决方案考虑了同时进行对多个自行搬运车的任务分配。有趣的是，在一个限制只有几秒钟的时间允许决策过程的实际情况下，该方法是不适用的。然而，他们图形构成的一些内容将在本文提出的方法中重新使用。Langevin等人于1994年也提出了一个最佳和更具全局性的方法：同时安排两

11、辆自行搬运车，但再次因为决策过程太长而不能在实时系统中运用。此外，这种方法为所有在轮班过程中执行的任务找到了最优排序，由于前面提到的操作具有一定的随机性，所以在我们的文章中也存在一些不恰当之处。3解决方案这里提出的解决方案受到了Kim和Tanchoco（1991）所提出的方法的启发，也包括一些由Vagenas（1991）和Krishnamurthy（1993）等人提出的图形设计的内容。提出这种方法，是因为在类似的解决方案中它能解决路径选择和调度方面的问题。该模型已进行了调整，将调度决策包含到相同的解决过程中。然而，对网络提出了重要变化，以确保铲运机用正确的方向（铲斗在前）到达目的地，并减少死锁

12、的发生。3.1图形构成从矿场的初始运输网络开始，基本的网络代表路段（弧），交叉口、卸载和装载点（节点）一一绘制。表示交叉点的节点是重复设置的，以表明在这些地点（路段的端点）车辆可以安全地等待其他车辆行进到相邻的路段（参见图1）。在地下矿井中，这些节点扮演另一个重要角色：在其所代表的地区车辆可以改变方向，即从正向变为反向运动。根据网络上的其他铲运机的位置和任务，一个时间窗口图便可以推算出来。图2给出了对应于图1所示运输网络的一个简化时间窗口图形例子。对应于某特定车辆的路径“K-J-H-I-L-M-N-O-Q”用黑色表示。黑色矩形表示节点被占用的时间段，弧代表路径上的路段；例如从“K”到“J”的弧

13、表示该车辆使用路段“KJ”。图1.基本网络对于每一个节点，一个白色的空间表示一个时间窗口，在此时窗内，节点（路口）是空闲的。两条路径不能同时占用同一个节点。弧线与时窗连接在一起表示一个路段的使用是安全可行的。已经做过相应测试，以确保节点之间有一条物理链路，以确保第二个时间窗口可以及时到达，以及避免在一条弧段发生迎面碰撞或追尾（当两弧交叉且使用相同的节点对时可能发生这样的冲突）。Kim和Tanchoco（1991）已对这些测试的更多细节进行过表述。图2.时间窗口网格图图中第二条通路“R-P-N-M-L-I-H-D-B-C-G”与灰色矩形连接在一起表示一条无冲突途径。该路径是众多可行路线中一条可以

14、安排给一台要求新任务的铲运机运行的路线。其目的是隐性地评估所有可能的路径并按照指定的标准从其中选择一条最优路径。图3是一个更加完整的图，称为离散图。在该图中，每一层次代表运输网络的一个交叉口而每个层次的节点表示交叉口空闲的时间单元，这些节点在图2中由白色空间表示。节点之间的弧线代表可行的链接。该图仅构建了从当前时间开始的一个预定的时间范围，这关联到一辆铲运机对新任务的要求。鉴于知道车辆要求新任务的位置（起始节点），则可到达的目的地的集合是确定的。例如，如果车辆位于节点“Q”（代表装载点），它之后可以到达节点“G”或节点“K”，这两个节点代表倾倒点。选择可行的目的地不仅取决于起始点，还取决于将要

15、搬运的材料的类型。对于每一个调度决策，特定的起始点与所有可行目的地之间的最短路径是经过评估的。在最短路径之间进行选择取决于预定的调度准则。最短路径是使用Dijkstra算法找出的。所选路径上的每个节点表示运输网络中的铲运机将沿着该路线运行，也表示车辆通过路口的时段，并且间接地限定了车辆在每个路段的运行速度。这个采用Dijkstra最短路径算法的决策方案允许将分配任务的两个方面（路径选择和行程安排）作为一个单一问题来考虑。图3.加入汇聚节点3.2调度决策通过在离散图上添加一个汇聚节点且仅将代表可行目的地的节点与汇聚节点连接起来（见图3），这可能将第三个问题，即调度决策，包含到决策过程中。为了实现

16、这一目标，弧线上的成本就所选择的客观标准来说必须具有代表性。通过选定的调度准则来看，起始点与汇聚节点之间的最短路之后将被定为可行路径，同样确定下来的还有行程安排和目的地。弧上的成本可表示在运输网络的路段上所花的时间或在节点处的等待时间。在这样一个模型里，汇聚节点的输入弧的成本为零。因此，最短路径代表从起始点到汇聚节点所用的时间最短。为了确定目的地，在解决方案中就需要去看汇聚节点的前趋弧线。考虑到另一个调度准则，网络中弧线的成本也可能需要修改。例如，如果采用一个类似于那些露天矿山所使用的计划驱动调度准则，则其目的是使生产水平和最优生产计划的指标水平之间的偏差最小化。汇聚节点的输入弧将采用这种偏差

17、。另一种可能性是将各种标准结合起来。例如，从起始点到目的地之间的最短时间路线可以作为第一客观标准而与生产计划的偏差则可作为第二标准。最短路径算法首先为每个目的地选择最短路线，然后从这些路线中选择与生产目标偏差最小的一条。为此目的，最短路径算法进行了修正，即离散图上的每个节点，除汇聚节点外，各路线之间的优势由时间标准来定，而汇聚节点的优势由第二标准来定。因此，与生产目标偏差有关的成本只算在汇聚节点的输入弧上，而其他弧的成本表示在这些弧上花费的时间。通过在离散图上使用最短路径算法，决策时间将足够短，能够在几秒钟之内为车辆分配一个新任务，以遵守该问题中无法避免的实时约束条件。事实上，大部分时间都用于

18、分析图形构成。图4.车辆方向改变3.3确保车辆在目的地定向正确运输网络中的一些路口允许车辆改变行进方向，以便正确地驶向（即铲斗在前）目的地。图4说明了两种情况下车辆改变方向的例子，第一例对应于车辆以前进方式到达目的地，而以后退离开的情形。因此，每当车辆以正确定向抵达目的地，那在开始下一个任务时，它必须先倒车。第二个例子显示车辆利用路口改变方向。在巷道A中，车辆后退行驶，之后，它后退进入路口B，并以前进方式离开路口进入巷道D。在基本图形中，其路线依次是“A-B1-B2-B3-D”。从这两个例子得出一条通用的规则：每当车辆通过一个由奇数个节点构成的路口（在本例中由节点序列B1、B2、B3表示）时，

19、改变方向是有效的；每当车辆通过一个由偶数个节点构成的路口时，将保持方向不变。图4中的第二个案例，将车辆的路线以“A-B1-B2-C”代替原来路线“A-B1-B2-B3-D”，那么它会保持相同的方向，如事实表明的，它通过关联到B1和B2两个节点的同一路口。这个简单的规则代表任何案例。图5.重叠的网络可以用两种方法确保车辆到达目的地时定向正确。第一种是使用一个能保存车辆定向记录的资源（一个二进制变量）。在汇聚节点，约束将检验车辆是否定向正确。在这种情况下，将使用相同的图形，但却通过利用资源制约条件解决一个最短路径问题的途径来获得决策方案。为了避免资源使用以及由于参与地下调度系统的图形尺寸相对较小，

20、从而提出第二种办法，即重叠离散图形。一层表示一个对应于向前移动的离散图形拷贝，而第二个拷贝则对应于后退移动。在之前的离散图形中对应一个路口节点的所有输入弧将从新图的每个层中删除并由跨层弧代替，其中尾节点和头节点位于不同的层（见图5）。当路径使用一个跨层弧时，车辆方向将改变（其中一些变向的发生是虚拟的）。例如，让我们考虑一下图4案例2中描述的路径“A-B1-B2-B3-D”。在新图的后退移动层中，没有弧线把节点A和节点B1连接起来，因为弧（A，B1）是路口节点B1的输入弧。路径将利用跨层弧（A，B1）把后退移动层上的节点A和向前移动层上的节点B1连接起来。向前移动层上的节点B1将被连接到后退移动

21、层上的节点B2，因为在向前移动层上没有连接节点B1和节点B2的弧。（路径“A-B1-B2”是一个虚拟变向的例子。）路径继续从后退移动层的节点B2到达向前移动层的节点B3。最后，向前移动层的节点B连接到同一层的节点D上，因为节点D不是一个路口节点。同样，图2中给出的两条路径遵循相同的规则。沿路径“K-J-H-I-L-M-N-O-Q”运行的第一辆车在经过节点序列“K-J-H-I”之后改变了行驶方向，但在经过节点序列“M-N-O”之后保持向前移动。相似地，沿路径“R-P-N-M-L-I-H-D-B-C-G”的第二辆车在经过节点序列“R-P-N”之后保持后退移动的方式运行，但在经过节点序列“D-B-C

22、”之后将其运行模式改为向前移动。为确保车辆都能以正确定向抵达目的地，在图中向前移动层上表示可行最终目的地的节点（图5中的装载点）是唯一能链接到汇聚节点的一些节点。根据这个新图形，Dijkstra算法可以再次引用来寻找到解决方案。3.4死锁情况当无法给一辆铲运机指派目的地时就发生死锁。使用本文提出的解决方案时也可能出现死锁情况。依次地调度车辆是导致死锁的原因之一。例如，就图6所示的网络而言，可以看到有一个装载点、一个卸载点和两条路径，在起始时（时刻0），位于节点B的车辆V1被指派到节点A，并将于时刻20达到目的地。在时刻0和时刻20之间，车辆V2和V3被指派到节点A，并在各自的路段等候，以避免跟

23、车辆V1发生正面冲突。在时刻20，系统必须再次调度车辆V1，但现在如果系统不重新安排车辆V2和V3则不可能找到一个可行的解决方案：即产生了一种死锁情况。为了避免或尽量减少出现这种情况的风险，该系统可以增加做出决定的时间范围。系统能够在一条更长的路线上调度车辆，而不是仅在半周期内调度，即半周期再加上一段从目的地到某一特定节点的安全路线，假设在该特定节点可以再次调度车辆。在现实中，这个额外的安全路线在解决过程中并不一定适用，因为只会将车辆派到与半周期相关的目的地。然而，额外的路线会在为其他车辆所采取的即将到来的调度决定中采用。事实上，系统会认为第一辆铲运车占据了额外的路线。考虑前面的例子（见图7）

24、，将安全节点C添加到网络中。在时刻0，车辆V1被安排从节点B驶向节点A，并于时刻20到达。系统记录了这一信息，并于车辆V1在节点A装载之后增加了从节点A到节点C的路线。在车辆V2和V3收到对它们的调度决定之后，它们将不能够在节点A和节点C等待。在时刻20，车辆V1会申请一个新任务，而系统正好能提供给它，因为至少有一个可行的方案。图6.死锁情况这种方法有时会得出次优的方案，因为有些路段要留作专用，但它减少了出现死锁情况的风险。图7.一个安全节点4解决方案前景实时的解决车队管理问题是一个复杂的任务。由于地下采矿作业的随机性，做出调度决策的时间不能太久。因此，调度决策将更加频繁，这暗示了高效决策策略

25、的使用。此外，对在短时间内做出调度决策的需要淡化了对生产优化问题的全局视野。为了减少这些制约因素的影响，一种计划驱动调度的方法被建议使用，因为它在露天矿山的使用是很普遍的（见Munirathinam和Yingling，1991）。基于第一层次的最优生产计划保证了该问题有一定的全局视野。这一计划也在不断更新，以便能始终反映矿井的实际状况。调度决策包括尽量减小实际与最优生产计划的偏差。对这个系统的一些测试工作已经完成（见Gamache等，2001）。这些测试结果表明，调度决策在同一时间仅涉及一辆铲运机则会导致较差的生产水平。在每次循环中，因为系统仅为一辆车寻找最佳目的地，所以它没有考虑那些即将派出

26、的车辆。关于该方法造成糟糕决策的例子是显而易见的。为了尽量减少这种缺乏远见的方法的影响，启发式算法目前已开发出来，用于重新检核已分配给铲运机的路线各部分情况，以改进该决策方案。本文提出的系统可以描述为车队管理研究项目的第一代。如前所述，这第一代有一些暂时的局限性：它认为决定论的服务和运行时间，而且一次只为一辆车做出决策，忽略了这个决策对后续车辆的影响。然而，这一系统已经整合了地下矿山车队管理系统的三个重要方面：调度，路径选择和行程安排。目前的系统以一种确定的方式工作。事实上，即便为了规避对采矿作业随机性的把握不全面，一些安全因素已被整合在每个决策中，这一策略依然不是十分充分。第二代地下矿山车队管理系统正在改进。它会考虑在采矿过程中的各种突发事件，如车辆故障，在巷道内意外停止等。正在进行的改进包括处理各种运行和服务时间问题的能力。与此同时，不仅能为某辆铲运机也能同时为其后续车辆迅速做出调度决策的第三代系统也正处于开发阶段。已证明，在露天矿调度系统中，这种策略显著提高了生产效率。在上述领域的进展是令人鼓舞的，应及时报导出来。参考文献1