基于遺傳蟻群混合算法的公交線網(wǎng)優(yōu)化模型

1、基于遺傳蟻群混合算法的公交線網(wǎng)優(yōu)化模型摘要：隨著城市經(jīng)濟不斷開展，城市交通問題日趨嚴重，公共交通成為解決城市交通供需矛盾的重要手段。文章提出了以社會總出行時間最小、污染排放量最低、乘客直達率最大、線網(wǎng)日均滿載率最大、公交企業(yè)年收益率最大以及線網(wǎng)效率最大為優(yōu)化目標的多目標城市公交網(wǎng)絡優(yōu)化模型，并運用遺傳蟻群混合算法對模型進展計算，大大降低了模型的求解時間。關鍵詞：公共交通；公交線網(wǎng)；多目標優(yōu)化；遺傳蟻群算法自二十世紀以來，國內(nèi)外很多學者都積極的投入到公交網(wǎng)線優(yōu)化的研究當中。公交網(wǎng)線優(yōu)化是一個多目標優(yōu)化問題，即在滿足優(yōu)化限制的空間解內(nèi)，尋找到公交網(wǎng)線優(yōu)化選擇中提出的目標函數(shù)都滿意的優(yōu)化解。具體的說

2、是在研究乘客流動規(guī)律之后，把公交車輛組織在規(guī)定的路線上，按照客流的數(shù)量、方向和時間制定有節(jié)奏的、周而復始的行車方案，以得到最正確的經(jīng)濟效益和社會效益。本文采用建立數(shù)學模型的方法來解決這個組合優(yōu)化問題。一、公交網(wǎng)線優(yōu)化的目標函數(shù)一社會總出行時間最短f1=Mt1+屹t2+23t3+設4+汨t5式中：入ii=1,2,3,4,5是時間系數(shù)；t1是乘客步行至起始車站的時間，且t1=+/乳其中si、sj分別是i小區(qū)和j小區(qū)的面積，（3是與路網(wǎng)密度有關的系數(shù)，一般取2-4,v為乘客步行的平均速度；t2是從出行點到相應車站后的候車時間，且t2=+pS,其中S為平均發(fā)車間隔時間，P為平均留站率S、P可取經(jīng)歷常數(shù)

3、；t3是中間轉(zhuǎn)換時間，且t3=+Pt0,其中t0為從下車站到上車站的中轉(zhuǎn)時間；t4是車輛行駛時間，且t4=lij/vl,其中vl為車輛平均旅行速度，lij第i區(qū)心形節(jié)點到第j區(qū)心形節(jié)點公交線路的長度；t5是下車后乘客步行到達目的地的時間，且t5=ld/w,其中l(wèi)d為乘客從車站下車后步行的到目的地的最短距離。二污染物排放率最低f5=qi,i+1,kli,i+1,kjk/qi,i+1,kli,i+1,kl冰式中：j=1,2,3,4分別表示co、co2、nox和chx;qi,i+1,k為第k條線路的站點i至站點i+1路段客流量人次；li，i+1，k為第k條線路的站點i至站點i+1路段的長度；0jk為

4、第k條線路上在車速yk行駛情況下第j種污染物的實際排放濃度mg/m3；dDjk為第k條線路上在車速yk行駛情況下第j種污染物的標準排放濃度mg/m3。三乘客直達率最大f2=aaqij/aadij式中：qij為線路起終點i,j之間直達乘客量人次；dij為交通小區(qū)i至交通小區(qū)j間的od量人次；n為通行公交車輛的道路網(wǎng)節(jié)點數(shù)；m為交通小區(qū)數(shù)。四線網(wǎng)日均滿載率最大f3=-qi,i+1,kli,i+1,k/q0,i,i+1li,i+1,k式中：q0,i,i+1為第k條線路的站點i至站點i+1路段車容量；li,i+1,k為第k條線路的站點i至站點i+1路段客流量間距離km;n公交線路數(shù)。五公交企業(yè)年收益率

5、最大f4=c1/c2+c3+c4+c5+c6+c7式中：c1為公交企業(yè)年均經(jīng)濟收入萬元；c2為年均公交網(wǎng)絡建立費用萬元；c3為年均公交網(wǎng)絡維修費用萬元；c4為年均公交車輛購置費用萬元；c5為年均公交車輛維修費用萬元；c6為年均工作人員工資福利等費用萬元；c7為年均公交企業(yè)其他費用萬元。六線網(wǎng)效率最大f6=lkqi,j,k/Blka,j,k式中：qi,j,k為線路k從站點i至站點j路段的客流量；Si,j,k為經(jīng)過站點i至站點j路段的客運需求量在線路k上分配的比例；r為所有公交線路的集合；lk為線k的路長度。二、公交網(wǎng)線優(yōu)化的約束條件一線路長度l的限定線路過短會降低公交企業(yè)的效益和增加乘客乘車的轉(zhuǎn)

6、換次數(shù)；線路過長會增加車輛班次的安排和調(diào)度難度，并且工作人員也容易疲勞。所以，在規(guī)劃時要根據(jù)規(guī)劃城市的實際情況，以及乘客和工作人員的體能情況對線路的長度進展一定的限制。一般限制在5km-30km內(nèi)位佳。二線路客流量不均勻系數(shù)P的限定為了充分利用交通資源，防止交通擁擠和交通事故，所以在做規(guī)劃時必須考慮到線路的客流量均勻系數(shù)。一般情況下：p=o/q?燮1.5。式中，o為線路中最大斷面客流量，q為平均斷面客流量。三客流平均轉(zhuǎn)換次數(shù)0的限定由于受經(jīng)濟開展的約束，公交出行不可能使每個乘客都在不換成的情況下到達目的地。一般情況下要求城市居民平均出行換乘次數(shù)0=i/n?燮15式中，n為總出行人數(shù)，腦為第i位

7、出行者的換行次數(shù)。條四復線條數(shù)丫的限定考慮到公交線路的分布均勻性、站點停靠能力等，在公交線網(wǎng)優(yōu)化中采用復線條數(shù)對其進展約束。線路多了，車站設置有困難，如果多條線路的車站設在一起，各線段的車輛同時停靠容易造成該路段的交通紊亂。一般情況下一條道路上設置的路線數(shù)為丫理3：5。五線路非直線系數(shù)e的限定路線拐彎過多容易引起道路堵塞和發(fā)生交通事故，但是由于城市實際地理形勢的限制，不可能做到所有路線都是直線。一般情況下，e=l/d?燮14式中，l為某條公交線路的長度km，d為該條線路起、終點站間的空間直線距離km。六線網(wǎng)的車站效勞面積率區(qū)的限定網(wǎng)線的車站效勞面積是以車站為圓心，以合理的效勞半徑r畫圓，圓面積

8、即為車站的效勞面積。硼市道路交通規(guī)劃設計規(guī)X?對林的規(guī)定值為：。線網(wǎng)的車站效勞面積率為：=sr/s。叩由=0.5,r=300m0.9r=500m式中，sr為線網(wǎng)r的公交車站效勞面積km2，s為城市用地面積km2。七公交車保有量工的限制公交企業(yè)的公交車保有量如果多了就會造成資源的浪費，少了就不能滿足需求，造成乘客滿意度下降，進而減少公交企業(yè)的收益。因此，公交企業(yè)必須保有合理的公交車數(shù)量。公交車保有量為：工=nr/p。式中，p為城市人口數(shù)，nr為城市的公交車車輛數(shù)折算為標臺數(shù)。一般情況下要求：1/1500償號燮1/1200。三、公交網(wǎng)線優(yōu)化模型的建立通過以上公交網(wǎng)線優(yōu)化的目標函數(shù)和約束條件，我們可

9、以建立以下公交網(wǎng)線優(yōu)化的數(shù)學模型：fx=max座3f3+?墜4f4+?墜5f5+?墜6f6-礙1f1-座2f2s.t.:gin=5?130?H1.5吸1.50燮3-5e燮1.4踞0.51/1500?燮容1/12000.9,r=500m式中，1、4B、江、石、o6分別為各分工程標經(jīng)濟轉(zhuǎn)化系數(shù)采用層次分析法來確定。四、遺傳蟻群混合算法對于一個城市來說，交通網(wǎng)絡是復雜的，可行的公交線網(wǎng)成千上萬條，必須借助先進的數(shù)學方法來求解。遺傳蟻群混合算法可以從空間解中多點出發(fā)搜索問題的最優(yōu)解，適合于大規(guī)模優(yōu)化問題的求解。此外，多項研究顯示，遺傳算法在搜索初期具有較高的向最優(yōu)解收斂的速度，但之后求最優(yōu)解的速率顯著

10、下降。而蟻群算法在搜索的初期由于缺乏信息素，搜索速度緩慢，但當信息素積累到一定強度之后，向最優(yōu)解收斂的速度就會迅速提高。兩種算法的收斂速度在變化的過程中有一個穿插點，我們稱這個點位最正確點。因此，該混合算法的根本思想是：在最正確點之前采用遺傳算法產(chǎn)生信息素分布，在最正確點之后采用蟻群算法求取最優(yōu)解。遺傳蟻群混合算法能大大縮短搜索的時間。公交線網(wǎng)優(yōu)化的算法步驟：步驟1：確定初始參數(shù)、初始化及編碼。遺傳蟻群混合算法首先是對優(yōu)化模型運行遺傳算法。確定最大迭代次數(shù)t=10,群體規(guī)模n=25,穿插概率pc=0.95,變異概率pm=0.005。這里的優(yōu)化問題采用實數(shù)編碼，將變量的編碼按一定順序連接在一起形

11、成個體編碼串，解碼時只需將染色體上的各個基因值按順序賦給相應的變量即可。步驟2：計算種群適應值。適應值是遺傳算法的驅(qū)動力，也是進展自然選擇的唯一標準，適應值越大，解的質(zhì)量就越好。因為目標函數(shù)是求最小化的，因此我們通常?。?，式中，cmax是fx=cmax-fx，cmax-fx00,cmax-fx0一個適當?shù)南鄬^大的數(shù)，是fx的最大估計值。步驟3：遺傳操作產(chǎn)生后代。在選擇、穿插、變異的根底上，增加了動態(tài)接種疫苗的遺傳操作，如果算法陷入局部最優(yōu)，那么對個體進展動態(tài)疫苗注射。運行算法直到到達最大迭代次數(shù)，保存運行結(jié)果。步驟4：蟻群算法與遺傳算法銜接。與遺傳算法銜接。設蟻群中螞蟻數(shù)為m,第kk=1,2

12、,，m只螞蟻的目標分配方案為兀k。由遺傳算法局部得到信息素分布pijt。=6+Sih式中旬t0為初始時刻第個分量的候選組在做動態(tài)變化的第j個值的信息量；T0是信息素常數(shù)；S可由式給定，而Sij聲SkijSkijt=wfk,假設螞蟻k的解的第i個分量選中第j個候選值0,否那么其中，w為一個常數(shù)，fk為第k只螞蟻所對應的解的適應度。按上面的式子更新各個分量的候選組的信息量，選取各分量的候選組XX息量交換高的m個值作為新的候選組。步驟5：停頓準那么。算法一旦開場就會循環(huán)執(zhí)行，直到滿足某個停頓準那么。停頓準那么一般是為了找到一個能承受的解或者已經(jīng)迭代到了預置的迭代次數(shù)，在線網(wǎng)優(yōu)化中我們一般會設置最大迭

13、代次數(shù)。步驟6：網(wǎng)線輸出。輸出優(yōu)化線網(wǎng)，并評價檢驗其合理性與正確性。五、完畢語本文考慮了社會總出行時間、污染排放率以及公交企業(yè)的經(jīng)濟效益，兼顧了社會和公交企業(yè)兩方面的利益，所以乘客和公交公司的利益在整體模式中得到了很好的表達。同時由于考慮了線網(wǎng)的效率問題，不但提高了現(xiàn)有交通資源的利用效益而且緩解了交通出現(xiàn)的供求矛盾。文章運用了遺傳蟻群算法對模型進展求解，提高了計算的工作效率。但是在實際生活中，公交系統(tǒng)具有復雜性，有些方面我們還需要進一步研究和探討。參考文獻：1、耿金花,尹濤,童剛.公交優(yōu)化調(diào)度模型j.XX科技大學學報,2004(4).2、常XX,胡啟洲.城市公交線網(wǎng)優(yōu)化的線性模型j.中國公路學報,2005(1).3、王志棟.公交線網(wǎng)優(yōu)化模型的建立j.XX鐵道學院學報,2006(1).4、szetowy,lohk.transportationnetworkimprovementandtollingstrategies:theissueofintergenerationequityj.tran