一種基于通信膜計算的擁堵道路收費(fèi)模型

黃宇達(dá)， 魏霞,2， 趙紅專， 王迤冉

(1. 周口職業(yè)技術(shù)學(xué)院 信息工程學(xué)院， 周口 466000； 2. 三峽大學(xué) 理學(xué)院， 宜昌 443002;3. 重慶大學(xué) 自動化學(xué)院， 重慶 400044； 4. 周口師范學(xué)院 網(wǎng)絡(luò)工程學(xué)院， 周口 466000)

一種基于通信膜計算的擁堵道路收費(fèi)模型

黃宇達(dá)1， 魏霞1,2， 趙紅專3， 王迤冉4

(1. 周口職業(yè)技術(shù)學(xué)院 信息工程學(xué)院， 周口 466000； 2. 三峽大學(xué) 理學(xué)院， 宜昌 443002;3. 重慶大學(xué) 自動化學(xué)院， 重慶 400044； 4. 周口師范學(xué)院 網(wǎng)絡(luò)工程學(xué)院， 周口 466000)

針對城市交通擁堵問題，提出了一種利用并行通信膜計算原理的擁堵道路使用收費(fèi)模型(CMC_ DTAM)。在考慮擁堵收費(fèi)的情況下，建立了出行者的出行決策算法，出行者在交通膜計算中動態(tài)進(jìn)化，外部可以通過調(diào)整收費(fèi)參數(shù)來影響出行者決策，進(jìn)而影響整個系統(tǒng)進(jìn)化。對CMC_ DTAM模型進(jìn)行了仿真并將該模型與基于粒子群算法的擁堵收費(fèi)模型(PSO_ DTAM)在同一參數(shù)條件下進(jìn)行了比較，仿真實(shí)驗(yàn)結(jié)果不僅驗(yàn)證了前者的有效性和可行性，而且表明了前者由于考慮了出行者的動態(tài)決策，故相對后者則更為符合客觀真實(shí)情況。

智能運(yùn)輸系統(tǒng)與交通工程； 道路收費(fèi)動態(tài)模型； 通信膜計算； 擁堵道路使用收費(fèi)； 出行者決策； 交通選擇算法

0 引言

中國近年來小轎車的家庭擁有量快速增長，導(dǎo)致連一些三四線城市的某些路段在上下班高鋒時也出現(xiàn)交通擁堵[1]。而通過擴(kuò)展道路設(shè)施不但投入大，而且周期長。因此需要轉(zhuǎn)變思路，尋求其它可能的緩解交通擁擠辦法[2]。如果城市路段在某些時段出現(xiàn)交通嚴(yán)重?fù)頂D，可以考慮通過擁擠道路使用收費(fèi) (congested road-use pricing)來達(dá)到緩解交通擁擠的目的。擁擠道路使用收費(fèi)是通過對道路使用者收取一定的費(fèi)用，讓一些不愿意出這些費(fèi)用的出行者改變出行時間或改變行程[3]。每個出行者都只會考慮自己的方便程度，或者考慮自己付出的經(jīng)濟(jì)和時間成本。當(dāng)?shù)缆吠ㄐ型〞车臅r候，這些行為不會影響到其它出行者，但當(dāng)?shù)缆吠ㄐ薪咏虻竭_(dá)極限時，就勢必會影響到其它出行者。實(shí)行道路使用收費(fèi)后交通緩解的程度，或者收費(fèi)價格的多少等問題都需要通過建模來進(jìn)行模擬。

目前，一些不同學(xué)科的學(xué)者從各種角度分析研究了道路擁堵問題，比如Rosenthal[4]從非合作博弈理論分析說明了納什均衡解的存在性對擁塞的影響；Levinson[5]用非合作博弈理論從微觀層面角度分析城市交通擁堵，研究了發(fā)生交通擁堵的條件和擁堵收費(fèi)是作為一種合作機(jī)制，決定最小化出行總成本；張毅媚等[6]用經(jīng)濟(jì)學(xué)理論和方法研究了城市交通擠塞情況的發(fā)生機(jī)制；許薇等[7]利用博弈論中的“公共地悲劇”理論模型對汽車擁有量增多與城市路網(wǎng)容量短缺問題進(jìn)行了系統(tǒng)分析，說明了交通擁堵產(chǎn)生的根源；劉志剛等[8]用基于博弈論分析“囚徒困境”問題的方法分析了城市交通擁擠；吳兵等[9]認(rèn)為交通出行是衍生的需求的博弈過程，分別用演化博弈理論分析了動態(tài)交通彈性和非彈性出行需求條件；曾鸚等[10]從合作博弈角度對城市道路擁堵網(wǎng)絡(luò)問題進(jìn)行了分析；何南等[11]分析討論了道路建設(shè)或擴(kuò)大誘增交通流量；趙柴厚等[12]應(yīng)用粒子群優(yōu)化算法和動態(tài)交通流分配理論，建立了一種系統(tǒng)動態(tài)擁堵收費(fèi)策略的系統(tǒng)算法，但沒有考慮出行者中改變出行路徑的情況，這不符合真實(shí)情況。擁擠道路使用收費(fèi)會讓一些不急于在上下班高峰期時段出門的出行者改變出行時間或者出行者不愿意繳納擁堵費(fèi)而不得不改變經(jīng)過路段。

膜計算(又稱為P系統(tǒng))是從細(xì)胞及從細(xì)胞組成的組織或器官的結(jié)構(gòu)和功能受到啟發(fā)而抽象出的一種計算模式，作為如今自然計算的一個新分支和較為活躍的智能計算研究領(lǐng)域之一，其不僅為計算機(jī)科學(xué)引入了一種新的并行分布式處理技術(shù)和方法，而且為計算困難問題的求解開辟了新途徑，同時為生物系統(tǒng)的仿真建模提供了新工具。通信膜計算是膜計算在通信相關(guān)領(lǐng)域中的進(jìn)一步應(yīng)用及研究。

本文將從出行者和交通流通量兩方面考慮，利用通信膜計算原理建立擁擠道路收費(fèi)動態(tài)演化模型，并進(jìn)行了仿真實(shí)驗(yàn)。仿真結(jié)果與文獻(xiàn)[12]所提出的用粒子群優(yōu)化算法進(jìn)行動態(tài)擁堵策略收費(fèi)模型(PSO_DTAM)進(jìn)行了對比分析，驗(yàn)證了模型的有效性并進(jìn)一步揭示出在不同時段收費(fèi)和不同路段收費(fèi)時的交通流量的變化規(guī)律。

1 通信膜計算優(yōu)化算法

1.1 出行者決策選擇算法

出行者決策基于如下思想：出行者會根據(jù)擁堵收費(fèi)指標(biāo)進(jìn)行決策，這些擁堵收費(fèi)指標(biāo)變量會帶來正傾向，也會帶來負(fù)傾向，當(dāng)擁堵收費(fèi)指標(biāo)變量超過某個臨界值，出行者則會作出“是”的出行決定，或作出“否”的出行決定。現(xiàn)在有3個方面的問題需要解決：

(1) 綜合傾向如何表達(dá)？

(2) 收費(fèi)的臨界值如何選取？

(3) 個體決策的概率如何計算？

(1)

在公式(1)中，ui是隨機(jī)擾動項，在本文中指道路擁堵收費(fèi)指標(biāo)，式(1)也稱為潛回歸方程，其中

(2)

如果給定ui～F(·)隨機(jī)擾動項的分布，那么可以確定出行者的決策概率。推導(dǎo)如式(3)。

(3)

1.2 通信膜計算

1998年，羅馬尼亞科學(xué)家Gheorghe Paun在芬蘭Turku Center for Computer Science的交流研究報告中首次提出膜計算的思想，并于2000年發(fā)表了論文“Computing with membranes”[13]。隨后，在學(xué)術(shù)界引起一部分研究者的興趣。從2003年開始，膜計算研討會每年召開一次；膜計算(membrane computation，MC)具有分布式計算和并行計算的特點(diǎn)，它是通過模擬生物細(xì)胞的機(jī)理來模擬進(jìn)化，膜計算具有類似于細(xì)胞膜性質(zhì)的層次結(jié)構(gòu)[14]。膜計算與其它智能優(yōu)化算法結(jié)合會得到更好的優(yōu)化效果，例如，黃亮等將基因算法和膜計算相結(jié)合，在搜索區(qū)域內(nèi)進(jìn)行收縮和擴(kuò)展[15]；潘林強(qiáng)等利用了活動膜的膜計算結(jié)構(gòu)求解了0-1背包問題[16]；Nishida求解TSP問題時，將問題空間分成一個個膜(區(qū)域)，在有的區(qū)域內(nèi)使用禁忌搜索算法，有的區(qū)域內(nèi)使用遺傳算法，并與模擬退火算法比較，得到較好的優(yōu)化結(jié)果[17]。

通信膜計算(Membrane system with symport/antiport rules)應(yīng)用共運(yùn)輸、對運(yùn)輸規(guī)則，在膜內(nèi)部，對象不會生成、改變、消失，只允許對象在膜之間進(jìn)行轉(zhuǎn)移，膜與膜之間的規(guī)則與膜中的對象集合相關(guān)，決定該線路相連的兩點(diǎn)，即規(guī)則與線路相關(guān)聯(lián)，抽象到圖型結(jié)構(gòu)則，如圖1所示。

圖1 圖型結(jié)構(gòu)

通信膜計算是樹型結(jié)構(gòu)[15,18-21]。

基于膜系統(tǒng)的結(jié)構(gòu)[19]，通信膜計算的形式化表示如式(4)。

∏=(O,E,μ,w1,…，wm,(R1,ρ1),…,(Rm,ρm),i0)

(4)

其中，O里面的元素一般稱為對象，是字符表集合；E?O表示對象的集合，可以在膜環(huán)境中進(jìn)行無限拷貝；μ表示系統(tǒng)膜結(jié)構(gòu)，H為標(biāo)號集(有m個膜)，表示各個膜及其所圍的區(qū)域，H={1,2,…,m}，其中m稱為Π的度；wi∈O*(1≤i≤m)表示在膜i中對象的多重集合，O*是字符串的集合，由O中字符組成的任意字符串；i0(1≤i0≤n)，是表示在運(yùn)算結(jié)束后的最后留下的那個輸出膜，為一個基膜。

用n+1元組(μ,wi,…,wn)來表示膜計算的初始狀態(tài)，通信膜計算的執(zhí)行方式如下：通信膜計算內(nèi)部不能產(chǎn)生新對象，只能從環(huán)境中運(yùn)輸進(jìn)來新的對象進(jìn)來，這里用符號集E表示，理論上可以運(yùn)輸無限個對象進(jìn)來，也就有可能得到無限大的運(yùn)算結(jié)果；膜計算的計算過程是由初始狀態(tài)經(jīng)過的一系列狀態(tài)轉(zhuǎn)換，計算是否成功的標(biāo)記是沒有規(guī)則可以被使用的狀態(tài)，而且，通信膜計算下不存在膜消散的情況。圖2是一個包含四個膜的通信膜計算示例圖，如圖2所示。

圖2 通信膜計算

通過該示例對通信膜計算過程進(jìn)行具體說明。

在圖2中，1、2 、3、4和5為膜的標(biāo)號，基本膜的含義是不包含其它膜，例如膜4；標(biāo)號為2的膜結(jié)構(gòu)稱為普通膜；表層膜是表示外面沒有其它膜，是最外層的膜，例如膜5；膜內(nèi)所包含的范圍稱為區(qū)域，區(qū)域內(nèi)有屬于該區(qū)域的對象，這些對象規(guī)定了本區(qū)域內(nèi)的進(jìn)化規(guī)則。膜計算利用區(qū)域中的對象和對應(yīng)的進(jìn)化規(guī)定進(jìn)行，計算過程如下：

(2) 個體的出行到2的成本由膜1中的催化劑β′來表示，ui代表擁堵收費(fèi)，系統(tǒng)的進(jìn)化規(guī)則如下：例如在膜2，規(guī)則b→β′b3在催化劑β的作用下將對象bi運(yùn)輸?shù)絽^(qū)域3，如果膜3中的對象集的個數(shù)等于某個指定臨界值，或到達(dá)指定的進(jìn)化代數(shù)，則計算停止。

1.3 通信膜計算交通選擇算法模型(CMC)

通信膜計算利用膜系統(tǒng)內(nèi)部的信息生成、傳遞以及處理規(guī)則來構(gòu)建交通選擇算法。具體來說，CMC算法迭代步驟如下：

第一步：初始化。隨機(jī)各個膜(區(qū)域)給定初始化種群，設(shè)定對象集的大小，最大運(yùn)行代數(shù)，變量數(shù)等運(yùn)行參數(shù)；

第二步：膜進(jìn)化。給定每個膜內(nèi)ui內(nèi)的參數(shù)和出行成本的參數(shù)，每個膜同時進(jìn)化，膜內(nèi)規(guī)則不分先后次序使用；

第三步：各個膜根據(jù)每個膜的交流規(guī)則彼此交換它們的一些對象；

第四步：如果滿足某個時間段交換的數(shù)量大于飽和容量ca，算法終止，重新調(diào)整ui的參數(shù)，回到第三步。ui參數(shù)是指影響出行者的隨機(jī)擾動項(也指擁堵收費(fèi)值)，其決定出行者作出“是”或“否”的行為，該參數(shù)動態(tài)可調(diào)，將影響整個系統(tǒng)的演化發(fā)展；

第五步：用運(yùn)行預(yù)先指定的進(jìn)化代數(shù)來停止，也可以根據(jù)實(shí)際情況來確定，例如當(dāng)某個路段或時段的交通流量值達(dá)到預(yù)先滿意的結(jié)果。

2 數(shù)值算例

選用有7個節(jié)點(diǎn)，包含3個起點(diǎn)，1個終點(diǎn)，11條路段的一個小型的路網(wǎng)作為算例，作為算例的路網(wǎng)結(jié)構(gòu)，如圖3所示。

圖3 路網(wǎng)結(jié)構(gòu)圖

假定收費(fèi)路段的收費(fèi)上下限分別為：0≤ua≤10，出行時間采用BPR函數(shù)形式為式(5)。

(5)

式(5)中是路段a上的個體自由選擇的時間；ca為路段a的容量；α，β為系數(shù)，取值分別為0.15和4。

可以用N來表示路段a上的出行量，采用公式(6)計算，表示為式(6)。

(6)

在式(6)中，A(p,ca)和B(p,ca)xa是與出行決策概率p和路段a的飽和容量ca相關(guān)的常數(shù)。ui為道路擁堵時的收費(fèi)值，初始值隨機(jī)給定，路網(wǎng)的基本輸入?yún)?shù)見表1所示。

表1 路網(wǎng)的輸入?yún)?shù)

在系統(tǒng)演化過程中，為了防止過多地將字符串進(jìn)入到同一個膜(區(qū)域)中，可以限制對象的最大重復(fù)數(shù)為膜內(nèi)對象規(guī)模的1/3。經(jīng)過一定時間進(jìn)化后，計算得到道路擁堵收費(fèi)ui如表2所示。

為了比較兩種算法模型的優(yōu)缺點(diǎn)，這里將基于膜計算的擁堵收費(fèi)模型(CMC_ DTAM)與基于粒子群算法的擁堵收費(fèi)模型(PSO_ DTAM)在同一條件下進(jìn)行比較， 結(jié)果如表3、圖4所示。

表2 道路費(fèi)表

表3 不同的算法模型比較

注：PSO_DTAM數(shù)據(jù)引用文獻(xiàn)[1]

圖4 收費(fèi)模型在三種收費(fèi)費(fèi)率下的路徑總流量對比

其中表3部分?jǐn)?shù)據(jù)引用文獻(xiàn)[12]。從實(shí)驗(yàn)結(jié)果不難發(fā)現(xiàn)：在考慮收費(fèi)的情況下，前者對應(yīng)3種收費(fèi)費(fèi)率情況下的路徑總流量都分別低于后者，當(dāng)然前者所對應(yīng)的3種收費(fèi)費(fèi)率情況下的車輛平均延誤也都分別低于后者，說明前者由于考慮了出行者決策，則更加符合實(shí)際交通運(yùn)行情況，因?yàn)閷?shí)行收費(fèi)以后有的出行者改變路線或者改變時間出行，以使得道路交通流量下降，如圖5所示。

3 總結(jié)

本文利用膜計算建立了一種擁擠道路收費(fèi)模型及其演化算法，選取有7個節(jié)點(diǎn)，包含3個起點(diǎn)，1個終點(diǎn)，11條路段的一個具有一定代表性的小型路網(wǎng)作為算例，考慮擁堵收費(fèi)后交通流量變化問題，以及路網(wǎng)收費(fèi)高低的問題進(jìn)行建模，通過仿真計算與同類算法進(jìn)行了比較，驗(yàn)證了這個用并行通信膜計算理論建立下的道路擁擠收費(fèi)模型的有效性和可行性。通過與基于粒子群算法的擁堵收費(fèi)模型(PSO_ DTAM)在相同參數(shù)條件下進(jìn)行對比分析，結(jié)果表明本文建立的模型與實(shí)際交通擁堵情況更為符合。到目前為止，膜計算在智能控制、NP難題、智能醫(yī)療等領(lǐng)域已有部分應(yīng)用，但還比較初步。膜計算應(yīng)用于交通擁堵收費(fèi)建模計算是膜計算應(yīng)用的一種嘗試，同時也給一些相關(guān)研究者提供了一種新的思路。膜計算作為一種相對較新的優(yōu)化算法，將該智能計算方法與其它智能算法相結(jié)合，深入探討各種混合膜計算的優(yōu)化方法，并進(jìn)一步開展在其他相關(guān)領(lǐng)域的應(yīng)用研究，將作為筆者下一步主要研究方向。

圖5 收費(fèi)模型在三種收費(fèi)費(fèi)率下的車輛平均延誤對比

[1] 熊偉.考慮排放的交通分配模型及其算法研究 [D].武漢：武漢理工大學(xué) ,2008.

[2] 崔紅建.城市交通結(jié)構(gòu)優(yōu)化機(jī)理與方法研究[D]. 西安:長安大學(xué),2010.

[3] 吳艷. 關(guān)于征收道路擁堵費(fèi)的思考[J]. 產(chǎn)業(yè)與科技論壇,2011,10(17):60-63.

[4] Rosenthal R W． A Class of Games Possessing Pure-strategy Nash Equilibria[J]． International Journal of Game Theory，1973，2( 1) : 65-67．

[5] Levinson D． Micro-foundations of congestion and pricing: a game theory perspective[J]． Transportation Research (Part A)，2005，39: 691-704．

[6] 張毅媚，晏克非．城市交通擁擠機(jī)理的經(jīng)濟(jì)解析[J]．同濟(jì)大學(xué)學(xué)報( 自然科學(xué)版) ， 2006， 34( 3) : 359-362．

[7] 許薇，賈元華．城市道路交通擁堵問題的博弈分析[J]．交通科技，2006，2: 80-82．

[8] 劉志剛，申金升．城市交通擁堵問題的博弈分析[J]．城市交通，2005，2: 63-65．

[9] 吳兵，李林波．交通擁堵的進(jìn)化動態(tài)分析[J]．中國公路學(xué)報，2006，19(3): 106-110.

[10] 曾鸚，李軍．合作博弈視角下城市道路交通擁堵收費(fèi)研究[J]. 運(yùn)籌與管理. 2013,22(1):9-14.

[11] 何南，趙勝川．道路誘增交通量及其相關(guān)交通政策的解決方法[J].交通科技. 2013,257(2) :143-146.

[12] 趙柴厚，劉偉銘．基于粒子群優(yōu)化的求解城市動態(tài)擁堵收費(fèi)費(fèi)率策略的模擬算法[J].科學(xué)技術(shù)與工程，2008,8 (10).

[13] Gh. Paun. Computing with Membranes [J].Journal of Computer and System Sciences，2000, 1(61):108-143.

[14] Huang L,He X X,Wang N. Membrane Systems Based on Multi-objective optimization algorithm[J]. Progress in Natural Science，2007，17(4):458-465

[15] 黃亮.膜計算優(yōu)化方法研究[D]. 杭州:浙江大學(xué),2007.

[16] Pan L, C. Martin. Solving Multidimensional 0-1 knapsaek Problem by Systems with Input and Active Membranes[J]. Journal of Parallel and Distributed Computing，2005，65(12):1578-1584

[17] Nishida T Y. An Application of Membrane system: A new Algorithm for NP-complete Optimization Problems[A]∥Proceeding of 8th world Multi- conference on Systems[C]. Orlando: Cybernetics and Informatics， 2004:18-21.

[18] 艾淼. 膜計算模型中若干運(yùn)算的研究及仿真實(shí)現(xiàn)[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2010.

[19] 張葛祥. 自然計算的新分支——膜計算[J]. 計算機(jī)學(xué)報,2010.33(2):208-214.

[20] Paun A， Paun G. The Power of Communication: Membrane Systems with Symport/Antipart[J]. New Generation Computing, 2002, 20(3):295-305.

[21] Gexiang Zhang, Marian Gheorghe, Chaozhong Wu. A Quantum-Inspired Evolutionary Algorithm Based on Membrane Systems for Knapsack Problem [J]. Fundamentals Informatics.2008, 87(l):93-116.

Pricing Model for Congestion Road Based on Membrane Computing

Huang Yuda1, Wei Xia1,2, Zhao Hongzhuan3, Wang Yiran4

(1. Information and Engineering College， Zhoukou Vocational and Technical College，ZhouKou 466000， China；2. College of Science, China Three Gorges University, Yichang 443002， China;3. ChongQing University，College of Automation，ChongQing 400044， China；4. College of Network Engineering， Zhoukou Normal University， ZhouKou 466001， China)

For urban traffic congestion problem, a congested road-use pricing model based on the theory of parallel communication membrane computing is proposed. Considering congestion charges, the travel decision algorithm of travelers is established, travelers dynamic evolution is given in traffic membrane system, In the outside, the charging parameters can be adjusted so as to influence the decision of the traveler, and then affect the whole system evolution. The CMC_ DTAM model is simulated, and is compared with the congestion pricing model based on the particle swarm algorithm (PSO_ DTAM) in the same parameters, the simulation results not only verify the validity and feasibility of the former, but also show because the former considers the dynamic decision of the traveller, it is more consistent with the objective reality.

Intelligent transportation system and traffic engineering; Dynamic model of road charge; Communication membrane computing; Congested road use charging; Traveler decision-making; Traffic selection algorithm

國家自然科學(xué)基金(61103143)；河南省科技計劃項目(112300410307)

黃宇達(dá)(1975-)，男，河南周口人，碩士，副教授，研究方向：交通信息化，智能計算，智能算法分析. 魏霞(1978-)，女，河南周口人，碩士，講師，研究方向：人工智能與模式識別. 王迤冉(1976-)，男，河南周口人，碩士，副教授，研究方向：人工智能，自動化技術(shù). 趙紅專(1985-)，廣西桂林人，博士研究生，研究方向：自動化技術(shù)及應(yīng)用.

1007-757X(2017)04-0004-05

TP18； U491

A

2016.09.29)