求解MNW隨機(jī)用戶均衡問題的改進(jìn)人工魚群算法

劉寶龍

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

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

0 引 言

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

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

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

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

1 MNW隨機(jī)用戶均衡模型

1.1 符號及變量定義

1.2 MNW隨機(jī)用戶均衡模型

MNW模型采用的效用函數(shù)可表示為：

2 算法和算例

2.1 改進(jìn)人工魚群算法

2.2 算例及結(jié)果分析

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)

[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] 黃海軍. 城市交通網(wǎng)絡(luò)平衡分析：理論與實踐[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分配的交通網(wǎng)絡(luò)設(shè)計模型的改進(jìn)粒子群算法[J]. 科學(xué)技術(shù)與工程， 2008， 8（19）：5446-5450，5456.

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

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

[9] 魏秋月. 基于蟻群優(yōu)化的隨機(jī)用戶均衡模型研究[D]. 西安：長安大學(xué)，2017.

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