基于遺傳算法的BRT站距雙層優化模型研究

商澤

摘 要：為了準確求解最優BRT站距，綜合考慮了BRT站點服務范圍和公交企業的利益，建立了雙層優化模型。上層微觀模型以公交車輛和BRT站點營運成本最小為目標，下層宏觀模型作為輔助，以BRT站點服務范圍最大為目標。針對該模型設計遺傳算法進行求解，并給出算法的具體實現步驟，最后結合算法案例驗證了模型和算法的有效性。

關鍵詞：BRT站距；遺傳算法；雙層規劃

中圖分類號：U491.17 文獻標識碼：A 文章編號：1671-2064（2018）16-0050-02

BRT站點間距優化最早于1968年由Vuchic和Newell[1]提出，以乘客出行時間最短為目標函數對輕軌和地鐵線路的站距進行優化。其后，S C Wirasinghe和N S Ghoneim[5]逐步完善了基于需求連續分布的站點間距優化理論。近年來，國內相繼提出了基于全局最優化理論的BRT站點布設模型[2]、基于乘客平均出行時間最小的公交站距優化模型[3]和基于社會福利最大的公交站距優化模型[4]等理論。本文在此基礎之上，提出了基于遺傳算法的BRT站距雙層優化模型，綜合考慮了BRT站點服務范圍和公交企業的利益兩方面的因素，建立上層以BRT車輛和站點營運成本最小為目標，下層以BRT站點服務范圍最大為目標的雙層模型，能夠更全面的對BRT站距進行優化。

1 雙層公交站距優化模型

1.1 基本假設

本文所研究的是BRT最優站距問題，所以可以做以下假設：

（1）BRT線路至少采用半封閉路權模式，節點采用公交信號優先，即公交車輛通過交叉口時的延誤忽略不計；（2）為了研究方便，將公交車運動劃分成為勻速運動、勻減速運動以及勻加速運動；（3）為了研究方便，公交車以固定時間間隔發車；（4）為了建立上層微觀模型的需要，忽略公交車輛調頭延誤，即將BRT線路近似看做閉合回路的形式，公交車輛由起點到終點循環營運，假設采取中央式布站，BRT線路設有N個站，每個站點均需停車兩次，公交車輛每次由起點到起點一個循環共需停車2N次；（5）為了建立下層宏觀模型，假設BRT線路可以由部分近似直線段組成，并且直線段數目盡量少，即忽略BRT線路轉彎造成的覆蓋率損失。在BRT線路中共有N個站，以站點為圓心形成圓形服務范圍。

1.2 上層微觀模型

1.2.1 車輛營運時間計算模型

車輛由起點到起點一個循環運行時間可表示成：

T車=T1+T2+T3 （1）

T1=2L/V （2）

（3）

（4）

N=L/D+1 （5）

式中：T車為車輛由起點到起點一個循環運行時間（s）；T1為車輛以穩定車速V運行時間（s）；T2為車輛因進出站而減速或加速所損失總時間（s）；T3為車輛在各站點的停車總時間（s）。L為起點到終點長度（m）；V為車輛的運行速度（m/s）；D為站距（m）；N為站點數；、分別為第i站臺進、出站時減速或加速時間（s）；為在第i個站臺的停車時間（s）。

1.2.2 車輛營運成本計算模型

車輛營運成本c車等于車輛每次由起點到起點一個循環所對應的運行成本之和，一個車輛由起點到起點一個循環運行成本等于該車輛以正常行駛時的時間乘以其時間成本和車輛在站點停站時的時間乘以成本之和。在上邊車輛由起點到起點一個循環運行時間的推導基礎上，可以求出車輛營運成本c車為：

（6）

式中：m為發車次數；T1j、T2j、T3j分別為汽車在第m次發車中正常行駛、加速或減速行駛和停車的時間；c1、c2、c3分別為汽車在正常行駛、加速或減速行駛、停車時的單位時間成本（單位：元/s），其值的的大小有汽車單位時間的油耗值和汽車損耗程度等因素確定。

將（2）、（3）、（4）式代入（6）式得車輛營運成本：

（7）

式中：、分別為第m次發車過程中在第i站臺進、出站時減速或加速時間（s）；T3ij為第m次發車過程中在第i個站臺的停車時間（s）；其他符號與上面提到的一致。

1.2.3 站臺營運成本計算模型

BRT的站臺的營運情況不同于普通公交站臺，其營運成本不可忽略。站臺營運成本c站等于所有站點單位時間的營運成本與營運時間之積。假設每個站點的單位時間營運成本相同，則站臺營運成本可表示為：

c站=60t（m-1）nQ （8）

式中：t為固定的發車時間間隔（min），Q為每個站點的單位時間營運成本（元/s）。

1.2.4 上層微觀模型的建立

假設車輛營運成本c車和站臺營運成本c站的加權系數分別為a和b，且a+b=1。加權系數的取值由實際營運下的權重情況綜合決定。則上層模型的目標函數可表示為：

Z1=c車+（1-）c站 （9）

1.3 下層宏觀模型

1.3.1 BRT站點服務范圍c范

BRT站點服務范圍等于本條BRT路線的總服務面積乘以服務面積折算系數。假設每個BRT站點的服務面積為以半徑為R的圓，以BRT線路的起點為坐標原點建立直角坐標系，忽略BRT線路轉彎造成的覆蓋率損失，可以按一條直線路線計算服務范圍，則BRT路線的服務面積示意圖如圖1所示。

基于以上假設，BRT路線的總服務面積為各個站點的服務面積減去重疊服務區的面積。則BRT路線的總服務面積可表示為：

（其中：R

式中：S為BRT路線的總服務面積；R為每個BRT站點的服務區半徑；D為公交站距。

假設服務面積折算系數為c，則BRT站點服務范圍c范可表示為：c范=cS （11）

1.3.2 下層宏觀模型的建立

下層宏觀模型是以BRT站點服務范圍最大為目標函數的宏觀模型。其目標函數可表示為：

Z2=c范（R

2 遺傳算法設計

2.1 編碼

本算法采用二進制編碼，每一個十位的二進制染色體對應著一個十進制的站距值（單位：m），由二進制編碼的站距值足以包括城市公共交通最優站距的取值范圍。

2.2 初始種群的產生

初始種群是通過隨機函數randperm產生n個十位的二進制染色體構成。

2.3 適應度

適應度是對該問題的一個解的評價值和目標值，按一定的數學變換規則生成適應度函數F（k），采用如下表達式：

（13）

式中d值取1z1（i）、z2（i）表示第k個染色體上、下層規劃的目標函數值。K∈M，M表示種群數量。

2.4 選擇

本文采用輪盤賭選擇法對每個染色體進行選擇。

2.5 交叉和變異

交叉：對于隨機從種群中選出的某對染色體，按交叉概率隨機地在其上選擇一個斷點，交換雙親上斷點的左端，生成新的后代。

變異：按變異概率選取染色體的某個位置實行變異，該位置若是0的則變成l，若是1的則變成0。

3 算法步驟

Step0：參數初始化。

Stepl：設定種群數目M、染色體長度l、迭代總數、交叉概率、變異概率。

Step2：采用0-1編碼，隨即產生初始種群。

Step3：將各染色體轉化成站距值并計算各染色體對應的上、下層目標函數值z1、z2。

Step4：計算種群的各染色體適應度函數值。

Step5：通過旋轉賭輪每一個染色體。

Step6：將各染色體轉化二進制的形式，按照概率進行交叉、變異操作，轉向Step3。

Step7：結束，從進化的代染色體群中選取適應度最好的染色體，該染色體就是問題的較優解。

4 算法案例及分析

4.1 案例的提出

本文以濟南市BRT1線路為算法案例，對其站距進行優化。BRT1西起黃崗，東至全福立交橋，全長11.5km，采用專用車道全封閉運行，沿途共設有17個實際營運站點，2個備用站點。實地調查BRT1線路工作日和周末的每次發車中在每個站點的實際延誤時間做為初始數據，并結合實際情況確定時間成本、營運成本、加權系數和服務區半徑等參數的取值。

4.2 利用Matlab遺傳算法工具箱求解算例

使用英國設菲爾德（Sheffield）大學推出的Matlab遺傳算法工具箱作為輔助工具通過編程對算例進行求解[7]。遺傳