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

0 引言

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

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

1 DRT規(guī)劃模型

1.1 問(wèn)題描述

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

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

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

② 每一局部區(qū)域的乘客需要到最近的臨時(shí)停靠點(diǎn)乘車(chē)；

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

④ 每輛公交車(chē)只開(kāi)行一次，每個(gè)停靠點(diǎn)只能被公交車(chē)訪(fǎng)問(wèn)一次。

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

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

N：表示公交車(chē)停靠站點(diǎn)總數(shù)量(n=1，2，……，N)；

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

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

cf：表示車(chē)輛固定成本；

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

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個(gè)乘客在第i個(gè)站點(diǎn)乘車(chē)(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表示車(chē)輛k從站點(diǎn)i行駛到站點(diǎn)j，否則xijk=0，(i，j=0，1，2，…，N，N+1；k=1，2，…，K)；

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

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

1.2 建立模型

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

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

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

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

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

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

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

2.2.1編碼

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

2.2.2適應(yīng)度計(jì)算

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

fitness(xi)=Zi

(9)

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

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

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

2.2.4交叉算子

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

在個(gè)體0-1-3-4-5-0-2-8-0-6-7和0-3-6-2-0-5-7-1-0-8-4中隨機(jī)選擇2個(gè)車(chē)輛路徑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個(gè)個(gè)體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è)計(jì)變異算子可以提高算法局部搜索能力。由于受約束條件(3)和(4)的限制，可隨機(jī)選擇2個(gè)停靠站點(diǎn)交換其位置。如，對(duì)于個(gè)體0-1-3-4-5-0-2-8-0-6-7，隨機(jī)選擇2個(gè)站點(diǎn)4和8，通過(guò)變異操作得到0-1-3-8-5-0-2-4-0-6-7。

2.2.6反轉(zhuǎn)算子

反轉(zhuǎn)算子本質(zhì)上也是一種變異策略，可以提高算法局部搜索能力。例如，對(duì)于個(gè)體0-1-3-4-5-0-2-8-0-6-7，隨機(jī)選擇一段路徑0-1-3-4-5，其通過(guò)反轉(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類(lèi)確定公交停靠站點(diǎn)，如圖5所示；然后根據(jù)乘客支付意愿確定每個(gè)站點(diǎn)的上車(chē)人數(shù)，如表2所示。

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

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

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

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

表2 公交?？奎c(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)化曲線(xiàn)Figure 6 Evolutionary Curve

表3 計(jì)算結(jié)果Table3 Calculationresults公交車(chē)路徑行駛里程成本/元乘客數(shù)量/人收入/元利潤(rùn)/元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合計(jì)3246.97339.7082502.00162.30

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

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

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

表4 算法對(duì)比Table4Algorithmcomparison運(yùn)行時(shí)間/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)化曲線(xiàn)對(duì)比Figure 8 Evolution curve comparison

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

4 結(jié)論

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

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

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