划分路网
确定主要道路的方法：
专家评估 实际调查
根据有关专家 对路网的了解， 选择居民出行 关专家对路网的了解， 选择居民出行 倾向大的路径作为主要道路。 倾向大的路 径 作为主要道路。
实际调查内容包 括查看路网资料 和询问司机等。 确定主要道路依 据的路网资料有： 交通流量和公交 路线的分布情况 等。
智能运输系统
最优路径选择模型及其算法
路网节点 的确定
路网节点的确定方法：
1）
小区路网的节点是小区中所有的交叉口；主要道路网的节点不仅包括各 小区的交点。且是全体主要道路的相邻交叉口的集合。
2）
小区边界上的交叉口，即同时还属于主要道路网的交叉口，应作有标记。
智能运输系统
最优路径选择模型及其算法
计算最优路径 的常用算法
最优路径选择模型及其算法
交通流诱导系统
——最优路径选择模型及其算法


学院：信息工程学院 姓名：刁含楼
智能运输系统
最优路径选择模型及其算法
最优路径选择 的背景：
1.最优路径选择 是每个出行者都 必须要面对的问 题，其本质就是 选择合适的路阻 函数 2.通过将路网合 理的优化，再选 择合适的算法就 能够计算出满足 一定条件的最优 路径 3.目前有很多优 秀的算法，如 dijkstra法,floyd 算法等
现实：
这些算法都是通用的算法，没有考虑到实 际的出行特点和缓解城市交通拥堵的问题
智能运输系统
最优路径选择模型及其算法
提出解决问 题的办法
把整个路网的所有 路段都投入搜索
最终的结果
浪费大量的时间，结 果也不能被驾驶员所 接受
这就要求我们从另一个角度来考虑 问题——优化路网结构
智能运输系统
最优路径选择模型及其算法 TC-B Method
消除路段难以 确定，多数情 况下，出行者 也许不会对某 一路段表示 “不满意”
智能运输系统
最优路径选择模型及其算法
k 条 最 优 路 算 法
结果常常不能满足要求，而且它的优势 在当k=2时体现不出来。当k=2时，所求 路径为次最短路。次最短路就是除最短 路以外所有路径中的最短路，运用Dijkstra 算法求出相应的最短路。
智能运输系统
最优路径选择模型及其算法
确定路网 组织调用 形式
城市道路的路网一旦确定，便少有改变，但对其组 织调用却有不同的方式，合理的调用形式会带来较 少的计算量和令人满意的结果
两套有效的且具有不同特点的方案：
方案一： 将主要道路网及各小区的任 两点间的最短路距离及相对 应的最短路径都预先计算出 来，编成数据库，搜索时， 只要调入相关小区的库文件， 按小区间不同的出入口，把 行经各小区的行程时间迭加 起来，再搜索出总行程时间 最小的路径所对应的路段即 可 方案二： 将主要道路网及各小区 的路网信息（交叉口） 编成数据库，计算最优 路径及备选路径时调入 相关小区的库文件，把 各小区的交叉口合并起 来，形成简化路网，在 简化的路网里搜索最优 路径及备选路径。
智能运输系统
最优路径选择模型及其算法
算 法 的 步 骤
给定赋权有向图D=(V，A)。 开始(i=0)令S0=｛vs｝，P(vs)=0，λ(vs)=0， 对每一个v≠vs，令T(v)=+∞，令k=s。 ① 如果Si=V，算法终止，这时，对每个v∈Si， d(vs，v)=P(v)；否则转入②。 ② 考查每个使(vk，vj)∈A且的点vj。 如果T(vj)＞P(vk)+wkj，则把T(vj)修改为 P(vk)+wkj，把λ(vj)修改为k；否则转入③。 ③ 如果，则把的T标号变为P标号，令，把i换 成i+1，转入①；否则终止，这时对每一个 v∈Si，d(vs，v)=P(v)，而对每一个，d(vs， v)=T(v)。
Dijkstra
智能运输系统
最优路径选择模型及其算法
智能运输系统
智能运输系统
最优路径选择模型及其算法
确定主要道路网时应注意的问 题：
（ 3）
（ 2）
（ 1）
兼顾道路的等级。一 般来说，城市路网中 的主要道路应并入主 要道路网。
根据道路网的疏密 程度，在道路网密 度大的地区（如市 中心），可将一些 次路作为主要道路。
应避免出现过于 狭长的小区，这 样可能导致错误 的结果。
Dijkstra算法,floyd算法。
计算备选路径 的常用算法
路段消除方法、k条最优路算法。
备选 路径
智能运输系统
最优路径选择模型及其算法
备选路径
备选路径并非是距离次最短路，备选路径与最优路径的差别不 仅仅在于小区里的路段不同，而是在主要道路上与最优路径区 分开来
优点
缺点
路段消除法
简便性—— 备选路径可 以像最优路 径一样容易 地确定出来。
优化路网结构
一种从优化路 网结构考虑的 模型 改进路网 结构
出行者特点 路网划分
智能运输系统
最优路径选择模型及其算法
TC-B Method流程图：
1
划分路网
2 确定路网组织调用形式
3
路网节点的确定
4
选定计算机最优路径和备用路径 通用算法
智能运输系统
最优路径选择模型及其算法
划分路网是TC-B Method的关键，路网划分的好坏直接 影响到方法执行的效果。建立路网的关键是确定主要道 路。
VS
智能运输系统
最优路径选择模型及其算法
两种方案的优缺点：
优点 缺点
方案一：
速度非常快，因为所 有最短路径都已经预 先确定只是搜索出最 优路径而已
无法实现最优路径的实 时性要求，而且浪费了 许多内存空间，影响程 序执行的效率
方案二：
简化了路网，搜素速度 快，结果较为合理，任 务轻，易于调试，达到 了实时的效果
什么是dijkstra算法
?
智能运输系统
最优路径选择模型及其算法
Байду номын сангаас
附录：目前公认的最好的求最短路的算法——dijkstra算法
Dijkstra
算 法 的 基 本 思 想 从vs出发，逐步向外探寻最短路。执行过程中，与 每个点对应，记录下一个数(称为这个点的标号)， 它或者表示从vs到该点的最短路的权(称为P标号)， 或者是从vs到该点的最短路的权的上界(称为T标号)， 方法的每一步是去修改T标号，并且把某一个具T标 号的点改变为具P标号的点，从而使D中具P标号的顶 点数多一个，这样，至多经过p−1步，就可以求出从 vs到各点的最短路。