基于模糊蟻群算法的城軌交通網(wǎng)絡(luò)節(jié)點(diǎn)分配優(yōu)化策略

邵東波，楊春林，錢(qián) 平，王 芳

(1．中南大學(xué) 自動(dòng)化學(xué)院，湖南 長(zhǎng)沙410083；2．成都地鐵運(yùn)營(yíng)有限公司 維保分公司，四川 成都610017)

0 引言

伴隨著我國(guó)經(jīng)濟(jì)水平的發(fā)展，城軌交通規(guī)模也呈現(xiàn)指數(shù)型增長(zhǎng)．北上廣深、南京、西安、成都等全國(guó)一線城市的城軌交通網(wǎng)絡(luò)覆蓋范圍越來(lái)越廣，城軌交通網(wǎng)絡(luò)布局和優(yōu)化成為一個(gè)新的研究方向[1]．

城軌交通網(wǎng)絡(luò)是一個(gè)復(fù)雜的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，文獻(xiàn)[2]從網(wǎng)絡(luò)拓?fù)浣３霭l(fā)，研究動(dòng)態(tài)網(wǎng)絡(luò)路由調(diào)度分配策略．文獻(xiàn)[3-4]從網(wǎng)絡(luò)中心性角度出發(fā)，評(píng)估網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)的重要性，識(shí)別網(wǎng)絡(luò)中的核心節(jié)點(diǎn)，從而對(duì)節(jié)點(diǎn)進(jìn)行排序?qū)崿F(xiàn)最優(yōu)分配．此外，文獻(xiàn)[5-6]分別利用K-means聚類(lèi)和模擬退火方法，在復(fù)雜網(wǎng)絡(luò)環(huán)境下確定核心節(jié)點(diǎn)，評(píng)估網(wǎng)絡(luò)的魯棒性．為了最大化網(wǎng)絡(luò)效率和容量，文獻(xiàn)[7-10]分別利用多目標(biāo)調(diào)度與K-最短路徑方法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的屬性進(jìn)行分配．此類(lèi)算法針對(duì)節(jié)點(diǎn)自身屬性進(jìn)行分配，雖然可以取得局部最優(yōu)解，但是無(wú)法最優(yōu)化網(wǎng)絡(luò)配置．

針對(duì)復(fù)雜網(wǎng)絡(luò)優(yōu)化問(wèn)題，文獻(xiàn)[11]提出利用蟻群算法實(shí)現(xiàn)電網(wǎng)的節(jié)點(diǎn)優(yōu)化．而文獻(xiàn)[12-13]將蟻群算法應(yīng)用于列車(chē)調(diào)度和公交網(wǎng)絡(luò)模型優(yōu)化問(wèn)題．文獻(xiàn)[14]進(jìn)一步將蟻群算法與K-最短路徑方法相結(jié)合研究突發(fā)狀況下的路徑選擇問(wèn)題．文獻(xiàn)[15]提出利用BFO細(xì)菌覓食優(yōu)化算法進(jìn)行交通調(diào)度優(yōu)化．雖然上述方法均能在一定程度上實(shí)現(xiàn)多目標(biāo)動(dòng)態(tài)優(yōu)化問(wèn)題，但并未考慮節(jié)點(diǎn)自身屬性，因此可能存在局部節(jié)點(diǎn)輻射能力不足的問(wèn)題．

針對(duì)現(xiàn)有算法無(wú)法兼顧節(jié)點(diǎn)屬性分配和全局網(wǎng)絡(luò)最優(yōu)化匹配的問(wèn)題，為了實(shí)現(xiàn)網(wǎng)絡(luò)多節(jié)點(diǎn)優(yōu)化分配，本文提出利用模糊蟻群算法的城軌交通網(wǎng)絡(luò)節(jié)點(diǎn)分配策略．首先構(gòu)建目標(biāo)函數(shù)，將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為節(jié)點(diǎn)模糊判決與蟻群優(yōu)化兩個(gè)問(wèn)題．并通過(guò)模糊映射對(duì)節(jié)點(diǎn)屬性進(jìn)行模糊判決，最后利用蟻群算法搜索目標(biāo)函數(shù)最優(yōu)解．仿真結(jié)果表明，本文所提算法相對(duì)于現(xiàn)有算法具有更優(yōu)的節(jié)點(diǎn)分配效果，且能夠快速收斂到最優(yōu)解．

1 系統(tǒng)模型

為了滿足城市化需求，城軌交通發(fā)展成為必然趨勢(shì)．據(jù)不完全統(tǒng)計(jì)，中國(guó)城軌交通已批復(fù)總長(zhǎng)度超過(guò)7 000 km．其中，北上廣深和成都等城市建設(shè)條數(shù)均超過(guò)十條，并形成了復(fù)雜的城軌交通網(wǎng)絡(luò)．為了有效提高交通網(wǎng)絡(luò)的效率，需要對(duì)城軌交通進(jìn)行網(wǎng)絡(luò)節(jié)點(diǎn)優(yōu)化分配．

如圖1所示，城軌交通網(wǎng)絡(luò)中的節(jié)點(diǎn)主要分為3類(lèi)，即核心節(jié)點(diǎn)、中間節(jié)點(diǎn)和邊緣節(jié)點(diǎn)．核心節(jié)點(diǎn)是不同線路間的換乘節(jié)點(diǎn)，其選址以及換乘線路的數(shù)量決定整個(gè)交通網(wǎng)絡(luò)的效率．中間節(jié)點(diǎn)是在核心節(jié)點(diǎn)之間的連接節(jié)點(diǎn)，其覆蓋周?chē)髁浚覍?shí)現(xiàn)雙向聯(lián)通．邊緣節(jié)點(diǎn)是每條線路的末端節(jié)點(diǎn)，實(shí)現(xiàn)單向聯(lián)通．

在3類(lèi)節(jié)點(diǎn)中，邊緣節(jié)點(diǎn)是根據(jù)城市發(fā)展規(guī)劃確定，一般處于城市邊緣地區(qū)．而提高城軌交通網(wǎng)絡(luò)效率主要是確定核心節(jié)點(diǎn)的數(shù)量及規(guī)模結(jié)構(gòu)．

如圖2所示，城軌交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)主要分為3類(lèi)，分別為方格式、放射式和環(huán)狀式．拓?fù)浣Y(jié)構(gòu)中的交匯點(diǎn)為不同線路之間的換乘節(jié)點(diǎn)．在城軌交通網(wǎng)絡(luò)中，規(guī)劃和分配網(wǎng)絡(luò)中心節(jié)點(diǎn)，能夠有效提高交通網(wǎng)絡(luò)效率．

圖1 城軌交通網(wǎng)絡(luò)示意圖

圖2 城規(guī)交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

2 優(yōu)化指標(biāo)

城軌交通網(wǎng)絡(luò)規(guī)劃需要綜合考慮各個(gè)因素．從圖3可以看出，城軌交通網(wǎng)絡(luò)規(guī)劃是一個(gè)混合網(wǎng)絡(luò)規(guī)劃問(wèn)題．其既要考慮靜態(tài)網(wǎng)絡(luò)中的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)規(guī)模，同時(shí)又要針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)中的客流特征與分布進(jìn)行規(guī)劃，從而最終確定整個(gè)交通網(wǎng)絡(luò)的承載能力和網(wǎng)絡(luò)效率[16-17]．

城軌交通網(wǎng)絡(luò)要實(shí)現(xiàn)優(yōu)化分配，并提高承載能力和網(wǎng)絡(luò)效率，則需要分為靜態(tài)網(wǎng)絡(luò)評(píng)估與動(dòng)態(tài)網(wǎng)絡(luò)評(píng)估兩部分進(jìn)行評(píng)估．動(dòng)態(tài)網(wǎng)絡(luò)評(píng)估是根據(jù)人流量和周?chē)a(chǎn)業(yè)分布情況等綜合因素來(lái)評(píng)估節(jié)點(diǎn)設(shè)置的需求．而靜態(tài)網(wǎng)絡(luò)評(píng)估指標(biāo)主要分為3大類(lèi)，包含網(wǎng)絡(luò)節(jié)點(diǎn)局部屬性，節(jié)點(diǎn)的全局屬性以及節(jié)點(diǎn)的連通屬性，如圖4所示．

圖3 城軌交通規(guī)劃策略

圖4 靜態(tài)網(wǎng)絡(luò)評(píng)估指標(biāo)

度表示某一節(jié)點(diǎn)的鄰邊數(shù)，即與該節(jié)點(diǎn)連通的節(jié)點(diǎn)數(shù)量．節(jié)點(diǎn)的度表示為：

(1)

式中，ki表示第i個(gè)節(jié)點(diǎn)的度，aij表示交通網(wǎng)絡(luò)鄰接矩陣中第i行j列的參數(shù)，N表示節(jié)點(diǎn)總數(shù)．

特征向量是對(duì)度的補(bǔ)充，即雖然某些節(jié)點(diǎn)的度不高，但其連接節(jié)點(diǎn)可能是一個(gè)具有高度值的核心節(jié)點(diǎn)．此時(shí)，該節(jié)點(diǎn)也相對(duì)較為重要，特征向量定義為：

(2)

式中，λ表示鄰接矩陣的特征值，ej為鄰接矩陣特征向量的第j列．

介數(shù)定義為經(jīng)過(guò)該節(jié)點(diǎn)的最短路徑數(shù)量與網(wǎng)絡(luò)中最短路徑總數(shù)之比，能夠表征節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度：

(3)

式中，σi表示通過(guò)節(jié)點(diǎn)i的最短路徑數(shù)，σij表示節(jié)點(diǎn)i和j之間的最短路徑數(shù)．

接近度定義為節(jié)點(diǎn)到其他節(jié)點(diǎn)最短距離之和的倒數(shù)，表征到其他節(jié)點(diǎn)的難易程度：

(4)

式中，dij表示節(jié)點(diǎn)i和j之間的最短距離．

節(jié)點(diǎn)的局部屬性和全局屬性是評(píng)估節(jié)點(diǎn)設(shè)置合理性的指標(biāo)．對(duì)網(wǎng)絡(luò)進(jìn)行評(píng)估需要使用連通屬性[18]，即評(píng)估網(wǎng)絡(luò)效率與平均路徑長(zhǎng)度．網(wǎng)絡(luò)效率定義為：

(5)

平均路徑長(zhǎng)度定義為：

(6)

動(dòng)態(tài)評(píng)估主要定義節(jié)點(diǎn)輻射容量參數(shù)，即某一節(jié)點(diǎn)對(duì)周邊的輻射能力：

(7)

式中，μ表示調(diào)節(jié)參數(shù)，pi和P分別表示第i個(gè)區(qū)域及核心區(qū)域的人口．wi和W分別表示第i個(gè)區(qū)域與核心區(qū)域的就業(yè)崗位．di表示第i個(gè)區(qū)域到核心區(qū)域的距離．

3 算法架構(gòu)

為了實(shí)現(xiàn)交通網(wǎng)絡(luò)節(jié)點(diǎn)優(yōu)化分配，需要確定最優(yōu)化目標(biāo)．根據(jù)第2節(jié)分析，交通網(wǎng)絡(luò)主要包含靜態(tài)拓?fù)浣Y(jié)構(gòu)和動(dòng)態(tài)輻射容量?jī)蓚€(gè)參數(shù)，并以此確定節(jié)點(diǎn)的選定與分配．

根據(jù)定義，交通網(wǎng)絡(luò)最優(yōu)化時(shí)，網(wǎng)絡(luò)效率和輻射容量均達(dá)到最大值．因此定義函數(shù)：

G=ηE+(1-η)∑Fi

(8)

式中，η表示模糊系數(shù)．則目標(biāo)函數(shù)可以表示為：

max(ηE+(1-η)∑Fi)

s．t． 0≤η≤1

(9)

目標(biāo)函數(shù)是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，無(wú)線性解[19]．因此本文提出基于模糊蟻群算法的交通網(wǎng)絡(luò)節(jié)點(diǎn)優(yōu)化分配方法，其流程框圖如圖5所示．

算法主要分為參數(shù)模糊處理與蟻群搜索兩部分．其中參數(shù)模糊處理主要是針對(duì)各節(jié)點(diǎn)的參數(shù)進(jìn)行處理，并根據(jù)模糊隸屬度函數(shù)計(jì)算生成模糊隸屬度集合，然后再進(jìn)行計(jì)算和綜合判決．節(jié)點(diǎn)參數(shù)模糊化處理流程，如圖6所示．

圖5 模糊蟻群交通節(jié)點(diǎn)優(yōu)化分配算法框圖

圖6 節(jié)點(diǎn)參數(shù)模糊處理流程框圖

首先定義兩個(gè)集合，評(píng)判因素集Q={q1，q2，…，qm}與參數(shù)狀態(tài)集合V={v1，v2，…，vn}．其中，評(píng)判因素主要包括節(jié)點(diǎn)區(qū)域人流量和工作崗位、附近核心區(qū)域的人流量和工作崗位；狀態(tài)集合主要包括，交通節(jié)點(diǎn)v1和非交通節(jié)點(diǎn)v2兩種．

判決因素集和節(jié)點(diǎn)之間的模糊映射可以表示為：

f：Q→Φ(V)

(10)

式中，Φ(V)是集合V的非空模糊集合．常用的模糊映射函數(shù)包括三角函數(shù)，梯形函數(shù)和高斯函數(shù)等[20]．考慮到交通網(wǎng)絡(luò)節(jié)點(diǎn)配置的多維評(píng)價(jià)指標(biāo)，本文使用灰色關(guān)聯(lián)模糊函數(shù)來(lái)計(jì)算模糊隸屬度集合R．

(11)

其中，rm1=1-rm2，rm1和rm2的取值根據(jù)灰色關(guān)聯(lián)理論計(jì)算得出[21]．

定義各評(píng)判因素的權(quán)重集合A，因此模糊判決運(yùn)算可以表示為：

W=A×R=[wy，wn]

(12)

根據(jù)模糊判決矩陣W的元素wy和wn的大小關(guān)系來(lái)確定每一個(gè)區(qū)域是否需要設(shè)立交通節(jié)點(diǎn)．在確定節(jié)點(diǎn)配置之后就可以對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行最優(yōu)化匹配．

假設(shè)螞蟻數(shù)量為N，x→y表示螞蟻可以由x轉(zhuǎn)移到y(tǒng)，則第k只螞蟻隨機(jī)轉(zhuǎn)移概率定義為：

(13)

式中，γxy表示信息能見(jiàn)度，即x和y之間的信息能見(jiàn)度，其是距離的倒數(shù)．τxy表示每條路徑上的信息素，信息素更新公式為：

(14)

根據(jù)轉(zhuǎn)移概率轉(zhuǎn)移螞蟻，并在所有迭代完成后對(duì)方案的目標(biāo)函數(shù)進(jìn)行評(píng)估，得到網(wǎng)絡(luò)節(jié)點(diǎn)的最優(yōu)配置方式以及換乘最優(yōu)路徑．

4 仿真驗(yàn)證及數(shù)據(jù)分析

為了評(píng)估本文所提出算法的有效性．根據(jù)2020年的成都軌道交通數(shù)據(jù)來(lái)配置網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)，其中節(jié)點(diǎn)數(shù)為308個(gè)，線路共計(jì)12條．區(qū)域人口數(shù)據(jù)使用2020年的人口普查結(jié)果．螞蟻個(gè)數(shù)設(shè)置為節(jié)點(diǎn)數(shù)的1．5倍，對(duì)比分析了現(xiàn)有算法與所提算法優(yōu)化的節(jié)點(diǎn)覆蓋能力和網(wǎng)絡(luò)效率．同時(shí)，通過(guò)分析本文所提算法在不同迭代次數(shù)下的網(wǎng)絡(luò)效率與目標(biāo)函數(shù)值，來(lái)驗(yàn)證所提算法運(yùn)行效率．

表1是本文算法與現(xiàn)有算法網(wǎng)絡(luò)節(jié)點(diǎn)分配之后的性能對(duì)比．通過(guò)對(duì)比可以發(fā)現(xiàn)：K-means聚類(lèi)算法在節(jié)點(diǎn)平均度和平均介數(shù)的性能較好，輻射能力也較高，但是網(wǎng)絡(luò)效率較低，說(shuō)明K-means聚類(lèi)算法更適合局部?jī)?yōu)化；BFO算法和蟻群算法性能基本相當(dāng)，整體優(yōu)于模擬退火算法；本文所提算法在輻射能力和網(wǎng)絡(luò)效率均優(yōu)于對(duì)比算法，說(shuō)明其在節(jié)點(diǎn)局部屬性和整體網(wǎng)絡(luò)規(guī)劃上的分配均更優(yōu)．

從表2可以看出，隨著迭代次數(shù)增加，網(wǎng)絡(luò)效率和目標(biāo)函數(shù)均得到提高，且提高幅度逐漸變小直至不變．說(shuō)明算法隨著迭代性能會(huì)逐漸提高但存在上限，其在迭代40次之后，算法性能逐漸收斂，即達(dá)到最優(yōu)解．此外，算法達(dá)到最優(yōu)解的迭代次數(shù)與網(wǎng)絡(luò)規(guī)模大小有關(guān)．

表1 不同算法交通網(wǎng)絡(luò)節(jié)點(diǎn)分配指標(biāo)對(duì)比

表2 不同迭代次數(shù)下模糊蟻群算法性能對(duì)比

5 結(jié)語(yǔ)

針對(duì)現(xiàn)代化城軌交通網(wǎng)絡(luò)優(yōu)化配置的需求，本文提出了基于模糊蟻群算法的交通網(wǎng)絡(luò)節(jié)點(diǎn)分配優(yōu)化策略．不同于現(xiàn)有算法，本文綜合考慮了節(jié)點(diǎn)局部輻射能力和整體網(wǎng)絡(luò)效率，并將目標(biāo)優(yōu)化問(wèn)題分解為節(jié)點(diǎn)覆蓋容量和網(wǎng)絡(luò)效率局部最優(yōu)解問(wèn)題．再分別利用模糊理論對(duì)節(jié)點(diǎn)覆蓋能力進(jìn)行判決排序．在此基礎(chǔ)上，利用蟻群算法進(jìn)行最優(yōu)解搜索，即可實(shí)現(xiàn)最優(yōu)解快速迭代，因此具有一定的工程意義．后續(xù)工作可結(jié)合更多元的模糊判決因素與復(fù)雜的拓?fù)渚W(wǎng)絡(luò)進(jìn)行研究．