模擬退火改進蟻群算法的公交網(wǎng)絡設計

沈顯慶,崔保峰

(黑龍江科技大學 電氣與控制工程學院,哈爾濱 150022)

?

模擬退火改進蟻群算法的公交網(wǎng)絡設計

沈顯慶,崔保峰

(黑龍江科技大學 電氣與控制工程學院,哈爾濱 150022)

針對基本蟻群算法設計公交網(wǎng)絡時,出現(xiàn)過早收斂和易陷入局部尋優(yōu),導致蟻群搜索停滯的問題，提出一種模擬退火改進蟻群算法。通過總運行時間和乘客總換乘次數(shù)構造目標函數(shù)，利用模擬退火算法生成比較優(yōu)秀的初始公交線路集，根據(jù)初始線路集初始化信息素，將模擬退火算法的蒙特卡洛循環(huán)思想加入蟻群的搜索中，對目標函數(shù)進行迭代求解。采用模擬退火算法、基本蟻群算法、改進后的模擬退火蟻群算法對目標函數(shù)進行優(yōu)化對比。結果表明：模擬退火改進蟻群算法比模擬退火算法和蟻群算法的求解效率分別高10.6倍和3.5倍。該算法有效地解決了公交網(wǎng)絡設計問題，優(yōu)化方案可使乘客換乘次數(shù)與乘客總乘車時間大幅縮減。

蟻群算法； 模擬退火算法； 公交網(wǎng)絡； 目標函數(shù)

0　引　言

城市化進程的加快給各大城市交通帶來了巨大的壓力。面對日益嚴重的交通擁堵問題，各大城市先后推進“智慧公交”的建設。城市公交網(wǎng)絡設計是城市公交規(guī)劃的基礎，合理的公交網(wǎng)絡設計直接關系到公眾對乘坐公共交通工具出行的熱情，其對整個公交網(wǎng)絡的運營與調度均至關重要。因此，研究一種能夠快速而精確地解決大規(guī)模公交網(wǎng)絡設計問題的算法具有重要現(xiàn)實意義。

城市公交網(wǎng)絡設計現(xiàn)已被證實是一個NP-Hard問題，需要處理的數(shù)據(jù)量比較大，傳統(tǒng)方法很難求其最優(yōu)解。目前，國內外多采用啟發(fā)式算法進行優(yōu)化求解，白子健等[1]提出了一種適用于禁忌搜索算法的優(yōu)化模型，利用該模型得到了較優(yōu)解。滿英等[2]將模擬退火算法與遺傳算法融合，成功地解決了溫州濱海新區(qū)的規(guī)劃問題。趙毅等[3]在只考慮公交路線設置的情況下，應用遺傳算法對公交線路進行了優(yōu)化。王佳等[4]采用遺傳算法解決了公交網(wǎng)絡層次性規(guī)劃的問題。張輝等[5]采用蜂群算法優(yōu)化貪婪算法產(chǎn)生的初始線路集得到了較優(yōu)解?，F(xiàn)有研究對公交網(wǎng)絡優(yōu)化問題的求解效率往往不是很高，且對大型公交網(wǎng)絡的適用性較差，仍存在很大的提升空間。

筆者根據(jù)城市公交網(wǎng)絡設計中的關鍵點，建立以乘客總乘車時間與乘客總換乘次數(shù)的加權和為目標函數(shù)的模型，通過模擬退火算法生成初始次優(yōu)路線集，按初始路線集更新初始信息素，利用經(jīng)過多項改進的蟻群算法優(yōu)化目標函數(shù)，以期能有效地提高問題的解決效率，使改進后蟻群算法能夠適用于大規(guī)模公交網(wǎng)絡優(yōu)化問題。

1　公交網(wǎng)絡模型的建立

筆者研究的城市公交網(wǎng)絡設計是在給定公交網(wǎng)絡圖、乘客需求矩陣(OD矩陣)及公交線路數(shù)的情況下，利用改進的模擬退火蟻群算法求解最優(yōu)路線的問題。

1.1模型假設

(1)公交在線路上運行時不發(fā)生意外，且線路暢通。

(2)乘客在所研究時間段內對公交的需求保持不變。

(3)公交在任意線路上的運行時間必須大于規(guī)定的最小時間、小于規(guī)定的最大時間。

(4)公交運行線路必須覆蓋全部站點。

(5)公交任意單條線路不能存在重復站點。

1.2模型的建立

為了將公交網(wǎng)絡模型[6-7]設計的較為合理，文中綜合考慮了乘客的總乘車時間和乘客的總換乘次數(shù)，建立二者的加權和模型：

(1)

式中：F——所建立模型的目標函數(shù)，該模型將最優(yōu)路線問題轉化為求取目標函數(shù)的最小值問題；

γ1、γ2——乘客總乘車時間和乘客總換乘次數(shù)的權值，該權值使二者保持在一個數(shù)量級上；

c——總的公交路線數(shù)；

S、P——公交起始站點集與公交終點站集；

Qij——站點i到站點j的乘客需求量；

Tkji——第k條線路上公交從站點i到站點j的運行時間；

Zip——如果公交站點i不能直達公交站點p，則Zip=1，否則Zip=0。

模型約束條件考慮到每個站點的平均停留時間t0，每條線路的公交行駛總時間tk不得低于60 min，不得高于90 min。

2　公交網(wǎng)絡模型的求解

文中將公交網(wǎng)絡設計類比該覓食過程，將起點站類比成蟻群的巢穴，終點站類比成食物源，那么該問題就成了蟻群算法最擅長的問題了。但由于公交網(wǎng)絡相當復雜，且存在公交站點全覆蓋與單條線路無重復站點等約束條件的限制，使采用基本蟻群算法求解時存在如搜索過早停滯等問題，故筆者提出一些改進，用于解決大型公交網(wǎng)絡設計問題。

2.1初始路線集的改進

蟻群算法多采用隨機初始化的方式更新初始信息素，由于隨機初始化的結果往往都比較差，致使蟻群前期容易陷入無用的搜索。前期信息素的匱乏導致蟻群自身搜索速度較慢，進一步降低了蟻群的搜索速度，因此，在此基礎上采用模擬退火算法去生成初始線路集。

模擬退火算法是一種全局搜索算法，它能快速地找到全局次優(yōu)解，進而可以用此次優(yōu)解去更新信息素，不但解決了隨機初始化時導致容易陷入無用搜索的問題，而且也解決了前期信息素匱乏的問題。具體步驟：

Step1設定初始溫度θ、終止溫度θ1與退火速度α。為了快速尋找全局次優(yōu)解，α的值不必太大。隨機產(chǎn)生(c-1)條路線，且任意一條路線無重復站點。

Step2產(chǎn)生第c條路線用來補充前(c-1)條路線遺漏的站點，使c條路線覆蓋全部站點。當溫度下降到終止溫度之前繼續(xù)執(zhí)行。

Step3設置內部蒙特卡洛循環(huán)，隨機更換(c-1)條中的k(1≤k≤c-2 )條，補充第c條線路。

Step4計算更新后的線路目標函數(shù)值，并計算更新前與更新后的目標函數(shù)的差值作為ΔE。如果ΔE≤0,則接受新值；否則如果exp(-ΔE/θ)>rand,則也接受新值，否則舍棄新值。

Step5記錄較優(yōu)秀的路線及目標函數(shù)值供下次蒙特卡洛循環(huán)使用，直至內部循環(huán)結束。

Step6降溫T←αT。

2.2改進蟻群算法優(yōu)化的目標函數(shù)

利用模擬退火算法的快速全局尋優(yōu)產(chǎn)生的次優(yōu)路線集去更新信息素，但是一個新的問題隨之出現(xiàn)，由于信息素的累積速度較快，較優(yōu)秀的路線被重復疊加信息素的概率較大，而較差的路線上的信息素卻在不斷揮發(fā)而越來越小，致使蟻群的搜索容易出現(xiàn)陷入局部最優(yōu)甚至搜索停滯等問題。

筆者借鑒最大-最小蟻群系統(tǒng)[8-10](MMAS)的思想，將信息素限制在(τmin,τmax)內，以解決基本蟻群算法求解公交網(wǎng)絡設計問題時出現(xiàn)的容易陷入局部最優(yōu)問題。與傳統(tǒng)MMAS的思想不同，文中初始化信息素時仍然按模擬退火算法產(chǎn)生的次優(yōu)解集去更新信息素軌跡，而不是全部初始化為τmax，當某條路徑上的信息素小于τmin時，將該路徑上的信息素重新賦值為τmax。

為擴大蟻群搜索范圍保證所求結果為全局最優(yōu)解，在蟻群搜索過程中加入蒙特卡洛循環(huán)，該循環(huán)通過多次隨機更換線路并與之前的線路比較，一方面增加了蟻群搜索的范圍，另一方面保留了更優(yōu)秀的解用來進行信息素的更新。

基本蟻群算法對螞蟻如何選擇下一個路徑一般存在兩種考慮：一是螞蟻有50%的概率選擇信息素濃度最高的可選路徑，有50%的概率按照輪盤賭法選擇下一個路徑；二是螞蟻只按輪盤賭法選擇下一個路徑。針對公交網(wǎng)絡設計問題優(yōu)化了概率選擇，使其更適用于大型公交網(wǎng)絡的設計。改進的蟻群算法具體實現(xiàn)步驟：

Step1n←0(n為循環(huán)次數(shù))，利用模擬退火算法產(chǎn)生的初始次優(yōu)解按照τnew=ρτold+Q/F更新初始信息素，其中，ρ為信息素持久性系數(shù)；τold為信息素初始值，一般設置成相等；Q為信息素總量；F為目標函數(shù)值。每次更新完信息素檢查各站點信息素量，如果信息素量小于τmin則將其置為τmax。

Step2每只螞蟻按更新后的信息素去更新路徑，選擇策略為有35%的概率選擇信息素濃度最大的站點，有65%的概率按輪盤賭法選擇下一個站點。

Step3設置內層循環(huán)，該循環(huán)次數(shù)較少，但每次循環(huán)若產(chǎn)生的路徑比step2產(chǎn)生的路徑優(yōu)秀則替換之前的路徑，直到循環(huán)結束產(chǎn)生更優(yōu)秀的解。

Step4記錄當前最好的路徑和目標函數(shù)值，n←n+1。

Step5當n大于設定的最大迭代次數(shù)時，輸出最優(yōu)解。

3　應用實例

3.1站點需求矩陣

為驗證算法的優(yōu)越性，筆者提供的公交網(wǎng)絡圖，如圖1所示。該公交網(wǎng)絡共由25個站點組成，其中包含三個起始站點S={1,2,3}和五個終點站P={21,22,23,24,25},17個中間站點。其中各站點之間的連線表示各站點的可行路徑，各站點連線上的數(shù)字為公交在站點間的理想行駛時間。

圖1　公交網(wǎng)絡

公交網(wǎng)絡設計中OD需求矩陣也是必需的，表1為圖1所對應的站點需求矩陣。

表1　站點需求矩陣

3.2結果與分析

綜合考慮OD需求矩陣，取公交總線路數(shù)c=6，乘客總乘車時間權重γ1=1.5，乘客總換乘次數(shù)權重γ2=2.5，公交平均每站換乘時間t0=1.5，分別用模擬退火算法、基本蟻群算法和改進后的模擬退火蟻群算法優(yōu)化目標函數(shù)，采用Matlab編程，運行環(huán)境CPU為英特爾酷睿13處理器、內存4 G。

3.2.1模擬退火算法的求解

經(jīng)過多次測試，取初始溫度θ=20 000 ℃，終止溫度θ1=1 ℃，退火速度α=0.95，測試20次得到最優(yōu)目標函數(shù)值曲線，如圖2所示。所對應最優(yōu)線路為{1 6 5 11 10 9 8 16 17 21}、{2 4 1 7 8 16 18 20 17 22}、{3 11 10 9 13 14 15 16 18 19 23}、{2 5 6 11 10 9 8 16 18 19 24}、{3 11 10 9 13 15 19 25}、{3 11 10 12 14 15 19 25}。

圖2　模擬退火算法優(yōu)化過程

Fig.2Optimization process of simulated annealing algorithm

3.2.2基本蟻群算法的求解

初始信息素量Q=200，最大迭代次數(shù)nmax=30(測試時發(fā)現(xiàn)當nmax>30時，蟻群搜索緩慢，并且易出現(xiàn)停滯狀態(tài))，信息素持久系數(shù)ρ=0.85。測試20次得到最優(yōu)目標函數(shù)值曲線,如圖3所示。所對應最優(yōu)線路為{1 6 7 9 13 14 19 18 17 21}、{2 4 1 6 7 8 16 18 17 22}、{3 12 10 9 13 14 15 19 23}、{2 5 6 7 9 13 14 19 24}、{2 5 6 7 9 13 14 19 25}、{3 11 6 7 8 16 18 20 17 22}。

圖3　基本蟻群算法優(yōu)化過程

Fig.3Optimization process of basic ant colony algorithm

3.2.3模擬退火改進蟻群算法的求解

初始溫度θ=20 000 ℃，終止溫度θ1=1 ℃，退火速度α=0.6，初始信息素量Q=200，最大迭代次數(shù)nmax=50，信息素持久系數(shù)ρ=0.85，τmin=0.05，τmin=0.1，測試20次得到最優(yōu)目標函數(shù)值曲線，如圖4所示。所對應最優(yōu)線路為{3 11 6 7 8 16 18 20 17 21}、{3 12 14 13 9 8 16 17 22}、{1 6 11 10 13 15 14 19 23}、{2 5 6 11 10 13 14 19 24}、{3 11 5 6 1 7 8 16 18 19 25}、{2 4 1 6 11 10 13 14 19 24}。

圖4　模擬退火改進的蟻群算法優(yōu)化過程

Fig.4Optimization process of simulated annealing improved ant colony algorithm

3.3算法對比

筆者分別采用模擬退火算法、基本蟻群算法和模擬退火改進的蟻群算法對目標函數(shù)進行了20次優(yōu)化，設平均求解時間為t，對比結果，如表2所示。

表2　不同算法結果對比

從表2可以看出，模擬退火改進的蟻群算法比基本蟻群算法和模擬退火算法在解決公交網(wǎng)絡設計時更優(yōu)秀，具有求解速度快、優(yōu)化結果更加精確的特點。

4　結　論

(1)該研究考慮乘客總乘車時間與乘客總換乘次數(shù),結合OD矩陣建立了公交網(wǎng)絡的模型，通過模擬退火算法產(chǎn)生初始次優(yōu)公交路線集，利用改進的蟻群算法對初始次優(yōu)路線集迭代尋優(yōu)，優(yōu)化目標函數(shù)最終得到最優(yōu)的公交線路集。

(2)與既有研究對比，模擬退火改進的蟻群算法有效地解決了公交網(wǎng)絡設計，優(yōu)化方案可使乘客換乘次數(shù)與乘客總乘車時間大幅縮減，具有很好的適用性。

(3)模擬退火改進的蟻群算法在解決公交網(wǎng)絡設計問題時能找到三種算法的最優(yōu)解，最差解與平均解，均優(yōu)于基本蟻群和模擬退火算法的解，求解效率是模擬退火算法的10.6倍，是基本蟻群算法的3.5倍。

[1]白子健,趙淑芝,田振中.公共交通網(wǎng)絡優(yōu)化的禁忌算法設計與實現(xiàn)[J].吉林大學學報:工學版,2006,36(3):340-344.

[2]滿英,劉三陽,陳小娟.基于改進的模擬退火遺傳算法的公交線網(wǎng)優(yōu)化[J].四川理工學院學報:自然科學版,2008,21(1):1-3.

[3]趙毅,鐘聲.基于遺傳算法的城市公交路線優(yōu)化問題[J].計算機工程與科學,2012,34(9):109-112.

[4]王佳,符卓,杜靖毅.基于遺傳算法的城市公交骨架線網(wǎng)優(yōu)化設計[J].計算機應用研究,2012,29(12):4518-4533.

[5]張輝,趙鵬.基于改進蜂群算法的城市公交網(wǎng)絡設計[J].北京交通大學學報,2015,39(4):118-124.

[6]金孟合,王慧.基于蟻群算法的公交路線走向模型及其求解[J].江南大學學報:自然科學版,2007,6(2):239-242.

[7]張莉,沈文國,安新磊.一種新的多重權重復雜公交網(wǎng)絡模型的研究[J].武漢理工大學學報:交通科學與工程版,2016,40(1):105-109.

[8]姚艷.一種最大最小螞蟻系統(tǒng)的改進算法[J].數(shù)學的實踐與認識,2014,44(5):242-247.

[9]高維,景小榮.基于MMAS的MIMO_OFDM系統(tǒng)上行多用戶檢測[J].重慶郵電大學學報：自然科學版,2015,27(6):745-749.

[10]王晶,王雪峰,王肖杰,等.基于改進型MMAS算法的微電源容量優(yōu)化布址[J].電力系統(tǒng)自動化,2015,39(2):73-80.

(編輯李德根)

Transit network design based on simulated annealing improved ant colony algorithm

SHEN Xianqing,CUI Baofeng

(School of Electrical &Control Engineering,Heilongjiang University of Science &Technology,Harbin 150022,China)

This paper proposes an improved ant colony algorithm based on simulated annealing as an alternative to the basic ant colony algorithm plagued by such drawbacks as premature convergence and vunerability to the local optimization with a resulting stagnation in ant colony search,such as is the case with the basic ant colony algorithm.This algorithm works firstly by constructing the objective function by the total running time and the total number of passengers transfer;then by generating a better initial bus line set using the simulated annealing algorithm;and ultimately by drawing on the initial line set initialization pheromone and applying the Monte Carlo cycle of simulated annealing algorithm to the ant colony search and thereby solving the objective function through loop iteration.The algorithm is validated by optimization and comparison of objective function using the simulated annealing algorithm,basic ant colony algorithm,and the improved ant colony algorithm and simulated annealing.Results show that the improved ant colony algorithm boasts 10.6 and 3.5 times respectively higher than efficiency the simulated annealing algorithm and the ant colony algorithm.The algorithm may provide an effective solution to the bus network design,and the resulting optimization scheme may afford a significant reduction in the passenger transfer times and the total passenger travel time.

ant colony algorithm;simulated annealing;transit network;objective function

2016-04-06

沈顯慶(1969-),男，吉林省通化人，教授，博士，研究方向：伺服系統(tǒng)與智能控制，E-mail:shenxianqing2001@163.com。

10.3969/j.issn.2095-7262.2016.03.019

TP301.6； U491.12

2095-7262(2016)03-0327-05

A