基于模糊蟻群算法的城軌交通網絡節點分配優化策略

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

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

0 引言

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

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

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

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

1 系統模型

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

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

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

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

圖1 城軌交通網絡示意圖

圖2 城規交通網絡拓撲結構

2 優化指標

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

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

圖3 城軌交通規劃策略

圖4 靜態網絡評估指標

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

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

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

(5)

平均路徑長度定義為：

(6)

動態評估主要定義節點輻射容量參數，即某一節點對周邊的輻射能力：

(7)

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

3 算法架構

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

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

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

(8)

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

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

s．t． 0≤η≤1

(9)

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

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

圖5 模糊蟻群交通節點優化分配算法框圖

圖6 節點參數模糊處理流程框圖

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

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

f：Q→Φ(V)

(10)

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

(11)

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

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

W=A×R=[wy，wn]

(12)

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

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

(13)

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

(14)

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

4 仿真驗證及數據分析

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

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

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

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

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

5 結語

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