一种简化交通路网模型的导航方法

1.一种简化交通路网模型的导航方法，该简化交通路网模型将两节点之间的单行道抽象成一条有向弧，两节点之间的双行道抽象成两条有向弧，其特征在于：该简化交通路网模型将交叉口抽象成节点，并且在每一条有向弧上只加权有时间花费权值并且至少有一个时间花费权值，每一节点的前方向都有至少一个前驱节点并且其后方向都有至少一个后向节点；
设定S集合表示已求得花费时间最短路径的节点的集合，V集合表示交通路网中所有节点的集合，节点vi∈V-S表示所述V集合中未加入所述S集合的节点，并且引入了信息变量s(vi)，d(vi)，p(vi)以及时间花费权值函数cost(i，j，pre)，其中s(vi)是布尔型变量用来表示所述节点vi是否已求得花费时间最短路径，d(vi)表示从初始起点v0到所述节点vi的最小时间花费权限上限，p(vi)表示节点vi的后向指针并且所述时间花费权值函数cost(i，j，pre)表示加权至有向弧上的多个时间花费权值中从所述节点vi的一个前驱节点方向驶来的车辆对应的一个时间花费权值，在电子地图上获得初始节点v0与终止节点vt之间的所述花费时间最短路径包含以下步骤：
S1：通过设置在车辆中的GPS装置采集获得表示时间花费权值的数据，以形成数据库；
S2：选定所述初始节点v0和所述终止节点vt，分别初始化所述信息变量s(vi)，d(vi)，p(vi)，并且将所述初始节点v0标记为已求得花费时间最短路径的节点，其到自身的所述最小时间花费权值上限为0，使得s(vi) = false，d(vi)= cost(0,i,-1)，p(vi)=-1以及s(v0) = true，d(v0)=0，p(v0)=-1，节点v0无确定前驱节点，其中cost(0,i,-1)表示从所述节点v0到所述节点vi的多个时间花费权值中的最小时间花费权值并且如果所述节点v0与所述节点vi不相邻，则取无穷大；
S3：考察未加入至所述S集合的所有节点，选择与所述初始节点v0具有最小时间花费权值上限的节点vj，将所述节点vj添加至所述S集合，使得d(vj) = min{d(vi)|s(vi) = false, vi∈V-S}并令s(vj) = true；
S4：修改与所述节点vj邻接且未加入所述S集合中的节点vk，
如果d(vk)>d(vj)+ cost(j,k,p(vj))，则修改所述初始节点v0至所述节点vk的时间花费权值上限使得d(vk)=d(vj)+ cost(j,k,p(vj))且修改节点vk的前向指针使得p(vk) = vj；
S5：判定所述终止节点vt是否加入所述S集合：
如果所述终止节点vt未加入所述S集合，则重复所述步骤S3至S4，直至所述终止节点vt加入所述S集合，
如果所述终止节点vt已加入所述S集合，则从所述终止节点vt开始遍历其前向指针p所指向的节点，直至指针指向所述初始节点v0，从而获得所述花费时间最短路径；
S6：将所述花费时间最短路径绘制在电子地图上并且通过显示模块显示。
2.如权利要求1所述的一种简化交通路网模型的导航方法，其特征在于：该简化交通路网模型中所述交叉口为普通交叉路口、红绿灯交叉路口、立交桥和环道中的一种或者多种。
3.如权利要求1所述的一种简化交通路网模型的导航方法，其特征在于：该简化交通路网模型中在三个节点分别为节点x，节点y和节点z时，
如果所述节点y与所述节点z之间为单行道，则所述两节点之间具有一条有向弧：从所述节点y行驶至所述节点z的有向弧为或者从所述节点z行驶至所述节点y的有向弧为；
如果所述节点y与所述节点z之间为双行道，则所述两节点之间具有两条有向弧：从所述节点y行驶至所述节点z的有向弧为以及从所述节点z行驶至所述节点y的有向弧为；
并且加权至所述有向弧上的时间花费权值为txyz，用来表示从所述节点x驶来的车辆经过所述节点y到达所述节点z所花费的时间；
加权至所述有向弧上的时间花费权值为txzy，用来表示从所述节点x驶来的车辆经过所述节点z到达所述节点z所花费的时间。
4.如权利要求1所述的一种简化交通路网模型的导航方法，其特征在于：该简化交通路网模型中所述时间花费权值包含从所述前驱节点方向驶来的车辆经过所述节点所花费的时间以及所述车辆从所述节点经过对应有向弧到达其后向节点所花费的时间，其中经过所述节点所花费的时间是在所述交叉口的堵塞时间、红绿灯时间或者车辆排队等待红绿灯时间与车辆正常通过所述交叉口的时间总和，从所述节点经过对应有向弧到达其后向节点所花费的时间是车辆在所述有向弧上的堵塞时间与正常通过所述有向弧的时间总和。
5.如权利要求1所述的一种简化交通路网模型的导航方法，其特征在于：该简化交通路网模型中加权至所述有向弧上的所述时间花费权值的数量等于与所述有向弧对应的节点的前驱节点的数目。
6.如权利要求5所述的一种简化交通路网模型的导航方法，其特征在于：如果所述节点与其后向节点存在禁止转弯的情况，则将对应的时间花费权值设置为无穷大或者省略所述对应的时间花费权值。
7.如权利要求1所述的一种简化交通路网模型的导航方法，其特征在于：该简化交通路网模型中从不同前驱节点方向驶来的车辆经过所述节点到达所述后向节点所花费的时间不同。
8.如权利要求1所述的一种简化交通路网模型的导航方法，其特征在于：所述步骤S1中所述数据库中的数据包含车辆进入所述节点的初始时间与到达其后向节点的终止时间，所述初始时间与所述终止时间的时间差即为加权至对应有向弧上的所述时间花费权值。
9.如权利要求1所述的一种简化交通路网模型的导航方法，其特征在于：所述数据库中每一有向弧的各时间花费权值都以单链表的形式来存储，各单链表的表头节点都存储于邻接表中，并且所述单链表在所述邻接表中表头节点的索引存储于邻接矩阵中。

一种简化交通路网模型的导航方法 \n技术领域\n[0001] 本发明涉及一种城市交通路网模型的构建方法，尤其是一种简化交通路网模型及基于此模型的导航方法。 \n背景技术\n[0002] 路网模型是用来描述路网拓扑结构和路网实体的信息，是智能交通运输系统\n（ITS）和车辆导航系统（VNS）的重要基础，在交通仿真系统中也起着十分重要的作用。在ITS和VNS中，通过路网模型和电子地图的结合，给用户提示道路信息或规划出行路线，并在行驶过程中提供可视化的动态交通导航。交通仿真也是基于一种路网模型，通过对车辆、行人、道路等特征的深入分析，再现交通流和交通事故等各种交通现象，进而有效的进行交通规划、交通组织管理。所以路网模型能容纳的信息量大小，数据的存储结构的优劣都直接影响到导航系统或仿真系统的性能和效率。因此设计一种更加贴近现实、而且简单实用的路网模型是十分重要的。 \n[0003] 现有的路径规划静态路网模型，大致可以分为两类。 \n[0004] 第一类即“点-弧”模型。这类模型是将道路的交叉口抽象成一个点，将道路抽象成一条弧，进而把整个交通路网描述成一个有向的拓扑图。在早期的静态路径规划研究中，没有将交叉口延误的时间考虑到整个路网规划中，所以仿真模拟的结果和实际的路径规划和指引结果有很大出入。随着进一步研究，有研究者提出将某一个交叉口的延误时间设定为一个特定的值然后加到道路的权值上，再进行总体的路径规划。但是这种方法并没有考虑从不同方向经过这个交叉口的延时是可能不同，并且也没有考虑到各个时段的交叉口延时也可能不同的情况，从而导致模拟规划的结果与现实也有较大出入。例如要经过一个立交桥的时候，如果简单地将立交桥抽象成一个节点并设置一个统一的延时时间，则因从各个方向来的车辆在立交桥上的延时都可能不一样，并且差距可能非常大，导致路径导航计算与实践行驶结果间产生较大差异。这种模型难以准确的描述车辆在交叉口的延误时间和车道的相关属性（道路等级，限速，转弯限制等）。在更进一步的研究中，有研究者提出将交叉口独立出来，抽象出一个复杂的交叉口模型(其中普通交叉口可以抽象成一个节点，而其他诸如红绿灯交叉口、立交桥、环道等交叉口则抽象成大小不等的弧段，从而使得该交叉口模型较为复杂)，通过交叉口的各个参数设置计算交叉口的动态延误时间，进而将计算出的交叉口的延误时间作为路径权值的一部分进行路径规划，这样路径规划结果比之前的两种情况原则上会更精确。但是这类计算方法通常需要得到大量的参数，比如红绿灯的延时，交叉口的堵塞，排队等待的车辆队长等多方面的因素，计算量非常庞大并且非常复杂。 [0005] 第二类即“弧-弧”模型。这种模型将道路交叉口抽象成一个节点，车道抽象成一条有向弧，对于多车道来说，两点之间就有多条有向弧。这种模型虽然在一定程度上弥补了“点-弧”的不足（如不能准确的描述道路属性），但是这种模型大大的增加了数据存储，可能是“点-弧”模型的几十甚至几百倍；并且这种模型还是不能有效的解决交叉口延误时间。 [0006] 综上所述，在传统的最优路径导航算法中，模型一（第一类）的路径权值只有一个，这个权值可以代表着这条路径的长度或时间花费，然后利用最短路径算法求解静态最优路径或者通过动态的最优路径算法规划出最优路径，但是，如上所述，通过模型一计算出的最短路径很难将交叉口延时考虑进去，从而引起整个规划结果与现实情况出现较大偏差，或者虽然计算得出的交叉口动态延迟时间较为精确，但是需要利用较多的交通参数通过复杂的数学公式才可以计算得出。如果利用模型二（第二类），因为每两点之间的弧可能有多条，所以两点之间的权值也可能有多个，但是这多个权值是车辆经过不同车道所经过的时间或车道长度，对实际路径规划的意义不大，因为现实中的车辆可能出现超车道的现象。同样，路径规划算法利用模型二路径有多个权值的情况也没有考虑到交叉口延时的情况。 \n发明内容\n[0007] 本发明的目的是提供一种能够快速精确地获得行驶所花费时间最短的路径导航\n结果的简化交通路网模型以及基于该模型的导航系统。 \n[0008] 本发明采用的技术方案是这样的：该简化交通路网模型将两节点之间的单行道抽象成一条有向弧，两节点之间的双行道抽象成两条有向弧，并且将交叉口抽象成节点，在每一条有向弧上只加权有时间花费权值并且至少有一个时间花费权值，每一节点的前方向都有至少一个前驱节点并且其后方向都有至少一个后向节点，交叉口为普通交叉路口、红绿灯交叉路口、立交桥和环道中的一种或者多种。 \n[0009] 具体地，在三个节点分别为节点x，节点y和节点z时，如果所述节点y与所述节点z之间为单行道，则所述两节点之间具有一条有向弧：从所述节点y行驶至所述节点z的有向弧为或者从所述节点z行驶至所述节点y的有向弧为； \n[0010] 如果所述节点y与所述节点z之间为双行道，则所述两节点之间具有两条有向弧：\n从所述节点y行驶至所述节点z的有向弧为以及从所述节点z行驶至所述节点y的\n有向弧为；\n[0011] 并且加权至所述有向弧上的时间花费权值为txyz，用来表示从所述节点x驶来的车辆经过所述节点y到达所述节点z所花费的时间；\n[0012] 加权至所述有向弧上的时间花费权值为txzy，用来表示从所述节点x驶来的车辆经过所述节点z到达所述节点z所花费的时间。\n[0013] 另外，时间花费权值包含从前驱节点方向驶来的车辆经过节点所花费的时间以及车辆从该节点到达其后向节点所花费的时间，其中经过该节点所花费的时间是在该交叉口的堵塞时间、红绿灯时间或者车辆排队等待红绿灯时间与车辆正常通过该交叉口的时间总和，从该节点经过对应有向弧到达其后向节点所花费的时间是车辆在该有向弧上的堵塞时间与正常通过该有向弧的时间总和；并且加权至有向弧上的时间花费权值的数量等于与有向弧对应的节点的前驱节点的数目。如果所述节点与其后向节点存在禁止转弯的情况，则可以将对应的时间花费权值设置为无穷大；也可以省略对应的时间花费权值。 \n[0014] 该基于上述简化交通路网模型的导航方法，设定S集合表示已求得花费时间最短路径的节点的集合，V集合表示交通路网中所有节点的集合，节点vi∈V-S表示所述V集\n合中未加入S集合的节点，并且引入了信息变量s(vi)，d(vi)，p(vi)以及时间花费权值函数cost(i，j，pre)，其中s(vi)是布尔型变量用来表示节点vi是否已求得花费时间最短路径，d(vi)表示从初始起点v0到节点vi的最小时间花费权限上限，p(vi)表示节点vi的后向指\n针并且时间花费权值函数cost(i，j，pre)表示加权至有向弧上的多个时间花费权值中从所述节点vi的一个前驱节点方向驶来的车辆对应的一个时间花费权值，在电子地图上获得初始节点v0与终止节点vt之间的花费时间最短路径包含以下步骤： \n[0015] S1：通过设置在车辆中的GPS装置采集获得表示时间花费权值的数据，以形成数据库；\n[0016] S2：选定初始节点v0和终止节点vt，分别初始化信息变量s(vi)，d(vi)，p(vi)，并且将初始节点v0标记为已求得花费时间最短路径的节点，其到自身的最小时间花费权值上限为0，使得s(vi) = false，d(vi)= cost(0,i,-1)，p(vi)=-1以及s(v0) = true，d(v0)=0，p(v0)=-1，节点v0无确定前驱节点，其中cost(0,i,-1)表示从所述节点v0到所述节点vi的多个时间花费权值中的最小时间花费权值并且如果所述节点v0与所述节点vi不相邻，则取无穷大；\n[0017] S3：考察未加入至所述S集合的所有节点，选择与初始节点v0具有最小时间花费权值上限的节点vj，将节点vj添加至S集合，使得d(vj) = min{d(vi)|s(vi) = false, \nvi∈V-S}并令s(vj) = true；\n[0018] S4：修改与节点vj邻接且未加入S集合中的节点vk，如果d(vk)>d(vj)+ \ncost(j,k,p(vj))，则修改初始节点v0至节点vk的时间花费权值上限使得d(vk)=d(vj)+ \ncost(j,k,p(vj))且修改节点vk的前向指针使得p(vk) = vj；\n[0019] S5：判定终止节点vt是否加入S集合：如果终止节点vt已加入S集合，则从终止\n节点vt开始遍历其前向指针p所指向的节点，直至指针指向起始节点v0，从而获得花费时间最短路径，如果终止节点vt未加入所述S集合，则重复步骤S3至S4，直至终止节点vt加入S集合。；\n[0020] S6：将花费时间最短路径绘制在电子地图上并且通过显示模块显示。\n[0021] 其中，在步骤S1中数据库中的数据包含车辆进入所述节点的初始时间与到达其\n后向节点的终止时间，初始时间与终止时间的时间差即为加权至对应有向弧上的时间花费权值，并且单链表在邻接表中表头节点的索引存储于邻接矩阵中。 \n[0022] 综上所述，由于采用了上述技术方案，本发明的有益效果是： \n[0023] 1、传统“点-弧”模型将交叉口单独抽象成一个交叉口模型，在该交叉口模型中将普通交叉口抽象成一个节点，而红绿灯交叉口、立交桥、环道等则抽象成多个大小不同的弧段来描述，本模型将上述交叉口均抽象成节点，简化了对交通路网的描述，并且可以明显降低有向图维度；\n[0024] 2、传统“点-弧”模型中独立的交叉口模型利用复杂的公式来计算交叉口的延\n时，需要考虑道路的等级、状况、车道数量、容量和流量等复杂因素，本模型则只需采集车辆进入节点的初始时间以及到达其后向节点的终止时间，初始时间与终止时间的时间差即为加权至有向弧上的时间花费权值(其包含交叉口的延迟时间和通过有向弧对应路段的时\n间)，从而提高了车辆路径导航的计算效率并且能够更为精确地反应出交叉口的延迟时间，进而高速精确地获得路径导航结果；\n[0025] 3、由于本导航系统中数据的采集只需要利用通常车辆中均装载的GPS设备，而不需另外设置传感器等，故该导航系统具有更广泛的应用范围并且应用成本较低；\n[0026] 4、与目前针对现有交通路网模型（一条路径只有一个时间花费权值）的一般路径导航计算方法相比，其基于该简化交通路网模型还可以处理每条道路存在包含转弯延时及来自不同方向的车辆有不同时间花费的多个时间花费权值的情况。\n附图说明\n[0027] 本发明将通过例子并参照附图的方式说明，其中： \n[0028] 图1是根据本发明的一个实施例，一种小型交通路网的抽象示意图；\n[0029] 图2是根据本发明的另一个实施例，仅具有一个时间花费权值的局部交通路网示意图；\n[0030] 图3是根据本发明的又一实施例，具有两个时间花费权值的局部交通路网示意\n图；\n[0031] 图4是根据本发明的一个实施例，对图1所示小型交通路网模型的每条有向弧都\n添加了完整时间花费权值后的抽象示意图；\n[0032] 图5是在本发明提出的模型中将被抽象为一个节点来表示的车辆绕过环道的示\n意图；\n[0033] 图6是根据本发明的一个实施例，用于存储一条有向弧对应的各个时间花费权值的单链表的示意图；\n[0034] 图7是根据本发明的另一实施例，由图6中多个单链表构成的邻接表的示意图；\n[0035] 图8是根据本发明的又一实施例，图1中路网模型的邻接矩阵的示意图；\n[0036] 图9是基于该简化交通路网模型的导航方法的流程图。\n具体实施方式\n[0037] 本说明书中公开的所有特征，或公开的所有方法或过程中的步骤，除了互相排斥的特征和/或步骤以外，均可以以任何方式组合。 \n[0038] 本说明书（包括任何附加权利要求、摘要和附图）中公开的任一特征，除非特别叙述，均可被其他等效或具有类似目的的替代特征加以替换。即，除非特别叙述，每个特征只是一系列等效或类似特征中的一个例子而已。 \n[0039] 在传统的“点-弧”导航模型中，如果要较为精确地计算出交叉口的动态延迟时间，通常将交叉口独立出来，抽象成一个交叉口模型，其中普通交叉口抽象为一个节点，而诸如红绿灯交叉口、立交桥和环道等交叉口则抽象成多个大小不等的弧段。在通过交叉口的各个参数来计算交叉口的动态延迟时间过程中，需要采集大量的参数(诸如红绿灯的延时，交叉口的堵塞，排队等待的车辆队长等多方面的因素)，计算量非常庞大并且复杂。 [0040] 本发明则提出了一种采集少量数据即可简单地实现各种不同交叉口动态延迟时\n间的精确计算的模型，以及基于此种模型的导航方法。 \n[0041] 相对于传统的“电-弧”导航模型，该模型不仅将普通的交叉路口视为一个节点，而且将红绿灯交叉口、立交桥和环道也视为一个节点，从而简化了以往不同的交叉口，并且将单行道视为一条有向弧，双行道视为两条方向相反的有向弧，其中每一节点都具有至少一个前驱节点和至少一个后向节点。根据本发明的一个实施例，一种小型交通路网的抽象示意图如图1所示，在该交通路网中具有5个节点p、q、x、i和j，其中这5个节点可以是普通交叉路口，也可以是红绿灯交叉口、立交桥和环道。节点p与q、p与j、i与j、q与i之\n间为双行道，故相互之间分别具有两条方向相反的有向弧。当两个节点之间存在禁止转弯的情况时，通过该节点的延迟时间可以设置为无穷大∞，另外，也可以在该模型中不予以标示。如图1所示，节点x与节点i之间存在禁止转弯的情况，即从节点x出发不允许经过节\n点i到达节点j，故两节点之间的延迟时间为∞。 \n[0042] 与传统的模型不同，本发明中不是将该交叉口抽象成一个独立的交叉口模型，将该交叉口的延迟时间权值加权至该交叉口模型上，而是将交叉口的延迟时间权值加权至与各节点邻接的有向弧上并且在有向弧上只加权有时间花费权值，从而使得在各条有向弧上均获得一组时间花费权值(该组时间花费权值中至少有一个时间花费权值)。该组时间花\n费权值用以表示来自不同前驱节点方向的车辆在该条道路(即对应的有向弧)上的行驶总\n时间，包括在起始节点处交叉口的延迟时间和车辆在有向弧所指道路上的行驶时间，并且从不同方向驶来的车辆经过某节点到达其下一节点所花费的时间不同。 \n[0043] 本路网模型采用四元组RN=(V，E，T，D)的形式来描述，其中V表示交通路网中所有节点的集合，即各种交叉口的集合，E表示交通路网中各有向弧的集合，即各单行道或者双行道的集合，T表示交通路网中车辆通过各起始节点处交叉口的延迟时间与在各有向弧上行驶时间的总和的集合，即从起始节点至终止节点的时间花费权值的集合，D表示交通路网中相邻节点之间路段距离的集合。具体地，T集合中元素的表现形式为txyz，其中x、y、z是交通路网中的抽象节点。txyz表示从x方向行驶而来的车辆通过节点y到达节点z，加权至有向弧上的时间花费权值，其是两个时间花费权值之和：通过节点y处交叉口的延迟时间(其可以在交叉口处的堵塞时间、红绿灯时间或者车辆排队等待红绿灯时间与车辆正常通过该交叉口时间的总和)及从节点y行驶至节点z的行驶时间(其是堵塞时间与车\n辆正常通过该道路的时间的总和)，其中t下标中的第一顶点x表示车辆驶来的方向，第二顶点y和第三节点z分别表示车辆经过的初始节点和终止节点。 \n[0044] 根据本发明的一个实施例，仅具有一个时间花费权值的局部路网示意图如图2所示，车辆从节点q方向行驶经过节点q到达节点i的时间花费权值为tqpi，从节点p方向行\n驶经过节点i到达节点j的时间花费权值为tpij。根据本发明的另一实施例，具有两个时间花费权值的局部路网示意图如图3所示，与图2相比，增设了有向弧，即与节点p邻接的前驱节点具有两个节点q与节点j且节点p的后向节点为j，故有向弧上加权\n有两个时间花费权值：车辆从q方向行驶经过p到达i的时间花费权值为tqpi，从j方向行\n驶经过p到达i的时间花费权值为tjpi。 \n[0045] 根据本发明的一个实施例，图1中所示小型交通路网加权时间花费权值后的示意图如图4所示。以四元组的形式来描述该交通路网为：V={p,q,x,i,j} （节点集合）； \n[0046] E={,,,,,,,,,,}（有向弧集合）；\n[0047] T={ tjpq,tqpq,tqpi,tjpi,tjpj,tqpj,tpqp,tiqp,tiqi,tpqi,,tpqx,tiqx,tqxi,tqiq,tjiq,tpiq,txiq,tpij,tqij,tjij,tpji,tiji,tijp,tpjp }（时间花费集合）；\n[0048] D={d,d,d,d,d,d,d,d,d,d,d}（路段长度集合）。\n[0049] 综上所述，本模型中如果车辆可以从与某个交叉口节点邻接的多个前驱节点方向驶来，并且可以通过该节点到达其邻接的后向节点，则该节点至其后向节点的有向弧上加权的时间花费权值的数量等于其起始节点的前驱节点的数目。例如，图4中节点p具有两\n个前驱节点j和q并且具有后向节点i，故节点p至i之间的有向弧上加权有两个\n时间花费权值tqpj和tjpi。 \n[0050] 另外，在交通路网中出现禁止转弯的情况时，也就是说，从某节点的前驱节点驶来的车辆不允许经过该节点到达对应的后向节点，则可以省略对应的时间花费权值。如图4所示，由于禁止从节点x方向驶来的车辆经过节点i到达节点j，故有向弧上只加权有三个时间花费权值(其中省略了txij)。应注意的是，在加权过程中也可以将txij设置为无穷大。 \n[0051] 在图5所示的车辆绕过环道情况，从i、j、k、m方向驶来的车辆向n方向行驶，由于各个方向绕过环道的路径不一样，理论上来说，i方向绕过环道的时间是最长的，j、k、m方向绕过环道所花费的时间依次递减。由此可见，从此等四个方向驶来的车辆绕过环道向n方向行驶到达其后向节点所花费的时间是不相同的。因此，在数据采集过程中，不是采集交叉口处红绿灯的延时、堵塞、排队等参数，而是只需要实时采集车辆从进入节点的初始时间以及到达其后向节点的终止时间，初始时间与终止时间的时间差值即为加权至两节点之间的有向弧上的时间花费权值。数据的采集通过外部的GPS设备来实现。 \n[0052] 数据库中每一有向弧上各时间花费权值都以图6所示的单链表结构来存储，而此等单链表的首指针则统一存储于图7所示的邻接表(其为一维数组)结构中。应注意的\n是，图8中邻接矩阵中各单元存储的并非是表示节点间有向弧连接关系1或0，而是相关有向弧的单链表在邻接表中对应的表头节点的索引。 \n[0053] 图6中单链表的表头节点由RID、SID、EID和next指针构成，其中RID表示道路\n(有向弧)的编号，SID 表示该条道路的起始结点的编号，EID 表示该条道路的终点结点的编号，next指针指向带有三个域(preID ,weight和next)的中间结点。preID是道路起始\n结点SID的一个邻接前驱结点的编号， weight是从preID方向驶来的车辆通过SID的时间\n与行驶至EID的时间之和，next为指向下一个此类型的中间结点的指针。以下是单链表的表头节点、中间节点以及邻接表的定义： \n[0054] 单链表的表头节点定义：\n[0055] struct RoadInfo \n[0056] Long RID； \n[0057] Long SID; \n[0058] Long EID; \n[0059] PreNodeInfo * next; \n[0060] }\n[0061] 单链表的中间节点定义：\n[0062] struct PreNodeInfo\n[0063] {\n[0064] Long preID;\n[0065] Double weight;\n[0066] PreNodeInfo * next;\n[0067] }\n[0068] 邻接表的定义：\n[0069] RoadInfo Road[N]; // N 是图中有向弧的数目。\n[0070] 一般地，采用以下步骤来访问所述数据库模块中的数据： \n[0071] S1：访问邻接矩阵，找到邻接表中与有向弧对应的单链表的表头节点；\n[0072] S2：根据表头节点，找到邻接表中对应的单链表；\n[0073] S3：遍历单链表得到有向弧的各个时间花费权值以及时间花费权值是车辆从哪个方向驶来的时间花费权值。\n[0074] 传统的静态路径算法是以行驶路径最短为目标，而本导航方法是以行驶时间最短为目标来优化行驶路线，供车辆导航使用。因此，本导航方法中采用的静态路径算法在传统Dijstra算法的基础上做出了改进，因为与传统算法不同本模型中每条有向弧可能存在多个时间花费权值，故在此引入了时间花费权值cost（i，j，pre）函数，用来求得一条有向弧上加权的多个时间花费权值中与当前路段的前驱节点(行驶方向)对应的时间花\n费权值。 \n[0075] 在该导航方法的实施过程中，设定S集合表示已求得花费时间最短路径的节点的集合，V集合表示交通路网中所有节点的集合，节点vi∈V-S表示V集合中未加入S集合的\n节点，并且引入了信息变量s(vi)，d(vi)，p(vi)，其中s(vi)是布尔型变量用来表示节点vi是否已求得花费时间最短路径(当节点vi求得花费时间最短路径，则s(vi)=true；当节点vi未求得花费时间最短路径，则s(vi)=false)，d(vi)表示从初始起点v0到节点vi的最短时间花费权值上限，p(vi)表示节点vi的后向指针。应注意的是：上述对节点i是对节点vi的简化描述。 \n[0076] 具体地，在电子地图中查找初始节点v0与终止节点vt之间的花费时间最短的路径包含以下步骤： \n[0077] 步骤一：通过设置在车辆中的GPS装置采集获得表示时间花费权值的数据，以形成数据库，其他步骤流程图如图9所示：\n[0078] 步骤二：选定初始节点v0和终止节点vt，分别初始化信息变量s(vi)，d(vi)，p(vi)，并且将初始节点v0标记为已求得花费时间最短路径的节点，其到自身的最小时间花费权值上限为0，使得s(vi) = false，d(vi)= cost(0,i,-1)，p(vi)=-1以及s(v0) = true，d(v0)=0，p(v0)=-1，节点v0无确定前驱节点，其中cost(0,i,-1)表示从节点v0到节点vi的多个时间花费权值中的最小时间花费权值并且如果节点v0与节点vi不相邻，则取无穷大；\n[0079] 步骤三：考察未加入至S集合的所有节点，选择与初始节点v0具有最小时间花\n费权值上限的节点vj，将节点vj添加至S集合，使得d(vj) = min{d(vi)|s(vi) = false, vi∈V-S}并令s(vj) = true，由于在初始化过程中在节点v0与节点vi不相邻时会取无穷\n大，所以节点vj一定与初始节点v0相邻接；\n[0080] 步骤四：修改与节点vj邻接且未加入S集合中的节点vk，如果d(vk)>d(vj)+ \ncost(j,k,p(vj))，则修改初始节点v0至节点vk的时间花费权值上限使得d(vk)=d(vj)+ \ncost(j,k,p(vj))且修改节点vk的前向指针使得p(vk)=vj；\n[0081] 步骤五：判定终止节点vt是否加入S集合：如果终止节点vt已加入所述S集合，\n则从终止节点vt开始遍历其前向指针p所指向的节点，直至指针指向所述起始节点v0，从而获得两节点之间的花费时间最短路径；\n[0082] 步骤六：将步骤四中获得的花费时间最短路径绘制在电子地图上并且通过显示模块显示出来。\n[0083] 其中，在步骤四中如果终止节点vt未加入所述S集合，则重复所述步骤三和步骤四，直至终止节点vt加入S集合。 \n[0084] 本发明并不局限于前述的具体实施方式。本发明扩展到任何在本说明书中披露的新特征或任何新的组合，以及披露的任一新的方法或过程的步骤或任何新的组合。