已知起点需求和部分路段流量的交通OD 反推模型及算法

何胜学

（上海理工大学管理学院，上海200093）

随着各种交通检测技术的发展和交通量检测器的网络布设，获取路网中部分路段交通流量也变得比较容易[1]。出于经济角度的考虑，目前全网范围的检测器布设还不现实[2]。本文希望针对起点交通生成量已知和部分路段流量可测条件下的交通OD 反推展开研究，提升现有研究的针对性和可行性。

交通流分配中OD 量作为输入，直接影响分配结果的有效性[3-4]。但是由于通过交通调查得到OD 量的复杂性和耗时性，利用已有信息对OD 量进行反推逐渐被理论研究者和实践工作者重视。 OD 反推大致分为静态和动态两大类[5]。静态反推研究形成了最大熵模型、最小二乘模型、最大似然模型和贝叶斯模型等。由于这些模型多假设现状OD 矩阵已知， 并通过建立OD 量与路段流量的直接关联关系， 期望推算出未来的OD量，因此现有模型需要的数据调查量仍然很大。 动态OD 反推是目前交通理论研究的一个重点，但是考虑到目前与之对应的动态交通流分配技术的停滞，相关研究的实用性还有待进一步证实。 由于OD 反推与交通流分配结果的密切相关，而实现网络交通流分配的计算复杂性，研究者开始着眼于如何有效利用各种现有交通规划和仿真软件实现OD 反推[5-8]。同时研究者也开始将OD 反推融合于其他相关研究，如路网脆弱性分析和高速公路效益评估[9-10]。 与现有研究相比，本文将考虑已知起点交通生成量，而非现状OD 矩阵，因此前期交通调查的工作量大大降低。 与传统理论利用单层模型简化出行者路线选择行为相比，本文将利用双层规划理论直接将交通流分配作为下层模型，从而提升反推结果的可靠性。

本文的主要研究贡献包括： ① 在起点交通生成量已知和部分路段流量可测条件下建立了OD 反推的优化模型；②基于上层约束的线性单纯性特征，设计了求解上层模型的近似Frank-Wolfe 算法；③利用微分近似处理不可导抽象函数的偏导数和采用Armijo 搜索减少调用求解下层模型的子程序，从而提升了新算法的效率和有效性。

1 参变量介绍与问题

1.1 参变量简介

1.2 问题介绍

2 双层规划模型

根据交通网络均衡状态下得到的路段流量xa（q），∀a∈A 应当与观测得到的路段流量xa，∀a∈A 相等或接近，建立如下的上层规划模型

约束

上述模型的约束（2）表示来自同一起点的交通需求量之和应当等于该起点的交通生成量；约束（3）是交通需求量的非负约束。 目标函数（1）表示在可观测路段集合上，均衡状态下的路段流量与观测路段流量之间的误差应当越小越好。 均衡状态下的xa（q）将在给定q 条件下通过下层的用户均衡模型求得。 与现有的OD 反推模型相比，我们增加了起点交通生成量qr，∀r∈O 已知的约束条件（2）。 该条件的增加将拓展现有OD 反推理论的应用场景，但也使得模型的求解变得更加复杂，下一节将给出一种针对上述模型的有效求解算法。

3 求解算法设计

在上层目标函数（1）中，xa（q）表示可由给定的q 确定对应的路段流量x。xa（q）的实现需要求解下层的用户均衡流量分配模型。 下面给出求解下层模型的经典Frank-Wolfe 算法步骤：

4 算例分析

本节利用Nguyen 和Dupius 路网[12]来对本文提出的模型和算法加以验证。 该路网包含13 个节点，其中节点1 和2 为起点，3 和4 为终点。 相关节点和路段的标号已在图1 中标示。算法的终止参数设定为ε=0.001 和ε′=0.001。 上层模型算法中Armijo 步长搜索的参数设定为σ=0.6，β=0.5 和s=0.5。 设定起点1 和2 的交通生成量分别为1 800 和1 600。 我们将采用常用的BPR 函数ta（xa）=ta0［1＋0.15（xa/Ca）4］作 为 路 段 行 程 时 间 函数。 表1 给出了各路段的自由流行程时间ta0和通行能力Ca。 路网中路段5，7 和13 构成可观测到流量的路段集合。 为了比较验证算法的有效性，我们分三种情景为上述3 条路段假设不同的观测交通流量，具体分情景的观测路段流量见表2。

图1 13 个节点的Nguyen 和Dupius 路网Fig.1 Nguyen and Dupius Network with 13 nodes

利用Java 程序语言实现上节的算法，并在NetBeans IDE 8.0.2 环境下执行。 不同情境下路段均衡流量的计算结果总结在表1；可观测路段的计算交通流量在表2 中列出；最终得到的OD 交通需求量在表3 中给出。利用节点流量守恒条件可判定表1 中路段流量计算结果的合理性。三种情境下算法整体依次执行9，16和11 次后收敛，三种情境下双层模型整体求解的运行时间均小于0.001 s（即计算机显示执行时间为0，小于其可给出的最小时间单位0.001 s）。

表1 路段行程时间函数的参数和均衡流量Tab.1 Coefficients of link travel time functions and the equilibrium flows on links

表2 不同情境下路段流量的观测值和计算值对比Tab.2 Observed and calculated flows on observable links with respect to different scenarios

5 结论

在已知起点交通生成量和部分路段流量可观测条件下，推算起讫点对间的分布交通需求需要考虑出行者路线选择行为的影响。本文利用双层规划模型分别将出行者的路径选择行为和如何利用可观测路段流量构建为数学规划模型，从而实现择路行为满足用户均衡原则条件下路段的分配流量与观测流量间差异的最小化。 考虑到上层模型约束的单纯形特点，为其设计了一个近似Frank-Wolfe 算法。 该近似算法中目标函数对变量的偏导数利用微分定义进行了近似处理。 本研究不仅针对一类特殊的OD 量反推问题给出了对应模型与算法，而且为处理类似问题提供了新的思路方法。