交通地理與網路科學/網路設計問題

網路設計：圖論視角

對於給定的圖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）演算法

基於敏感性分析的演算法

• 其他方法

計算智慧

遺傳演算法

模擬退火

基於路段使用比例的演算法