浅析航线选择中的改进最短路径算法

,

(海军潜艇学院，山东 青岛 266071)

最佳航线选择不仅是船舶驾驶员经常关注的问题之一，而且还是船舶经营公司时常面临的重要问题之一。船舶从起始地到目的地之间有多条航线可供选择，由于自然条件、距离、船舶密度等多种因素的影响，各条航线所含的参数不同。在多条可供选择的航线中，选择出一条最佳航线，无疑将会对提高船舶经营公司的竞争力起到至关重要的作用。

对于一个网络简单的规划来说，最短路径算法具有良好的适用性；但是对于一个较为复杂的交通网络来说，最短路径算法在搜索效率上则会大打折扣，因此，需要更为高效的搜索算法。

1 数学模型的建立

船舶最佳航线选择问题可以描述为：某船从起始港S出发前往目的港E，S、E两港之间存在多条可供船舶航行的航线，并且这些航线和船舶在航线上的挂靠港或锚地组成了一个交通网络图。那么，从起始港S出发前往目的港E，存在一条最佳航线。这里，“最佳”包括有航程最短、时间最省、能耗最少、最安全等内容。若要研究时间最省、能耗最少、最安全等内容时，只需将研究问题中的一些参数作一些必要的变换后，这些问题将会变成最短路径问题。这里将航程最短作为目标，建立数学模型[2]。

起始港与目的港之间为一交通网络。无向图G=(V，E，L)。式中：V为m个节点构成的点集；E为n条边构成的边集；L为路权集。同时满足：

1)G为一个简单图，不含环和多重边；

2) 路权具有可加性。若有路径νi-νk-νj，则有

l(νi,νj)=l(νi,νk)+l(νk,νj)

求A，B间的最短路径P*，满足

2 最短路径算法

目前最短路径问题的最成熟算法是Dijkstra算法。先给赋权图的每一顶点记一个数(称标号)，临时标号(T标号)或固定标号(P标号)。T标号表示从始点到这一点还没有寻找到最短路径；P标号则表示从始点到这一点已寻找到最短路径。计算的每一步是把某个点的T标号变成P标号。这样一旦终点得到P标号，计算就停止。若寻求从始点到每一点的最短路径，则最多经过N-1步计算，计算就要停止(N是G的顶点数)。

步骤1：给始点v1标上P标号d(v1)=0，给其他各点标上T标号d(vj)=l1j(j=2，3，4，…，N)；

步骤2：取所有T标号中的最小者，如，d(vj0)=l1j0，则把该点的T标号改为P标号；

步骤3：重新计算具有T标号的其他各点T标号：选vj点的T标号与d(vk)+lj中较小者作为vj的新标号。

一般情况下，设：

P={vj|vj具有P标号}

T={vj|vj具有T标号}

VP(V为图G的顶点集合)

step4：重复上述步骤，直到vN∈P，这时d(vN)是从v1到vN的最短路径。

3 改进算法

最短路径问题首先考虑是否将此问题分解多个子问题进行求解。这样可以降低问题复杂度，符合并行处理思想。Dijkstra最短路径算法是从起点到终点求最短路径，同样也可以表述为从终点到起点求最短路径。于是考虑最短路径问题是否可以分解为由起点到终点求解最短路径和由终点到起点求解最短路径两个子问题[3]。

步骤1：开始时，P=Ø，Q=Ø，易知vm=v1，vn=vN。P，Q分别是由开始点v1、终点vN开始的扩展点(固定标号)集合，vm,vn分别是集合P，Q的当前扩展点；

式中：d(vm)、e(vn)——起点到vm、终点到vn的最短路径。

P∪{vm}→P，Q∪{vn}→Q

步骤3：重复步骤2直到P∩Q={vm}且vm唯一时终止；

步骤4：计算最短路径

l1=d(vm)+e(vn)

l2=d(vx)+e(vy)+l(vx,vy)

式中：l(vx,vy)——vx，vy相邻两点的路权值，

l(vx,vy)>0

vx∈P

vy∈Q

最短路径lmin为：lmin{l1,l2}

算法程序框图见图1。

图1 改进算法程序框图

4 实例

如图2所示，若船从起始港S港出发前往目的港E港执行运输任务，其间有多条航线以及挂靠港或锚地可供船舶驾驶员或船舶经营公司选择，两点之间的航线上的权值表示该航线的航程，权值越大，表示航程越大，反之，航程越小。作为船舶驾驶员或船舶经营公司，要在这些航线中选择出航程最短的航线。

图2 交通网络图

各航线的航程见表1。

表1 航线航程表 n mile

Dijkstra算法搜索过程及结果见表2。

表2 Dijkstra搜索过程

航程最短航线为S→D→C→B→A→E。

改进算法搜索过程及结果见表3。

表3 改进算法搜索过程 n mile

航程最短航线为S→D→C→B→A→E。

比较两算法：搜索结果相同，但是显然改进后的算法在效率上较第一种有所提高。在节点较少、边较少简单的交通网络中两种算法也许没有太大的区别，但是对于一个较为复杂的交通网络来说，改进算法就能发挥出优势。

[1] 龙光正，杨建军.改进的最短算法[J].系统工程与电子技术，2002(6)：106-108.

[2] 邓成梁.运筹学(OR)的原理和方法[M].武汉：华中理工大学出版社,1996.

[3] 傅冬绵.交通问路系统中最短路径的新算法[J].华侨大学学报:自然科学版，2001(2)：139-142.

收稿日期：2007-08-30

修回日期：2007-10-22

作者简介：蔡文学(1968-)，男，博士，副教授。

研究方向：交通信息化与电子政务、交通地理信息

系统、物流信息系统等。E-mail：jzhf2605@yahoo.com.cn