基于ESGA的純電動需求響應公交路徑規(guī)劃

郭獻超,夏戈松,徐士偉,陳興博

(1.廣州市交通規(guī)劃研究院,廣東 廣州 510000; 2.華南理工大學土木與交通學院,廣東 廣州 510000; 3.廣東省交通運輸規(guī)劃研究中心,廣東 廣州 510000)

近年來隨著中國經(jīng)濟的快速發(fā)展和城鎮(zhèn)化的加快,機動車輛迎來了爆發(fā)式增長,大量農(nóng)村人口進入城市,城市的交通壓力越來越大,雖然城市公共交通進入快速發(fā)展時期,但仍無法滿足市民便捷出行的需求。如今,我國的公共交通已經(jīng)進入了高速發(fā)展軌道,出現(xiàn)了各種各樣的交通方式,乘客的出行需求也各不相同,越來越傾向個性化發(fā)展的趨勢。需求響應公交的出現(xiàn)滿足了許多乘客的要求,迎來了快速發(fā)展的契機。通過對純電動需求響應公交路徑規(guī)劃的研究,可以進一步完善我國公共交通體系,增加公共交通的多樣性,擴大公共交通的覆蓋面和提高乘客對公共交通的滿意度。

我國對需求響應公交的研究開始的較晚,國內(nèi)缺乏需求響應公交的研究內(nèi)容,尤其是純電動騎車在需求響應公交的應用研究。Lajunen[1]模擬了不同公交線路,通過對混合動力公交和純電動公交車能量消耗分析,計算出了它們在運營中的成本效益;李軍等[2]根據(jù)純電動公交車的特點,考慮了充電時間、電池狀態(tài)、充電速率等因素,設(shè)計了以營運車輛數(shù)最小為目標的純電動公交車輛調(diào)度算法;楊揚等[3]應用整數(shù)規(guī)劃、網(wǎng)絡流等基本理論,將純電動公交調(diào)度計劃問題轉(zhuǎn)換為網(wǎng)絡模型,通過使用列生成方法對模型進行求解;Schilde等[4]研究了不同速度下對DRT服務水平的影響;潘述亮等[5]對包含特殊需求的DRT模型進行了研究;盧小林等[6]提出一種以最小化公交車運營時間為目標的DRT路徑優(yōu)化模型;Masmoudi等[7]研究了異質(zhì)車輛的DAR的路徑規(guī)劃問題,提出了一種針對已知DAR問題特性的混合遺傳算法;Masmoudi等[8]建立了以總路徑成本最小化為目標的混合整數(shù)非線性規(guī)劃模型;鄭漢等[9]構(gòu)建需求響應公交服務定制等價分解模型,采用分布式列生成算法對模型進行求解;柳伍生等[10]提出了多需求響應機制下的城市綠色定制公交線網(wǎng)優(yōu)化模型,利用上車線網(wǎng)和下車線網(wǎng)相結(jié)合的分層線網(wǎng)算法對模型進行求解。目前國內(nèi)外研究主要集中在傳統(tǒng)公交的研究中,隨著電動車的推廣,許多城市都將常規(guī)公交換成了電動公交,然而有關(guān)電動公交應用在DRT的研究卻很少。

純電動需求響應公交路徑規(guī)劃可分為臨時?？空疽?guī)劃和路徑規(guī)劃兩階段,首先規(guī)劃純電動公交臨時停靠站點,通常通過K-means算法實現(xiàn)[11]。對公交路徑規(guī)劃可看作是一種特殊形式的帶有容量約束的車輛路徑問題(CVRP,capacitated vehicle routing problem),不同的是公交車需要從同一場站出發(fā)到達同一目的地,目的地與出發(fā)地往往不同。車輛路徑規(guī)劃已被證實為NP(non-deterministic polynomial)完全問題,通常設(shè)計啟發(fā)式算法[12-14]求解。遺傳算法(GA,genetic algorithm)是通過模擬生物在自然環(huán)境中的遺傳和進化過程而設(shè)計,是一種廣泛使用的啟發(fā)式搜索算法,其選擇策略通常是基于輪盤賭(RWSGA,roulette wheel selection genetic algorithm)的概率選擇。為了提高算法收斂速度和搜索結(jié)果,提出以精英選擇遺傳算法[15](ESGA,elitist selection genetic algorithm)求解純電動需求響應公交路徑規(guī)劃問題,并通過實例驗證猜想。

1 問題描述和模型建立

1.1 問題描述

純電動公交車需求響應式公交路徑優(yōu)化問題可描述如下:在研究的區(qū)域內(nèi),通過調(diào)度公交場站若干輛相同的純電動公交車以滿足該區(qū)域乘客的出行需求,所有乘客會在預先規(guī)劃好的區(qū)域上車,并到達同一終點站。通過合理規(guī)劃公交車的行駛路徑,以實現(xiàn)企業(yè)利潤的最大化。該問題屬于帶有軟時間窗的車輛路徑問題(VRPSTW),主要分兩個部分進行處理。

第一部分為需求響應站點規(guī)劃,根據(jù)乘客的響應點的位置分布,規(guī)劃若干需求響應站點,用于使需求響應公交車停車接收上車的乘客,并根據(jù)站點乘客的期望上車時間分布,確定需求響應站點的時間窗。

第二部分為純電動公交車路徑規(guī)劃,根據(jù)已規(guī)劃的需求響應站點,規(guī)劃需求響應公交車的行駛路徑,這一部分可以看作帶有軟時間窗的車輛路徑問題,但是由于純電動公交車的特殊性,在路徑規(guī)劃的過程中,需要根據(jù)純電動公交車的續(xù)航狀態(tài),合理安排公交車到充電樁的充電策略。為了方便模型建立和求解,有以下基本假設(shè):

(1) 假設(shè)純電動公交車不會載送乘客駛?cè)氤潆姌冻潆?

(2) 假設(shè)配送車輛為相同車型的純電動公交車,最大載客量相同、單次充電行駛里程相同;

(3) 假設(shè)配送車輛為相同車型的純電動公交車,最大載客量相同、單次充電行駛里程相同;

(4) 假設(shè)從場站發(fā)出的純電動公交車只有兩種:第1種是純電動公交車發(fā)出前已經(jīng)充滿電(即k≤P0);第2種是純電動公交車需要到場站附近的充電樁(即h=n+1)完成快速充電后再發(fā)車(即k>P0);

(5) 假設(shè)在所研究的網(wǎng)絡上分布若干充電樁能夠滿足純電動公交車的充電需求;

(6) 假設(shè)每輛公交車都只從固定的站場出發(fā),完成所有乘客的接收后,到達統(tǒng)一的目的地;

(7) 假設(shè)公交車只在臨時?？空就＼?每一區(qū)域的乘客需要到最近的臨時?？空境塑?

(8) 假設(shè)每輛公交車只開一條線路,每個停靠點只能被公交車訪問一次。

基于以上對純電動需求響應式公交路徑規(guī)劃問題的描述和對模型構(gòu)建的假設(shè),為方便建立純電動需求響應公交路徑規(guī)劃的數(shù)學模型,定義以下數(shù)學符號的含義:

p0表示公交場站充電樁的總數(shù)量;

V表示純電動公交車的集合,v={k},k=1,2,…,p,當k≤p0時,表示純電動公交車在公交場站已充滿電,即滿電量發(fā)車;當k>p0時,表示純電動公交車需要去公交場站臨近的充電樁充滿電后再發(fā)車;

S表示純電動公交車?？空镜暮霞?v={i},i=1,2,…,n;

E表示路網(wǎng)中充電樁的合集,E={j},j=1,2,…,m,j=1表示公交場站附近的充電樁,即k>p0的車輛需要先到該充電樁充電,再去接送乘客;

A表示路網(wǎng)中所有研究點的合集,即充電樁總數(shù)量、純電動公交車?？空究倲?shù)量、出發(fā)地、目的地的四者數(shù)量之和,A={h},h=0,1,2,…,n,n+1,…,n+m,n+m+1,h=0表示純電動公交車出發(fā)地,h=n+m+1表示純電動公交車目的地;

O表示乘客的集合,O={a},a=1,2,…,b;

Rk表示所有車輛的單次充電的行駛路徑集;

Lk表示所有車輛完成響應需求的行駛路徑集;

Cf表示純電動公交車的啟動成本,其與車輛行駛里程無關(guān),而與車輛開行數(shù)量有關(guān);

C0表示純電動公交車的運行成本,其與車輛單位行駛里程成正比;

ETi表示?？空军ci的時間窗上界;

LTi表示?？空军ci的時間窗下界;

C0表示純電動公交車在充電樁充電的時間;

s表示純電動公交車在行駛過程中的平均行駛速度;

Ct表示單位時間的懲罰成本;

ua表示乘客a使用需求響應公交車的意愿，ua=1表示乘客具有使用意愿,否則ua=0,a=1,2,…,b;

ea表示乘客a支付需求響應公交的意愿(元);

e0表示企業(yè)響應乘客最低支付意愿(元);

ra表示企業(yè)對乘客a出行需求的響應意愿,ra=1表示企業(yè)響應乘客需求,否則ra=0;

dij表示點i到點j的行駛距離(i,j=0,1,2,…,n,n+1,…,n+m,n+m+1);

d0表示純電動公交車充滿電后的最大行駛里程;

xijk=1表示車輛k從點i行駛到站點j,否則xijk=0(i,j=0,1,2,…,n,n+1,…,n+m,n+m+1,k=1,2,…,p);

Qi表示第i個?？空军c的上車人數(shù),i=1,2,…,n;

Q0表示需求響應公交車的最大載客量。

1.2 模型建立

純電動需求響應公交路徑規(guī)劃模型的目標函數(shù)包括總利潤和時間懲罰成本兩部分,純電動需求響應公交的成本包括運營車輛的人力成本和可變成本,收入為乘客支付的乘車票價總和,二者之差為企業(yè)的總利潤。將公交車超出時間窗的時間量化為時間函數(shù),并通過懲罰函數(shù)計入到總優(yōu)化目標中。綜上所述,純電動需求響應公交路徑規(guī)劃模型如下:

(1)

(2)

當xijk=1時,

(3)

p≤pmax,

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

xijk=0或1,

(13)

k>p0?x0,n+1,k=1,

(14)

式(2)表示純電動公交車到達臨時停靠站i超出時間窗的偏離值;式(3)表示純電動公交車到達臨時?？空緄的行程時間;式(4)表示企業(yè)可投入用于響應乘客需求的純電動公交車數(shù)量不大于場站公交車的總數(shù)量;式(5)表示純電動公交車只能在接送乘客之前駛?cè)氤潆姌冻潆?式(6)表示每輛純電動公交車的乘客數(shù)量不大于公交車的載客上限;式(7)表示每輛純電動公交車在每次充電后的行駛里程不超過其最大行駛里程;式(8)表示運營企業(yè)只響應支付意愿大于等于e0的乘客出行需求;式(10)表示每個臨時?？空军c只有唯一的一輛純電動公交車駛?cè)?式(11)表示每個臨時?？空军c只有唯一的一輛純電動公交車駛出;式(12)表示每輛純電動公交車的起點都是停車場站,終點都是乘客所要到達的目的地;式(13)表示決策變量被限制為0、1變量;式(14)表示對于未在公交場站充電的公交車,需要先去場站附近的充電樁快速充電,再去接送乘客。

2 模型求解

2.1 基于K-means算法的?？空疽?guī)劃

首先基于K-means聚類算法規(guī)劃了公交臨時?？空尽-means聚類算法可以根據(jù)樣本之間的內(nèi)在聯(lián)系,將相同的樣本劃分為一類,從而將樣本整體劃分為有不同特征的若干類。K-means聚類的基本流程是先隨機選取k個樣本作為初始的類中心點。然后計算每個樣本與各個種類中心點的距離,把每個樣本劃分為與其距離最近的類中心點。當所有樣本對象都劃分完成后,每一類的類中心點會根據(jù)類中現(xiàn)有的樣本重新計算,這個過程一直重復直到?jīng)]有中心再發(fā)生變化為止。K-means算法的基本流程如圖1所示。

圖1 K-means算法流程Fig.1 K-means algorithm flow

通過選擇歐式距離作為樣本點到類中心點的判別距離,其計算公式為

(15)

選擇點合集的重心作為每一類的中心點,其計算公式為

(16)

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

采用精英種群選擇的遺傳算法(ESGA,elitist selection genetic algorithm)來求解純電動需求響應公交路徑規(guī)劃模型,相比于常規(guī)的遺傳算法,ESGA用每一代種群中適應度較高的個體建立精英種群,精英種群不經(jīng)過選擇的操作直接進入子代種群。因此ESGA相對于常規(guī)的遺傳算法收斂速度更快,能夠更快地獲得求解結(jié)果。ESGA流程如下:

(1) 編碼 編碼是為了將需要解決的實際問題轉(zhuǎn)化為可被遺傳算法直接求解的數(shù)學形式。在現(xiàn)代生物學中,個體的基因代表著不同個體特征。相似的,在遺傳算法中經(jīng)過基因編碼的個體代表優(yōu)化目標的一組可行解。常用的編碼方案主要有0、1編碼和整數(shù)編碼兩種,本文采用整數(shù)編碼方案,并根據(jù)純電動公交車行駛路徑的實際問題設(shè)計了編碼方案。

為了解釋ESGA中編碼過程,通過實例來具體描述。首先,假設(shè)路網(wǎng)中有10個規(guī)劃的公交車臨時?？空竞?個充電樁,此外還有公交車起點和目的地2個點。編碼的具體流程如下:

步驟1:對路網(wǎng)中的點進行編號,0表示公交車起點,1～10表示臨時?？空?11～14表示充電樁;

步驟2:隨機生成1～10不重復的數(shù)列,表示公交車到達臨時?？空镜捻樞?

步驟3:在上述數(shù)列隨機插入若干個公交車的出發(fā)點0,表示需要安排調(diào)度的公交車數(shù)量;

步驟4:在上述的列序號0后面隨機插入若干充電樁編碼,表示純電動公交車需要駛?cè)氤潆姌冻潆?

步驟5:將上述的數(shù)列作為個體的基因編碼;

步驟6:重復步驟2～步驟5,形成一定規(guī)模的種群。

上述過程中個體基因編碼的示意圖如圖2所示。

圖2 染色體編碼Fig.2 Chromosome coding

(2) 適應度計算 ESGA通過選擇算子淘汰劣勢個體,保留優(yōu)勢個體,適應度為個體選擇的依據(jù),目標函數(shù)以最小化企業(yè)利潤的相反數(shù)為優(yōu)化目標,因此,使得目標函數(shù)值較小的個體具有較高的適應度。以目標函數(shù)的倒數(shù)作為計算個體的適應度函數(shù),即

(3) 基于精英保留的選擇算子 通過采用了精英個體保留的選擇策略,在每一代種群中選擇一部分適應度最高的個體,不進行任何操作而直接保留到下一代,剩下部分的個體再通過選擇得到。保留的精英個體只占種群的小部分,這是為了避免種群陷入局部最優(yōu)解。精英個體保留的選擇策略可以保證種群的適應度不會增加,加快收斂速度,從而提高最優(yōu)解的搜索速度。

(4) 交叉算子 遺傳算法使用交叉算子通過模擬種群進化中染色體的交叉重組,從而產(chǎn)生子代個體。ESGA采用的交叉算子操作流程如圖3所示。

圖3 交叉操作Fig.3 Cross operation

(5) 變異算子 遺傳算法的變異算子通過模擬種群進化中個體的基因發(fā)生突變,進而產(chǎn)生新的個體。ESGA采用兩點變異,操作流程如圖4所示。

圖4 變異算子Fig.4 Mutation operator

(6) 反轉(zhuǎn)算子 反轉(zhuǎn)算子從本質(zhì)上來說也是基因突變的一種類型,通過逆轉(zhuǎn)染色體基因片段的基因位順序,從而實現(xiàn)改變?nèi)旧w的基因。反轉(zhuǎn)算子也可以提高遺傳算法搜索能力。ESGA采用的反轉(zhuǎn)算子操作流程如圖5所示。

圖5 反轉(zhuǎn)算子Fig.5 Inversion operator

(7) 進化終止條件 從理論上來說,當搜索到最優(yōu)解時,即算法達到100%收斂時,算法會自動終止,然而在實際情況下,由于算法會陷入局部最優(yōu)很難到達100%收斂。因此,需要設(shè)計終止條件以避免算法進入無限迭代循環(huán)。遺傳算法的終止條件判別主要有以下兩種方法:

① 判定相鄰兩代種群適應度的差值小于某一閾值時終止進化。即當種群進化速度緩慢,種群進化進一步搜索到的最優(yōu)解對目標函數(shù)沒有顯著變化,繼續(xù)求解所花費的時間和資源對優(yōu)化的目標沒有顯著意義,目前的求解結(jié)果已經(jīng)可以滿足實際規(guī)劃方案了。

② 當種群進化到某一代數(shù)時終止循環(huán)。第二種方法相對第一種更便于理解和操作,可以根據(jù)結(jié)果靈活調(diào)整。因此選擇種群進化最大代數(shù)作為種群進化終止的判定條件。

3 實例分析

3.1 實驗算例

通過對某區(qū)域的公交客流點進行支付意愿調(diào)查,該區(qū)域內(nèi)有5個充電站,該區(qū)域的公交客流需求點、起終點、充電樁如圖6所示。

圖6 乘客坐標Fig.6 Passenger coordinates

3.2 求解結(jié)果

首先根據(jù)坐標信息使用K-means算法將乘客分為32類確定公交?？空军c,如圖7所示。然后根據(jù)乘客支付意愿確定每個站點的上車人數(shù),公交?？奎c信息如表1所列。

圖7 公交?？奎c規(guī)劃Fig.7 Bus stop planning

表1 公交?？奎c信息Table 1 Bus stop information table

然后基于ESGA規(guī)劃純電動需求響應公交路徑,其中種群規(guī)模為500,進化代數(shù)為1 000,精英種群比例為15%,變異概率為0.1,反轉(zhuǎn)概率為0.1,站場車輛數(shù)為14,每輛車的限載人數(shù)為30,單位時間懲罰成本為0.5元/min,車輛啟動成本司機工資為150元/輛,可變成本為0.49元/km。經(jīng)過20次的獨立重復試驗,選取最好試驗結(jié)果作為最終結(jié)果,其進化曲線、不同情況下的車輛路徑和計算結(jié)果見圖8～圖11和表2。

圖8 進化曲線Fig.8 Evolution curve

圖9 不需充電的車輛行駛路徑Fig.9 The driving path of the vehicle without charging

圖10 需要充電的車輛行駛路徑Fig.10 The driving path of the vehicle that needs to be charged

圖11 補充電能車輛行駛路徑Fig.11 Supplementary electric vehicle driving path

表2 計算結(jié)果Table 2 Calculation result table

由表2可以看出每輛公交車的實際行駛里程均在30 km左右,約為單次充電行駛里程(60 km)的一半。需求響應公交載客率均在50%以上,平均載客率為86.67%,其中11輛車的載客率在80%以上,企業(yè)的成本包括人力成本、可變成本和時間懲罰成本3部分,分別為2 100.00元、226.35元和361.97元,企業(yè)的總收入全部來源于乘客乘坐響應公交所支付的票價,共7 643元。企業(yè)的總利潤是企業(yè)的總收入減去總成本,為4 954.68元。

4 結(jié)語

通過描述純電動需求響應式公交路徑優(yōu)化問題,構(gòu)建了特定假設(shè)下的數(shù)學模型,采用ESGA算法進行問題求解,并通過實際算例驗證了ESGA算法,結(jié)果表明ESGA算法精英種群的規(guī)模設(shè)為15%左右時求解結(jié)果較好。由于研究水平有限,在對純電動需求響應公交進行路徑規(guī)劃時有部分問題沒有考慮到,存在一定的局限性和不足。今后主要從以下幾個方面進行研究和完善:

(1) 此次研究只考慮了單一的純電動車型,而企業(yè)在實際運營過程中,可以根據(jù)乘客的個性化需求和實際乘客數(shù)量來考慮同時使用多種車型,這樣可以節(jié)約運營成本，提高需求響應公交滿意度。

(2) 此次研究未考慮動態(tài)響應需求,在實際運營中會出現(xiàn)新的需求,考慮實時的動態(tài)需求不僅可以增加企業(yè)的收入,也可以為更多乘客提供需求響應服務。