交通分配及其算法.ppt

交通分配及其算法交通分配及其算法城市交通网络：O-D量：从出发点Original到目的地Destination之间 的交通量 ：路段a的通行能力 ：路段a的阻抗 配流问题要解决的问题就是将O-D量分配到交通网络中基本概念基本概念 1 1配流问题配流问题 2 21952年，wardrop首次提出了关于出行者路径选择的 第一、第二原理Wardrop第一准则：所有出行者选择道路的依据是使 自己的出行总费用最少—用户最优Wardrop第二准则：所有出行者选择道路的依据是使 整个系统的总费用最少--系统最优平衡状态：总是选择阻抗最小的路径，当不存单方面 改变其路径并能降低其阻抗时，认为达到了稳定状态 1956年，Beckman及他的同事研究了交通分配的数学 模型，根据非线性最优化理论，把这两个准则对应于 线性约束的凸非线性最优问题的解，证明了满足 Wardrop用户均衡原理的配流等价于一个非合作博弈 中的Nash均衡解，得到其配流模型Boyce于2005年就UE基本模型对交通科学及相关学科 建模技术发展的深远影响进行了回顾和展望 同年，Frank和Wolfe共同提出了关于求解凸二次优 化问题的迭代算法，被称为Frank-Wolfe算法。

1975年Leblanc将Frank-Wolfe算法用于求解这个模 型获得成功配流算法配流算法 3 3平衡配流问题等价于如下数学规划:启发式算法：比例配流法容限配流法全有全无法第0步 初始化:令 进行全有全无分配，得到 ，令n=1 第1步 计算 ， 第2步 搜索下降方向：根据 进行全有全无分配， 得到 ，从而确定下降方向第3步 确定步长 :第4步 更新流量： ，第5步 收敛检验:如果收敛标准满足，则停止;否则令 n=n-1转步1 Frank-Wolfe算法 模型发展和算法改进模型发展和算法改进 4 4模型发展：路段相互影响的平衡配流 含能力约束的分配模型 弹性需求分配模型 随机用户平衡 算法改进：F-W算法--收敛特性：方向、步长加速和流量更新其他优化算法：简约梯度法、凸单纯型法等Dial于2006年提出了一个基于路径的，但又能避免路径存储和枚举的算法，因而是效率更高的新算法。