第三章 路径规划的分析及设计 13 用的较多有基于路段连接和基于Arc-Node（弧-节点法）等若干种。本文采用Arc-Node结构，其主要特点是，容易表达实际路网的拓扑关系，且形式简洁。
Arc-Node模型的基本原理是，将显示中的真实道路用一系列折线段来模拟和近似，即在一定精度的允许范围内，采用以直代曲的思想，用分段连续的小段直线段所组成的折线段来代替和逼近真实的道路曲线，将其中小段的直线段称作Arc，Arc的端点称为Node,这样，整个道路网络将由Arc和Node组成，其形式化定义为
Rw = (N,R) N = {x|x∈Ns} R = {NR}
NR = {＜x,y＞|L(x,y)...(x,y∈N)}
式中：Rw ——道路网络；
Ns ——道路网络的节点集；
NR——道路网络中任意两节点间拓扑关系的集合； ＜x,y＞——节点x和y之间存在的一条弧；
L(x,y) ——节点x和y之间的权值，节点和节点之间连接的权值可以用节
点之间的集合长度或者其他费用来表示。
根据实际交通网络的特点，我们作如下分析假设：
①所有的编制都是直线。对于弯曲弧度较大的路段，可以通过在该路段上 插入一系列节点使该路段由一些弧度较小的路段构成，弧度较小的路段可以认 为是一条边。如图3.3，节点1、2之间路段的弧度较大，在路段上加入节点2，把原来的路段分成两个弧度相对较小的路段。 ②边通常是双向可通的，边的权值为正值。 ③网络中有较多的节点和边。
④和节点相关联的边数为常数，且远小于网络中总的节点数。
14 GPS车载导航仪的路径规划研究 节点3
节点1 节点2 图 3.3 弧度较大的路段处理
2.导航电子地图中道路网络的计算机存储
计算机存储的是矢量化的道路网络，网络的存储结构是影响路径规划算法搜索速度和事件复杂度的一个重要因素。一个简单直观的存储方法是对道路网络图中的每一个节点进行编号，采用邻接表的链式存储结构。在邻接表中，对图的每个节点建立一个单链表，每个单链表都由表节点和表头节点构成。第i个单链表的w个表节点分别对应着和图中第i个节点相关联的w条边。链表的表头节点以顺序结构形式存储，以便随机访问图中任一节点的单链表。因此，采用邻接表的链式存储结构，很容易找到和图中任一节点相关联的边。单链表的表头节点和表节点的结构如图3.4所示，图中，Name：节点编号；Position：节点位置坐标；First：指向链表中的第一个表节点；Next：指向链表中的下一个表节点；Weight：边的权值。
Name 表头节点 Position First Name Position 表节点
Weight Next
图 3.4 链表结构
3.2.2 折线道路网络的拓扑生成法
1.折线道路网络的组成特点
折线道路网络组成的最大特点是，每一条道路都是由带有宽度值的折线段（简称道路中心线）表示。有时，为了数据获取方便，也可能以近似的道路中心线来表示。各种来源提供的实际数据使得折线道路网络中可能存在以下情况：
①线段间的虚交特性，即两条实际相交的路段，在给定的道路网络数据中却
第三章 路径规划的分析及设计 15 不存在与交点对应的节点。如图3.5（a）所示，路段AB与路段CD实际应相交于节点O，而节点O并未出现在路段AB与路段CD的给定数据中。
②线段间的虚段特性，即两条实际相交的路段，因其中一条路段偏短导致没能相交。如图3.5（b）所示，路段AB与路段CD实际应相交于节点B，而节点B并未出现在路段CD的给定数据中，将节点B称为虚断点。
③线段间的过交特性，即两条相交的路段，因其中一条路段偏长而导致过短的毛刺路段出现。如图3.5（c）所示，路段AB与路段CD相交于节点O，过短路段BO应该不存在，然而，节点B却出现在路段AB给定数据中，将节点B称为过交点。
④节点的冗余特性，一种情况是，实际应该是同一节点的点却存在多个相邻的节点。如图3.5（d）所示，节点A、B、C、D实际表示的地图中的同一点，换言之，此时应该只用一个节点来表示地图中的该点，然而，给定的道路网络数据中却存在节点A、B、C、D；另一种情况是，本来可以由两个节点表示的路段，给定的道路网络数据中却存在其他节点，如图3.5（e）所示，路段AB只需节点A和B便能在精度允许范围内准确表示，而实际数据中却包括节点C和D。
A C D B O C A (b)线段间的虚断特B A (c)线段间的过交特性 D B C O D (a)线段间的虚交特性 A D C 性 C A D B B (e)可以压缩掉的中间节点 (d)表示同一点的多个节点 图 3.5 实际数据中折线道路网络的情况 2.折线道路网络拓扑生成算法原理
算法的原理可以简单的描述为：依据折线道路网络的组成特点及Arc-Node数据模型，由给定的折线道路网络数据生成表示其拓扑结构的Arc-Node数据结构。具体生成过称分为两步：
第一步是完善给定的折线道路网络数据，即对前面介绍的道路网络的几种特
16 GPS车载导航仪的路径规划研究 性进行相应的处理。具体的处理方法是：虚交时，将实际应该有的交点分别插入两条路段中，从而两条路段分裂成四条路段，如图3.5（a）中，应将节点O分别插入路段AB和路段CD中，从而使路段AB与路段CD分裂成路段AO、OB、CO和OD；虚断时，应以偏短路段延长线与另一路段的交点代替偏短路段中靠近该交点节点，如图3.4（b）中，应将路段AB的节点B用路段AB的延长线与路段CD之交点来代替；过交时，应该删除过短路段，如图3.5（c）中，应将路段OB删除，即将节点B从路段AB中删除；节点冗余时，如果是第一种情况，应以冗余节点的中心点代替这些冗余点；如果是第二种情况，则应将所有的冗余节点删除，如图3.5（d）中，应将A、B、C、D用它们的中心点来代替，该中心点的纵横坐标分别为这些冗余节点纵横坐标的均值，如图3.5（e）中，应将路段AB中的节点C和D删除而只保留节点A和B。
第二步是在第一步的基础上，由完善以后的折线道路网络数据生成表示其拓扑结构的Arc-Node数据结构，Arc-Node数据结构采用邻接表结构。
3.3 路径规划的分析及设计
路径规划是现代智能车辆导航的一项关键技术，是基于具有拓扑结构的道路网络，在车辆行驶前或行驶过程中寻找出发点到目标点最优行车路线的过称。本节充分挖掘实际道路网络具有的各种特性，分别利用道路网络空间分布特性和道路等级特性，设计了两种针对道路网络的启发式搜索策略，即方向搜索策略和分层搜索策略；利用所构造的搜索策略设计了三种不同的启发式搜索策略。 3.3.1 路径规划的基础算法
Dijkstra算法是设计各种路径规划的基础。本节简要的介绍Dijkstra算法的原理及特点，并给出它的两种具体实现方法，即邻接矩阵法和邻接节点法，作为后续几个路径规划算法的基础算法。
1.算法原理
给定带权有向图G=(V,E),其中V是包含n个节点的节点集，E是包含m条弧的弧集，〈v,w〉是E中从v至w的弧，c〈v,w〉是弧〈v,w〉的非负权值，设a,b是V中的节点，Pab={v0=a,v1,?,vn=b}是V中由a到b的一条路径，则路径Pab的权值总和TC(Pab)表示为：
相关推荐：
loading