邵東波，楊春林，錢 平，王 芳

(1．中南大學 自動化學院，湖南 長沙410083；2．成都地鐵運營有限公司 維保分公司，四川 成都610017)

0 引言

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

城軌交通網絡是一個復雜的網絡拓撲結構，文獻[2]從網絡拓撲建模出發(fā)，研究動態(tài)網絡路由調度分配策略．文獻[3-4]從網絡中心性角度出發(fā)，評估網絡拓撲中節(jié)點的重要性，識別網絡中的核心節(jié)點，從而對節(jié)點進行排序實現最優(yōu)分配．此外，文獻[5-6]分別利用K-means聚類和模擬退火方法，在復雜網絡環(huán)境下確定核心節(jié)點，評估網絡的魯棒性．為了最大化網絡效率和容量，文獻[7-10]分別利用多目標調度與K-最短路徑方法對網絡節(jié)點的屬性進行分配．此類算法針對節(jié)點自身屬性進行分配，雖然可以取得局部最優(yōu)解，但是無法最優(yōu)化網絡配置．

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

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

1 系統(tǒng)模型

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

如圖1所示，城軌交通網絡中的節(jié)點主要分為3類，即核心節(jié)點、中間節(jié)點和邊緣節(jié)點．核心節(jié)點是不同線路間的換乘節(jié)點，其選址以及換乘線路的數量決定整個交通網絡的效率．中間節(jié)點是在核心節(jié)點之間的連接節(jié)點，其覆蓋周圍流量，且實現雙向聯通．邊緣節(jié)點是每條線路的末端節(jié)點，實現單向聯通．

在3類節(jié)點中，邊緣節(jié)點是根據城市發(fā)展規(guī)劃確定，一般處于城市邊緣地區(qū)．而提高城軌交通網絡效率主要是確定核心節(jié)點的數量及規(guī)模結構．

如圖2所示，城軌交通網絡拓撲結構主要分為3類，分別為方格式、放射式和環(huán)狀式．拓撲結構中的交匯點為不同線路之間的換乘節(jié)點．在城軌交通網絡中，規(guī)劃和分配網絡中心節(jié)點，能夠有效提高交通網絡效率．

圖1 城軌交通網絡示意圖

圖2 城規(guī)交通網絡拓撲結構

2 優(yōu)化指標

城軌交通網絡規(guī)劃需要綜合考慮各個因素．從圖3可以看出，城軌交通網絡規(guī)劃是一個混合網絡規(guī)劃問題．其既要考慮靜態(tài)網絡中的網絡拓撲結構和網絡規(guī)模，同時又要針對動態(tài)網絡中的客流特征與分布進行規(guī)劃，從而最終確定整個交通網絡的承載能力和網絡效率[16-17]．

城軌交通網絡要實現優(yōu)化分配，并提高承載能力和網絡效率，則需要分為靜態(tài)網絡評估與動態(tài)網絡評估兩部分進行評估．動態(tài)網絡評估是根據人流量和周圍產業(yè)分布情況等綜合因素來評估節(jié)點設置的需求．而靜態(tài)網絡評估指標主要分為3大類，包含網絡節(jié)點局部屬性，節(jié)點的全局屬性以及節(jié)點的連通屬性，如圖4所示．

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

圖4 靜態(tài)網絡評估指標

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

(1)

式中，ki表示第i個節(jié)點的度，aij表示交通網絡鄰接矩陣中第i行j列的參數，N表示節(jié)點總數．

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

(2)

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

介數定義為經過該節(jié)點的最短路徑數量與網絡中最短路徑總數之比，能夠表征節(jié)點在網絡中的重要程度：

(3)

式中，σi表示通過節(jié)點i的最短路徑數，σij表示節(jié)點i和j之間的最短路徑數．

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

(4)

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

節(jié)點的局部屬性和全局屬性是評估節(jié)點設置合理性的指標．對網絡進行評估需要使用連通屬性[18]，即評估網絡效率與平均路徑長度．網絡效率定義為：

(5)

平均路徑長度定義為：

(6)

動態(tài)評估主要定義節(jié)點輻射容量參數，即某一節(jié)點對周邊的輻射能力：

(7)

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

3 算法架構

為了實現交通網絡節(jié)點優(yōu)化分配，需要確定最優(yōu)化目標．根據第2節(jié)分析，交通網絡主要包含靜態(tài)拓撲結構和動態(tài)輻射容量兩個參數，并以此確定節(jié)點的選定與分配．

根據定義，交通網絡最優(yōu)化時，網絡效率和輻射容量均達到最大值．因此定義函數：

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

(8)

式中，η表示模糊系數．則目標函數可以表示為：

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

s．t． 0≤η≤1

(9)

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

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

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

圖6 節(jié)點參數模糊處理流程框圖

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

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

f：Q→Φ(V)

(10)

式中，Φ(V)是集合V的非空模糊集合．常用的模糊映射函數包括三角函數，梯形函數和高斯函數等[20]．考慮到交通網絡節(jié)點配置的多維評價指標，本文使用灰色關聯模糊函數來計算模糊隸屬度集合R．

(11)

其中，rm1=1-rm2，rm1和rm2的取值根據灰色關聯理論計算得出[21]．

定義各評判因素的權重集合A，因此模糊判決運算可以表示為：

W=A×R=[wy，wn]

(12)

根據模糊判決矩陣W的元素wy和wn的大小關系來確定每一個區(qū)域是否需要設立交通節(jié)點．在確定節(jié)點配置之后就可以對整個網絡進行最優(yōu)化匹配．

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

(13)

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

(14)

根據轉移概率轉移螞蟻，并在所有迭代完成后對方案的目標函數進行評估，得到網絡節(jié)點的最優(yōu)配置方式以及換乘最優(yōu)路徑．

4 仿真驗證及數據分析

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

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

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

表1 不同算法交通網絡節(jié)點分配指標對比

表2 不同迭代次數下模糊蟻群算法性能對比

5 結語

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