黃宇達(dá), 魏霞,2, 趙紅專, 王迤冉
(1. 周口職業(yè)技術(shù)學(xué)院 信息工程學(xué)院, 周口 466000; 2. 三峽大學(xué) 理學(xué)院, 宜昌 443002;3. 重慶大學(xué) 自動(dòng)化學(xué)院, 重慶 400044; 4. 周口師范學(xué)院 網(wǎng)絡(luò)工程學(xué)院, 周口 466000)
一種基于通信膜計(jì)算的擁堵道路收費(fèi)模型
黃宇達(dá)1, 魏霞1,2, 趙紅專3, 王迤冉4
(1. 周口職業(yè)技術(shù)學(xué)院 信息工程學(xué)院, 周口 466000; 2. 三峽大學(xué) 理學(xué)院, 宜昌 443002;3. 重慶大學(xué) 自動(dòng)化學(xué)院, 重慶 400044; 4. 周口師范學(xué)院 網(wǎng)絡(luò)工程學(xué)院, 周口 466000)
針對(duì)城市交通擁堵問題,提出了一種利用并行通信膜計(jì)算原理的擁堵道路使用收費(fèi)模型(CMC_ DTAM)。在考慮擁堵收費(fèi)的情況下,建立了出行者的出行決策算法,出行者在交通膜計(jì)算中動(dòng)態(tài)進(jìn)化,外部可以通過調(diào)整收費(fèi)參數(shù)來影響出行者決策,進(jìn)而影響整個(gè)系統(tǒng)進(jìn)化。對(duì)CMC_ DTAM模型進(jìn)行了仿真并將該模型與基于粒子群算法的擁堵收費(fèi)模型(PSO_ DTAM)在同一參數(shù)條件下進(jìn)行了比較,仿真實(shí)驗(yàn)結(jié)果不僅驗(yàn)證了前者的有效性和可行性,而且表明了前者由于考慮了出行者的動(dòng)態(tài)決策,故相對(duì)后者則更為符合客觀真實(shí)情況。
智能運(yùn)輸系統(tǒng)與交通工程; 道路收費(fèi)動(dòng)態(tài)模型; 通信膜計(jì)算; 擁堵道路使用收費(fèi); 出行者決策; 交通選擇算法
中國(guó)近年來小轎車的家庭擁有量快速增長(zhǎng),導(dǎo)致連一些三四線城市的某些路段在上下班高鋒時(shí)也出現(xiàn)交通擁堵[1]。而通過擴(kuò)展道路設(shè)施不但投入大,而且周期長(zhǎng)。因此需要轉(zhuǎn)變思路,尋求其它可能的緩解交通擁擠辦法[2]。如果城市路段在某些時(shí)段出現(xiàn)交通嚴(yán)重?fù)頂D,可以考慮通過擁擠道路使用收費(fèi) (congested road-use pricing)來達(dá)到緩解交通擁擠的目的。擁擠道路使用收費(fèi)是通過對(duì)道路使用者收取一定的費(fèi)用,讓一些不愿意出這些費(fèi)用的出行者改變出行時(shí)間或改變行程[3]。每個(gè)出行者都只會(huì)考慮自己的方便程度,或者考慮自己付出的經(jīng)濟(jì)和時(shí)間成本。當(dāng)?shù)缆吠ㄐ型〞车臅r(shí)候,這些行為不會(huì)影響到其它出行者,但當(dāng)?shù)缆吠ㄐ薪咏虻竭_(dá)極限時(shí),就勢(shì)必會(huì)影響到其它出行者。實(shí)行道路使用收費(fèi)后交通緩解的程度,或者收費(fèi)價(jià)格的多少等問題都需要通過建模來進(jìn)行模擬。
目前,一些不同學(xué)科的學(xué)者從各種角度分析研究了道路擁堵問題,比如Rosenthal[4]從非合作博弈理論分析說明了納什均衡解的存在性對(duì)擁塞的影響;Levinson[5]用非合作博弈理論從微觀層面角度分析城市交通擁堵,研究了發(fā)生交通擁堵的條件和擁堵收費(fèi)是作為一種合作機(jī)制,決定最小化出行總成本;張毅媚等[6]用經(jīng)濟(jì)學(xué)理論和方法研究了城市交通擠塞情況的發(fā)生機(jī)制;許薇等[7]利用博弈論中的“公共地悲劇”理論模型對(duì)汽車擁有量增多與城市路網(wǎng)容量短缺問題進(jìn)行了系統(tǒng)分析,說明了交通擁堵產(chǎn)生的根源;劉志剛等[8]用基于博弈論分析“囚徒困境”問題的方法分析了城市交通擁擠;吳兵等[9]認(rèn)為交通出行是衍生的需求的博弈過程,分別用演化博弈理論分析了動(dòng)態(tài)交通彈性和非彈性出行需求條件;曾鸚等[10]從合作博弈角度對(duì)城市道路擁堵網(wǎng)絡(luò)問題進(jìn)行了分析;何南等[11]分析討論了道路建設(shè)或擴(kuò)大誘增交通流量;趙柴厚等[12]應(yīng)用粒子群優(yōu)化算法和動(dòng)態(tài)交通流分配理論,建立了一種系統(tǒng)動(dòng)態(tài)擁堵收費(fèi)策略的系統(tǒng)算法,但沒有考慮出行者中改變出行路徑的情況,這不符合真實(shí)情況。擁擠道路使用收費(fèi)會(huì)讓一些不急于在上下班高峰期時(shí)段出門的出行者改變出行時(shí)間或者出行者不愿意繳納擁堵費(fèi)而不得不改變經(jīng)過路段。
膜計(jì)算(又稱為P系統(tǒng))是從細(xì)胞及從細(xì)胞組成的組織或器官的結(jié)構(gòu)和功能受到啟發(fā)而抽象出的一種計(jì)算模式,作為如今自然計(jì)算的一個(gè)新分支和較為活躍的智能計(jì)算研究領(lǐng)域之一,其不僅為計(jì)算機(jī)科學(xué)引入了一種新的并行分布式處理技術(shù)和方法,而且為計(jì)算困難問題的求解開辟了新途徑,同時(shí)為生物系統(tǒng)的仿真建模提供了新工具。通信膜計(jì)算是膜計(jì)算在通信相關(guān)領(lǐng)域中的進(jìn)一步應(yīng)用及研究。
本文將從出行者和交通流通量?jī)煞矫婵紤],利用通信膜計(jì)算原理建立擁擠道路收費(fèi)動(dòng)態(tài)演化模型,并進(jìn)行了仿真實(shí)驗(yàn)。仿真結(jié)果與文獻(xiàn)[12]所提出的用粒子群優(yōu)化算法進(jìn)行動(dòng)態(tài)擁堵策略收費(fèi)模型(PSO_DTAM)進(jìn)行了對(duì)比分析,驗(yàn)證了模型的有效性并進(jìn)一步揭示出在不同時(shí)段收費(fèi)和不同路段收費(fèi)時(shí)的交通流量的變化規(guī)律。
1.1 出行者決策選擇算法
出行者決策基于如下思想:出行者會(huì)根據(jù)擁堵收費(fèi)指標(biāo)進(jìn)行決策,這些擁堵收費(fèi)指標(biāo)變量會(huì)帶來正傾向,也會(huì)帶來負(fù)傾向,當(dāng)擁堵收費(fèi)指標(biāo)變量超過某個(gè)臨界值,出行者則會(huì)作出“是”的出行決定,或作出“否”的出行決定?,F(xiàn)在有3個(gè)方面的問題需要解決:
(1) 綜合傾向如何表達(dá)?
(2) 收費(fèi)的臨界值如何選???
(3) 個(gè)體決策的概率如何計(jì)算?
(1)
在公式(1)中,ui是隨機(jī)擾動(dòng)項(xiàng),在本文中指道路擁堵收費(fèi)指標(biāo),式(1)也稱為潛回歸方程,其中
(2)
如果給定ui~F(·)隨機(jī)擾動(dòng)項(xiàng)的分布,那么可以確定出行者的決策概率。推導(dǎo)如式(3)。
(3)
1.2 通信膜計(jì)算
1998年,羅馬尼亞科學(xué)家Gheorghe Paun在芬蘭Turku Center for Computer Science的交流研究報(bào)告中首次提出膜計(jì)算的思想,并于2000年發(fā)表了論文“Computing with membranes”[13]。隨后,在學(xué)術(shù)界引起一部分研究者的興趣。從2003年開始,膜計(jì)算研討會(huì)每年召開一次;膜計(jì)算(membrane computation,MC)具有分布式計(jì)算和并行計(jì)算的特點(diǎn),它是通過模擬生物細(xì)胞的機(jī)理來模擬進(jìn)化,膜計(jì)算具有類似于細(xì)胞膜性質(zhì)的層次結(jié)構(gòu)[14]。膜計(jì)算與其它智能優(yōu)化算法結(jié)合會(huì)得到更好的優(yōu)化效果,例如,黃亮等將基因算法和膜計(jì)算相結(jié)合,在搜索區(qū)域內(nèi)進(jìn)行收縮和擴(kuò)展[15];潘林強(qiáng)等利用了活動(dòng)膜的膜計(jì)算結(jié)構(gòu)求解了0-1背包問題[16];Nishida求解TSP問題時(shí),將問題空間分成一個(gè)個(gè)膜(區(qū)域),在有的區(qū)域內(nèi)使用禁忌搜索算法,有的區(qū)域內(nèi)使用遺傳算法,并與模擬退火算法比較,得到較好的優(yōu)化結(jié)果[17]。
通信膜計(jì)算(Membrane system with symport/antiport rules)應(yīng)用共運(yùn)輸、對(duì)運(yùn)輸規(guī)則,在膜內(nèi)部,對(duì)象不會(huì)生成、改變、消失,只允許對(duì)象在膜之間進(jìn)行轉(zhuǎn)移,膜與膜之間的規(guī)則與膜中的對(duì)象集合相關(guān),決定該線路相連的兩點(diǎn),即規(guī)則與線路相關(guān)聯(lián),抽象到圖型結(jié)構(gòu)則,如圖1所示。
圖1 圖型結(jié)構(gòu)
通信膜計(jì)算是樹型結(jié)構(gòu)[15,18-21]。
基于膜系統(tǒng)的結(jié)構(gòu)[19],通信膜計(jì)算的形式化表示如式(4)。
∏=(O,E,μ,w1,…,wm,(R1,ρ1),…,(Rm,ρm),i0)
(4)
其中,O里面的元素一般稱為對(duì)象,是字符表集合;E?O表示對(duì)象的集合,可以在膜環(huán)境中進(jìn)行無限拷貝;μ表示系統(tǒng)膜結(jié)構(gòu),H為標(biāo)號(hào)集(有m個(gè)膜),表示各個(gè)膜及其所圍的區(qū)域,H={1,2,…,m},其中m稱為Π的度;wi∈O*(1≤i≤m)表示在膜i中對(duì)象的多重集合,O*是字符串的集合,由O中字符組成的任意字符串;i0(1≤i0≤n),是表示在運(yùn)算結(jié)束后的最后留下的那個(gè)輸出膜,為一個(gè)基膜。
用n+1元組(μ,wi,…,wn)來表示膜計(jì)算的初始狀態(tài),通信膜計(jì)算的執(zhí)行方式如下:通信膜計(jì)算內(nèi)部不能產(chǎn)生新對(duì)象,只能從環(huán)境中運(yùn)輸進(jìn)來新的對(duì)象進(jìn)來,這里用符號(hào)集E表示,理論上可以運(yùn)輸無限個(gè)對(duì)象進(jìn)來,也就有可能得到無限大的運(yùn)算結(jié)果;膜計(jì)算的計(jì)算過程是由初始狀態(tài)經(jīng)過的一系列狀態(tài)轉(zhuǎn)換,計(jì)算是否成功的標(biāo)記是沒有規(guī)則可以被使用的狀態(tài),而且,通信膜計(jì)算下不存在膜消散的情況。圖2是一個(gè)包含四個(gè)膜的通信膜計(jì)算示例圖,如圖2所示。
圖2 通信膜計(jì)算
通過該示例對(duì)通信膜計(jì)算過程進(jìn)行具體說明。
在圖2中,1、2 、3、4和5為膜的標(biāo)號(hào),基本膜的含義是不包含其它膜,例如膜4;標(biāo)號(hào)為2的膜結(jié)構(gòu)稱為普通膜;表層膜是表示外面沒有其它膜,是最外層的膜,例如膜5;膜內(nèi)所包含的范圍稱為區(qū)域,區(qū)域內(nèi)有屬于該區(qū)域的對(duì)象,這些對(duì)象規(guī)定了本區(qū)域內(nèi)的進(jìn)化規(guī)則。膜計(jì)算利用區(qū)域中的對(duì)象和對(duì)應(yīng)的進(jìn)化規(guī)定進(jìn)行,計(jì)算過程如下:
(2) 個(gè)體的出行到2的成本由膜1中的催化劑β′來表示,ui代表擁堵收費(fèi),系統(tǒng)的進(jìn)化規(guī)則如下:例如在膜2,規(guī)則b→β′b3在催化劑β的作用下將對(duì)象bi運(yùn)輸?shù)絽^(qū)域3,如果膜3中的對(duì)象集的個(gè)數(shù)等于某個(gè)指定臨界值,或到達(dá)指定的進(jìn)化代數(shù),則計(jì)算停止。
1.3 通信膜計(jì)算交通選擇算法模型(CMC)
通信膜計(jì)算利用膜系統(tǒng)內(nèi)部的信息生成、傳遞以及處理規(guī)則來構(gòu)建交通選擇算法。具體來說,CMC算法迭代步驟如下:
第一步:初始化。隨機(jī)各個(gè)膜(區(qū)域)給定初始化種群,設(shè)定對(duì)象集的大小,最大運(yùn)行代數(shù),變量數(shù)等運(yùn)行參數(shù);
第二步:膜進(jìn)化。給定每個(gè)膜內(nèi)ui內(nèi)的參數(shù)和出行成本的參數(shù),每個(gè)膜同時(shí)進(jìn)化,膜內(nèi)規(guī)則不分先后次序使用;
第三步:各個(gè)膜根據(jù)每個(gè)膜的交流規(guī)則彼此交換它們的一些對(duì)象;
第四步:如果滿足某個(gè)時(shí)間段交換的數(shù)量大于飽和容量ca,算法終止,重新調(diào)整ui的參數(shù),回到第三步。ui參數(shù)是指影響出行者的隨機(jī)擾動(dòng)項(xiàng)(也指擁堵收費(fèi)值),其決定出行者作出“是”或“否”的行為,該參數(shù)動(dòng)態(tài)可調(diào),將影響整個(gè)系統(tǒng)的演化發(fā)展;
第五步:用運(yùn)行預(yù)先指定的進(jìn)化代數(shù)來停止,也可以根據(jù)實(shí)際情況來確定,例如當(dāng)某個(gè)路段或時(shí)段的交通流量值達(dá)到預(yù)先滿意的結(jié)果。
選用有7個(gè)節(jié)點(diǎn),包含3個(gè)起點(diǎn),1個(gè)終點(diǎn),11條路段的一個(gè)小型的路網(wǎng)作為算例,作為算例的路網(wǎng)結(jié)構(gòu),如圖3所示。
圖3 路網(wǎng)結(jié)構(gòu)圖
假定收費(fèi)路段的收費(fèi)上下限分別為:0≤ua≤10,出行時(shí)間采用BPR函數(shù)形式為式(5)。
(5)
式(5)中是路段a上的個(gè)體自由選擇的時(shí)間;ca為路段a的容量;α,β為系數(shù),取值分別為0.15和4。
可以用N來表示路段a上的出行量,采用公式(6)計(jì)算,表示為式(6)。
(6)
在式(6)中,A(p,ca)和B(p,ca)xa是與出行決策概率p和路段a的飽和容量ca相關(guān)的常數(shù)。ui為道路擁堵時(shí)的收費(fèi)值,初始值隨機(jī)給定,路網(wǎng)的基本輸入?yún)?shù)見表1所示。
表1 路網(wǎng)的輸入?yún)?shù)
在系統(tǒng)演化過程中,為了防止過多地將字符串進(jìn)入到同一個(gè)膜(區(qū)域)中,可以限制對(duì)象的最大重復(fù)數(shù)為膜內(nèi)對(duì)象規(guī)模的1/3。經(jīng)過一定時(shí)間進(jìn)化后,計(jì)算得到道路擁堵收費(fèi)ui如表2所示。
為了比較兩種算法模型的優(yōu)缺點(diǎn),這里將基于膜計(jì)算的擁堵收費(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)率下的路徑總流量對(duì)比
其中表3部分?jǐn)?shù)據(jù)引用文獻(xiàn)[12]。從實(shí)驗(yàn)結(jié)果不難發(fā)現(xiàn):在考慮收費(fèi)的情況下,前者對(duì)應(yīng)3種收費(fèi)費(fèi)率情況下的路徑總流量都分別低于后者,當(dāng)然前者所對(duì)應(yīng)的3種收費(fèi)費(fèi)率情況下的車輛平均延誤也都分別低于后者,說明前者由于考慮了出行者決策,則更加符合實(shí)際交通運(yùn)行情況,因?yàn)閷?shí)行收費(fèi)以后有的出行者改變路線或者改變時(shí)間出行,以使得道路交通流量下降,如圖5所示。
本文利用膜計(jì)算建立了一種擁擠道路收費(fèi)模型及其演化算法,選取有7個(gè)節(jié)點(diǎn),包含3個(gè)起點(diǎn),1個(gè)終點(diǎn),11條路段的一個(gè)具有一定代表性的小型路網(wǎng)作為算例,考慮擁堵收費(fèi)后交通流量變化問題,以及路網(wǎng)收費(fèi)高低的問題進(jìn)行建模,通過仿真計(jì)算與同類算法進(jìn)行了比較,驗(yàn)證了這個(gè)用并行通信膜計(jì)算理論建立下的道路擁擠收費(fèi)模型的有效性和可行性。通過與基于粒子群算法的擁堵收費(fèi)模型(PSO_ DTAM)在相同參數(shù)條件下進(jìn)行對(duì)比分析,結(jié)果表明本文建立的模型與實(shí)際交通擁堵情況更為符合。到目前為止,膜計(jì)算在智能控制、NP難題、智能醫(yī)療等領(lǐng)域已有部分應(yīng)用,但還比較初步。膜計(jì)算應(yīng)用于交通擁堵收費(fèi)建模計(jì)算是膜計(jì)算應(yīng)用的一種嘗試,同時(shí)也給一些相關(guān)研究者提供了一種新的思路。膜計(jì)算作為一種相對(duì)較新的優(yōu)化算法,將該智能計(jì)算方法與其它智能算法相結(jié)合,深入探討各種混合膜計(jì)算的優(yōu)化方法,并進(jìn)一步開展在其他相關(guān)領(lǐng)域的應(yīng)用研究,將作為筆者下一步主要研究方向。
圖5 收費(fèi)模型在三種收費(fèi)費(fèi)率下的車輛平均延誤對(duì)比
[1] 熊偉.考慮排放的交通分配模型及其算法研究 [D].武漢:武漢理工大學(xué) ,2008.
[2] 崔紅建.城市交通結(jié)構(gòu)優(yōu)化機(jī)理與方法研究[D]. 西安:長(zhǎng)安大學(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é)報(bào)( 自然科學(xué)版) , 2006, 34( 3) : 359-362.
[7] 許薇,賈元華.城市道路交通擁堵問題的博弈分析[J].交通科技,2006,2: 80-82.
[8] 劉志剛,申金升.城市交通擁堵問題的博弈分析[J].城市交通,2005,2: 63-65.
[9] 吳兵,李林波.交通擁堵的進(jìn)化動(dòng)態(tài)分析[J].中國(guó)公路學(xué)報(bào),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)化的求解城市動(dòng)態(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] 黃亮.膜計(jì)算優(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] 艾淼. 膜計(jì)算模型中若干運(yùn)算的研究及仿真實(shí)現(xiàn)[D]. 哈爾濱:哈爾濱工業(yè)大學(xué),2010.
[19] 張葛祥. 自然計(jì)算的新分支——膜計(jì)算[J]. 計(jì)算機(jī)學(xué)報(bào),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
國(guó)家自然科學(xué)基金(61103143);河南省科技計(jì)劃項(xiàng)目(112300410307)
黃宇達(dá)(1975-),男,河南周口人,碩士,副教授,研究方向:交通信息化,智能計(jì)算,智能算法分析. 魏霞(1978-),女,河南周口人,碩士,講師,研究方向:人工智能與模式識(shí)別. 王迤冉(1976-),男,河南周口人,碩士,副教授,研究方向:人工智能,自動(dòng)化技術(shù). 趙紅專(1985-),廣西桂林人,博士研究生,研究方向:自動(dòng)化技術(shù)及應(yīng)用.
1007-757X(2017)04-0004-05
TP18; U491
A
2016.09.29)