• 动态用户分配

引言#

对于一组具有起讫点（OD）关系的车辆（行程），仿真必须确定通过网络到达目的地的路线（边的列表）。寻找这些路线的最简单方法是使用路由算法（如 Dijkstra 或 A*）计算网络中的最短或最快路线。这些算法需要假设每条网络边的行程时间，而由于行程时间取决于网络中的车辆数量，通常在运行仿真之前并不知道这些时间。

确定考虑交通负载网络中行程时间的合适路线的问题称为用户分配。SUMO 提供了不同的工具来解决此问题，下文将对此进行描述。

迭代分配（动态用户均衡）#

工具 duaIterate.py 可用于计算（近似的）动态用户均衡。

python tools/assign/duaIterate.py -n <网络文件> -t <行程文件> -l <迭代次数>

duaIterate.py 支持许多与 sumo 相同的选项。在调用 duaIterate.py 时未列出的任何选项（通过 --help 查看），都可以通过在常规选项后添加 sumo--长选项名 参数 来传递给 sumo（例如 sumo--step-length 0.5）。对于 duarouter 选项也是如此，使用 duarouter--长选项名 参数。请注意，这些选项必须位于常规选项之后。

此脚本尝试计算用户均衡，即尝试为每辆车（上述行程文件中的每个行程）找到一条路线，使得每辆车无法通过使用不同的路线来降低其出行成本（通常是行程时间）。它是通过迭代来实现的（因此得名）：

1. 调用 duarouter，使用最后已知的边成本（从空网行程时间开始）为车辆路由。
2. 调用 sumo 模拟计算路线得出的“实际”行程时间。结果边成本将用于下一步的网络路由。

迭代次数可以设置为固定值，也可以根据使用的选项动态确定。为了确保收敛，采用了不同的方法来根据路线成本计算路线选择概率（因此车辆并不总是选择“成本最低”的路线）。通常，路由器会在每次迭代中将新路线添加到每辆车的路线集合中（至少在现有路线都不是“成本最低”的情况下），并可能根据下文描述的路线选择机制进行选择。

备选路线选择#

在连续调用 duarouter 之间，使用 .rou.alt.xml 格式记录当前的最佳路线以及先前计算的备选路线。默认情况下，最快的路线被视为最佳，但可以通过选项 --eco-measure 更改此标准，以最小化污染物（例如 CO2）。

通过这种方式，可以在每次迭代中添加一条新的备选路线。备选路线的总数限制为 5，可以通过选项 --max-alternatives 更改此限制。在每次迭代中，会计算每条路线的路线使用概率（见下文）。当某辆车的路线数量超过定义的数量时，概率最小的路线将被移除。

这些最佳路线被收集在路线分布中，并用于决定下一步仿真中实际行驶的路线。这并不总是当前成本最低的路线，而是通过下文描述的可配置算法从备选路线的分布中采样得出的。

路线选择算法#

实现的两种方法分别称为 Gawron 和 Logit。每种方法的输入都是网络边上的权重或成本函数 (w)（来自仿真或默认成本，在第一步或尚未行驶过的边上使用），以及一组路线 ，其中每条路线 都有一个旧成本 和一个旧概率 （来自上一次迭代），并需要一个新的成本 和一个新的概率 。

Gawron（默认）#

Gawron 算法为每个驾驶员计算从一组备选路线中选择的概率。计算这些概率时会考虑以下值：

• 上一步仿真中沿所用路线的行程时间
• 一组备选路线的边行程时间之和
• 上一次选择路线的概率

行程时间更新#

更新规则通过以下示例进行说明。驾驶员 d 在迭代 i 中选择路线 r。行程时间 Tau_d(r, i+1) 是根据迭代 i 中定义间隔（默认：900 秒）内聚合和平均的路段行程时间计算的。驾驶员 d 的路线 r 在迭代 i+1 的行程时间等于 Tau_d(r, i)，如公式 (1) 所示。驾驶员 d 路线集合中其他路线的行程时间则分别使用公式 (2) 更新，其中 Tau_d(s, i) 是在迭代 i 中行驶路线 s 所需的行程时间，并使用与计算 Tau_d(r, i) 和 T_d(s, i-1) 相同的方式计算。参数 beta 用于防止出行者强烈“记住”其路线集合中每条路线的最新行程时间。beta 的当前默认值为 0.3。

T_d(r, i+1) = Tau_d(r, i) ------------------------------------(1)

T_d(s, i+1) = beta * Tau_d(s, i) + (1 - beta) * T_d(s, i-1) ---(2)

其中 s 是驾驶员 d 路线集合中在迭代 i 未被选择使用的路线之一。

上述更新规则也适用于其他出行成本单位。使用模拟路段成本计算路线成本的方法可能会导致成本低估，特别是当某个交通流（例如左转或右转）出现严重拥堵时。现有的工单 #2566 处理此问题。在公式 (1) 中，也可以使用驾驶员 d 在迭代 i 的实际出行成本作为 Tau_d(r, i)。

Logit#

Logit 机制应用一个固定公式来计算每条路线的新概率。它忽略旧成本和旧概率，并直接将路线成本视为上次仿真中边成本的总和。

概率由带有参数 的指数函数计算，并按所有路线值的总和进行缩放：

终止#

DuaIterate 的收敛很难预测，结果即使在 1000 次迭代后也可能继续变化。在这方面有几种策略：

默认#

默认情况下，执行固定次数的迭代，通过 --first-step 和 --last-step（默认 50）配置。

平均行程时间的偏差#

选项 --max-convergence-deviation 可用于检测收敛并自动中止迭代。在每次迭代中，会计算所有行程的平均行程时间。根据这些值的序列（每次迭代一个），计算相对标准差。一旦计算了最小迭代次数（--convergence-iterations，默认 10）且此偏差低于 max-convergence 偏差阈值，迭代将被中止。

强制收敛#

选项 --convergence-steps 可用于通过迭代减少可以改变路线的车辆比例来强制收敛。

• 如果使用正值 x，则保持旧路线的车辆比例设置为 max(0, min(step / x, 1)，这可以防止在步骤 x 之后分配发生变化。
• 如果使用负值 x，则在 |x| 步之后，保持旧路线的车辆比例设置为 1 - 1.0 / (step - |x|)，这会在 |x| 步之后渐近地减少分配。

加速迭代#

目前无法通过并行化来加速 duaIterate.py。然而，duaIterate 的总运行时间受“拥堵”迭代的总运行时间影响很大。这在早期迭代中经常发生，此时许多车辆试图在不考虑容量的情况下选择最快的路线。有几种选项可以缓解此问题：

• 通过逐步增加交通比例，使前几次迭代的交通量较少（--inc-start, --inc-base, --inc-max, --incrementation）
• 在较早的时间中止较早的迭代（--inc-time）
• 通过提供具有合理初始解的需求（例如由 marouter 计算）以及选项 --skip-first-routing
• 通过尝试在运行之间携带更多信息（--weight-memory, --pessimism）

使用示例#

从附加文件加载车辆类型#

默认情况下，车辆类型取自输入行程文件，然后通过 duarouter 迭代传播（始终作为写入的路线文件的一部分）。

为了使用来自 additional-file 的车辆类型定义，必须设置更多选项

duaIterate.py -n ... -t ... -l ...
  --additional-file <包含车辆类型的文件>
  duarouter--aditional-file <包含车辆类型的文件>
  duarouter--vtype-output dummy.xml

以字符串 duarouter-- 开头的选项会直接传递给 duarouter，并且必须使用选项 vtype-output dummy.xml 来防止在生成的输出文件中重复定义车辆类型。

迭代分配（近似系统最优）#

系统最优条件可以通过将路径行程时间替换为路径边际行程时间（MTT）来实现。计算路径 MTT 有两种方法：1）全局近似，表示在特定时间间隔内向路径添加一辆额外车辆所引起的总系统行程时间的变化；2）局部近似，表示在特定时间间隔内向路线添加一辆额外车辆所引起的路径行程时间的变化。duaIterate.py 支持一种方法，其中路径 MTT 被近似为相应路段 MTT 的总和。由于 MTT 的全局近似计算成本高昂且不适用于大规模 DTA，因此该工具实现了 MTT 的局部近似。

鉴于 SUMO 提供了每个路段的平均行程时间，无法直接计算一辆车对路段造成的额外行程时间。计算路段 MTT 的另一种方法是计算连续迭代中的平均行程时间（每次迭代中分配给每个路段的车辆数量不同），并计算路段平均行程时间的差异。使用此方法，可以计算路段上造成的平均额外行程时间。因此，使用 MTT 的替代模型来实现 SO，如下所示：

其中 是仿真步骤 i 时路段 a 的替代 MTT； 和 分别是仿真步骤 i-1 和 i-2 时路段 a 的行程时间（成本）；而 和 分别是仿真步骤 i-1 和 i-2 时路段 a 的交通流量。

可以通过在 duaIterate.py 中设置选项 --marginal-cost, --marginal-cost.exp 来激活动态系统最优交通分配。由于所提出算法中的 MTT 是基于局部近似计算的，可能会导致其被高估。因此，建议使用 MTT 方程的第二项进行校准（选项 --marginal-cost.exp）。 有关 SUMO 中动态系统最优建模的更多信息，请参阅 https://doi.org/10.52825/scp.v3i.119。

迭代分配（混合 DUE 和 SO）#

如果交通由人类驾驶车辆和计算控制车辆混合组成，可以假设前者遵循“利己”路由方法（DUE），而后者可以配置为根据系统最优考虑进行路由。 工具 duaIterateMix.py 可用于计算混合交通流的基于仿真的多类交通分配问题。此问题涉及具有两个车辆类别的动态交通分配问题：一个类别遵循系统最优（SO）原则，而另一个类别遵循用户均衡（UE）原则。目标是实现多类交通分配，使得寻求 UE 的车辆和寻求 SO 的车辆在同一 OD 对之间的行程时间相等且最小化。有关使用 SUMO 解决多类交通分配问题的详细信息，请参阅以下链接：https://doi.org/10.1080/23249935.2023.2257805

oneShot-分配#

上述迭代用户分配的另一种方法是增量分配。当在 sumo 中直接使用 <trip> 输入而不是具有预定义路线的 <vehicle> 时，这种情况会自动发生。在这种情况下，每辆车将在出发时计算最快路径，这可以防止所有车辆盲目驶入同一个拥堵路段，并且在经验上效果相当好（对于较大的场景）。

此增量分配的路线使用 自动路由 / 路由设备 机制计算。还可以启用周期性重新路由，以增加对发展中的拥堵的反应能力。

由于自动重新路由允许各种配置选项，因此可以使用脚本 Tools/Assign#one-shot.py 来自动尝试不同的参数设置。

marouter#

marouter 应用程序计算经典的宏观分配。它采用数学函数（阻力函数）来近似增加流量时行程时间的增加。这允许计算迭代分配，而无需耗时的微观仿真。