基于遺傳禁忌算法的城市公交線網(wǎng)優(yōu)化研究＊

周 媛 鄧 衛(wèi) 胡啟洲

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

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

1 公交線網(wǎng)優(yōu)化模型的建立

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

1.1 目標函數(shù)

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

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

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

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

1.2 約束條件

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

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

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

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

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

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

1.3 公交線網(wǎng)優(yōu)化模型

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

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

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

2 遺傳禁忌算法基本原理

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

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

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

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

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

步驟6 變異.根據(jù)生物遺傳中的基因變異原理,以概率Pm對個體進行變異運算,即對執(zhí)行變異的串的對應位求反(0變?yōu)?,1變?yōu)?),產(chǎn)生子代群體

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

步驟8 調(diào)用TS搜索過程,對子代群體中的每個個體進行局部搜索,改進群體點的質(zhì)量,若改進后的群體點為 x1,x2,…,xN,其中目標函數(shù)最優(yōu)的即為最終計算結(jié)果.

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

3 公交線網(wǎng)優(yōu)化的遺傳禁忌算法

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

步驟1 優(yōu)化模型的建立.根據(jù)兼顧乘客利益、企業(yè)效益最大以及環(huán)境影響最小的優(yōu)化目標及與該目標密切相關的約束條件建立合適的城市公交線網(wǎng)優(yōu)化模型.

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

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

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

步驟6 若t＞T,轉(zhuǎn)步驟8;否則轉(zhuǎn)步驟7.步驟7 運行優(yōu)化模型

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

步驟8 調(diào)用TS算法,對GA最后一代公交線網(wǎng)中的每個方案進行局部搜索,改進線路質(zhì)量,設改進后的公交線網(wǎng)為 x1,x2,…,xN,其中最優(yōu)方案為x＊.

步驟9 停止運算,輸出結(jié)果x＊為近似最優(yōu)的公交線網(wǎng)優(yōu)化方案.

4 案例分析

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

依據(jù)2015年銀川市中區(qū)全日居民公交出行OD量預測結(jié)果,結(jié)合預測年居民出行方式結(jié)構(gòu)以及城市用地規(guī)劃布局,選取適當?shù)男示庀禂?shù)α1,α2,α3,建立銀川市公交線網(wǎng)優(yōu)化目標函數(shù)

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

5 結(jié)束語

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

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

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

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

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

[4]韓 印.城市公交線網(wǎng)調(diào)整優(yōu)化PSO算法[J].中國公路學報,1999(3)：101-104.

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

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

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

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

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