快速公交線路組合頻率優化的禁忌模擬退火算法仿真

摘要:針對快速公交(BRT)線路組合的頻率優化目標，建立了兼顧公交運營效益和乘客服務要求的BRT運營作業安排數學模型。根據問題的特點，將禁忌算法與模擬退火算法相結合，對BRT線路組合的頻率進行優化。多次仿真運算結果及分析表明，該算法具有比禁忌算法#65380;模擬退火算法都更好的效率，是解決該類問題的一個有效途徑。

關鍵詞:快速公交; 線路組合; 模擬退火算法; 禁忌算法; 優化; 仿真

中圖分類號:TP391文獻標志碼:A

文章編號:1001－3695(2008)02－0355－04

0引言

快速公交系統發車頻率的設計是其日常經營管理的核心內容之一，它決定了運行時刻表#65380;車輛調度以及分配司機等其他的日常調度工作[1~3]。以往國內外的研究多集中于普通的站站停車公交的頻率優化問題。實際上無論在國外還是國內，很多高峰時段高流量的線路上常常采取線路組合的方式，即采取普通線路結合大站快線的發車模式，如巴西的庫里蒂巴#65380;哥倫比亞的波哥達#65380;美國的邁阿密#65380;中國的北京等地。對于這類BRT線路組合發車頻率優化設計，國內外成型的研究成果甚少，文中不再贅述。由于BRT系統所具有的專用車道#65380;交叉口相位優先#65380;車下購票和水平登車等特性[4，5]，大大減少了各種隨機的延誤和干擾，使得采用數學建模仿真手段進行研究的優勢非常明顯，并且有一定的現實指導意義。實際上，BRT系統線路組合的車輛頻率優化問題是一個有約束的組合優化問題，屬于典型的NP問題。筆者針對傳統的數學規劃方法解決這類優化問題效果不甚理想，采用了基于禁忌規則的模擬退火算法[6，7]，給出了算法設計過程和優化計算的仿真結果，并進行了合理的分析論證。

1BRT線路組合頻率優化問題[8，9]

1.1問題描述

BRT站點已定，上下行路線相同#65380;站點不同，車輛沿確定的路線行駛;BRT采用站站停的標準線路和只在客流較大的幾個站點停靠的快速線路的線路組合形式;各站點OD量已知，且乘客均勻到達。BRT標準線路為乘客提供基本的公共交通出行方式，采用每站都停的停靠方式。BRT快速線路上的運營車輛一般速度較快，在客流高峰期運營。考慮在客流高峰期BRT標準線路和快速線路組合的調度方式，進行快速線路停靠站點選擇和兩種線路頻率優化，模型如下:

其中:NVi為第i條線路配置的公交車輛數量;TSi，k為第i條線路第k次車的發車時間;Nk為第i條線路第k次車的發車時間和返回后發第一次車的時間間隔內的發車次數。

2禁忌模擬退火算法設計

2.1編碼及初始解的產生

BRT線路組合優化頻率優化問題的決策變量為快速線路站點集合和標準線路#65380;快速線路的發車頻率。采用0－1編碼表示快速線路站點集合，用自然數編碼表示標準線路#65380;快速線路的發車頻率。編碼長度為N+2。前N個編碼為0－1編碼，依次表示N個標準線路站點中被選為快速線路的情況。編碼為1表示選中該站點作為快速線路站點;否則為0。最后兩個編碼為自然數編碼，表示兩條線路的發車頻率。例如解(0，1，1，0，1，20，18)表示將第2#65380;3#65380;5個標準線路站點選為快速線路站點，標準線路的發車頻率為20次/h，快速線路的發車頻率為18次/h。

首先，在區間[NSmin，NSmax]生成隨機數α1，在N個標準線路站點中隨機挑選α個，并在相應編碼位置賦1，其他位置賦0。分別在區間[F1min，F1min+β]，[F2min，F2min+β]生成隨機數α2#65380;α3，將它們作為標準線路和快速線路初始發車頻率，得到一個完整的初始解。

2.2狀態生成函數

根據BRT線路組合優化的特點，本文為狀態生成函數設計了三種鄰域操作，分別為單點取反#65380;2－swap交換和單點增減操作。

1)單點取反針對解的前N個編碼進行的操作，為單點操作，即選擇解中i點，對該點的值取反。

2)2－swap交換針對解的前N個編碼進行的操作，為雙點操作，選擇解中兩點進行交換，其他位置的值不變。例如解(0，1，1，0，1，10，5)中的2#65380;4點被選中，則2－swap交換后變為(0，0，1，1，1，10，5)。

3)單點增減針對解的最后兩個編碼進行的操作，為單點操作，即對被選點進行增1和減1的操作。

自身取反#65380;2－swap交換是為快速線路進行站點選擇的操作，而單點增減是針對線路發車頻率進行操作的鄰域。每進行一次站點選擇，都要進行發車頻率優化，即多次發車頻率鄰域操作。

2.3禁忌規則及特赦條件

基于禁忌規則的模擬退火算法雖然用狀態生成函數進行全鄰域操作，但是并不是所有鄰域都有機會被抽樣采用作為當前解。算法利用禁忌規則避免迂回搜索的能力，控制抽樣鄰域群體的范圍，實現全局快速尋優。針對不同鄰域設計了相應的兩種禁忌表，即2－swap和單點禁忌表。2－swap禁忌表存儲的是η1個外循環內2－swap交換的逆操作;單點禁忌表存儲的是η2#65380;η3個循環內單點變化鄰域的逆操作(單點取反為η2個外循環;單點增減為η3個內循環)。

特赦條件:如果經過某鄰域操作得到比當前最好解更好的解，那么不管該鄰域是否被禁忌，均采用該鄰域作為當前鄰域。

2.4約束處理

BRT線路組合頻率優化問題包含的約束有快速線路站點數量上下限限制#65380;線路最大發車間隔限制。這些限制在鄰域操作中加以控制。如果當前解經過某鄰域操作，得到的鄰域解不滿足以上約束，則取消此鄰域操作。

2.5退火過程

模擬退火算法的退火過程如下:

2.6抽樣過程

a)令k=0時的當前狀態為s′(0)=s(i)，初始最優解s′=s，q=0。k表示抽樣的次數;q表示連續抽樣而沒有改進狀態的次數。

b)由狀態s通過鄰域操作產生新狀態s′。ΔC′=C(s′)-C(s)。

c)若ΔC′<0，則接受s′作為當前解，并判斷C(s′)>C(s′)。若是，則令s′=s′，q=0;否則q=q+1。若ΔC′>0，首先判斷是否滿足禁忌規則。如果此鄰域為禁忌解，則轉b);否則應用metropolis準則以概率exp(-ΔC′/(bt))接受s′作為下一當前狀態，b為Boltamann常數。若s′被接受，則令s′(k+1)=s′，q=q+1;否則令s′(k+1)=s′(k)。

d)令k=k+1，判斷q>Nc。若是，則繼續;否則，返回b)。

e)將當前最優解s′和當前狀態s′(k)返回到退火過程。

2.7混合算法整體框架

基于禁忌規則的模擬退火算法整體框圖如圖1所示。

3仿真試驗結果及分析

3.1仿真算例

BRT標準線路由25個站點組成，乘客出行OD如表1所示。除了BRT標準線路外，還有其他兩條普通公交線路經過BRT線路的部分站點。經過站點如表2所示。發車頻率分別為14次/h和10次/h。BRT標準線路#65380;普通公交線路#65380;BRT快速線路中車輛站間行駛時間如表3所示。乘客上下車時間均為1 s。BRT車輛由于進/出站減速造成的時間損失均為10 s。BRT標準線路和快速線路票價均為3元，普通公交車輛票價為1.5元。標準線路和快速線路車輛的折舊費用分別為100元/h和30元/h，運營費用分別為600元/次和200元/次，額定座位數分別為200和120個/輛，最小發車頻率分別為8次/h和6次/h，最大滿載率分別為1.2和1.1。快速線路的停車站點數上下限分別為10和6;乘客平均最大等車時間為3.5 min。

3.2仿真結果

運算20次，得到如表4所示的運算結果。其中最優解表示選擇3#65380;4#65380;6#65380;8#65380;9#65380;12#65380;13#65380;15#65380;18#65380;20站點作為BRT快速線路的站點。BRT標準線路的發車頻率為10次/h;BRT快速線路的發車頻率為8次/h。BRT運營公司客流高峰期盈利12 284元/h。

3.3比較試驗

為了體現混合算法的優勢，本文將禁忌算法和模擬退火算法進行相應設計，分別對算例進行20次運算并與混合算法的計算結果進行比較，得到如表4所示的結果。

通過與禁忌算法和模擬退火算法對同一算例運算的比較，本文提出的混合算法在最優解#65380;平均解和波動率幾項指標方面占有明顯的優勢。

3.4仿真結果分析

a)組合線路優化前后，BRT運營公司支出和收益比較如表5所示。

從表5可以看出，由于增加快速線路，減少了BRT公司的支出，增加了收入，BRT公司客流高峰期比之前增加了15.2%。

b)組合線路優化前后標準線路公交車輛滿載率曲線如圖2所示。

從圖2可以看到，增加了快速線路后，改善了調度之前滿載率曲線中間大#65380;兩頭小的現象，提高了標準線路公交車輛的滿載率，節約了資源，節省了運營成本。

4結束語

本文提出了一類基于公交運營效益最大化的BRT線路組合的頻率優化問題，并建立了該問題的數學模型。模型以BRT公司運營效益為目標，兼顧車輛服務水平，同時考慮路線中普通公交對BRT客流量的影響，比較接近實際。文中設計了基于禁忌規則的模擬退火算法對該類BRT頻率優化問題的仿真試驗，并且分別與禁忌算法和模擬算法進行比較，發現它是解決該類問題的一個有效途徑。

參考文獻:

[1]于濱.城市公交系統模型與算法研究[D].大連:大連理工大學，2006.

[2]牛學勤，陳茜，王煒.城市公交線路調度發車頻率優化模型[J].交通運輸工程學報，2003，3(4):68－69.

[3]任傳祥，張海，范躍祖.混合遺傳—模擬退火算法在公交智能調度中的應用[J].系統仿真學報，2005，17(9):2075－2076.

[4]LEVINSON H S， ZIMMERMAN S， CLINGER J. Bus rapid transit: synthesis of case studies[R]. Washington， D C: Transportation Research Record， 2003:1－11.

[5]HERBERT S L， SCOTT R， ERIC B. TCRP report 90: bus rapid transit[R].Washington，D C:Transportation Research Record， 2003.

[6]GLOVER F. Tabu search: part Ⅰ[J]. ORSA Journal on Computing， 1989(1):190－206.

[7]GLOVER F. Tabu search Ⅱ[J]. ORSA Journal on Computing， 1989(2):4－32.

[8]SAKA A A. Model for determing optimum bus－stop spacing in urban areas[J]. Journal of Transportation Engineering， 2001，127(3):195－199.

[9]FURTH P G，RAHBEE A. Optimal bus stop spacing through dynamic programming and geographic modeling[R]. Washington， D C: Transportation Research Record， 2000:15－22.

[10]CHIEN S I， QIN Zhao－qiong. Optimal of bus stop locations for improving transit accessibility[J]. Journal of Transportation Planning and Technology， 2004，27(3):211－227.

[11]白子建，趙淑芝，田振中.公共交通網絡優化的禁忌算法設計與實現[J].吉林大學學報:工學版，2006，36(3):40－44.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”