A* 算法在露天矿运输道路最优路线的应用

肖英才

(江西地质科学研究所，江西 南昌 330030)

0 引言

露天矿运输成本在矿山总投资中，占有很大比重，并且运输系统安排的合理与否直接关系到矿山的后续的生产作业安排及赢利。因此，通过对运输系统的优化，建立高效、合理的运输系统，从而实现充分发挥卡车运输的潜力，提高运输效率，最终达到减少运输卡车的数量，降低运输成本的目标，并对于减少设备损耗、节能和减少环境污染都具有重要意义［1］。

最优路径在交通网络中有着广泛的应用，其算法有着重要的研究价值。目前，最优路径算法研究比较多，主要有:Dijkstra 算法及其改进算法、Floyd算法［2］、A*及其改进算法，粒子群算法等，Dijkstra算法要遍历所有的节点，因此在其求解中必然要产生冗余，时间花费较多;Floyd 算法的时间复杂度为O(n3)，且不能直观反映出各个顶点之间最短路径序列的先后关系［3］;粒子群算法有较强的全局搜索能力，但是在搜索时易陷入局部最优并导致搜索停滞的缺点［4］;A*算法利用合适的估价函数，从而减少搜索空间，提高搜索效率［5］。综上所述，各类算法都有其优缺点，其中Dijkstra 算法是典型的最短路径搜索算法，且可以保证找到最优路径，但是由于它要求解当前点到所有的节点，因此其效率低下。

综上所述，以上各种算法各有其优缺点，本文选用人工智能中的A*算法，通过在估计函数中引入距离和方向两个参数，使估价值尽可能接近实际值，保证找到最优路径。

1 露天矿运输网络模型

露天矿的运输网络是由完成采矿场采出的矿石运送到选矿厂、破碎站或贮矿场，把剥离的岩土送至排土场等运输工作的路径组成，在露天矿各生产环节中起着“动脉”和“纽带”的作用［6］。以露天矿各采区的装载点为入点，以排土场、卸矿点及贮矿点为收点，中间节点为道路的交汇点或道路性质突变处为中间节点，两节点间以其直线距离为权值，构成露天运输网络模型［7］，某露天矿山的部分运输网络示意图见图1。

图1 部分运输网络示意图

通过对运输网络图的研究，在从装载点到卸载点之间卡车运行的路线有很多种可能，在各结点间的距离已知条件下，求出入点到收点间的最短路径。该问题的解随着顶点数目的增加，可行解将呈几何级数增大，当顶点的规模较大时，由于耗时太长而在实际应用中受限。A*算法通过引入估价函数，大大减少搜索时间，迅速找到最优路径。

2 A* 算法

2.1 A* 算法的基本原理

A*算法是由Hart，Nilsson，Raphael 等人首先提出的，它是在Dijkstra 算法和BFS(最好优先搜索)算法基础上建立起来的［8］，被广泛应用于路径优化领域［9］。它采用启发信息来决定哪一个是下一步要扩展的节点，然后搜索就可能沿着某个被认为最有希望的边缘区段向外扩展［10］，因此可以大大降低计算的空间与时间。这种需要估算节点希望的度量即是估价函数f(n)为:

f(n)=g(n)+h(n)

式中:g(n)是在网络中从初始节点到目标节点的实际距离，h(n)是从初始点到目标节点最优路径的估计距离。

搜索算法的可采纳性(Admissibility)是指该算法一定能找到一条最佳的路径［11］;A*算法满足可采纳性的充要条件是:h(n)≤h*(n)，h*(n)为初始点到目标点的实际最短距离。因此只要h(n)小于实际最短距离，则A*算法一定能找到最优解。

2.2 估价函数f(n)的确定

估价函数是影响A*算法效率的重要因素，提高其精确度，算法运行效率也会提高［11］。估价函数f(n)能够提供一个确定扩展节点的方法，用以决定哪个节点最有可能通往最优路径，使得搜索沿着最有希望的区段扩展。由于A*算法总是选择h(n)值最小的节点作为扩展节点，所以若估价函数选h(n)大于实际的最短距离，将不能保证找到一个最优的解，而当h(n)为0 没有利用启发信息时，A*算法就变成了Dijkstra 算法［12］;在实际中是不可能达到h(n)=h*(n)的理想状态，但是可以让构造的估价函数值应尽可能接近实际值。

构造精确的估价函数常用的方法是计算初始节点到目标节点间的最短路径的长度，常用的估价函数有:

①曼哈顿距离(Manhattan distance):h(n)=abs(x-xn)+abs(y-yn)

②对角线距离:h(n)=max(abs(x-xn)，abs(y-yn))

③欧几里德(Euclid)距离:h(n)=sqrt((x-xn)2+(y-yn)2)

上述构造的估价函数在实际应用中有着明显的弊端，因为节点的选择不仅仅受距离的影响，还受到很多其他因素的影响，因此，需在估价函数中加入更多的约束信息，保证算法快速准确向目标移动。为此需要在估价函数中引入距离和方向两个因素，其启发函数为:

其中:a 为当前节点线段与当前节点到目标节点线段的夹角;L 为欧几里得距离;起始点(Xst，Yst)，目标点(Xend，Yend)，当前节点(Xi，Yi)，当前节点的下一节点(Xi+1，Yi+1);w1和w2是距离和角度加权值，取值范围为0.55～0.65 与0.35～0.45。通过引入权值w1和w2，可使搜索在深度浅的地方靠启发函数发挥作用，在深度较深的地方，搜索变为宽度优先，从而保证到达目标的最优路径最终被找到。

3 利用A* 算法对道路网络路径优化

根据图1 所建立的运输网络模型，运用A*算法对其进行优化。其实现步骤为:

(1)首先建立2 个表格，OPEN 表和CLOSED表;OPEN 表内存放已生成而未考察的节点;CLOSED 表记录已访问过的节点。

(2)将起始节点加入到OPEN 表中;选取OPEN表中没有设置过的且有最小估价值的最佳节点放入CLOSED 表中，对最佳节点考察，如果是目标点，则成功求得一解;如果不是，则扩展之，产生后继节点，计算后继节点能进行选择的价值，把与其相邻的节点加入OPEN 表中，然后根据这个方法，完成所有节点的访问价值排序。

(3)重复第二步，直至找到终点为止。

选取网络中的两点做为装载点和卸载点，利用改进了的A*算法对网络进行优化，在matlab 软件中进行仿真试验，启发函数的值h 取不同的值，其求解的路径相同，但是程序运行的时间有差别，当w1取0 时，程序运行时间为0.047 ms;当w1取0.6 时，运行时间为0.32 ms;当w1取1 时，运行时间为0.15 ms，其运行结果见图2。由运行结果可知，改进的A*算法能够提高搜索的效率，同时也可以保证找到最优解。

图2 求解结果

4 结语

通过对运输系统的优化，建立高效、合理的运输系统，提高运输效率，从而达到减少运输卡车的数量，降低矿山运营成本的目标，本文利用A*算法，通过选择合适的启发信息，对运输网络的最短运输路径进行优化，并仿真求解，计算出较合理的卡车运输路线。露天矿运输系统是个复杂而动态的网络，且道路条件多变，还需要选取更合适的启发函数用以提高算法的效率，需要考虑到网络的动态性，使其更好地解决实际问题。

［1］王纯义.露天矿道路质量是影响卡车运输能力、成本、安全的重要因素［J］.煤矿安全，2001，(1):59-61.

［2］周春辉，李诗高.Dijkstra 算法与A*算法研究［J］.软件导刊，2007，(1):102-103.

［3］代修宇，程国中.Floyd 算法的改进与优化［J］.西昌学院学报，2012，(3):63-65.

［4］孙臣良，刘 静.粒子群算法分析及其求解露天矿道路路径优化问题［J］.计算机系统应用，2011，(11):142-145.

［5］史 辉，曹 闻，朱述龙，等.A*算法的改进及其在路径规划中的应用［J］.测绘与空间地理信息，2009，(6):208-211.

［6］骆中洲.露天采矿学［M］.北京:中国矿业学院出版社，1986:77-91.

［7］孙臣良，刘 静.露天矿运输道路网络的建立及其路径优化［J］.科技导报，2011，(9):47-51.

［8］Steven M.Lava the Planning Algorithms ［M］.Cambridge University Press，2006.

［9］Nilsson N J.Principles of Artificial Intelligence［M］.New York:Tioga Publishing Co.，1980.

［10］蔡自兴，徐光佑.人工智能及其应用［M］.北京:清华大学出版社，2003.

［11］林尧瑞，马少平.人工智能导论［M］.北京:清华大学出版社，1989.

［12］I Chabini，S Lan.Adaptations of the A*Algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks ［J］.IEEE Transactions onIntelligent Transportation Systems，2002，(3):60-74.