本篇是对罗家山的蚊子_导航路径规划之一 路网模型
的阅读笔记
一、对路网模型表达方式和存储结构的总体要求
路网作为网络的特殊性以及路线优化问题的要求，符合导航需要的路网表达方法和存储结构应满足如下要求：
- 存储量小
- 便于路线优化算法对其进行操作
- 充分考虑路网作为网络的特殊性——大型稀疏网络
- 能充分表达路网的要素和拓扑结构
- 能表达单项交通、交叉口转向限制等交通管制措施
- 能表达路网的各种特殊结构
- 要考虑节点权重如何存储
二、路网模型的描述
Q：如何来描述路网？
可采用有向带权图来描述路网。
描述路网的基本要素有节点、路段与形状点。
从路网的直观结构来考虑，很自然地用图来表示路网。
- 交叉口对应节点
- 两交叉口之间的路段对应边或弧
- 路段的某种量化属性作为权
这样，用一个带权图初步描述路网。又由于，同一路段不同方向其属性不一定相同，故可以采用有向带权图描述路网。
Q：何为节点？
节点并不是实际的点，它是一个抽象概念。在路网中我们通常理解的节点就是交叉口、高速路出入口、起点、终点等。
- 交叉口
- 道路特性发生了变化的点（节点处道路的权重会发生变化，这会影响路径规划的结果。）
- 可能进行转向的点
为了导航中路径优化的需要，节点需具备以下属性：
节点属性
在路径规划中，节点应具备如下属性：
- 节点标识：在全国路网中，每个节点都有一个唯一的标识
- 节点坐标（经纬度）
- 节点类型？
- 红绿灯信息：该节点所处的交叉口是否有红绿灯信息
- 路牌信息
节点分类
节点在形态上可以分为简单路口和复杂路口。
-
简单路口
由1个节点、>=1个路段组成的路口
简单路口 -
复杂路口
由>=2个节点、>=2个路段组成的路口
复杂路口
Q：何为路段？
路段是两结点之间连接的弧，是道路包含的最小单元。同一路段上的道路属性完全相同。同一条道路中，可以有很多路段，但每个路段必须具有同一道路属性。
路段属性
在路径规划中，路段应具备如下属性：
- 路段标识：在全国路网中，每个路段都有唯一的标识
- 起始节点编号
- 路段长度：长度为米
- 路段宽度：长度为米
- 道路等级：高速公路、国道、省道、县道、乡道、城市快速路等
- 道路属性：上下行、交叉点内部路、换到、内部路等
- 形状点：描述该道路形状的坐标点数据
- 路段名称
- 收费设置：是否收费
- 通行关系：双向通行、逆方向、顺方向通行
Q：路网的拓扑关系
拓扑关系：是指节点、弧段等要素之间的邻接、关联、包含等关系。对路网来说，主要是连通性和方向性。连通性：如何表达路段以及节点之间的链接关系；方向性：用有向图来表示。连通性包含实体意义上的相邻性和实际交通行为中的可达性。
包含内容
- 实体意义上的相邻性
直观上，一个路段与哪些路段是相连的，一个节点和哪些路段邻接，这是较低层次的连通性，利用一般的网络表示法就可直观表达； - 交通行为中的可达性
在实际路网中交通管理部门会经常采用一些交通管制措施，比如单项交通、转向限制、分时段限行等，由此造成直观上连通的路线，在实际交通行为中是不可达的，因而不连通。
如何表达禁行关系
- 两个节点之间的连通关系
由于采用的是有向图表示路网，两个节点间有弧，则表示两节点可达，否则不可达。 - 三个节点之间的连通关系（或一个节点、两条弧）
需特别考虑
例如下面的几种禁行情况
-
路段禁止通行的（两节点间的连通关系）
有向图的弧表示，无弧则不连通 - 允许单向通行（两节点间的连通关系）
两节点间只有一条边 - 分时段限制通行（两节点间的连通关系）
被视为禁止通行
- 转向（3节点间的连通关系）
涉及三个节点，需特别考虑
