基于遺傳算法的BRT站距雙層優(yōu)化模型研究

商澤

摘 要：為了準(zhǔn)確求解最優(yōu)BRT站距，綜合考慮了BRT站點(diǎn)服務(wù)范圍和公交企業(yè)的利益，建立了雙層優(yōu)化模型。上層微觀模型以公交車輛和BRT站點(diǎn)營(yíng)運(yùn)成本最小為目標(biāo)，下層宏觀模型作為輔助，以BRT站點(diǎn)服務(wù)范圍最大為目標(biāo)。針對(duì)該模型設(shè)計(jì)遺傳算法進(jìn)行求解，并給出算法的具體實(shí)現(xiàn)步驟，最后結(jié)合算法案例驗(yàn)證了模型和算法的有效性。

關(guān)鍵詞：BRT站距；遺傳算法；雙層規(guī)劃

中圖分類號(hào)：U491.17 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-2064（2018）16-0050-02

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

1 雙層公交站距優(yōu)化模型

1.1 基本假設(shè)

本文所研究的是BRT最優(yōu)站距問題，所以可以做以下假設(shè)：

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

1.2 上層微觀模型

1.2.1 車輛營(yíng)運(yùn)時(shí)間計(jì)算模型

車輛由起點(diǎn)到起點(diǎn)一個(gè)循環(huán)運(yùn)行時(shí)間可表示成：

T車=T1+T2+T3 （1）

T1=2L/V （2）

（3）

（4）

N=L/D+1 （5）

式中：T車為車輛由起點(diǎn)到起點(diǎn)一個(gè)循環(huán)運(yùn)行時(shí)間（s）；T1為車輛以穩(wěn)定車速V運(yùn)行時(shí)間（s）；T2為車輛因進(jìn)出站而減速或加速所損失總時(shí)間（s）；T3為車輛在各站點(diǎn)的停車總時(shí)間（s）。L為起點(diǎn)到終點(diǎn)長(zhǎng)度（m）；V為車輛的運(yùn)行速度（m/s）；D為站距（m）；N為站點(diǎn)數(shù)；、分別為第i站臺(tái)進(jìn)、出站時(shí)減速或加速時(shí)間（s）；為在第i個(gè)站臺(tái)的停車時(shí)間（s）。

1.2.2 車輛營(yíng)運(yùn)成本計(jì)算模型

車輛營(yíng)運(yùn)成本c車等于車輛每次由起點(diǎn)到起點(diǎn)一個(gè)循環(huán)所對(duì)應(yīng)的運(yùn)行成本之和，一個(gè)車輛由起點(diǎn)到起點(diǎn)一個(gè)循環(huán)運(yùn)行成本等于該車輛以正常行駛時(shí)的時(shí)間乘以其時(shí)間成本和車輛在站點(diǎn)停站時(shí)的時(shí)間乘以成本之和。在上邊車輛由起點(diǎn)到起點(diǎn)一個(gè)循環(huán)運(yùn)行時(shí)間的推導(dǎo)基礎(chǔ)上，可以求出車輛營(yíng)運(yùn)成本c車為：

（6）

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

將（2）、（3）、（4）式代入（6）式得車輛營(yíng)運(yùn)成本：

（7）

式中：、分別為第m次發(fā)車過程中在第i站臺(tái)進(jìn)、出站時(shí)減速或加速時(shí)間（s）；T3ij為第m次發(fā)車過程中在第i個(gè)站臺(tái)的停車時(shí)間（s）；其他符號(hào)與上面提到的一致。

1.2.3 站臺(tái)營(yíng)運(yùn)成本計(jì)算模型

BRT的站臺(tái)的營(yíng)運(yùn)情況不同于普通公交站臺(tái)，其營(yíng)運(yùn)成本不可忽略。站臺(tái)營(yíng)運(yùn)成本c站等于所有站點(diǎn)單位時(shí)間的營(yíng)運(yùn)成本與營(yíng)運(yùn)時(shí)間之積。假設(shè)每個(gè)站點(diǎn)的單位時(shí)間營(yíng)運(yùn)成本相同，則站臺(tái)營(yíng)運(yùn)成本可表示為：

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

式中：t為固定的發(fā)車時(shí)間間隔（min），Q為每個(gè)站點(diǎn)的單位時(shí)間營(yíng)運(yùn)成本（元/s）。

1.2.4 上層微觀模型的建立

假設(shè)車輛營(yíng)運(yùn)成本c車和站臺(tái)營(yíng)運(yùn)成本c站的加權(quán)系數(shù)分別為a和b，且a+b=1。加權(quán)系數(shù)的取值由實(shí)際營(yíng)運(yùn)下的權(quán)重情況綜合決定。則上層模型的目標(biāo)函數(shù)可表示為：

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

1.3 下層宏觀模型

1.3.1 BRT站點(diǎn)服務(wù)范圍c范

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

基于以上假設(shè)，BRT路線的總服務(wù)面積為各個(gè)站點(diǎn)的服務(wù)面積減去重疊服務(wù)區(qū)的面積。則BRT路線的總服務(wù)面積可表示為：

（其中：R

式中：S為BRT路線的總服務(wù)面積；R為每個(gè)BRT站點(diǎn)的服務(wù)區(qū)半徑；D為公交站距。

假設(shè)服務(wù)面積折算系數(shù)為c，則BRT站點(diǎn)服務(wù)范圍c范可表示為：c范=cS （11）

1.3.2 下層宏觀模型的建立

下層宏觀模型是以BRT站點(diǎn)服務(wù)范圍最大為目標(biāo)函數(shù)的宏觀模型。其目標(biāo)函數(shù)可表示為：

Z2=c范（R

2 遺傳算法設(shè)計(jì)

2.1 編碼

本算法采用二進(jìn)制編碼，每一個(gè)十位的二進(jìn)制染色體對(duì)應(yīng)著一個(gè)十進(jìn)制的站距值（單位：m），由二進(jìn)制編碼的站距值足以包括城市公共交通最優(yōu)站距的取值范圍。

2.2 初始種群的產(chǎn)生

初始種群是通過隨機(jī)函數(shù)randperm產(chǎn)生n個(gè)十位的二進(jìn)制染色體構(gòu)成。

2.3 適應(yīng)度

適應(yīng)度是對(duì)該問題的一個(gè)解的評(píng)價(jià)值和目標(biāo)值，按一定的數(shù)學(xué)變換規(guī)則生成適應(yīng)度函數(shù)F（k），采用如下表達(dá)式：

（13）

式中d值取1z1（i）、z2（i）表示第k個(gè)染色體上、下層規(guī)劃的目標(biāo)函數(shù)值。K∈M，M表示種群數(shù)量。

2.4 選擇

本文采用輪盤賭選擇法對(duì)每個(gè)染色體進(jìn)行選擇。

2.5 交叉和變異

交叉：對(duì)于隨機(jī)從種群中選出的某對(duì)染色體，按交叉概率隨機(jī)地在其上選擇一個(gè)斷點(diǎn)，交換雙親上斷點(diǎn)的左端，生成新的后代。

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

3 算法步驟

Step0：參數(shù)初始化。

Stepl：設(shè)定種群數(shù)目M、染色體長(zhǎng)度l、迭代總數(shù)、交叉概率、變異概率。

Step2：采用0-1編碼，隨即產(chǎn)生初始種群。

Step3：將各染色體轉(zhuǎn)化成站距值并計(jì)算各染色體對(duì)應(yīng)的上、下層目標(biāo)函數(shù)值z(mì)1、z2。

Step4：計(jì)算種群的各染色體適應(yīng)度函數(shù)值。

Step5：通過旋轉(zhuǎn)賭輪每一個(gè)染色體。

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

Step7：結(jié)束，從進(jìn)化的代染色體群中選取適應(yīng)度最好的染色體，該染色體就是問題的較優(yōu)解。

4 算法案例及分析

4.1 案例的提出

本文以濟(jì)南市BRT1線路為算法案例，對(duì)其站距進(jìn)行優(yōu)化。BRT1西起黃崗，東至全福立交橋，全長(zhǎng)11.5km，采用專用車道全封閉運(yùn)行，沿途共設(shè)有17個(gè)實(shí)際營(yíng)運(yùn)站點(diǎn)，2個(gè)備用站點(diǎn)。實(shí)地調(diào)查BRT1線路工作日和周末的每次發(fā)車中在每個(gè)站點(diǎn)的實(shí)際延誤時(shí)間做為初始數(shù)據(jù)，并結(jié)合實(shí)際情況確定時(shí)間成本、營(yíng)運(yùn)成本、加權(quán)系數(shù)和服務(wù)區(qū)半徑等參數(shù)的取值。

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

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