本篇是对罗家山的蚊子_导航路径规划之一 路网模型
的阅读笔记

一、对路网模型表达方式和存储结构的总体要求

路网作为网络的特殊性以及路线优化问题的要求，符合导航需要的路网表达方法和存储结构应满足如下要求：

• 存储量小
• 便于路线优化算法对其进行操作
• 充分考虑路网作为网络的特殊性——大型稀疏网络
• 能充分表达路网的要素和拓扑结构
• 能表达单项交通、交叉口转向限制等交通管制措施
• 能表达路网的各种特殊结构
• 要考虑节点权重如何存储

二、路网模型的描述

Q：如何来描述路网？

可采用有向带权图来描述路网。

描述路网的基本要素有节点、路段与形状点。

从路网的直观结构来考虑，很自然地用图来表示路网。

• 交叉口对应节点
• 两交叉口之间的路段对应边或弧
• 路段的某种量化属性作为权

这样，用一个带权图初步描述路网。又由于，同一路段不同方向其属性不一定相同，故可以采用有向带权图描述路网。

Q：何为节点？

节点并不是实际的点，它是一个抽象概念。在路网中我们通常理解的节点就是交叉口、高速路出入口、起点、终点等。

• 交叉口
• 道路特性发生了变化的点（节点处道路的权重会发生变化，这会影响路径规划的结果。）
• 可能进行转向的点
  为了导航中路径优化的需要，节点需具备以下属性：

节点属性

在路径规划中，节点应具备如下属性：

• 节点标识：在全国路网中，每个节点都有一个唯一的标识
• 节点坐标（经纬度）
• 节点类型？
• 红绿灯信息：该节点所处的交叉口是否有红绿灯信息
• 路牌信息

节点分类

节点在形态上可以分为简单路口和复杂路口。

• 简单路口
  由1个节点、>=1个路段组成的路口

  
  简单路口

• 复杂路口
  由>=2个节点、>=2个路段组成的路口

  
  复杂路口

Q：何为路段？

路段是两结点之间连接的弧，是道路包含的最小单元。同一路段上的道路属性完全相同。同一条道路中，可以有很多路段，但每个路段必须具有同一道路属性。

路段属性

在路径规划中，路段应具备如下属性：

• 路段标识：在全国路网中，每个路段都有唯一的标识
• 起始节点编号
• 路段长度：长度为米
• 路段宽度：长度为米
• 道路等级：高速公路、国道、省道、县道、乡道、城市快速路等
• 道路属性：上下行、交叉点内部路、换到、内部路等
• 形状点：描述该道路形状的坐标点数据
• 路段名称
• 收费设置：是否收费
• 通行关系：双向通行、逆方向、顺方向通行

Q：路网的拓扑关系

拓扑关系：是指节点、弧段等要素之间的邻接、关联、包含等关系。对路网来说，主要是连通性和方向性。连通性：如何表达路段以及节点之间的链接关系；方向性：用有向图来表示。连通性包含实体意义上的相邻性和实际交通行为中的可达性。

包含内容

• 实体意义上的相邻性
  直观上，一个路段与哪些路段是相连的，一个节点和哪些路段邻接，这是较低层次的连通性，利用一般的网络表示法就可直观表达；
• 交通行为中的可达性
  在实际路网中交通管理部门会经常采用一些交通管制措施，比如单项交通、转向限制、分时段限行等，由此造成直观上连通的路线，在实际交通行为中是不可达的，因而不连通。

如何表达禁行关系

• 两个节点之间的连通关系
  由于采用的是有向图表示路网，两个节点间有弧，则表示两节点可达，否则不可达。
• 三个节点之间的连通关系（或一个节点、两条弧）
  需特别考虑

例如下面的几种禁行情况

1. 路段禁止通行的（两节点间的连通关系）

   
   有向图的弧表示，无弧则不连通
2. 允许单向通行（两节点间的连通关系）
   两节点间只有一条边
3. 分时段限制通行（两节点间的连通关系）

被视为禁止通行

4. 转向（3节点间的连通关系）

涉及三个节点，需特别考虑

参考文献

罗家山的蚊子_导航路径规划之一 路网模型