最短路径Auction算法及其在路径诱导中的应用＊

（东南大学交通学院 南京 210096）

0 引 言

在路径诱导模块中，最短路径算法成为决定导航性能的关键因素［1］．常用的最短路径算法可分为两类：标号设定算法（如Dijkstra算法）和标号修正算法（如Bellman－Ford算法）．以上2类算法在应用于最短路径问题时，都是通过先推出指定起始结点到达其余各点的最短路径，再通过终点反向追踪的方法求解起终点之间最短路径的．这样的求解思路显然产生了多余的求解信息．当驾驶员在道路网络中行车时，通常关注的仅是从所处位置到达预定目的地2点之间的最短行车路线．寻求更加符合路径诱导需求的路径算法、提高算法的针对性，成为导航系统关注的焦点．

Auction算法（拍卖算法）于1991年由Bertsekas应用于网络最短路径问题［2］．值得关注的是，Auction算法是一种能够直接求解“点对点”之间最短路的路径算法．因此，本文将就该算法在路径诱导中的应用作进一步的讨论．

本文将路径诱导中的“点对点”最短路径问题，根据比较试验讨论算法的复杂性以及影响算法速度的主要因素，评价其在路径诱导中的适用性．

1 Auction算法的基本原理

1.1 算法原理

Auction算法是模仿现实中的拍卖过程．考虑如下拍卖过程：有n个人和n个物体，遵循“一对一”的原则，实现派对．假设物体j的价格为pj，要得到这一物体的人必须支付相应的价钱．人i与物体j派对可以获得的效益为aij，纯利润为aij－pj．每个人想获得使他获利最大的那一个物体ji，即aiji－pji＝max｛aij－pj｝．因此必须通过竞争和抬高价格，选择获益最多的那个物体．经过十几年的发展，这种算法已经推广用于解决一般的最小费用路径问题，择优条件也相应地发生了改变，成为较为解决线性网络流的综合性算法，也是近年来较新也较为受到关注的最短路径算法．

对于一幅赋权有向图，Auction算法是一种能够求解单一起点和单一终点的最短路问题的简单方法．这一特点恰恰满足了路径诱导技术中的最短路求解需求．Auction算法在求解过程中，始终维持一条从起点出发的简单路径P．算法的每一步对路径P中最后一个结点采取的“延伸”或“收缩”操作．当路径P的最后一个结点到达指定终点时，算法结束，且两点之间的最短路径得出．

为了直观的反映Auction算法的迭代过程，Bertsekas将算法过程比喻为“在迷宫中移动的小鼠”．小鼠在迷宫中移动，或者向未知区域前进，或者沿曾经走过的路线返回．每当小鼠从一个岔路口（结点）沿原路返回时，将记录一个估计值，作为重新回到该结点时的期望值；每当小鼠在向前探索时，根据对结点估计值的比较，选择一个期望最优的结点作为前进目标．在如此的前进与返回的过程中，直至找寻到迷宫中的目的地（终点）．由此反映出，Auction算法是一种从起点向终点迭代的探索性算法．

1.2 算法的基本步骤［3］

在给定一个有向网络G（V，E）中，V，E分别为G的点集合和弧集合，弧段（i，j）的费用为aij．首先，对算法作如下基本假设：（1）假设网络中的弧段费用均为正值；（2）假设除终点外的每一个结点至少有一条前向弧，对于不满足条件的结点，可增加一条指向终点的弧，并赋给它一个很大的弧费用；（3）假设两个结点间在一个方向上最多有一条弧连接（这一点仅仅是为了方便表述，拍卖算法能很好地解决一对结点间有多条弧连接的情况）．

下面描述最短路径求解过程：用1表示起点，t表示终点，（i1，i2，…，ik）表示一条路径．其中：（im，im＋1）表示弧（m＝1，…，k－1）．如果i1，i2，…，ik是各不相同的，则称（i1，i2，…，ik）为初等路，结点ik为路径的终点，所有弧的费用之和就是路径的长度．

定义P为迭代路径，在迭代过程中，P＝（i1，i2，…，ik）始终保持为初等路，并不断延伸和收缩．如果ik＋1不是路径P 中的结点，并且（ik，ik＋1）是一条边，则用结点ik＋1来延伸P，是指用路径（i1，i2，…，ik，ik＋1）来代替路径 P；如果路径 P不只包含起点i1，收缩P 是指用路径（i1，i2，…，ik－1）代替路径P．

定义p＝（p1，p2，…，pn）为网络中结点的价格矢量，其中元素与网络结点一一对应，例如pi表示第i个结点的价值量．在迭代过程中，价格矢量p需满足如下条件：

pi≤aij＋pj∀（i，j）∈E；pi＝aij＋pj

对于路径P上所有连续的结点对，这一条件称作松弛互补性条件（complementary slackness，简称CS条件），这与指派问题Auction算法的CS条件等价，并且，都可以由最小费用流问题的CS条件推导出来．可以证明，如果（P，p）满足CS条件，i是路径P中的结点，则从起点1沿P到结点i的路径也是从1到i的最短路，并且p1－pi就是相应的最短路长度．

根据Auction算法求解最短路径的过程，其“拍卖原则”体现于路径迭代的每一步中．在最短路径问题中，以aiji＋pji＝min｛aij＋pj｝取代原始拍卖问题中条件aiji－pji＝max｛aij－pj｝．在路径P延伸的过程中，将符合条件aiji＋pji＝min｛aij＋pj｝的结点ji分配给上游结点i，即以结点ji延伸路径P，有在路径P收缩时，以min｛aij＋pj｝更新价值量pi，记录该结点的估计值，便于路径P再次延伸时的回溯．这便是最短路径Auction算法中的拍卖原理．

为了使用计算机语言实现Auction最短路径算法，现给出算法的程序化描述（见图1）．对于符合基本假设的道路网络，求解从起点1到任意点i的Auction算法的基本步骤如下．

1）初始化（P，p） P＝ （1），pj＝0，j∈V．

图1 Auction算法流程图

2）用i表示路径P的最后一个结点．如果pi＜min ｛aij＋pj｝，进入下列步骤（1），否则进入（i，j）∈v步骤（2）：（1）收缩路径．令如果i≠1，收缩P，转到下一个迭代过程；（2）延伸路径．通过结点ji来延伸P，ji＝arg｛min｛aij（i，j）∈V＋pj｝｝．如果j是终点t，则迭代终止，P就是要求的最短路径．否则转入下一个迭代过程．

3）重复步骤2），直到算法推出．

1.3 算例

为了清楚的说明问题，本文采用了一幅简单的有向网络图，如图2所示，通过求解结点1至结点4的最短路径，演示Auction算法在求解网络最短路径时的迭代过程，见表1．

图3反映了在使用Auction算法求解上述最短路径问题时，路径P末节点的移动轨迹，反映了路径延伸和收缩的过程．

图2 简单的赋权有向网络图

图3 路径P末结点的移动轨迹

表1 Auction算法求解结点1到4最短路的迭代过程

2 “点对点”的最短路径问题

2.1 Auction算法的运算性能分析

最短路径算法的运算性能主要体现为算法的准确性和复杂性．为了进一步反映Auction算法在计算道路网络中“点对点”最短路径时的运算性能，本文采用了随机生成的赋权有向网络，对Auction算法的运算速度和运算准确性进行了测试（CPU Intel 1．76GHz），并选用了经典的Dijkstra算法作为参照．测试程序采用C＃语言编写，考虑到路径诱导系统的硬件环境，程序使用了单线程的前向的拍卖算法（forward algorithm）．比较测试在不同规模（结点数量规模、路段数量规模）的网络中进行，以测试算法的准确性和运算时间为主，对两种不同的算法选用相同的起终点进行测试试验．根据Auction算法的迭代特点，进行有针对性的测试，得出定量的数据分析，反映出算法的主要特点和结果随参数变化的趋势．

Auction算法的复杂度可以表示为O（EhL）．h表示起点1到终点t之间最短路径的最小路段数；L表示网络中路段费用的最大值．E＝I×G．其中，I表示从起点1出发，路径长度小于起终点间最短路径长度的结点i的数量；G表示上述结点i的最大结点出度．由此可见，影响Auction算法运算速度的主要因素为h，L，I，G几个参数．根据算法的复杂度分析，本文选择起、终点间隔（最短路路径所经过结点的数目）、网络平均结点出度（路段密度）、网络结点数作为主要试验参数，对于Auction算法的运算性能做出测试．具体试验过程如下．

1）根据随机网络生成方法，产生结点数量分别为500，1 000，2 000，5 000，10 000的5种规模的道路网络．

2）对于每种结点数量的网络，产生结点平均出度分别为2，3，4的3种路段密度不同的网络．其中，结点的平均出度为2，表示一种稀疏的网络结构；平均出度为4，表示密集的网络结构．按照这样的方法，共产生15幅随机网络．

3）在这15幅网络中，分别测试Auction算法和Dijkstra算法．每幅随机网络，随机产生100对起终点，对这100对起终点分别使用Auction算法和Dijkstra算法，记录算法的结果及性能（最短路径时间、最短路径、起终点间隔、算法运行时间）．通过算法运行时间，反映算法的复杂程度．

4）对于测试结果，以结点数量分为5大类，以路段数量分为3个次类，进行比较分析．

总体来说，由具有代表性的试验结果发现，2种最短路径的运算结果相同，对于所有的起始点对，都能够通过迭代得到相同的最短路径．因此，可以说明，两种基本算法的准确性相同．但是，在不同规模的网络中，Dijkstra算法均表现出了速度上的优越性．如图4所示，两种计算方法的运算速度都是随着网络规模的增加而降低的，Auction算法的速度受网络中结点总数的影响较大，Dijkstra算法则受网络中路段总数的影响较大．

此外，Auction算法受起终点间隔影响明显，其运算时间基本随起终点间最短路径结点数量增加呈递增趋势．运算时间呈现波动，在个别点处有下降，如图5所示，根据试验数据分析，造成下降的原因是该最短路径总时间相对较小，在路径P延伸时易于被优先选择．这样的测试结果，是符合Auction算法复杂性分析的．Auction算法仅在起终点间隔较短时，速度上优于Dijkstra算法．这种现象在如图5所示的大型网络中更为明显．随着路径结点数量的增加，Auction算法迭代的次数将明显增加，运算速度也明显低于Dijkstra算法．

图4 包含500个结点、1 000个结点和2 000个结点的网络中，2种算法运算速度比较

图5 包含10 000个结点的网络中，2种算法运算速度的比较

2.2 在路径诱导中的适用性

根据路径诱导设备的技术参数要求［4］，对于现行导航设备中，其存储空间已经达到了比较高的容量，但处理器主频速度和内存空间大小，还不能与一般的个人计算机相提并论．参考测试程序对运算速度要求高，对内存空间需求适中的特点，算法的速度应当作为首要考虑因素，其次考虑数据的存储空间问题．因此，将最短路径算法的运行时间控制在1s以内是比较合适的，也是用户可接受的速度．从上一节对于Auction算法性能的测试和算法复杂度的讨论中发现，算法能够准确的求解网络中任意两点之间的最短路径，但是在运算速度方面却与Dijkstra算法有着明显的差异．Dijkstra算法在所有的测试网络中，都能够将计算控制在极短的时间以内（＜0．5s），因此它具有普遍的适用性．Auction算法的速度主要受到起终点间隔的影响，仅在最短路径结点数量较少时，能够体现出其运算速度的优势．随着迭代距离的增加，Auction算法的复杂性迅速提高，运算速度明显下降，低于Dijkstra算法．Auction算法在实际“点对点”最短路问题的应用中，没有明显地体现出其算法原理优势，反而在整体性能上低于传统标号路径算法．因此，单线程的Auction算法在路径诱导中的适用范围较为有限，算法的计算步骤有待优化和改进．

3 结束语

尽管Auction算法已经在交通分配中，求解单一起点到多个终点的问题，以及多处理器的并行计算中，得到了很好的应用［5］，但是作为以“点对点”最短路径为求解目标的算法，单线程的Auction算法并没有在导航系统的“一对一”问题中体现出其原理上的优势［6－8］．即 Auction算法具有准确求解网络中最短路径的能力，可是仍然存在速度方面的局限性，仅适用于大型稀疏网络结构，或求解起终点间隔较少的最短路问题．因此，Auction算法的整体平均速度较传统的Dijkstra算法偏低．

综述之，仅仅是依照当前的算法步骤和单线程的算法程序，无法达到预期的算法效率．通过对于Auction算法的反复试验，可以发现，在算法的求解过程中，最费时的是每步迭代中对当前下游结点最小费用的计算．利用算法迭代过程中的性质，减少迭代过程的重复步骤，将有希望降低算法复杂性，提高算法的实际效率．此外根据文献［3］，双（多）线程的Auction算法采用双（多）处理器，在共用价格矢量的基础上，可同时从起点和终点开始延伸路径．考虑使用双处理器的路径诱导设备，能够发挥Auction算法在多处理器上并行计算的优势，将显著地提高算法的求解速度．

［1］张 可．车辆导航系统关键技术研究［D］．北京：北京工业大学，2001．

［2］王京元，程 琳．最短路拍卖算法在交通分配中的应用［J］．交通运输系统工程与信息，2006，6（6）：79－82．

［3］BERTSEKAS D P．An auction algorithm for shortest paths［J］．SIAM J．for Optimization，1991（1）：425－447．

［4］王 芬．Dijkstra最短路径优化算法在汽车导航的研究及实现［D］．上海：上海师范大学，2006．

［5］BERTSEKAS D P，CASTANON D A．The auction algorithm for the transportation problem［J］．Annals of Operations Research，1989，20（1）：67－96．

［6］LEONE R D，PRETOLANI D．Auction algorithms for shortest hyperpath problems［R］．Technical Report OR－CAM－1998－01，Universit′a di Camerino，1998．

［7］BERTSEKAS D P，PALLOTTINO S，SCUTELLA M G．Polynomial auction algorithm for shortest paths［R］．Technical Report TR－16／92，Dipartimento di Informatica，University of Pisa，1992．

［8］PALLOTINO S，SCUTELLA M G．Shortest path algorithms in transportation models：classical and innovative aspects［EB／OL］．http：／／ftp．di．unipi．it／pub／techreports／TR－97－06．ps．Z，1997－06－25．