基于遺傳禁忌算法的城市公交線網優化研究＊

周 媛 鄧 衛 胡啟洲

(西安外事學院工學院1) 西安 710077) (東南大學交通學院2) 南京 210096) (清華大學交通研究所3) 北京 100084)

城市公交線網優化旨在以公交乘客OD分布量為依據,以方便居民出行為目的,并兼顧公交企業效益,尋求使目標函數達到最優的公共交通線網布局方案.而公交線網優化的理論模型是一個多目標非線性規劃問題,其影響因素和約束條件也很多.特別優化模型中目標函數和約束條件的確定以及實際問題規模的大小與其復雜程度呈指數增長關系.對于規模較大,布局復雜多樣的公交線網優化問題,可行方案數較多,傳統的優化算法不易得到滿意的近似解,故筆者將建立合理的、可實施的優化模型,并采用遺傳禁忌搜索算法彌補傳統算法的不足,在所有可行的線路中選取整體最優的線路集.

1 公交線網優化模型的建立

公交線網優化目標可歸結為公共交通效率最大化,而公共交通效率則是在一定的公共交通投入與該投入產生的對人們公共交通需求滿足程度之間的對比關系[1].能夠影響公共交通投入和需求滿足程度的相關因素很多,本文從乘客利益、企業效益及社會環境的角度出發,運用系統科學的思想,確定相應的目標函數,分析相關約束條件,建立公交線網優化模型.

1.1 目標函數

1)乘客總出行時間最短[2]公交線網優化中應首先考慮乘客利益,合理線網應盡量節約乘客出行時間,保證較低的換乘率,提高乘客公交出行的直達率.因此,乘客總出行時間最短是公交線網規劃社會整體效益最顯著的目標.

2)公交運營收益最大[3]公交線網優化過程中,必須適當考慮公交企業的運營收益,使其能獲得較好的收益而提高企業的運營活力.

式中：Vij為從交通區i到交通區j的公交客流量,人?次;Pi為公交車運營票價,分/(km?人?次);Lij為從交通區i到交通區j的公交線長, km;Yh為公交車運營的油耗價值,分/km.

3)公共交通污染物排放最少 設污染物種類組成集合為G,則由公共交通引起的第g種污染物的排放量為

1.2 約束條件

公交線網的優化受到客運交通需求、道路場站及車輛條件、交通效率、交通政策等諸多方面因素限制,其主要約束條件歸納如下.

1)線路長度l 線路長度與城市規模、城市居民的平均乘距大小等有關.線路過長會增加系統的運營費用,過短則不利于運營調度,也增加了乘客的換乘次數.

式中：lmin,lmax分別為線路長度的上、下限,一般取公交線長約束為5 km≤l≤10 km.

2)線路的路段客流量不均勻系數 μ的限定[4]路段不均勻系數是指統計時間內營運線路某路段客流量與平均路段客流量之比值.路段不均勻系數大于1的路段被稱為客流高峰路段,必要時考慮在規定時間內開辟區間車,一般不大于1.5為宜.

3)乘客平均轉換次數η的限制 平均轉換次數指全部乘客的換乘次數總和除以全部乘客人數的商.換乘要增加乘客途中耗費的時間和精力,使之感到不便.一般情況下,整個城市的平均換乘次數應少于1.5.

4)線路非直線系數δ的限制 線路拐彎過多,行駛不便,也易引起車輛的延誤,所以一般情況下線路非直線系數δ＜1.4.

1.3 公交線網優化模型

在對公交線網優化基本原則、主要目標函數以及關鍵約束條件詳細分析的基礎上,本文將建立以尋求乘客出行時間最短、公交企業運營收益最大以及對環境污染最少,即以取得城市公共交通系統效率最大化為總體目標的可持續發展的公交線網優化模型,具體形式表述如下.

式中：α1,α2,α3分別為各分項目標的效率均衡系數,其他符號同前.

此模型旨在給定的關鍵約束條件下,獲取目標函數的最優值,以達到公交線網的優化目標,屬于多條線路的搜索組合優化,是一個典型的多約束0-1規劃問題,這一復雜大規模優化問題必須借助先進的數學方法求解.遺傳禁忌算法(tabu search,TS)是一種通用性和優化性能好的近似搜索算法,非常適于復雜大規模優化問題的求解[5],是解決這個問題的適宜算法.

2 遺傳禁忌算法基本原理

本文提出的GATS混合算法就是先用GA進行全局搜索,使群體中的個體分布于各個最優解附近,再從群體中每個個體開始,用 TS算法進行局部搜索,改善群體的質量,有效結合GA并行的大范圍搜索能力和 TS算法的局部搜索能力,力圖在算法的收斂性能和避免局部極小方面有較大改善.混合策略的計算步驟如下.

步驟1 給定初始參數(包括最大迭代次數T,群體規模N,交叉概率Pc和變異概率Pm).

步驟2 確定編碼方式,令t=0.

步驟4 選擇.根據適者生存原則選擇適應性強的個體為下一代的父本為個體1,…,N)的適應度,其被選擇的概率

步驟5 交叉.對于選中用于繁殖下一代的個體,隨機選擇2個個體的相同位置,按交叉概率Pc在選中位置實行交換.

步驟6 變異.根據生物遺傳中的基因變異原理,以概率Pm對個體進行變異運算,即對執行變異的串的對應位求反(0變為1,1變為0),產生子代群體

步驟7 準則判斷.t＜T,令t=t+1,轉步驟4;否則轉步驟8.

步驟8 調用TS搜索過程,對子代群體中的每個個體進行局部搜索,改進群體點的質量,若改進后的群體點為 x1,x2,…,xN,其中目標函數最優的即為最終計算結果.

步驟9 停止運算,輸出最終計算結果.

3 公交線網優化的遺傳禁忌算法

城市公交線網由多條線路組成,在城市中符合既定約束條件的公交線路很多,在進行線網優化時,可對每一條線可行線路給出布設與不布設兩種選擇,在數學上可以歸結為 0-1規劃問題[6-9].對于規模較大、布局復雜多樣的城市公交線網的優化則構成了大規模復雜函數的優化問題,用傳統計算方法難以得到滿足.采用GATS算法計算公交線網優化的過程如下,令xit代表第t次迭代的第i點,它是l維向量,代表一個線網布局方案.優化目標是尋找最優公交線網布局方案x＊使f(x＊)最小.

步驟1 優化模型的建立.根據兼顧乘客利益、企業效益最大以及環境影響最小的優化目標及與該目標密切相關的約束條件建立合適的城市公交線網優化模型.

步驟2 確定初始參數.公交線網優化模型目標函數值f(x)可用來衡量不同線網方案的優劣,若其被選方案較多則計算量很大,鑒于此,用GATS算法進行公交線網優化時,取最大迭代次數T=10,群體規模N=16,交叉概率變異概率

步驟3 可行線路集的形成和編碼.根據節點性質及線路長度、非直線系數、路段客流量不均勻系數的約束,在整個網絡中選取可行線路納入可行線路集,每條線路在優化線網中有布設和不布設兩種方案,分別用0和1表示,即將公交線網優化轉化為0-1規劃問題.

步驟4 初始化.令t=0,對可行線路集中的每條線路用0或1隨機選取可構成一個初始公交線網,對每個公交線網進行檢查,不合理網絡取其適應值為0或某一固定值,繼而產生 N個相對合理的初始公交線網方案.計算公交線網優化目標函數值.令

步驟6 若t＞T,轉步驟8;否則轉步驟7.步驟7 運行優化模型

1)運用GA進行線網搜索,對初始線網集進行選擇、交叉、變異計算,輸出N個新的公交線網方案

步驟8 調用TS算法,對GA最后一代公交線網中的每個方案進行局部搜索,改進線路質量,設改進后的公交線網為 x1,x2,…,xN,其中最優方案為x＊.

步驟9 停止運算,輸出結果x＊為近似最優的公交線網優化方案.

4 案例分析

銀川市全市總面積9 170.3 km2,建成區面積89.2 km2,中期規劃(2015年)市域戶籍人口160萬,流動人口25萬.公交出行在居民非體力出行中所占比例最高,達17.42%,根據居民出行產生和分布預測,規劃年銀川市中心區公交出行量為125萬人?次.

依據2015年銀川市中區全日居民公交出行OD量預測結果,結合預測年居民出行方式結構以及城市用地規劃布局,選取適當的效率均衡系數α1,α2,α3,建立銀川市公交線網優化目標函數

進行銀川市公交線網優化時,取最大迭代次數T=10,群體規模N=16,交叉概率Pc=0.95,變異概率Pm=0.005,運用GATS算法得到中期公交線網優化方案,由中心城區99條公交線路構成的公交網絡.公交線路總長度為1 456.1 km,有公交服務的城區面積118 km2,純線網密度3.73 km/km2,站點覆蓋率(規劃區內,R=300 m) 76.01%,路線重復系數2.0,乘客直達率26. 12%,線路路段客流量不均勻系數1.46,公交分擔率可達到29%左右,公交出行成本約為0.036元/(人?km).由此結果可知,銀川市公交線網在乘客利益、公交企業效益以及社會效益方面都基本達到了優化目標,取得了令人滿意的效果.

5 結束語

1)利用遺傳禁忌算法對公交線網優化問題的計算方法進行了新的嘗試,有效結合GA并行的大范圍搜索能力和TS的局部搜索能力,在算法的收斂性能和避免局部極小方面有較大改善,為公交線網優化問題的求解提供了合理有效的新方法.

2)以公共交通效率最大化為公交線網優化的目標,選取與該目標密切相關的關鍵約束條件,建立兼顧乘客利益、公交企業效益以及對環境的影響程度的公交線網優化模型.充分考慮到城市公交所涉及的重要方面,所以對進一步發展公共交通系統,改善城市公共交通具有重要的理論意義和實用價值.

[1]吳世江.基于交通效率的城市公共交通路網布局模型[J].土木工程學報,2005(1)：117-119.

[2]胡啟洲,石 琴,張衛華.城市公交線網優化的理想決策方法[J].交通運輸工程學報,2005(5)：87-91.

[3]王 煒.城市交通規劃理論及其應用[M].南京：東南大學出版社,1998.

[4]韓 印.城市公交線網調整優化PSO算法[J].中國公路學報,1999(3)：101-104.

[5]孫艷豐.基于GATS算法的城市土地使用規劃問題研究[J].公路交通科技,2002(4)：122-125.

[6]胡 剛.城市公共交通網絡及站點優化技術研究[D].南京：東南大學交通學院,2003.

[7]王 煒,楊新苗,陳學武.城市公共交通系統規劃方法與管理技術[M].北京：科學出版社,2002.

[8]湯可夫,吳大為.基于改進遺傳算法的公交線網整體優化方法[J].重慶交通學院學報,2004(6)：97-101.

[9]倪 捷,劉志強.基于螞蟻算法的公交網絡優化方法研究[J].交通與計算機,2007(1)：36-39.