基于精英選擇遺傳算法的需求響應(yīng)公交規(guī)劃

(華南理工大學(xué) 土木與交通學(xué)院，廣東 廣州 510641)

0 引言

傳統(tǒng)公交系統(tǒng)通常是基于固定線路固定時刻規(guī)劃的，無法根據(jù)乘客需求做出動態(tài)調(diào)整。今年來隨著“公交優(yōu)先”口號的提出，定制公交、需求響應(yīng)公交(Demand Responsive Transit，DRT)等乘客需求導(dǎo)向性新型公交模式被提出并嘗試運(yùn)營。以DRT為例，企業(yè)需要根據(jù)乘客的響應(yīng)狀態(tài)規(guī)劃合適的車輛?？空军c(diǎn)和行駛路徑，在盡可能滿足乘客需求的條件下，控制運(yùn)輸成本，實(shí)現(xiàn)企業(yè)利潤最大化。對于DRT的研究，Carlos[1]在1984首次提出DRT的設(shè)想，Rodier[2]對DRT中乘客出行收益進(jìn)行了研究，Bellini等[3]建立了DRT車輛調(diào)度模型。Schilde等[4]等研究了不同速度下對DRT服務(wù)水平的影響。在國內(nèi)，潘述亮等[5]等對包含特殊需求的DRT模型進(jìn)行了研究，盧小林等[6]同時提出一種最小化公交車運(yùn)營時間為目標(biāo)的DRT路徑優(yōu)化模型，鄭漢等[7]等對混合車型DRT進(jìn)行了建模，并設(shè)計了Dantzig-Wolfe分解算法求解。

對DRT規(guī)劃可分為站點(diǎn)規(guī)劃和路徑規(guī)劃兩階段，首先規(guī)劃公交臨時?？空军c(diǎn)，通常通過K-means算法實(shí)現(xiàn)[8]。對公交路徑規(guī)劃可看作是一種特殊形式的帶有容量約束的車輛路徑問題(Capacitated Vehicle Routing Problem，CVRP)，不同的是公交車需要從同一戰(zhàn)場出發(fā)到達(dá)同一目的地，目的地與出發(fā)地往往不同。車輛路徑規(guī)劃已被證實(shí)為NP(Non-deterministic Polynomial)完全問題，通常設(shè)計啟發(fā)式算法[9-11]求解。遺傳算法(Genetic Algorithm，GA)是通過模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而設(shè)計，是一種廣泛使用的啟發(fā)式搜索算法，其選擇策略通常是基于輪盤賭(Roulette Wheel Selection Genetic Algorithm，RWSGA)的概率選擇。為了提高算法收斂速度和搜索結(jié)果，本文提出了一種基于精英選擇遺傳算法[12](Elitist Selection Genetic Algorithm，ESGA)求解DRT中路徑規(guī)劃問題，并通過試驗驗證。本文首先建立的DRT站點(diǎn)選擇和路徑規(guī)劃模型，并通過試驗數(shù)據(jù)求解分析，對DRT規(guī)劃具有一定的參考意義。

1 DRT規(guī)劃模型

1.1 問題描述

在某一限定的區(qū)域內(nèi)，已知一定數(shù)量乘客的位置、使用DRT意愿和支付意愿，企業(yè)根據(jù)乘客信息規(guī)劃若干數(shù)量的臨時?？空军c(diǎn)響應(yīng)乘客出行需求，并在已有的車輛數(shù)量和車輛容量限制下，根據(jù)車輛出發(fā)地、目的地和?？奎c(diǎn)規(guī)劃響應(yīng)公交接送乘客路徑，以實(shí)現(xiàn)企業(yè)利潤最大化。

為了方便模型建立和求解，有以下基本假設(shè)。

① 只有乘客的支付意愿高于或等于企業(yè)最低支付意愿時，乘客需求才會被企業(yè)響應(yīng)；

② 每一局部區(qū)域的乘客需要到最近的臨時?？奎c(diǎn)乘車；

③ 每輛公交車都從固定的站場出發(fā)，完成所有乘客的接收后，到達(dá)固定的目的地；

④ 每輛公交車只開行一次，每個?？奎c(diǎn)只能被公交車訪問一次。

為了方便數(shù)學(xué)模型的建立，定義相關(guān)變量含義如下：

K：表示戰(zhàn)場公交車總數(shù)量(k=1，2，……，K)；

N：表示公交車?？空军c(diǎn)總數(shù)量(n=1，2，……，N)；

M：表示公交車?？空军c(diǎn)總數(shù)量與出發(fā)地和目的地的數(shù)量之和(m=0，1，2，……，N，N+1)，m=0表示公交車出發(fā)地，m=N+1表示公交車目的地；

L：表示乘客總數(shù)量(l=1，2，…，L)；

cf：表示車輛固定成本；

c0：表示車輛可變成本，即單位距離行駛成本；

ua：表示乘客使用DRT的意愿，ua=1表示乘客具有使用意愿，否則ua=0；

pa：表示乘客支付DRT的意愿(元)；

p0：表示企業(yè)響應(yīng)乘客最低支付意愿(元)；

ra：表示企業(yè)是否響應(yīng)乘客需求，ra=1表示企業(yè)響應(yīng)乘客需求，否則ua=0；

yai：yai=1表示第a個乘客在第i個站點(diǎn)乘車(a=1，2，…，L；i=1，2，…，N);

dij：表示點(diǎn)i到點(diǎn)j的行駛距離(i，j=0，1，2，…，N，N+1)；

xijk：xijk=1表示車輛k從站點(diǎn)i行駛到站點(diǎn)j，否則xijk=0，(i，j=0，1，2，…，N，N+1；k=1，2，…，K)；

Qi：表示第i個停靠站點(diǎn)的上車人數(shù)；

Qc：表示響應(yīng)公交的最大載客量。

1.2 建立模型

由上述的問題描述和基本假設(shè)，以企業(yè)最大化利潤為目標(biāo)，建立DRT路徑規(guī)劃模型。

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

2 DRT規(guī)劃模型求解

2.1 基于K-means算法的停靠站規(guī)劃

本文首先基于K-means聚類算法規(guī)劃了DRT?？空军c(diǎn)。K-means算法根據(jù)乘客坐標(biāo)劃分為k個簇，可以并將每個簇中心作為DRT的停靠站點(diǎn)，可以使得每位乘客到其所屬簇內(nèi)的站點(diǎn)的距離最小。K-means算法獲得停靠站的流程如圖1所示。

圖1 K-means算法流程Figure 1 The flow of k-means Algorithm

2.2 基于ESGA的路徑規(guī)劃

本文設(shè)計了基于精英選擇遺傳算法(ESGA)求解模型，其相比于普遍使用的基于輪盤賭選擇遺傳算法(RWSGA)具有更快的收斂速度。ESGA其基本思想：依據(jù)上一代種群的適應(yīng)度建立精英種群，在新一代的選擇的過程中，用精英種群替換種群中適應(yīng)度低的個體。ESGA流程如圖2所示。

圖 2 精英選擇遺傳算法流程Figure 2 The flow of elitist selection genetic algorithm

2.2.1編碼

本文采用整數(shù)編碼方案，用0表示公交車戰(zhàn)場，1，2，……，n表示上車站點(diǎn)。如編碼方案0-1-3-4-5-0-2-8-0-6-7表示企業(yè)需要規(guī)劃3條響應(yīng)公交線路，從公交站場0出發(fā)，路徑分別為1-3-4-5、2-8和6-7，然后再到達(dá)目的地。

2.2.2適應(yīng)度計算

ESGA通過選擇算子淘汰劣勢個體，保留優(yōu)勢個體，適應(yīng)度為個體選擇依據(jù)，適應(yīng)度計算公式為：

fitness(xi)=Zi

(9)

其中,xi表示第i個個體;Zi表示第i個個體的總利潤。對于不滿足約束條件的個體，將其適應(yīng)度設(shè)為0，可以通過選擇操作將其淘汰。

2.2.3基于精英保留的選擇算子

ESGA的選擇算子主要包括精英種群的建立和選擇操作兩部分。通過上一代適應(yīng)度最高的部分個體建立種群，然后在使用精英種群替換下一代適應(yīng)度最低的部分個體。

2.2.4交叉算子

交叉算子通過隨機(jī)選擇2個個體的基因片段互換位置。由于受約束公式(3)和(4)的限制，為了保證交叉重組后的個體依然具有實(shí)際意義，交叉操作如圖3所示。

在個體0-1-3-4-5-0-2-8-0-6-7和0-3-6-2-0-5-7-1-0-8-4中隨機(jī)選擇2個車輛路徑0-2-8和0-8-4置于基因首端得到0-8-4-0-1-3-4-5-0-2-8-0-6-7和0-2-8-0-3-6-2-0-5-7-1-0-8-4，剔除重復(fù)基因位得到交叉后的2個個體0-8-4-0-1-3-5-0-2-0-6-7和0-2-8-0-3-6-0-5-7-1-0-9-4。

圖3 交叉操作Figure 3 Cross operation

2.2.5變異算子

設(shè)計變異算子可以提高算法局部搜索能力。由于受約束條件(3)和(4)的限制，可隨機(jī)選擇2個停靠站點(diǎn)交換其位置。如，對于個體0-1-3-4-5-0-2-8-0-6-7，隨機(jī)選擇2個站點(diǎn)4和8，通過變異操作得到0-1-3-8-5-0-2-4-0-6-7。

2.2.6反轉(zhuǎn)算子

反轉(zhuǎn)算子本質(zhì)上也是一種變異策略，可以提高算法局部搜索能力。例如，對于個體0-1-3-4-5-0-2-8-0-6-7，隨機(jī)選擇一段路徑0-1-3-4-5，其通過反轉(zhuǎn)操作得到0-5-4-3-1。

3 實(shí)例分析

3.1 實(shí)例數(shù)據(jù)

實(shí)例數(shù)據(jù)為某區(qū)域內(nèi)的100位乘客，其坐標(biāo)和支付意愿如圖4和表 1所示。

3.2 求解結(jié)果

首先根據(jù)坐標(biāo)信息使用K-means算法將乘客分為10類確定公交?？空军c(diǎn)，如圖5所示；然后根據(jù)乘客支付意愿確定每個站點(diǎn)的上車人數(shù)，如表2所示。

然后基于ESGA規(guī)劃公交路徑，其中種群規(guī)模為200，進(jìn)化代數(shù)為200，精英種群比例為10%，交叉概率為0.9，變異概率為0.1，反轉(zhuǎn)概率為0.1，站場車輛數(shù)k為5，每輛車的限載人數(shù)Qc為40，表示企業(yè)響應(yīng)乘客最低支付意愿為4元，車輛固定成本cf為5，車輛可變成本c0為0.1。經(jīng)過20次的獨(dú)立重復(fù)試驗，選取最好試驗結(jié)果作為最終結(jié)果，其進(jìn)化曲線、車輛規(guī)劃路徑和計算結(jié)果如圖6、圖7和表3所示。

圖4 乘客坐標(biāo)Figure 4 Passenger coordinates

表1 乘客支付意愿Table1 Thepayingwillingnessforpassengers站點(diǎn)支付意愿/元0123456789總計1101021221010200111321111133000110400942000320401125200000321086100012201297001131220010800100141311190001331111111011001211209

圖5 公交?？奎c(diǎn)規(guī)劃Figure 5 Bus stop planning

表2 公交停靠點(diǎn)信息Table2 Busstopinformation站點(diǎn)坐標(biāo)響應(yīng)人數(shù)1(343.74,883.97)82(656.42,361.95)93(632.76,812.99)64(313.41,593.06)105(547.09,243.67)66(819.06,601.69)87(814.77,221.22)88(326.92,240.38)109(502.46,477.59)1010(133.39,666.06)7

圖6 進(jìn)化曲線Figure 6 Evolutionary Curve

表3 計算結(jié)果Table3 Calculationresults公交車路徑行駛里程成本/元乘客數(shù)量/人收入/元利潤/元0-3-6-7-111137.56118.7622132.0013.240-1-10-4-8-111227.13127.7135218.0090.290-9-2-5-11882.2893.2325152.0058.77合計3246.97339.7082502.00162.30

從上述試驗結(jié)果可以看出，ESGA經(jīng)過近50代的進(jìn)化即搜索到了最大利潤方案，該方案共需要安排3輛公交車，共響應(yīng)了82名乘客的出行需求，響應(yīng)率達(dá)82%，車輛載客率分別為55%、87.5%和62.5%，均達(dá)到了50%以上，企業(yè)可獲得的總利潤為162.30元。

圖7 行駛路徑Figure 7 The routing of driving

為了對比ESGA與RWSGA的優(yōu)劣，在同一初始種群的條件下，對精英種群為5%、10%、15%和20%的ESGA和RWSGA分別進(jìn)行了20次獨(dú)立重復(fù)試驗。統(tǒng)計每種算法的運(yùn)行時間和最優(yōu)值的平均值和標(biāo)準(zhǔn)差如表 4所示。并選取結(jié)果最好的試驗作進(jìn)化曲線對比圖如圖8所示。

表4 算法對比Table4Algorithmcomparison運(yùn)行時間/s最優(yōu)值/元RWSGA平均值5.37124.47標(biāo)準(zhǔn)差0.6214.6ESGA(5%)平均值7.09145.37標(biāo)準(zhǔn)差0.2310.42ESGA(10%)平均值6.86148.02標(biāo)準(zhǔn)差0.2011.82ESGA(15%)平均值6.49156.36標(biāo)準(zhǔn)差0.828.02ESGA(20%)平均值7.02154.35標(biāo)準(zhǔn)差0.438.21

圖8 進(jìn)化曲線對比Figure 8 Evolution curve comparison

從上述結(jié)果中可以看出，ESGA雖然會少量增加算法的運(yùn)行時間，但ESGA均在50代以內(nèi)就可以搜索到最優(yōu)方案；RWSGA需要50代以上才能收斂，并且還未搜索到最優(yōu)解。因此，在收斂速度和搜索結(jié)果上，ESGA均優(yōu)于RWSGA，證實(shí)了ESGA求解DRT路徑規(guī)劃的有效性，其中精英種群的規(guī)模設(shè)為15%左右求解結(jié)果較好。

4 結(jié)論

本文通過對DRT進(jìn)行研究并建立了數(shù)學(xué)模型，通過K-means算法實(shí)現(xiàn)公交停靠站點(diǎn)規(guī)劃，并提出了基于ESGA的公交線路規(guī)劃，并進(jìn)行了100名乘客需求的實(shí)例試驗，得出以下結(jié)論：

a.在利潤最大的方案下，企業(yè)需要規(guī)劃3條公交線路路徑，響應(yīng)82人的需求，最大可獲得利潤為162.30元；

b.ESGA在50代以內(nèi)就可以搜索到最優(yōu)方案，相比于RWSGA具有更快的收斂速度和更好的搜索結(jié)果，其中精英種群的規(guī)模設(shè)為15%左右時，求解結(jié)果更好。