交通地理与网络科学/网络设计问题

网络设计：图论视角

对于给定的图G=(V,E,W)，其中V表示顶点集，E表示每个连接节点或顶点之间边的集合，W表示图中与边相关的权重。网络设计问题通常涉及识别图边的一个子集，该子集满足一组约束条件，并且总权重（或成本）最小。一些网络设计问题的例子包括：

1. 约束最小生成树问题

此问题的目标是在约束度、直径（见w:距离（图论））、节点之间传递给定通信需求的成本的情况下，找到最小生成树。

2. 广义网络设计问题

图被划分为簇或社区，目标是在某些约束条件（如成本、长度等）下，识别一个子图，该子图连接每个簇中恰好或至少一个节点。此类别下著名的一个问题是广义旅行商问题（见w:旅行商问题）。

此类问题本质上是组合问题和NP难问题。通常使用进化算法、分支切割等精确技术或两者的组合来解决这些问题。

道路网络设计

引言

交通规划和管理任务通常涉及通过优化不同的系统性能指标（例如安全、拥堵、可达性等）来确定某些预先指定决策变量的一组最优值，这些指标基于用户的路径选择行为。随着道路交通需求的增长，网络设计问题已成为交通规划人员最关键的任务之一，尤其是在系统容量扩展资源有限的情况下。网络设计问题中的典型决策包括道路定价和最优信号控制。在交通领域，网络设计方面已经做了大量工作。从结构上讲，问题有两种不同的形式：a）离散形式，例如向现有道路系统添加新的连接路段。b）连续形式，例如现有道路的容量扩展。

网络设计问题的类型

• 离散网络设计问题

与网络拓扑相关。例如，添加新的连接路段或关闭连接路段。

• 连续网络设计问题

与网络参数化相关。例如，容量扩展、道路定价、信号配时。

• 混合网络设计问题

与拓扑和参数化都相关。例如，添加新的基础设施和容量扩展、区域定价。

双层框架

双层规划是解决网络设计问题(NDP)的常用技术之一。以下是与交通道路网络中双层框架相关的总体特征。

• 在上层（即系统层）优化整体系统性能函数。
• 在下层（用户层）单个旅行者最小化其实际或感知的出行成本。
• 上层决策只能影响用户行为，但不能控制用户行为。

双层规划的数学公式

$\min \limits _{x\in X}\;\;F(x,y(x))$

约束条件

$G(x,y(x))\leq 0,\;\;$

其中$y(x)$是以下优化问题的解，对于任何固定的$x\in X$

$\min \limits _{y\in Y}\;\;f(x,y)$

约束条件：$g(x,y)\leq 0$

下层用户均衡分配

在上式中，y(x) 是给定任何 x（决策变量向量）时的网络均衡流量（下层响应）。两种最常见的均衡流量形式是确定性用户均衡 (DUE) 和随机用户均衡 (SUE)。

例如，在 DUE 下，当假设链路旅行成本函数 ($t_{a}$) 可分离（例如 BPR 函数）时，下层优化问题，即 y(x) 的解可以写成

$\min \limits _{v}\sum _{a\in A}{\int _{0}^{v_{a}}{t_{a}\left(w,x\right)}dw}$

约束条件

$v_{a}=\sum _{i\in I}\sum _{j\in J}\sum _{r\in P_{ij}}f_{r}^{ij}\delta _{ar}^{ij}$

$\sum _{r\in P_{ij}}f_{r}^{ij}=q_{ij}(x),f_{r}^{ij}\geq 0,r\in P_{ij},i\in I,j\in J$

其中 $v_{a}$ 是链路 $a$ 上的流量，$f_{r}^{ij}$ 是从 $i$ 到 $j$ 路径 $r$ 上的路径流量，而 $\delta$ 是链路-路径关联矩阵。SUE 用户均衡的对应关系也可以在相关文献中找到，。由于 NDP 通常涉及长期投资，因此有必要考虑交通需求的弹性以获得一致的结果。Sheffi 在考虑弹性需求的情况下，对用户均衡分配给出了修改后的解决方案。

上层优化

根据目标的不同，可以制定不同的上层目标函数。

1. 最小化均衡状态下的网络总成本

$\max _{u}F\left(u,v(u)\right)=\sum _{a\in A}t_{a}(u).v_{a}(u)$

约束条件

$\sum _{a\in A}g_{a}(u_{a})\leq B,\;\;\ 0\leq u_{a}\leq u_{a}^{max},\;\;\ a\in A$

其中 $u_{a}$ 表示道路 $a$ 的连续容量提升，而 $g_{a}(u_{a})$ 是建设成本（通常假设为非负、递增且可微）。

2. **最大化预留容量**

这种上层公式可以预测网络在改进后能够承受多少额外需求。最大化预留容量将偏向于边际社会成本更高的道路（即，具有高临界流量/容量比的道路将被选为未来投资对象）。预留容量被评估为 OD 矩阵的乘数，受流量守恒和容量约束的限制。相应的 NDP 公式可以表示为：

$\max _{\mu u}\;\mu$

约束条件

$v_{a}(\mu d,u)\leq C_{a}(u_{a}),\;\ a\in A$

其中 $v_{a}\left(\mu d,u\right)$ 表示当每个 OD 对增加 $\mu$ 倍时，道路 $a\in A$ 上的均衡流量。

3. **最大化具有弹性需求的消费者剩余**

当需求具有弹性时，总出行成本可能不是一个合适的上层目标函数，因为它可能对出行需求产生不良影响。在这种情况下，消费者剩余或净社会效益可以被视为一个有效的目标函数。相应的 NDP 可以表述为：

$\max _{u}\;\ F\left(u,d(u),v(u)\right)=\sum _{w\in W}{\int _{0}^{d_{w}}D_{w}^{-1}(x)dx-c_{w}d_{w}}$

其中 $D_{w}^{-1}$ 是单调递减的需求函数的逆函数，$D_{w}\left(c_{w}\right)$ 是 OD 对 $w$ 的需求函数。

博弈论概念

双层运输问题可以从博弈论的角度来处理。 w:博弈论 模型描述了两个或多个参与者参与其中，并且他们的个人决策相互影响的情况。通常，纳什非合作 和 Stackelberg 博弈反映了网络设计问题的公式化。 纳什非合作 均衡是指当没有玩家可以通过单方面改变其决策来改善其目标时达到的状态。更正式地说，在不失一般性的前提下，如果博弈中有两个玩家参与，每个玩家都旨在最小化其目标函数，$f_{i}\left(x_{1},x_{2}\right)$，其中 $x_{i}$ 是博弈中第 $i^{t}h$ 个玩家的决策变量。那么 $(x_{1}^{*},x_{2}^{*})$ 是纳什均衡解，如果

$f_{1}\left(x_{1},x_{2}^{*}\right)\geq f_{1}\left(x_{1}^{*},x_{2}^{*}\right)$

$f_{1}\left(x_{1}^{*},x_{2}\right)\geq f_{1}\left(x_{1}^{*},x_{2}^{*}\right)$

相反，Stackelberg 博弈有一个领导者，他了解其他玩家（跟随者）对其可能做出的任何决策的反应。例如，在一个两人博弈中，如果玩家 *1* 是领导者，那么玩家 *2*（即跟随者）的反应，$x_{2}=Y\left(x_{1}\right)$，其中 $x_{1}$ 是领导者（玩家 1）做出的决策。 Stackelberg 均衡解可以通过求解以下优化问题来获得

$\min \limits _{x_{1}}f\left(x_{1},Y(x_{1})\right)$，其中

$Y\left(x_{1}\right)$ 是对于任何给定的 $x_{1}$ 下层优化问题的解，即

$\min \limits _{x_{2}}f\left(x_{1},x_{2}\right)$

类似于纳什解，Stackelberg 均衡解，$\left(x_{1}^{*},x_{2}^{*}\right)$ 满足以下不等式

$f_{1}\left(x_{1},Y(x_{1})\right)\geq f_{1}\left(x_{1}^{*},Y(x_{1}^{*})\right)$

$f_{2}\left(x_{1},Y(x_{1})\right)\leq f_{2}\left(x_{1},x_{2}\right)$

从上述两个博弈的表述可以看出，路网中的双层NDP是一个Stackelberg博弈，而在下层，用户在选择个人路线时表现出非合作行为，这满足了Nash非合作博弈的条件。

算法枚举

• 离散NDP

分支定界法

• 连续NDP

迭代优化分配（IOA）算法

基于敏感性分析的算法

• 其他方法

计算智能

遗传算法

模拟退火

基于路段使用比例的算法