基于遺傳算法的公交調(diào)度模糊最優(yōu)解

武 斌

(中國石油大學(xué)勝利學(xué)院 基礎(chǔ)科學(xué)學(xué)院,山東 東營 257061)

發(fā)展城市公共交通可以緩解交通擁堵,減少環(huán)境污染,方便人們出行,因此研究公共交通調(diào)度的數(shù)學(xué)模型及其求解方法有其現(xiàn)實(shí)意義。關(guān)于公交調(diào)度的研究內(nèi)容,許多學(xué)者針對公交調(diào)度的滿載率問題[1]、發(fā)車頻率[2]、車型優(yōu)化[2]、客流分布[3]以及指揮系統(tǒng)[4-5]等進(jìn)行了研究。然而,以往的公交調(diào)度模型大多是確定性的模型,要求精確地確定目標(biāo)函數(shù)值,這樣可能無法完全發(fā)揮模型的作用,而且很多模型沒有充分考慮乘客和公交公司利益的協(xié)調(diào)。鑒于此,筆者首先建立能夠模擬公交車運(yùn)行的確定性模型,然后在此之上建立公交優(yōu)化調(diào)度的模糊多目標(biāo)非線性規(guī)劃模型,使用遺傳算法對其進(jìn)行求解,得出模糊最優(yōu)解并進(jìn)行實(shí)例分析。

1 公交調(diào)度模糊多目標(biāo)規(guī)劃模型建立

公交公司在運(yùn)營過程中,若乘車票價(jià)一定,則總是希望加大發(fā)車間隔以減少其可變運(yùn)營成本,但是發(fā)車間隔過大,乘客則會(huì)因?yàn)榈溶嚂r(shí)間過長,車內(nèi)過于擁擠而選擇其他出行方案。因此確定合理的發(fā)車時(shí)刻表是至關(guān)重要的。公交車在行駛過程中外部環(huán)境多變、客流隨機(jī)性大,因此為建立能夠模擬公交運(yùn)營的多目標(biāo)規(guī)劃模型,假設(shè)如下:

(1)公交車均按照規(guī)定路線行駛,不存在超車和等客現(xiàn)象;

(2)公交車輛始終是勻速行駛,并且不受道路突發(fā)情況的影響;

(3)公交車均采用同一車型,即額定的載客人數(shù)相同。

1.1 符號說明

建立模型所用到的變量如表1所示。

1.2 模型的目標(biāo)函數(shù)

公交優(yōu)化調(diào)度主要是要考慮如何協(xié)調(diào)公交公司和乘客之間的利益,既要讓公交公司在固有運(yùn)營條件下盡可能的獲利,也要盡可能地降低車上擁擠程度,減少乘客等車時(shí)間。從極大化公交公司盈利和極小化乘客的等車費(fèi)用、車內(nèi)費(fèi)用出發(fā)建立發(fā)車間隔優(yōu)化模型[6]。該模型的目標(biāo)函數(shù)有:

(1)乘客的等車費(fèi)用。

(1)

表1 變量符號說明

(2)乘客在車內(nèi)的費(fèi)用。乘客的車內(nèi)費(fèi)用是乘客在車內(nèi)的時(shí)間與轉(zhuǎn)換系數(shù)U2的乘積,而乘客在車內(nèi)的時(shí)間主要分為T1和T2兩部分,其中T1為乘客從第i-1站到第i站的乘車時(shí)間,T2是公交車到達(dá)第i站時(shí)不下車的乘客需要在車上等待的時(shí)間,可以取在第k站時(shí)乘客上車時(shí)間與下車時(shí)間的平均值。

(2)

(3)

(3)公交公司的收益。在時(shí)間段T內(nèi),公交公司的發(fā)車數(shù)為60 T/h,則表示公交公司運(yùn)營收益的目標(biāo)函數(shù)為

(4)

1.3 模型的約束條件

(1)發(fā)車次數(shù)約束。

(5)

公交公司在一個(gè)時(shí)段內(nèi)總的發(fā)車次數(shù)不應(yīng)超過其固有條件下的最大發(fā)車次數(shù)Smax。

(2)發(fā)車間隔約束。

(6)

(3)滿載率約束。

(7)

公交車的滿載率應(yīng)該低于公司設(shè)定的最大滿載率ηmax,即車上不能過于擁擠。

1.4 模型處理

對于目標(biāo)函數(shù)(1)、(3)、(4)可以分別引入如下的隸屬函數(shù)。

乘客等車費(fèi)用目標(biāo):

(8)

式中,Re、Ru分別表示等車費(fèi)用目標(biāo)的期望值和上限值。

乘客車內(nèi)費(fèi)用目標(biāo)為

(9)

式中,Ie、Iu分別表示車內(nèi)費(fèi)用目標(biāo)的期望值和上限值。

公交公司的運(yùn)營收益目標(biāo)為

(10)

式中,Qe,Ql分別為公交公司的可變運(yùn)營費(fèi)用目標(biāo)的期望值和下限值。

由于隸屬度函數(shù)的引入,模糊多目標(biāo)規(guī)劃模型的目標(biāo)函數(shù)為

(11)

2 基于遺傳算法的模糊最優(yōu)解求解方法

由于模型的約束條件(5)～(7)是確定性的,則模糊多目標(biāo)模型可以等價(jià)于如下形式的確定型非線性規(guī)劃:

maxα

s.t.

α≤μk(zk(X)),k=1,2,3;

gi(X)≤Gi,i=1,2,3;

0≤λ≤1.

(12)

式中,gi(X)≤Gi,i=1,2,3表示原模型的約束條件,α是決策者對各個(gè)模糊目標(biāo)的最小滿意度。

α表示為

α=min{μk(x),k=1,2,3}.

(13)

在求解過程中,對于個(gè)體x,

μmin(x)=min{μ1(x),μ2(x),μ3(x)}.

(14)

使用的適應(yīng)度函數(shù)為

(15)

式中,α0為事先確定的可以接受的滿意度,0≤ε≤1。

使用遺傳算法求解的步驟[8]如下:

(1)初始化。輸入滿意度α0=0.2,最大遺傳代數(shù)max_gen=200,種群大小NP=200,考慮的準(zhǔn)則依次取各個(gè)目標(biāo)的隸屬度最大值;

(2)在區(qū)間[Xl,Xu]內(nèi)隨機(jī)產(chǎn)生初始種群,然后按照式(15)計(jì)算個(gè)體的適應(yīng)度函數(shù)值;

(3)初始迭代步數(shù)k=1;

(4)對于個(gè)體j(j=1,2,…,NP),計(jì)算個(gè)體的適應(yīng)度函數(shù)F(j)以及選擇概率P(j):

(16)

(17)

(18)

式中,r是區(qū)間[0,1]上任取的隨機(jī)數(shù),T為該算法設(shè)定的最大迭代步數(shù),t為本次迭代次數(shù),b是不一致參數(shù)。該函數(shù)能夠隨著迭代步數(shù)的增加,縮小搜索范圍,也就是局部搜索;

(6)用式(15)計(jì)算個(gè)體j的隸屬度函數(shù)值,從種群中選擇最優(yōu)隸屬度函數(shù)值用于更新μmax,并依次更新各個(gè)準(zhǔn)則的隸屬度最大值,同時(shí)保存最優(yōu)個(gè)體的信息;

(7)令k+1→k,若k≤T,則返回第2步,否則則輸出最優(yōu)的隸屬度函數(shù)值μmax以及各準(zhǔn)則對應(yīng)的最優(yōu)解。

3 實(shí)例分析

選取某一公交線路,使用上述分析的模型及算法進(jìn)行求解,該公交線路的總長為7.3 km,共有15個(gè)站點(diǎn),發(fā)車時(shí)間為6:00～19:00,公交車的票價(jià)為1元/人·次,公交車行駛速度為20(km/h),最大發(fā)車車次為20,公交車的額定載客數(shù)為40(人/車),最大發(fā)車間隔hmax=15 min,最小發(fā)車間隔hmin=2 min,每輛車的平均期望滿載率τ0=0.5,每輛車的最高斷面期望滿載率τmax=0.7,乘客等車時(shí)間轉(zhuǎn)換為運(yùn)營成本的系數(shù)為0.3(元/(人·min)),乘客在車內(nèi)時(shí)間轉(zhuǎn)換為運(yùn)營成本的系數(shù)為0.15(元/(人·min)),每位乘客的平均上下車時(shí)間為3(s/人),本文使用模糊聚類分析對發(fā)車時(shí)段進(jìn)行了劃分,并采用駐站調(diào)查法[9]對東營市某公交線路的單向斷面通過量進(jìn)行了統(tǒng)計(jì),具體調(diào)查數(shù)據(jù)如表2所示:

表2 各時(shí)段的單向斷面通過量

將各參數(shù)代入模型,使用遺傳算法求解可得各時(shí)段的發(fā)車間隔如表3所示。

普通公交調(diào)度多目標(biāo)非線性規(guī)劃模型的過結(jié)果如表4所示。

表3 模糊最優(yōu)解結(jié)果

表4 多目標(biāo)非線性規(guī)劃結(jié)果

設(shè)論域U={x1,x2},其中x1為模糊多目標(biāo)非線性規(guī)劃模型,x2為常規(guī)多目標(biāo)規(guī)劃模型,使用模糊綜合評判對其進(jìn)行優(yōu)劣分析,可得x1為第一優(yōu)越對象?？梢娛褂媚：?guī)劃制定的發(fā)車間隔比較合理,兼顧了乘客和公交公司雙方的利益。從表3和表4可以看出,模糊多目標(biāo)規(guī)劃降低了乘客的出行成本,但公交公司的運(yùn)營收益有所降低,本文是客流量一定的前提下進(jìn)行模型求解的,若乘客乘坐公交車的成本降低,客流量就會(huì)有所增加,公交公司的運(yùn)營收益會(huì)有所提高,所以使用遺傳算法求解的模型模糊最優(yōu)解比一般多目標(biāo)規(guī)劃更為合理,符合實(shí)際應(yīng)用。

4 結(jié)束語

建立以發(fā)車間隔為決策變量的公交調(diào)度模糊多目標(biāo)規(guī)劃模型,并給出了求解該模型的遺傳算法,能夠得出該模型的模糊最優(yōu)解。模糊規(guī)方法采用隸屬度函數(shù)來表示目標(biāo)與期望值之間的接近程度,允許模型在一定范圍內(nèi)求解。因此使用模糊規(guī)劃求解公交優(yōu)化問題能夠在一定范圍內(nèi)協(xié)調(diào)各個(gè)目標(biāo)值,得到更好的優(yōu)化結(jié)果,所以對于公交調(diào)度問題,建立模糊多目標(biāo)規(guī)劃模型并對其求解更合理。