改进logit多路径分配模型及其求解算法研究.pdf

1 改进改进 logit 多路径分配模型及其求解算法研究多路径分配模型及其求解算法研究 陈扶崑 朱月河 河海大学交通学院 南京 210098 E mail fukunchen163 摘摘 要要 研究多路径 logit 分配模型及经典的 Dail 算法 针对 logit 分配模型及 Dail 算法的 缺陷 本文提出了一种改进的 logit 模型及其相应改进的 Dail 算法 改进后的 Dail 算法使得 交通分配更加符合实际 并提高了分配的速度 最后用一简单算例说明求解过程及算法的有 效性 关键词关键词 交通分配 改进 logit 模型 Dail 算法 1 引言引言 交通分配是 四阶段法 中最后关键一步 如何准确的将出行 OD 分布量分配到具体各路 段上成为人们关注的问题 现有的交通分配方法大致分为符合 Wardrop 原理的均衡分配方法 与不符合 Wardrop 原理的非均衡分配方法 均衡分配方法理论上结构严谨 但其数学规划模 型维数太多 约束条件也多 且为非线性规划问题 所以求解困难 非均衡分配方法可分为 路径阻抗可变与路径阻抗不变两类 就路径选择可分为单路径与多路径两类 各种分配方法 均有不足 所以设计出更加合理而有效的分配模型成为一项重要研究 本文以阻抗为常数的 多路径logit分配方法为出发点 在原有logit模型与Dail算法基础上 提出了一种改进的logit 模型和相应改进的 Dail 算法 2 logit 模型及其改进模型及其改进 在出行者多路径选择中 称可供选择的路径叫 选择枝 Alternative 如果有两条路 径可供选择 就是二项选择问题 否则就是多项选择问题 选择枝具有令人满意的程度叫做 效用 Utility 关于 效用 本文做以下假定 1 个人在每次选择中总选择效用值最大的选择枝 2 个人关于每个选择枝的效用由个人自身的特性和选择枝的特性共同决定 在多路径分配问题中 定义各备选路径为选择枝 起讫点 r s 间出行者总是选择他认为 阻抗最小的路径 k 称出行者主观判断的阻抗为 感知阻抗 所以第 k 条路径的效用可表 示为 rsrsrs kkkk UCc 1 式中 k U为起迄点选择路径 k 的效用 rs k C为路径 k 的感知阻抗 rs k c为路径 k 的实测 阻抗 rs k 是服从二重指数分布 Gumbel 分布 的随机变量 并且所有的 rs k 是相互独立的 应用概率论的相关知识 可以推得出行者在起迄点之间选择路径 k 的概率 rs k P如公式 2 所示 1 exp exp rs rs k k rs l l bc P bc 2 2 2 式中 b 为与 方差有关的参数 文献 1 证明了参数 2 6 b D Logit 模型本身有明显的不足之处 它认为路径的选择概率是由路径间阻抗的绝对差决 定的 这会在分配过程导致一些不合理的结果 另外模型中的参数 2 6 b D 是一个带量 纲的物理量 其大小没有固定的变化范围 标定时要求先求出感知阻抗的方差 D 而感知 阻抗的方差很难求得 国内学者采用相对阻抗差计算路径选择概率 将 logit 模型改进为 exp exp rs k i bL kL P bL iL 3 3 式中 L i为路径 i 的实测阻抗 L为所有路径阻抗的平均值 参数 b 无量纲 仅与可 供选择的路径数有关 通过试验发现 b 的变化范围相当稳定 在 3 4 之间 一般取 b 3 3 在实际大型复杂网络中 所有路径阻抗的平均值L计算繁琐 本文借鉴上述改进 logit 模型 的思想 将L改为从起点到迄点的最短路阻抗 rs m L 采用与最短路阻抗相比较的形式 则 logit 模型可改进为 exp exp rsrs rs km k rsrs im i bLL P bLL 4 改进后的 logit 模型不用计算所有路径阻抗的平均值L 简化了计算步骤 并且经简单实例 验证 符合路径选择概率 3 Dail 算法及其改进算法及其改进 1971 年 Dail 提出的算法能较好的实现 logit 模型的求解过程 其出发点是通过判断一条 路径是否为 有效路径 来排除大量的 无效路径 在所定义的有效路径的集合中建立满足式 2 的递推公式 从而达到避免所有路径枚举的目的 用 r i表示节点 i 到起点 r 的最小 阻抗 s i表示从节点 i 到终点 s 的最小阻抗 Dail 算法的 有效路径 要求路段 ij 满足 r ir j 5 路段交通量计算分为正向计算路权与反向分配流量两个过程 这对于大型复杂网络计算量会 很大 耗时较多 本文对 Dail 算法进行了改进 降低了有效路段的评定标准 重新定义有效路段 r ir j 即只要路段 ij 使出行者更远离起点 至少不更靠近起点 路段 ij 就定义为有效路段 具体改进 Dail 算法步骤如下 第 1 步 初始化 找出所有有效路段和有效路径 1 计算各节点到起点 r 的最小阻抗 r i 最短路算法有 Dijkstra 算法 Floyd Warshall 算法和 Moore pape 算法等 其中 Floyd Warshall 算法和 Dijkstra 算法可用于大型网络分析 本文采用 Floyd Warshall 算法 从起点到迄点的最短路阻抗 rs m L 即为 r s 2 从终点出发 判断各个节点上游的有效路段 并计算经该路段的最小阻抗 3 L ij r 0 d i jr i r ir j 其他 6 其中 6 式中 d i j是路段 ij 的实际阻抗 第 2 步 根据本文改进的 logit 模型 计算各有效路段的似然值 L i j exp 0 rs m bL ij rL r ir j 其他 7 第 3 步 逆序计算有效路段的权重 从 s 点开始 按 r i 的下降顺序依次考虑每个节点 j 计算进入节点 j 所有有效路段的权 重 对节点 j 它的权重 W i j为 W i j j m O L i j L i jW j m js 其他 8 其中 j O为离开 j 节点的路段另一个端点的集合 第 4 步 逆序计算有效路段的流量 从终点 s 开始 按 r i 的下降顺序依次考虑每个节点 j 计算所有进入节点 j 的路段流 量 X i j j j j rs m I l O m I W i j q W m j W i j X j l W m j js 其他 9 其中 j I为进入节点 j 的路段另一个端点的集合 4 算例分析算例分析 以下将以如图 1 所示道路网络为例 运用改进的 logit 模型以及相应改进的 Dail 算法对 该道路网络进行多路径分配 其中起点 1 到迄点 9 的 OD 分布量 19 q 为 1000 弧段上方 或左侧数字代表该路段的阻抗 根据文献 1 取参数 b 3 3 图 1 道路网络图 图 2 各节点到起点的最小阻抗 第 1 步 1 计算各节点到起点 r 的最小阻抗 记为 r i 如图 2 所示 4 2 从终点出发 根据条件 r ir j 判断各个节点上游的有效路段 并计算经 该路段的最小阻抗 L i j r 本例中从节点 1 到 9 的 6 条路径均为有效路径 下面以节点 5 示例说明 45 1 4 5 4 224Ldr 25 1 2 5 2 123Ldr 第 2 步 计算各个有效路段的似然值 利用公式 7 如 4 5 L 4 5 exp exp3 3 45 1 60 11080 rs m LbL ij rLL 第 3 步 利用公式 8 逆序计算路段的权重 例如 4 5 4 5 5 6 5 8 0 0006034WLWW 第 4 步 逆向计算路段流量 如 5 8 X 5 8 5 8 8 9 476 5 8 7 8 W XX WW 详细计算结果见表 1 最终分配路段流量见图 3 路段下方或右侧为流量 表 1 计算结果汇总 路段 似然值 权重 路段交通量 12 0 33287 0 00037711 583 14 0 33287 0 000251 417 23 0 11080 0 0000870 134 25 0 19205 0 0010459 449 45 0 11080 0 0006034 259 47 0 11080 0 00015068 158 58 0 11080 0 0040860 476 78 0 03688 0 00136 158 36 0 03688 0 0007848 134 56 0 06393 0 00136 232 69 0 02128 0 02128 366 89 0 03688 0 03688 634 图 3 路段流量分配图 5 5 对对 logit 模型及模型及 dail 算法的思考算法的思考 Logit 本身存在两个缺陷 第一个是 IIA 特性 即它假定各条选择路径是彼此独立的 第二个缺陷是它认为路径的选择概率只由路径之间的阻抗绝对差来决定 后来出现的多路径 Probit 方法能够克服 logit 方法的这些缺陷 但模型复杂 计算工作量大 一般较少采用 许 多学者对 logit 模型进行了改进 改进后的 logit 模型有 Dogit 模型 BCL 模型 BCD 模型 GL 模型 巢式 logit 模型 NL 模型 分裂 logit 模型与广义 logit 模型 另外国内学者对多 路径 logit 分配模型也进行了改进 见文献 1 分析 Dail 算法 发现存在很多缺陷 国内外学者对其进行了改进 使得求解 logit 模型 更加合理而有效 1 Dail 算法要求计算每对 OD 点对间两种最小阻抗 一是正向 一是反向 这对于大 型复杂网络计算量会很大 文献 1 与本文已经对其进行了改进 2 Dail 算法对 有效路径 的定义过于严格 导致分配结果中阻抗较大的路段不被使用 而最短路分配的流量过大 针对 Dail 算法的此缺陷 Bell 提出了两种计算方法 2 第一种近 似方法为近似计算 缺乏理论依据证明计算结果与 logit 模型的定义相符 Bell 的第二种方 法假设网络的权重矩阵的求和序列收敛并通过矩阵求逆来计算 logit 模型 Akamatsu 后来证 明 Bell 这一计算方法和包含所有路径的 logit 模型是等价的 并建立了一个仅包含路段流量 变量的模型 Bell Akamatsu 模型没有排除任何路径 无限循环的回路均包括在计算中 是 一种全路径 logit 分配模型算法 3 4 对于大型的路网 Bell Akamatsu 算法明显不合理 文 献 5 在此基础上 考虑了路网的连通性提出了一种改进的Dail算法来求解全路径 logit模型 并给出了改进的算法和 logit 模型的等价证明 但它没能有效解决有环网络的情况 有待后 续进一步研究 3 在交通分配问题中 路径阻抗与交通流量紧密相关 但多路径 logit 分配方法中的 阻抗不变 这会与实际有一定的误差 特别是拥挤路网 文献 6 对多路径 logit 分配模型进 行了改进 并用逐次分配算法成功实现求解 该方法考虑了阻抗与流量的关系 使分配结果 更加合理 6 结语结语 准确分配 OD 分布量有较大难度 国内外出现了许多关于交通分配的方法 其中 logit 模型以其直观易懂 算法简洁 有较强的可解释性等优点得到广泛应用 而 Dail 算法较好 的实现了 logit 模型的求解 但是该算法在实际应用中仍存在一定缺陷 本文在原有 logit 模 型与国内外学者研究基础上 对 logit 模型进行了改进 并修改了 Dail 算法中关于有效路径 的定义条件 结合算例给出了具体改进 Dail 算法的分配过程 最后本文分析并总结了 logit 模型及 Dail 算法的缺陷 结合参考文献 给出国内外现有研究成果及今后研究方向 6 参考文献参考文献 1 刘灿齐 现代交通规划学 M 北京 人民交通出版社 2001 206 230 2 BELL G H Alternatives to Dail LOGIT as signment algoriyhm J Transportation Research 1995 29B 287 296 3 AKAMATSU T Cyclic flows Markov process and stochastic traffic assignment J Transportation Research 1996 30B 369 386 4 AKAMATSU T Decomposition of path choice entropy in general transport networks J Transportation Science 1997 31 349 362 5 李军 聂佩林 余志 全路径 logit 交通分配模型的求解方法 J 中山大学学报 自然科学版 2004 43 卷 第 5 期 124 126 6 陈义华 何仁斌 王伟 改进的 logit 随机路径选择模型及其算法实现 J 重庆大学学报 2002 25 卷 第 12 期 95 97 Improved multi path distribution logit model and algorithm research Chen Fukun Zhu Yuehe School of Tran