求解MNW隨機用戶均衡問題的改進人工魚群算法

劉寶龍

摘 要：MNW隨機用戶均衡模型解決了Logit模型所有路徑感知方差完全相等的假設，因此在交通分配中具有一定的應用前景。針對這一模型，本文采用了一種定向搜索變異的改進人工魚群算法，該算法在迭代時可以保證魚群在當前狀態下自適應變異的同時還可以向當前的最佳位置移動。隨后在固定需求下的Nguyen & Dupuis中對該算法進行驗證，取得了預期的結果，說明了MNW模型良好的應用價值。同時，針對實驗中存在的不足提出了進一步的研究方向。

關鍵詞：隨機用戶均衡模型;MNW模型;人工魚群算法;交通分配文章編號：2095-2163（2019）04-0125-04 中圖分類號：U491 文獻標志碼：A

0 引 言

交通分配是城市交通規劃過程中的重要問題，1952年，Wardrop[1]提出了著名的用戶均衡（User Equilibrium ， UE）原則，該原則指出出行者總是選擇最短的路線，當不存在某一個出行者可以通過單一地改變自己的路徑選擇而減少行程時間的時候，就達到了用戶均衡狀態。均衡狀態下，所有被出行者選擇的路徑具有相等或者最少的行程時間，未被使用的路徑則具有相等或者更多的行程時間。然而，UE原則假設所有的出行者都是完全理性且相同的，并且完全了解所有路徑的道路情況和行程時間，這種假設在通常情況下是不現實的。實際路網中，出行者通常只掌握路網的部分信息，并且由其選擇自己的路線的過程總是隨機的。1977年，Daganzo等人 [2]提出了隨機用戶均衡（Stochastic User Equilibrium， SUE）原則，放寬了Wardrop用戶均衡中關于用戶完全了解路徑的完美假設，更符合實際的路網情況，因此SUE模型成為時下學界的研究熱點。

SUE原則既考慮了路徑流量對行程時間的影響，也考慮了出行者的感知誤差。而且，其所允許路徑的實際阻抗與出行者的感知阻抗之間存在隨機誤差，這在實際交通分配問題中更為合理。在 SUE 解點，出行者單方面改變路徑不能降低自己的路徑感知阻抗，即達到SUE條件：系統中不再存在司機認為自己能通過單邊改變路徑來降低其阻抗的機會[3]。 SUE 模型路徑阻抗隨機誤差項的分布決定了所使用離散選擇模型的不同。目前常用的主要是Logit型SUE模型（隨機誤差項服從Gumbel分布）。Logit型SUE模型簡單直觀，而且具有較強的可解釋性，因此，在交通分配過程中得到了較為廣泛的應用。

然而，Logit型SUE模型假設所有路徑感知方差完全相等，這在交通分配的研究應用中存在著一定的局限性。為了放松該假設，Castillo等人[4]提出了服從Weibull分布的 Weibit模型、即MNW模型。該模型與Logit模型的主要區別是：Logit模型的效用函數采用加法形式，而MNW模型的負效用函數是乘法形式。在此之后，Kitthamkesorn等人[5]將MNW模型和SUE模型聯系起來，構建了MNW-SUE模型，并給出了相應的數學規劃形式，從而為MNW-SUE模型的求解提供了可能。本文主要研究這種MNW隨機用戶模型及其求解算法。

在求解SUE模型的過程中，學界已陸續推出了很多算法，如全有全無分配法、增量分配法、Dial算法、粒子群算法[6]、蟻群算法[7]、截斷擬牛頓型信賴域法[8]等。為了對MNW-SUE模型進行求解，本文采用定向搜索變異的改進人工魚群算法來展開驗證。對此擬做研究論述如下。

1 MNW隨機用戶均衡模型

1.1 符號及變量定義

1.2 MNW隨機用戶均衡模型

MNW模型采用的效用函數可表示為：

2 算法和算例

2.1 改進人工魚群算法

2.2 算例及結果分析

本文基于Nguyen & Dupuis路網利用改進的人工魚群算法對求解MNW隨機用戶均衡模型的性能進行驗證，如圖1所示。

該路網共有4個OD對，分別為：（1， 2），（1， 3），（4， 2），（4， 3），25條有效路徑和19條路段。在該路網中，每個OD對之間具有固定的交通需求，各OD對之間的交通需求為：（1， 2）：100;（1， 3）：200;（4， 2）：150;（4， 3）：150。路段的基本屬性采用魏秋月[9]設置的路段屬性，如路段容量、路段初始阻抗等相關信息。

路段的行駛時間函數采用美國聯邦公路局提出的費用-流量（BPR）函數，可將其寫作如下數學形式：

從圖2可以看出，改進人工魚群算法具有較快的收斂速度，并且在迭代后期的收斂性趨于穩定。圖3給出了分配結束時各條路段上的流量情況，表明該改進人工魚群算法有能力求解該類型交通分配問題，具有良好的應用價值。同時從圖3可以看出，路段15、18的路段流量超出了路段容量，這是由于算法未考慮路段容量限制造成的，這也為后續研究指明了方向。

3 結束語

本文針對近年來新提出的MNW模型采用定向搜索變異的改進人工魚群算法進行求解，取得了預期的結果，結果表明該算法具有良好的收斂表現和應用價值。同時，由于該算法在應用過程中并未對路段容量進行限制，所以分配結果中有可能會出現流量超出路段容量的情況，這也是下一步的研究重點。

參考文獻

[1]WARDROP J G. Some theoretical aspects of road traffic research [J]. Proceeding of the Institute of Civil Engineers， 1956， 1（2）：57-68.

[2] DAGANZO C F， SHEFFI Y. On stochastic models of traffic assignment [J]. Transportation Science， 1977， 11（3）：253-274.

[3] 黃海軍. 城市交通網絡平衡分析：理論與實踐[M]. 北京：人民交通出版社， 1994.

[4] CASTILLO E， MENENDEZ J M， JIMNEZ P， et al. Closed form expressions for choice probabilities in the Weibull case[J]. Transportation Research Part B：Methodological， 2008，42（4）：373-380.

[5] KITTHAMKESORN S， CHEN A. A path-size weibit stochastic user equilibrium model[J]. Transportation Research Part B：Methodological，2013，57：378-397.

[6] 劉炳全， 孫廣才. 基于Logit分配的交通網絡設計模型的改進粒子群算法[J]. 科學技術與工程， 2008， 8（19）：5446-5450，5456.

[7] 張福龍. 基于最大最小蟻群算法的隨機用戶交通分配模型研究[D]. 西安：長安大學，2016.

[8] 劉建美， 馬帥奇. 關于求解隨機用戶均衡問題的截斷擬牛頓型信賴域法研究[J]. 數學的實踐與認識， 2017，47（10）：184-190.

[9] 魏秋月. 基于蟻群優化的隨機用戶均衡模型研究[D]. 西安：長安大學，2017.

[10]姜山，季業飛. 改進的人工魚群混合算法在交通分配中的應用[J]. 計算機仿真， 2011， 28（6）：326-329.