王 军，贾 斌，董立峰，吉 帅，石钰磊

(1.军事交通学院 研究生管理大队，天津300161;2.军事交通学院 国家应急交通运输装备工程技术中心，天津300161)

军事运输具有很强的约束性，在制订运输方案中，如何选择最优路径，以最快速度将人员、物资、装备运送到目的地是军事运输决策部门需要解决的重要问题。由于运输的军事装备多数情况下超限(超长、超宽、超高)，对道路限重标准、纵坡、曲半径和车辆行驶速度等具有很高的要求，因此，在选择运输路径时不仅需要考虑路线距离，还要考虑各项道路技术条件以及道路的交通状况，只有这样，才能制定出具有实际价值的最优路径。对最优路径的求解，可以按照求解最短路径的方法进行拓展。最短路径算法种类很多，包括Dijkstra 算法、A*算法、D*算法等［1］，其中，Dijkstra 算法是目前采用最多的传统方法。但是，作为一种基于单一权值的算法，未能考虑路径的多种约束条件。本文针对传统Dijkstra 算法，结合制订军事运输方案需求，对该算法进行拓展，可有效解决多约束条件的路径选择问题，并通过限制搜索区域方法、降低路网规模提高算法搜索效率。

1 路径选择模型建立

1.1 Dijkstra 算法描述

Dijkstra 算法使用广度优先搜索解决非负权有向图的单源点最短路径问题，算法以源点为中心向外层层扩展遍历，直到目标点为止，按路径长度递增次序产生最短路径。

假设G=(V，E)是一个带权的有向图，其中V为所有节点的集合，E为边的集合。设:M为已确定最短路径的标定节点集合;T为未确定最短路径的未标定节点集合。有向图中任意一个节点i都有一对标号(di，pi)，其中:di为从源点s到点i的最短路径的长度;pi为从s到i的最短路径中i点的前一点。dij表示节点i和j之间的距离(i与j直接相连，否则dij=∞)。算法求解过程如下:

(1)初始化。M= {s}，T=V-M，ds=0，ps为空;其他节点dij=∞，pi为空。

(2)从T中选取节点k，使得dk最小，并将k加入集合M中，即M={s，k}，T=V-{k}，pk=s。

(3)以标记节点k为中间点，检验k到其直接相连的未标记节点i的距离，并设置

若di改变，则pi=k。

(4)从所有未标记节点集T中，选取di中最小的一个点j，dj= mindi，i∈T，点j即被选为最短路径中一个节点，M={s，k，j}，T=V-{k，j}。

(5)如果所有节点都已标记，包含于M，则算法结束;否则，记k=j，转到步骤(3)再重复进行。

1.2 多约束条件定义

Djikstra 算法基于单一指标(路径距离)，不能直接用于多约束条件路径选择，需要对算法进行扩展。在最优路径选择中，涉及因素不仅包括传统的时间、里程指标，还包括道路等级、必经路段、禁止路段、通行能力、安全通过概率等，在数学模型中表现为图中边的权值并不是唯一的，因此，有必要建立一种能够把边上多约束条件映射成单一权值的数学模型［2］。在所有涉及因素中，根据约束条件对最优路径选择影响的不同，分为加法约束、乘法约束和凹性约束3 种类型。

记d(x，y)表示路段(x，y)的约束权值，则对于路径P = (h，i，j，k)，可以作出以下定义:如果d(P)=d(h，i)+d(i，j)+d(j，k)，称d(x，y)为加法约束，例如路段长度;如果d(P)=d(h，i)×d(i，j)×d(j，k)，称d(x，y)为乘法约束，例如路径安全通过概率;如果d(P)=min{d(h，i)，d(i，j)，d(j，k)}，称d(x，y)为凹性约束，例如道路限重标准。

通常可将不同约束类型转化为加法约束，以实现计算的简单化。对于凹性约束，在进行最优路径选择之前，将不满足最小权值要求的路段删除，例如公路运输中，某一路段对车辆进行限重，并且限制重量低于装载货物重量，那么在选择路径时不必考虑该路段;对于乘法约束，将各路段约束权值取对数变换，变为加法约束，使得在进行路径选择时，一般只考虑加法约束。

1.3 路径选择多约束模型

考虑到军事运输最优路径选择计算的复杂性，本文选择以路段距离、道路限重标准、道路安全通过概率3 个约束条件为例，建立出行路径选择模型。

设一条路径P 由路段(e1，e2，…，ei)组成，运输车辆通过该路径时行驶距离可以表示为

式中sk表示路段ek的距离。

假设车辆匀速通过邻近节点各路段，此时，路程最短就等同于时间最短，可以满足时间最短原则，行驶时间记为

式中:tk=sk/v0为车辆在路段ek的行驶时间;v0为车辆行驶速度。

路段ek的道路限重标准用hk来表示，主要对车辆荷载质量进行约束，那么由路段(e1，e2，…，ei)组成的路径P 的整体限重标准属于凹性约束，可以表示为

即一条路径的限重标准为组成该路径的所有路段限重标准的最小值。

路段ek的安全通过概率用pk来表示，用来描述该路段的交通状况。设路径P 由路段(e1，e2，…，ei)组成，根据概率论相关知识可知，该路径的安全通过概率P属于乘法约束:

即一条路径的安全通过概率等于组成该路径所有路段安全通过概率的乘积。根据1.2 中对多约束条件的定义，对等式两边取对数，将乘法约束表示为加法约束:

由于pk≤1，等式两边均为负数。两边同乘-1，得

根据对数函数的性质可知，P取最大值等价于P*取最小值，符合Dijkstra 算法搜索最小权值的原理和边权值为非负数的要求。

1.4 多约束条件向单一权值的转换

在最优路径选择过程中，可以把道路限重标准作为一个瓶颈约束条件，在搜索之前将不符合运输要求的路段删除。对于道路长度和安全通过概率，将2 个约束条件融合，引入估值函数:

式中:λ1和λ2分别为决策部门对道路长度和安全通过概率2 个约束条件的关注度，0 ≤λ1≤1，0≤λ2≤1，且λ1+ λ2=1;sk为路段距离;mk为安全通过概率等价转化后的距离，且式中:¯v为车辆行驶的平均速度;lk为路段ek本身固有的交通状况，由实际勘测、综合考虑发生交通事故、道路损坏等因素后评估得到;p*k=-lnpk是安全通过概率pk经过取对数、乘以-1 得到。

如果一条路径P 包括n个路段，则该条路径的权值可以表示为

2 拓展Dijkstra 算法的实现

2.1 传统求解Dijkstra 算法的不足

传统Dijkstra 算法搜索路径的效率与路网节点数量密切相关［3］。在军事运输路网这种大规模网络中，节点路段数量多，若直接应用Dijkstra 算法，程序的计算时间和存储空间将会变得非常庞大，导致系统运行效率低下。在算法的循环迭代过程中，未标记节点以无序状态存放，每次选择路径必须把所有节点搜索一遍，并且是毫无方向性地向四周扩散，在大数据量的情况下，将严重制约计算速度［4］。

本文从2 个层面对算法的实现过程进行优化:①使用合适的路网表示方法，降低路网规模，节约计算时间;②使用新的矩形区域限定模型，减少算法搜索的节点和路段，提高最优路径选择效率。

2.2 运输路径网络构建

运输路径网络是最优路径选择的基础和对象，要实现算法搜索，首先要把路径网络抽象为图论理论中的拓扑图，然后将其转化为计算机能够识别的信息，以合理的结构存储起来。

路网通常用赋权有向图来表示，针对道路交通网络的实际情况，本文采用二次读入边数据方法来建立路网［5］。

2.2.1 支点到支点的网络

按照连接边的数量，可以将路网中的节点分为2 类:中间站点(连接2 条边)和支点(连接3 条及3 条以上边)。首先把中间站点删除，只保留支点，支点之间的路段权值进行相加(如图1 所示)。

图1 运输路径网络

2.2.2 中间点起止的网络

中间节点作为源点或目标点，可以从数据库中查询该点到所在边2 个端点的距离，暂时删除这条边，然后增加1 个站点vk及2 条边(vk，vi)和(vk，vj)，边长等于该站点到这2 个端点的距离。

2.3 应用矩形搜索区域处理搜索范围

传统Dijkstra 算法计算过程中，搜索区域基本是以起始点为原点、起始点与目标点的欧式距离为半径的圆，如图2 中的圆。s、t分别为起始点和目标点，这样遍历了太多不必要的节点和边。

图2 限制搜索区域路径算法的比较示意

Nordbeck 等［6］提出了椭圆限制搜索区域算法，其基本思想是将构成路径的节点限制在1 个椭圆区域中，假设路网中的1 个节点n到起始点s和目标点t的直线距离分别为|sn⇀|、|tn⇀|(sn、tn分别为节点n到起始点和目标点的连线)，将节点是否在限制区域中的判断条件写成|sn⇀| + |tn⇀|≤MD，正好形成一个以s、t为焦点，以MD为长轴的椭圆，如图2 中的椭圆。进行路径选择时，椭圆外的节点不予考虑，这样就大幅度缩小了搜索规模，但是计算时需要执行大量的乘积与开方来判断节点是否在椭圆内，占用时间较多。针对椭圆限制搜索区域算法效率不高的缺点，陆锋等［7］提出矩形限制搜索区域算法，在椭圆搜索的基础上，求出椭圆的最小包含矩形，如图2 中的较大矩形。判断新扩展出的节点是否落在限制搜索区域，只需将节点坐标与矩形边界进行比较，避免了椭圆算法中大量的乘积和开方计算，效率更高。

在图2 中对给定2 节点进行最短路径搜索时，从起始点s到目标点t的连线方向基本代表了最短路径的走向，以此推测，最短路径基本在2 节点连线的两侧。因此，可以将搜索区域进一步缩小，限制在以st为对角线的矩形中，如图2 中的较小矩形。如果2 节点附近出现短距离的反向路径，即在线段st外，沿st或ts延长线方向的路径(在现实情况中表现为车辆为驶入合适车道所选择的道路)，此时最短路径显然不会落在小矩形区域，这时以椭圆的最小包含矩形为限制搜索区域来进行搜索。

建立路网之后，经过路径网络预处理，选择合理的数据存储结构，限制搜索区域来约束节点搜索范围，并恰当地制定搜索策略，利用Dijkstra 算法对最优路径进行搜索。整个算法的流程如图3所示。

图3 算法流程

3 模拟仿真分析

为验证算法的实用性和有效性，以郑州基地物资运输为背景，利用计算机软件平台进行仿真实验。通过实际调查与查询资料，得到郑州基地周边部分公路线路简图和相关数据，线路图如图4所示。

现有一批物资，需要从郑州基地运送到周口市，从线路图中可以看出，备选路径共有10 条。利用本文设计算法搜索最优路径，限制搜索区域并构建路网。分别用数字1 ～10 代表郑州、谢庄镇、开封、陈留镇、禹州、通许县、许昌、西华营镇、漯河、周口，路网如图5 所示。

应动 Matlab (实验使用版本为 Matlab7.12.0 R2011a，操作系统为Windows XP，32 位)，按图3 算法进行计算，得到郑州到周口的最优路径为郑州—谢庄镇—陈留镇—通许县—西华营镇—周口。

图4 部分公路线路

图5 郑州—周口路网结构

4 结 论

本文根据国家科技支撑计划项目“特种运输规划组织与监控技术研究”关于公路运输路径规划方案的提出，通过对传统Dijkstra 算法基于单一权值的特点进行拓展，使之能够解决军事运输多约束路径选择问题。从实验仿真结果可以看出，算法简化了路网结构，缩小了搜索规模，搜索时间基本能够满足实际需要。

［1］ 向冬梅，陈树辉.基于动态交通的最短时间路径规划方法研究［J］.微计算机信息，2012，28(9):317-319.

［2］ 廖建军.基于道路交通网络的多约束最优路径算法的研究［D］.南京:南京理工大学，2009.

［3］ 阮洁，钟宝荣.Dijkstra 算法在物流配送运输中的最短路径优化研究［J］. 计算机光盘软件及应用，2013，16(15):42-44.

［4］ 王兆南.基于Dijkstra 算法改进的海量数据最优路径计算方法研究与实现［J］.测绘通报，2012(9):32-37.

［5］ 杨斌，魏佳. 铁路超限货物最短运输径路查询系统的研究［J］.铁道运营技术，2010，16(2):1-7.

［6］ Nordebck S，Rystedt B. Computer Cartography Shortest Route Programs［M］.Sweden:The Royal University of Lund，2003.

［7］ 陆锋，卢冬梅，崔伟宏. 交通网络限制搜索区域时间最短路径算法［J］.中国图像图形学报，1999，4(10):849-853.