改進(jìn)人工蜂群算法的農(nóng)村DRT路徑優(yōu)化研究

靳文舟，鄧欽原，郝小妮，朱子軒

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

0 引言

在大多數(shù)農(nóng)村地區(qū)，出行需求密度偏低且分布分散，導(dǎo)致常規(guī)公交運(yùn)營效率低下。針對常規(guī)公交模式在農(nóng)村地區(qū)運(yùn)營的局限性，研究者提出在農(nóng)村地區(qū)推行需求響應(yīng)公交模式(demand responsive transit，DRT)，需求響應(yīng)公交模式可以動態(tài)地改變出行路線和時間表，更靈活地為農(nóng)村居民提供精準(zhǔn)出行服務(wù)。

近年來，對于DRT的研究正在逐步深入。Daganzo[1]首次提出了可變線路公交(需求響應(yīng))系統(tǒng)；Amirgholy等[2]建立了分析模型,用來近似求解DRT系統(tǒng)運(yùn)行的動態(tài)需求成本和總的廣義成本。Diana等[3]通過對比分析發(fā)現(xiàn)需求響應(yīng)式系統(tǒng)在低需求水平地區(qū)表現(xiàn)最佳。Dantzig等[4]最早提出車輛路徑問題，采用線性規(guī)劃可得到近似最優(yōu)解。Sánchez-oro等[5]提出一種求解多目標(biāo)開放車輛路徑問題的廣義變鄰域搜索方法。Gu等[6]研究了一種考慮時間效率的多車輛段車輛路徑規(guī)劃問題，并利用改進(jìn)人工蜂群算法求解。人工蜂群算法(artificial bee colony algorithm，ABC算法)是由Karaboga等[7]提出的一種基于蜂群智能行為的優(yōu)化算法。毛聲等[8]提出了一種雙重進(jìn)化人工蜂群算法，提高了搜索效率且不易陷入局部最優(yōu)解。自適應(yīng)大鄰域搜索算法在車輛路徑問題的研究中，最早由Ropke等[9]用于解決帶有時間窗和預(yù)定線路的同時接送問題。此外，魏占陽等[10]通過自適應(yīng)大鄰域搜索算法對車輛路徑問題模型進(jìn)行了改進(jìn)和優(yōu)化。

目前的DRT模式研究[11-12]并未考慮農(nóng)村客運(yùn)出行需求的特殊運(yùn)行規(guī)律和同時接送模式。本文基于農(nóng)村地區(qū)客運(yùn)出行的實(shí)地調(diào)查結(jié)果，構(gòu)建了考慮同時接送農(nóng)村乘客的DRT問題模型，并用實(shí)例驗(yàn)證了模型和算法的可行性。

1 模型構(gòu)建

1.1 問題描述

本文對某地進(jìn)行了為期2個月的出行情況調(diào)查，共3 013份問卷，其中有效問卷為2 301份。結(jié)果顯示，在某地農(nóng)村地區(qū)出行需求量很小，人均出行率為0.97次/d，遠(yuǎn)低于中心城區(qū)平均出行率。在出行方式結(jié)構(gòu)上，公共交通總占比僅為0.48%。相對于中心城區(qū)，農(nóng)村地區(qū)需求密度偏低，且需求比較分散。另外，公共交通在出行方式中占比很小，表明了常規(guī)公交在這類地區(qū)面臨的運(yùn)營困境。

調(diào)查顯示，某地村級范圍的出行是農(nóng)村居民最重要的出行路徑，頻率高達(dá)71.6%。此外，農(nóng)村居民的出行特征具有往返的性質(zhì)。出行頻率最高為6次/d，頻率為2次/d的出行占比最大，為60%。顯然，農(nóng)村居民的出行頻率以偶次出行居多。因此，在本文模型構(gòu)建中，參照物流研究中的同時取送貨方式和需求響應(yīng)公交在低需求密度地區(qū)的研究[13-14]提出需求響應(yīng)公交模型的同時接送模式，如圖1所示。

圖1 需求響應(yīng)同時接送模式Figure 1 Demand response simultaneous pick-up and delivery mode

研究場景設(shè)置如下：在農(nóng)村地區(qū)，通過網(wǎng)上預(yù)約獲得居民的出行需求，然后實(shí)時規(guī)劃農(nóng)村居民的需求響應(yīng)公交線路。需求響應(yīng)公交線路規(guī)劃包含一個中心車場，以及從車場中衍生的連接到不同的需求點(diǎn)的不同路線。車輛線路的起訖點(diǎn)均為中心車場。

普通需求響應(yīng)模型一般只考慮單一的接乘客或送乘客，然而，在實(shí)際情況中，由于農(nóng)村居民出行具有往返的特性，不能將農(nóng)村DRT模式簡單地當(dāng)作普通需求響應(yīng)模型處理。在規(guī)劃需求響應(yīng)線路時應(yīng)考慮實(shí)現(xiàn)同時接送農(nóng)村居民，因此，本文提出了一種需求響應(yīng)公交同時接送模式。需求響應(yīng)同時接送模式，是指需求響應(yīng)公交車輛在一次完整的運(yùn)輸過程中，包含接收乘客和送達(dá)乘客，即車輛在同一地點(diǎn)同時服務(wù)上車需求點(diǎn)和下車需求點(diǎn)。

對于此類農(nóng)村地區(qū)需求響應(yīng)式公交模式問題，可以用一個實(shí)時的包含同時接送條件的車輛路徑問題模型來解決。

1.2 模型構(gòu)建

該農(nóng)村地區(qū)DRT的同時接送車輛路徑問題模型(the simultaneous pick-up and delivery vehicle routing problem，SPDVRP)包含的基本參數(shù)如表1所示。

表1 SPDVRP模型相關(guān)參數(shù)Table 1 Related parameter of SPDVRP model

模型中運(yùn)輸總成本包含：車輛固定成本、可變運(yùn)輸成本和時間窗懲罰成本，其中時間窗懲罰成本包含停留懲罰成本和延遲到達(dá)懲罰成本。模型表達(dá)式為

(1)

(2)

s.t.:

(3)

(4)

(5)

(6)

(7)

QRPk≤QPk；

(8)

gPjk=QRPk-qPj+pPj；

(9)

gPjk=gPik-qPj+pPj；

(10)

gPjk≤QPk；

(11)

max{qPj,pPj}≤QPk；

(12)

si+fi+tij-M(1-Xijk)≤sj；

(13)

Xijk=0,1；

(14)

Xk=0,1。

(15)

式中：?i=0；?j∈H；?P∈H；?k∈V。其中，式(1)是模型的目標(biāo)函數(shù)，T(t)表示其時間窗懲罰成本函數(shù)；式(2)是函數(shù)T(t)的具體表達(dá)式，其包含停留懲罰成本和延遲到達(dá)懲罰成本兩部分；式(3)表示每一條車輛路徑起點(diǎn)和終點(diǎn)均為中心車場；式(4)表示車輛路徑的連續(xù)性，進(jìn)出某一需求響應(yīng)點(diǎn)的車輛必須為同一車輛；式(5)、(6)表示每一個需求響應(yīng)點(diǎn)只被一輛車服務(wù)；式(7)表示某一車輛k在離開車站時的需要送達(dá)目的地的乘客數(shù)QRPk的計(jì)算；式(8)表示對于某一車輛k在離開車站時，車輛內(nèi)乘坐的乘客數(shù)不能超過該車輛k的最大乘客數(shù)限制；式(9)、(10)表示某一車輛k在離開某一個需求響應(yīng)點(diǎn)j時的車內(nèi)剩余乘客數(shù)量；式(11)表示對于某一車輛k在離開某一個需求響應(yīng)點(diǎn)j時的乘客數(shù)限制，不能超過該車輛k的最大乘客數(shù)限制；式(12)表示任一需求響應(yīng)點(diǎn)的接送乘客的數(shù)量均要滿足車輛的最大乘客數(shù)限制；式(13)確保在規(guī)劃路徑中滿足車輛行駛、需求響應(yīng)點(diǎn)服務(wù)耗時的時間窗約束；式(14)、(15)為0～1整數(shù)限制。

2 自適應(yīng)大鄰域人工蜂群求解算法設(shè)計(jì)

自適應(yīng)大鄰域人工蜂群算法采用兩階段嵌套算法模型。針對人工蜂群算法中由于同類蜜蜂缺乏交流而導(dǎo)致的易陷入局部最優(yōu)解的缺陷，在算法的雇傭蜂階段，嵌套采用ALNS算法進(jìn)行鄰域搜索，在搜索大鄰域過程中盡可能多地探索解空間。

2.1 編碼方式

首先假設(shè)例子中需求點(diǎn)的數(shù)量為N(由1～N之間的N個整數(shù)，表示各需求點(diǎn))，可行解中路徑數(shù)量為M，那么就有長度為N+M+1的向量表示其中的一個解[15]。其次，有M+1個0來表示每條路徑的起訖點(diǎn)，即中心車場。

如圖2所示，圖中2個0之間的字符表示車輛到達(dá)不同需求點(diǎn)的路徑順序。在這個解中，N=7，M=3。第1條路徑0—4—1—0表示車輛從中心車場出發(fā)，依次經(jīng)過需求點(diǎn)4、1，最后回到中心車場。同理，該解中第2、3條路徑具備相似的路徑過程。

圖2 編碼示意圖Figure 2 Coding diagram

2.2 人工蜂群算法算子

人工蜂群算法通過連續(xù)派出雇傭蜂、跟隨蜂和偵察蜂來尋找最優(yōu)解。

雇傭蜂搜索開發(fā)食物源，食物源的個數(shù)(N)和雇傭蜂逐一對應(yīng)。用xi=(xi1,xi2,…,xiD)表示第i個食物源(i=1,2,…,N),其中D表示搜索空間的維數(shù)[16-17]。雇傭蜂搜索對應(yīng)的食物源后記錄食物源優(yōu)劣程度，回到巢穴后把這些信息共享給跟隨蜂。雇傭蜂搜索時在食物源的鄰域生成一個候選食物源為

vij=xij+rij(xij-xkj)。

(16)

式中：j∈{1，2，…，D}；k∈{1，2，…，N}，且k≠i；rij是[-1，1]上均勻分布的隨機(jī)數(shù)。

跟隨蜂根據(jù)食物源的適應(yīng)值確定更優(yōu)的食物源進(jìn)一步開采[16-17]。其適應(yīng)值表示為

(17)

跟隨蜂以輪盤賭的方式選擇相應(yīng)的食物源進(jìn)行進(jìn)一步的開采。食物源選擇的概率為

(18)

當(dāng)在某個食物源附近搜索多次都找不到更好的食物源(達(dá)到最大食物源連續(xù)搜索次數(shù)Lmax)，則轉(zhuǎn)化產(chǎn)生新的偵察蜂尋找新的食物源代替該食物源[18]。食物源生成規(guī)律為

(19)

2.3 ALNS算法算子

ALNS算法給每個移除和重建算子賦予一個權(quán)重，權(quán)重決定算子被選擇的概率，且在搜索過程中可以根據(jù)解的優(yōu)劣自適應(yīng)地調(diào)整[19-20]。

ALNS算法在搜索過程中可以有多個移除和重建方式。根據(jù)求解情況反饋，動態(tài)地選擇其中的一種移除或重建方式來操作[21]。

Step1移除算子,從當(dāng)前解中刪除部分食物源節(jié)點(diǎn)，得到破壞解[22]。移除算子1：隨機(jī)刪除，隨機(jī)選擇一個食物源節(jié)點(diǎn)進(jìn)行刪除。移除算子2：鄰近刪除，選擇距離候選食物源最近的一個食物源節(jié)點(diǎn)進(jìn)行刪除。

Step2重建算子,將未搜索過的食物源節(jié)點(diǎn)以及刪除的食物源節(jié)點(diǎn)插入破壞解中，得到新解[22]。重建算子1：隨機(jī)插入，隨機(jī)選擇任務(wù)池中的食物源節(jié)點(diǎn)進(jìn)行插入，產(chǎn)生新的解。重建算子2：最優(yōu)貪婪插入，每次都選擇任務(wù)池中適應(yīng)值最高的食物源節(jié)點(diǎn)插入破壞解，從而得到更優(yōu)的新解。

2.4 改進(jìn)的自適應(yīng)大鄰域人工蜂群算法流程

Step1初始化階段，隨機(jī)生成一組初始解。

Step2雇傭蜂階段，計(jì)算每個食物源的適應(yīng)值fiti，之后內(nèi)部采用ALNS算法進(jìn)行鄰域搜索：①初始化權(quán)重，并在權(quán)重的基礎(chǔ)上隨機(jī)生成移除算子和重建算子；②ALNS移除操作；③ALNS重建操作。

Step3跟隨蜂階段，跟隨蜂通過輪盤賭的方式，按食物源概率pi選擇相應(yīng)的食物源開采。

Step4偵察蜂階段，當(dāng)達(dá)到最大食物源連續(xù)搜索次數(shù)Lmax時，按式(19)尋找新的食物源。

Step5記錄當(dāng)前最優(yōu)食物源，并令迭代次數(shù)C=C+1。

Step6判斷C是否大于等于Cmax，若是，則輸出最優(yōu)解；否則，轉(zhuǎn)到Step 2重新開始循環(huán)。

圖3 算法流程圖Figure 3 Algorithm flow chart

3 算例分析

某地全縣17個鄉(xiāng)鎮(zhèn)、280個行政村，居民調(diào)查顯示農(nóng)村居民對于公交的需求在提升，同時對于需求響應(yīng)公交的接受度也比較高。

算例選擇在某地東部農(nóng)村地區(qū)設(shè)置了7個需求響應(yīng)點(diǎn)(包括5個行政村需求點(diǎn)、1個客運(yùn)站需求點(diǎn)和1個學(xué)校需求點(diǎn))，設(shè)置1個中心車場。車輛平均時速為40 km/h，單位運(yùn)輸成本為1元/km，最大運(yùn)輸距離為300 km，每次運(yùn)輸均有相應(yīng)的時間窗限制。車輛裝載人數(shù)限制為15人，車輛的固定成本為50元/d。其中，中心車場信息和需求響應(yīng)點(diǎn)信息如表2所示，為了滿足公交實(shí)際運(yùn)營與數(shù)據(jù)計(jì)算的直觀性，根據(jù)經(jīng)緯度坐標(biāo)和實(shí)際距離的歐幾里德度量建立相應(yīng)坐標(biāo)系，表2中的坐標(biāo)位置信息是換算后的信息。中心車場為厚埔停保場。

表2 中心車場和需求響應(yīng)點(diǎn)信息Table 2 The information of central depot and demand response point

需要代入SPDVRP模型中的需求響應(yīng)點(diǎn)的詳細(xì)參數(shù)信息如表3所示。

表3 需求響應(yīng)點(diǎn)的參數(shù)信息Table 3 Parameter information of demand response point

人工蜂群算法預(yù)設(shè)蜂群規(guī)模為400，其中雇傭蜂規(guī)模為200，觀察蜂規(guī)模為200。偵查蜂偵查閾值為30，自適應(yīng)大鄰域人工蜂群算法的終止條件迭代次數(shù)為1 000次。

從圖4求解迭代的情況可以看出，自適應(yīng)大鄰域人工蜂群算法在第50次左右開始快速收斂。在迅速收斂后，從第50～100次陸續(xù)出現(xiàn)明顯的跳躍式進(jìn)化過程，這是自適應(yīng)大鄰域人工蜂群算法在雇傭蜂階段進(jìn)行新的自適應(yīng)鄰域搜索。

圖4 自適應(yīng)大鄰域人工蜂群算法求解迭代情況Figure 4 Iteration of adaptive large neighborhood search artificial bee colony algorithm

最終的模型求解結(jié)果為：需求響應(yīng)公交車輛調(diào)度共安排2條需求響應(yīng)線路，分別是0—3—7—4—0和0—5—1—2—6—0，運(yùn)行軌跡如圖5所示。

圖5 自適應(yīng)大鄰域人工蜂群算法求解結(jié)果的運(yùn)行軌跡Figure 5 Adaptive large neighborhood search artificial bee colony algorithm solution result trajectory

為了深入分析計(jì)算結(jié)果的優(yōu)劣程度，利用MATLAB編程工具分別采用遺傳算法和ALNS算法對同一算例模型進(jìn)行求解，求解迭代結(jié)果分別如圖6、7所示。

圖6 遺傳算法求解迭代情況Figure 6 Iteration of genetic algorithm

從圖4、6、7所示算法的求解迭代情況來看，自適應(yīng)大鄰域人工蜂群算法的收斂速度最快，其次是遺傳算法。ALNS算法在第50～100次開始逐步收斂，但在第100次之后收斂速度減緩，出現(xiàn)波動，導(dǎo)致迭代的收斂速度和計(jì)算精度下降。

從表4的求解結(jié)果對比情況來看，自適應(yīng)大鄰域人工蜂群算法比其他2種算法在成本均值、迭代計(jì)算的標(biāo)準(zhǔn)差上效果更優(yōu)。在優(yōu)化效果上，自適應(yīng)大鄰域人工蜂群算法具有較大的優(yōu)勢，最優(yōu)成本均值僅為114.946元，比遺傳算法結(jié)果低9%，比ALNS算法低3%?？傮w而言，自適應(yīng)大鄰域人工蜂群算法在解決這類農(nóng)村地區(qū)需求響應(yīng)公交問題時有更好的優(yōu)化效果。在迭代計(jì)算的精度方面，自適應(yīng)大鄰域人工蜂群算法迭代計(jì)算的標(biāo)準(zhǔn)差為0.942，比遺傳算法低22%。在求解速度上，自適應(yīng)大鄰域人工蜂群算法也具有明顯優(yōu)勢，計(jì)算耗時僅268.601 s。

圖7 ALNS算法求解迭代情況Figure 7 Iteration of adaptive large neighborhood search algorithm

表4 不同算法結(jié)果對比Table 4 Comparative of the results of different algorithms

4 結(jié)論

算例分析結(jié)果顯示，在農(nóng)村低需求密度的環(huán)境下，農(nóng)村DRT同時接送模型更具實(shí)用性與現(xiàn)實(shí)意義。采用這一模型既能精準(zhǔn)滿足農(nóng)村居民出行需求，又能有效控制運(yùn)輸成本、提高路徑優(yōu)化效果。自適應(yīng)大鄰域人工蜂群算法具有收斂速度快、計(jì)算精度高的特點(diǎn)。與遺傳算法相比，自適應(yīng)大鄰域人工蜂群算法在解決農(nóng)村DRT問題時有更好的表現(xiàn)。與ALNS算法相比，自適應(yīng)大鄰域人工蜂群算法在繼承了ALNS算法優(yōu)點(diǎn)的同時，在算法收斂速度和結(jié)果的優(yōu)劣性上更有優(yōu)勢。本文模型為需求響應(yīng)公交模式在農(nóng)村地區(qū)的應(yīng)用與探索提供了一種思路，關(guān)于本文算法在其他領(lǐng)域的應(yīng)用還有待進(jìn)一步拓展。