面向動態(tài)公交的離散分層記憶粒子群優(yōu)化算法

黃君澤,吳文淵,李軼,石明全,王正江

(1.中國科學(xué)院重慶綠色智能技術(shù)研究院自動推理與認(rèn)知重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400714;2.中國科學(xué)院大學(xué)重慶學(xué)院人工智能學(xué)院,重慶 400714;3.重慶市鳳筑科技有限公司,重慶 401120)

0 引言

隨著信息技術(shù)基礎(chǔ)設(shè)施在交通領(lǐng)域的不斷完善,智慧交通——一種集成了信息技術(shù)與數(shù)據(jù)分析的現(xiàn)代交通系統(tǒng)也正快速發(fā)展。在運(yùn)營端,公交信息基礎(chǔ)設(shè)施如公交全球定位系統(tǒng)(GPS)、公交智能交互平臺正不斷完善;在乘客端,移動互聯(lián)網(wǎng)的發(fā)展使得乘客能將自己的需求實(shí)時(shí)提交給出行服務(wù)商。這兩點(diǎn)變化的發(fā)生使得一種名為動態(tài)公交的新型公交運(yùn)營模式成為可能,并且動態(tài)公交已經(jīng)成為了許多城市公交企業(yè)布局智慧交通的重要落腳點(diǎn)。動態(tài)公交融合了傳統(tǒng)公交和網(wǎng)約車[1]的運(yùn)營模式,乘客可以像預(yù)約網(wǎng)約車拼車模式一樣在網(wǎng)上平臺下單,告知運(yùn)營商自己的上車點(diǎn)、下車點(diǎn)和預(yù)計(jì)的上車時(shí)間,并在約定時(shí)間和約定地點(diǎn)上車,在無換乘的前提下前往目的地;但與網(wǎng)約車不同的是,前來接上乘客的不是小型轎車,而是相對較大的面包車、大客車等,并且一車可以同時(shí)接送多人。

在動態(tài)公交的運(yùn)營機(jī)制和所需考慮的運(yùn)營指標(biāo)上,已經(jīng)有了較多研究[2],運(yùn)營機(jī)制方面的改動包括添加換乘點(diǎn)[3]、設(shè)置多車場[4]、使用電動車[5]、設(shè)置充電站[6]、訂單設(shè)置軟時(shí)間窗[7]等;而運(yùn)營指標(biāo)方面包括著眼于提升居民出行滿意度、減少政府在公共交通領(lǐng)域的開支、緩解城市擁堵現(xiàn)象、降低出行帶來的碳排放等。但在對動態(tài)公交數(shù)學(xué)建模、對動態(tài)公交問題求解這兩方面的研究尚有不足。

動態(tài)公交問題從路徑規(guī)劃問題的角度而言,屬于電召問題(DARP)的一類子問題。電召問題是一種區(qū)別于車輛路徑問題(VRP),每個(gè)訂單有兩個(gè)或更多個(gè)需要依序經(jīng)過的途徑點(diǎn)的路徑規(guī)劃問題,并且在車載客量大于2人時(shí)是NP難問題[8]。而動態(tài)公交問題在電召問題的基礎(chǔ)上,要求訂單隨機(jī)生成(Stochastic)、允許根據(jù)新信息更新在途車輛的路徑(Dynamic)。需要指出的是,另一種常見的新型公交——定制公交,則是電召問題中確定訂單(Deterministic)、不允許更新在途車輛路徑(Static)的另一子類型問題,所建立的模型和使用的求解算法與動態(tài)公交存在巨大的差異。

需要指出的是,本文提出的動態(tài)公交問題具有一定的特殊性:1)動態(tài)公交問題的解空間是離散空間,這使得在連續(xù)問題上的求解算法不適用,并且動態(tài)公交問題的解由兩個(gè)子問題的解構(gòu)成,還存在大量相似或相同的子問題;2)動態(tài)公交問題的離散狀態(tài)較多,動態(tài)公交問題中車輛數(shù)、可訪問點(diǎn)數(shù)和訂單數(shù)決定了動態(tài)公交問題的解空間的大小,在實(shí)際問題中,相較于之前的研究,這三者都較多,因此離散狀態(tài)較多,許多算法無法很好地進(jìn)行求解;3)動態(tài)公交問題的實(shí)時(shí)性要求較高。在動態(tài)公交問題的實(shí)際應(yīng)用中,以本文后續(xù)實(shí)驗(yàn)所選定區(qū)域?yàn)槔?高峰期訂單數(shù)平均可達(dá)180個(gè)/min,而服務(wù)器需要在一定時(shí)間內(nèi)為用戶反饋計(jì)算結(jié)果。

目前,電召問題求解算法可以分為求精確解算法與啟發(fā)式算法兩大類,其中多數(shù)算法不能滿足上述動態(tài)公交問題的具體要求。求精確解算法以分支定界法[3]和約簡法[9]及其變種為主,但目前,求精確解算法的計(jì)算復(fù)雜度都較高,因而可解決問題規(guī)模較小,一般僅能解決使用車輛數(shù)在10車以內(nèi)、訂單數(shù)在100單以內(nèi)的問題[10],不能滿足上述實(shí)時(shí)性的要求,難以在現(xiàn)實(shí)場景中應(yīng)用。啟發(fā)式算法包括神經(jīng)網(wǎng)絡(luò)[11]、仿生算法[12]、插入算法[13]、模擬退火算法[6,14]、多方逼近算法[15]、禁忌搜索(Tabu Search)算法[3,16]、變鄰域搜索(VNS)算法[4]和大鄰域搜索(ALNS)算法[5,13]等,當(dāng)解空間離散且離散狀態(tài)較多時(shí),大多數(shù)啟發(fā)式算法對初始解高度敏感,并且都會面對探索和利用的平衡問題。

由于現(xiàn)有算法都存在一定的問題,因此有必要探索新的求解算法。在求解優(yōu)化問題時(shí),粒子群優(yōu)化(PSO)算法是一種被長期驗(yàn)證有效和使用的算法。PSO算法是一種將問題的解視為粒子,并使多個(gè)粒子依一定規(guī)則相互作用以探索解空間、尋找最優(yōu)解的優(yōu)化算法。國內(nèi)早在2004年就有基于PSO算法求解多目標(biāo)問題的研究[17],并一直得到研究者的廣泛關(guān)注[18-19]。在連續(xù)空間下,PSO算法的參數(shù)設(shè)置和改進(jìn)方向[20]都較為成熟,但相關(guān)的研究無法簡單地套用在離散空間PSO算法上[21]。

在路徑規(guī)劃領(lǐng)域,PSO算法也長期得到廣泛的研究與應(yīng)用。國內(nèi)同樣于2004年就有學(xué)者研究了PSO算法求解車輛路徑問題[22],王飛在帶時(shí)間窗的車輛調(diào)度問題上應(yīng)用了改進(jìn)的PSO算法[23],近期的車輛路徑問題綜述[24]中也對PSO算法近年來的研究進(jìn)行了總結(jié)。在面對多目標(biāo)問題時(shí),PSO算法也展現(xiàn)出了較好的適用性[19,25]。然而,目前較少有將PSO算法應(yīng)用到動態(tài)公交問題上的研究[21]。

原始的PSO算法不能較好地適用于動態(tài)公交問題,有以下原因:1)在粒子群迭代的過程中,多個(gè)粒子會重復(fù)計(jì)算相同或相似訂單集的最優(yōu)路徑,造成冗余計(jì)算;2)相對于其他啟發(fā)式算法,PSO算法較為不依賴初始解,但優(yōu)質(zhì)的初始解也可以幫助算法快速收斂;3)PSO算法在離散空間存在容易早熟的問題。

針對以上問題,基于相關(guān)領(lǐng)域的研究現(xiàn)狀,結(jié)合動態(tài)公交問題的解的形式的特點(diǎn),本文提出了動態(tài)公交問題的模型,并在此基礎(chǔ)上對基礎(chǔ)的PSO算法做出了以下創(chuàng)新:

1)將PSO算法也針對性地拆分成兩層分別進(jìn)行迭代優(yōu)化,并提出可復(fù)用、可繼承的低層粒子結(jié)構(gòu),避免重復(fù)計(jì)算的開銷,提高算法的實(shí)時(shí)性。

2)提出基于出行偏好的初始解生成算法,從而利用數(shù)據(jù)生成在未來時(shí)間片更優(yōu)的初始解,同時(shí)幫助算法快速收斂。

3)引入自適應(yīng)變異機(jī)制,在離散空間上重新設(shè)計(jì)自適應(yīng)參數(shù)和變異概率,避免算法早熟,減少收斂到局部最優(yōu)的情況。

1 動態(tài)公交問題

動態(tài)公交問題是一種多車路徑規(guī)劃問題,源于動態(tài)公交這一公交運(yùn)營模式。動態(tài)公交區(qū)別于傳統(tǒng)公交,其由乘客先發(fā)起一個(gè)包含該乘客的起終點(diǎn)、上下車時(shí)間窗等信息的訂單,隨后公交公司結(jié)合訂單信息和當(dāng)前公交車輛狀態(tài)將該訂單指定到一輛公交車,由其完成該乘客的需求,并且公交車可以部分或完全不沿公交線路行駛;動態(tài)公交也區(qū)別于定制公交,其允許訂單實(shí)時(shí)發(fā)起、允許乘客期望上車時(shí)間接近發(fā)起時(shí)間,因此需要能夠?qū)崿F(xiàn)實(shí)時(shí)計(jì)算并分配訂單;動態(tài)公交還區(qū)別于網(wǎng)約車,每輛公交上可以搭載超過5名乘客,這對算法的復(fù)雜度提出了一定的挑戰(zhàn)。動態(tài)公交運(yùn)營模式示意圖如圖1所示。

圖1 動態(tài)公交運(yùn)營模式示意圖Fig.1 Schematic diagram of dynamic public transport operation mode

在動態(tài)公交問題中,每個(gè)訂單都具有兩個(gè)途徑點(diǎn),并且要求以給定的先后順序訪問這兩個(gè)途徑點(diǎn),這使得動態(tài)公交問題模型區(qū)別于傳統(tǒng)的路徑規(guī)劃問題。但在其他路徑規(guī)劃問題如旅行商問題(TSP)、車隊(duì)尋徑問題(VRP)中,也存在一些目標(biāo)函數(shù)、變量和限制條件的設(shè)置具有一定的參考價(jià)值。在過往的動態(tài)公交模型的研究中則探索了動態(tài)公交的運(yùn)營機(jī)制,包括是否設(shè)立實(shí)體站點(diǎn)、是否允許換乘[26]等。在現(xiàn)實(shí)問題中,設(shè)立實(shí)體站點(diǎn)、存在多車場[4]、允許訂單超時(shí)[11]是較為普遍的情況,并且一般不允許換乘。因此,本文所構(gòu)建模型也包括多車場,并在單目標(biāo)模型下設(shè)置了訂單時(shí)間窗。

1.1 目標(biāo)函數(shù)建模

針對動態(tài)公交所應(yīng)關(guān)注的運(yùn)營指標(biāo),也已有了較多的討論。動態(tài)公交服務(wù)有3個(gè)主要的相關(guān)方:乘客,公交服務(wù)運(yùn)營商,其他社會組織。這三方具有各自不同的關(guān)心點(diǎn):公交服務(wù)運(yùn)營商希望盡可能降低凈支出;乘客希望能接受公交服務(wù),并希望最小化自身的總出行時(shí)間;其他社會組織則希望通過推廣公共交通緩解城市擁堵和降低燃油消耗和碳排放。根據(jù)以上三方的實(shí)際關(guān)系構(gòu)建目標(biāo)函數(shù),其中:與乘客相關(guān)的指標(biāo)包括接單率、乘客候車時(shí)間和乘客在車時(shí)間3項(xiàng);與運(yùn)營方相關(guān)的指標(biāo)包括服務(wù)訂單數(shù)、所需司機(jī)工時(shí)和運(yùn)營里程3項(xiàng),其中,服務(wù)訂單數(shù)在訂單數(shù)不可控的情況下等價(jià)于接單率,司機(jī)工時(shí)與最大可用車數(shù)呈正相關(guān);其他社會組織關(guān)心的指標(biāo)包括服務(wù)訂單數(shù)、燃油消耗和碳排放量3項(xiàng),其中,服務(wù)訂單數(shù)越多,城市道路車輛數(shù)就越少,對城市擁堵現(xiàn)象的緩解就越明顯,而燃油與碳排放量一般都與運(yùn)營里程呈正比。因此,最終構(gòu)建的目標(biāo)函數(shù)旨在實(shí)現(xiàn)最大化接單率、最小化平均乘客候車時(shí)間、最小化平均乘客在車時(shí)間和最小化運(yùn)營里程,具體公式如下:

(1)

(2)

(3)

(4)

多目標(biāo)問題的求解方法主要包括引入博弈機(jī)制[11]和轉(zhuǎn)化為單目標(biāo)2種,本文將采用將多目標(biāo)問題中的目標(biāo)一部分通過加權(quán)和的方式轉(zhuǎn)化為新的單目標(biāo),另一部分轉(zhuǎn)化為約束條件的方式將動態(tài)公交問題建模為單目標(biāo)問題進(jìn)行求解。具體地,本文對上述目標(biāo)函數(shù)進(jìn)行轉(zhuǎn)化,合并式(1)與式(4),并將式(2)與式(3)轉(zhuǎn)化為約束條件,如下式所示:

(5)

(6)

(7)

本文通過新增每單收入常量、每里程代價(jià)常量合并了對接單率和里程的目標(biāo);通過新增比例約束和常量約束來限制乘客在車和等車時(shí)間。在式(5)中:po表示接受該訂單帶來的收入;co表示車輛的支出。在式(6)中:Ttravel表示訂單可接受的最長在車時(shí)間。在式(7)中:Twait表示訂單可接受的最長候車時(shí)間。這一形式下,式(6)、式(7)即一般意義上的時(shí)間窗約束。

1.2 約束條件建模

動態(tài)公交具有的訂單是動態(tài)、隨機(jī)生成的,因此動態(tài)公交的訂單分配過程也需要分時(shí)間片進(jìn)行,并且滿足訂單約束。具體到某一輛公交,其任意時(shí)刻的路徑都應(yīng)是滿足車輛路徑約束的,并且在公交往往具有多車場的現(xiàn)實(shí)背景下,公交路徑的起終點(diǎn)也應(yīng)滿足一定約束。

1.2.1 訂單約束

訂單約束包括分配約束與載客量約束。其中,分配約束表示訂單在車輛間的分配情況,載客量約束則限制車輛的最大接單數(shù)。設(shè)b載客量為vb,vo表示訂單的人數(shù),Tnow表示算法中的當(dāng)前時(shí)刻,則:

(8)

(9)

(10)

(11)

式(8)表示所有訂單都被歸入一個(gè)分配集,其中分配集0為下一時(shí)刻的待分配集;式(9)表示所有分配集間交集為空,即訂單不能重復(fù)分配;式(10)表示車輛的接受訂單集為車輛在當(dāng)前時(shí)刻之前的所有時(shí)刻的分配集的并集;式(11)表示車輛的接受集的載客量之和不能大于車輛的額定載客量。

1.2.2 車輛路徑起終點(diǎn)約束

在動態(tài)公交實(shí)際運(yùn)營過程中,在車輛沒有訂單時(shí)停靠在何處是一個(gè)具有實(shí)際意義的問題。如果要求公交每次接單后都必須回到集中停放的車場,可能會產(chǎn)生不必要的成本;但公交車輛也不能停放在任意的道路或公交車站邊,否則會引起交通堵塞。為此,根據(jù)公交運(yùn)營的實(shí)際情況,本文提出可以將部分暫時(shí)無訂單車輛臨時(shí)停放在道路邊的臨時(shí)停車位,避免車輛不必要地返回車場。此外,在新能源公交車需要充氣、充電時(shí),需要前往指定的停放點(diǎn)進(jìn)行充氣、充電。為對以上情況進(jìn)行建模,設(shè)置車輛路徑起終點(diǎn)約束。

車輛路徑具有一個(gè)起點(diǎn),是車輛當(dāng)前所處或出站車輛當(dāng)前正要前往的站點(diǎn);車輛路徑具有一個(gè)終點(diǎn),是滿足約束條件下離車輛的最后一個(gè)途徑節(jié)點(diǎn)最近的可行停放點(diǎn);車輛終點(diǎn)的約束條件包括是否需要充電、充氣、加油,以及是臨時(shí)停放還是長時(shí)間停放。

(12)

(13)

(Eb≤Elimit)=Cb

(14)

(15)

(16)

其中:路徑及其后的中括號表示路徑中的指定下標(biāo)位置的元素,下標(biāo)從0開始標(biāo)號。式(12)、式(13)表示車輛路徑起終點(diǎn),分別指車輛路徑經(jīng)過的第一個(gè)站點(diǎn)與最后一個(gè)站點(diǎn);式(14)表示當(dāng)車輛能源低于給定值時(shí),車輛需要充能;式(15)表示若車輛需要充能,則車輛路徑的終點(diǎn)需要可以為車輛提供對應(yīng)的能源補(bǔ)充;式(16)表示若車輛需要退出運(yùn)營,則車輛路徑終點(diǎn)需要支持長時(shí)間停放車輛。

1.2.3 車輛路徑約束

(17)

(18)

(19)

(20)

Lb=distance(rb)

(21)

式(17)、式(18)約束了訂單起點(diǎn)在巴士路徑中的位置;式(19)、式(20)約束了訂單終點(diǎn)在巴士路徑中的位置;式(21)表示車輛里程數(shù),即車輛全天路徑的長度。

2 離散分層記憶粒子群優(yōu)化算法

本章分為3個(gè)部分:第1個(gè)部分介紹離散空間中的動態(tài)公交問題的解的結(jié)構(gòu)及基礎(chǔ)運(yùn)算的定義;第2個(gè)部分介紹基于出行偏好的初始解生成算法,該算法首先在給定城市道路圖上生成名為路網(wǎng)的圖結(jié)構(gòu),隨后在該圖結(jié)構(gòu)上依一定規(guī)則游走產(chǎn)生符合要求的隨機(jī)路徑;第3個(gè)部分介紹分層自適應(yīng)變異記憶PSO算法,該算法基于離散空間中動態(tài)公交問題解的編輯距離動態(tài)調(diào)整粒子收斂速度、控制粒子隨機(jī)擾動的方法,同時(shí)基于對車輛種類的定義給出將粒子群分層、記憶、繼承和復(fù)用的方法。

本文算法整體流程如圖2所示,其中訂單層粒子單次迭代流程如下:對每輛車所分配到的訂單集,首先在以訂單集為鍵的路徑層解字典中檢索其對應(yīng)的粒子群;若檢索到,將對應(yīng)的粒子群進(jìn)行相對于正常次數(shù)而言較少的次數(shù)的迭代;若未檢索到,則根據(jù)2.3.1節(jié)所述規(guī)則進(jìn)行求解,并迭代正常次數(shù)。此處的迭代次數(shù)具體值為超參數(shù),本文所用迭代次數(shù)詳見3.2節(jié)實(shí)驗(yàn)參數(shù)。完成路徑層求解后,通過在路徑層解的最后一個(gè)訂單結(jié)束的站點(diǎn)最近的符合約束的停放點(diǎn)加入路徑,即可得到一個(gè)車輛的路徑及其對應(yīng)的代價(jià),由此訂單層的每個(gè)粒子可以計(jì)算得出其所對應(yīng)的所有車輛的代價(jià)和,從而可以進(jìn)行粒子位置優(yōu)劣的比較,并進(jìn)行速度和位置的更新。

圖2 分層自適應(yīng)變異PSO算法流程Fig.2 Procedure of discrete hierarchical memory PSO algorithm

2.1 動態(tài)公交問題解的結(jié)構(gòu)及運(yùn)算的定義

PSO算法在迭代過程中需要計(jì)算兩個(gè)解間的距離,但在動態(tài)公交問題中,解空間為離散空間,因此不能直接使用連續(xù)空間中對解的距離的定義[27]。本文采用定義解及對解的操作的方式解決這一問題。動態(tài)公交問題的解包括以下兩部分:訂單在車輛間的分配情況,車輛行駛路徑中對節(jié)點(diǎn)的訪問順序。設(shè)點(diǎn)全集為V,有k個(gè)可用車輛,則粒子的解S為一個(gè)包含k+1個(gè)分量的向量,其中,第一個(gè)分量D表示訂單的分配狀況,包含|O|個(gè)有k種取值的變量d;其后的k個(gè)分量Rb分別表示其右下角標(biāo)所指示的車輛經(jīng)過的點(diǎn)的序,包含l個(gè)在點(diǎn)集V中取值的變量v,l的取值范圍為0～2|O|。可將動態(tài)公交問題的解S表示如下:

S=

D={do∈D}

Rb=

由于動態(tài)公交問題中不同的解可以通過使用上述兩個(gè)算子進(jìn)行轉(zhuǎn)化,因此可以根據(jù)兩個(gè)不同解間變換所需的基礎(chǔ)操作定義解與操作算子的加減法。設(shè)V為粒子的速度,μ1、μ2分別為兩種操作的操作次數(shù),則有:

S1+μ1Reassign+μ2Insert=S2

S2-S1=μ1Reassign+μ2Insert

將兩解間變化所需基礎(chǔ)操作的次數(shù)定義為兩解間的編輯距離ΔS1,S2,則有:

ΔS1,S2=|S2-S1|=μ1+μ2

需要注意的是,由于將解S1變化為解S2所需的操作次數(shù)與將解S2變換為解S1所需的操作次數(shù)可能不一致,因此ΔS1,S2?ΔS2,S1。

2.2 基于出行偏好的初始解生成算法

本文提出基于從歷史數(shù)據(jù)中總結(jié)的出行偏好的初始解生成算法。初始解的生成關(guān)系到算法的收斂速度,并且會在很大程度上影響算法最終的收斂結(jié)果。在動態(tài)公交問題中,由于訂單生成的隨機(jī)性,當(dāng)前時(shí)間片的最優(yōu)路徑可能不利于后續(xù)訂單的接收,因此需要一定的設(shè)計(jì)來使得算法生成的路徑能盡可能地滿足未發(fā)起訂單的需求[15]。盡管在動態(tài)公交問題中訂單的生成是隨機(jī)的,但在實(shí)際場景下,這種隨機(jī)并非是無規(guī)律的。在某一地區(qū),訂單的生成一定是遵循某種規(guī)律的,這也是智慧交通領(lǐng)域研究的課題之一[28],但這種規(guī)律的探索不在本文的研究范圍之內(nèi),下述初始解生成算法將基于已有的出行偏好。出行偏好的表示形式是一個(gè)以公交站點(diǎn)為行索引和列索引的矩陣,矩陣中的元素表示行索引所對應(yīng)的公交站點(diǎn)出發(fā)到列索引所對應(yīng)的公交站點(diǎn)的出行偏好。

近年來,基于數(shù)據(jù)的預(yù)計(jì)算路徑集方法逐漸受到研究者的重視[29]。本文提出了將出行數(shù)據(jù)歸約到路網(wǎng),并通過對路網(wǎng)進(jìn)行掃描生成備選路徑集的路網(wǎng)掃描算法。該算法可以分開利用帶權(quán)路網(wǎng)上的點(diǎn)信息與邊信息,也可以將點(diǎn)信息與邊信息進(jìn)行加權(quán)綜合利用,得到符合要求的備選路徑。其中:點(diǎn)信息是指公交車打卡上車數(shù)據(jù)、住宅區(qū)居民人數(shù)、商圈人流量及蜂窩網(wǎng)絡(luò)網(wǎng)點(diǎn)使用人數(shù)等,描述一個(gè)在給定問題規(guī)模下可被抽象為一點(diǎn)的區(qū)域的與動態(tài)公交問題中需求數(shù)具有直接關(guān)系的信息;邊信息是指以各種方式統(tǒng)計(jì)或計(jì)算得到的兩服務(wù)點(diǎn)間的客流量,或出行軌跡數(shù)據(jù)集中兩服務(wù)點(diǎn)相鄰的次數(shù)。

下面將介紹路網(wǎng)掃描算法的具體流程。路網(wǎng)掃描算法基于深度優(yōu)先遍歷算法,首先選定初始節(jié)點(diǎn),隨后從初始節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)延伸路徑,若路徑各邊的訪問概率之和大于路徑訪問次數(shù)下限a,則將其加入結(jié)果集;若路徑長度超過從初始節(jié)點(diǎn)到路徑末端節(jié)點(diǎn)的最短路徑距離的b倍,則不繼續(xù)延伸該路徑。具體算法流程見算法1。

算法1路網(wǎng)掃描算法

輸入點(diǎn)集V,V上的邊集E,E上的邊訪問次數(shù)P,E上的邊長度L,路徑訪問次數(shù)下限a,路徑繞路上限b

輸出預(yù)計(jì)算路徑集R

1)初始化預(yù)計(jì)算路徑集R。

2)從V中取出一個(gè)未訪問過的點(diǎn)v。

3)初始化棧結(jié)構(gòu)stack,將一條僅含v的路徑壓入棧。

4)從棧stack中彈出頂元素,記為路徑r。

5)檢查路徑r上各邊的訪問次數(shù)之和,若該和大于路徑訪問下限a,則將路徑r加入預(yù)計(jì)算路徑集R。

6)取r的最后一個(gè)訪問節(jié)點(diǎn)的未訪問過的鄰居節(jié)點(diǎn)u。

7)記在訪問完路徑r的所有節(jié)點(diǎn)后,再訪問節(jié)點(diǎn)u的路徑為路徑r′,若路徑r′中所有節(jié)點(diǎn)間沿路徑的距離均不超過其在地圖上的距離的b倍,則將r′壓入棧stack。

8)若路徑r的最后一個(gè)訪問節(jié)點(diǎn)尚有未訪問過的鄰居節(jié)點(diǎn),回到步驟6)。

9)若棧stack非空,回到步驟4)。

10)若V中還有未訪問過的節(jié)點(diǎn),回到步驟2)。

11)算法結(jié)束。

在后續(xù)的PSO算法中,通過在預(yù)計(jì)算路徑集中檢索出全部對當(dāng)前訂單可行的路徑,并以每條路徑的長度除以全部可行路徑的長度之和作為各路徑被選中的概率,通俗來說,在路徑均有較高概率滿足較多需求的情況下,路徑越短,被選中概率越高。設(shè)預(yù)計(jì)算路徑集為R,則其中一條路徑r被選中的概率為:

2.3 分層自適應(yīng)變異記憶PSO算法

上文引言中提到,在將PSO算法應(yīng)用在動態(tài)公交問題上時(shí)存在以下問題:

1)在動態(tài)公交問題中,由于車輛數(shù)、地圖中存在的可訪問點(diǎn)以及同時(shí)存在的訂單數(shù)較多,因此問題解空間較大、等價(jià)狀態(tài)較多,基礎(chǔ)的PSO算法難以平衡探索與利用的過程。

2)使用不完全隨機(jī)的初始解算法固然可以提高收斂速度,但可能將粒子解局限在特定區(qū)域,使得粒子解缺乏隨機(jī)性,容易收斂到局部最優(yōu)。

3)動態(tài)公交需要在多個(gè)時(shí)間片上重復(fù)計(jì)算具有相似訂單的車輛的最優(yōu)路徑,尤其是PSO算法迭代輪次多、計(jì)算耗時(shí)長,容易在高峰期不能及時(shí)求解。

針對以上問題,本文提出根據(jù)動態(tài)公交問題的解的結(jié)構(gòu)將粒子解進(jìn)行拆分,并將路徑層的結(jié)果保存復(fù)用,同時(shí)使當(dāng)前時(shí)間片中的其他粒子和之后時(shí)間片的粒子計(jì)算在繼承、復(fù)用之前計(jì)算結(jié)果的基礎(chǔ)上縮短計(jì)算時(shí)間;此外,引入連續(xù)空間PSO算法所常見的兩大PSO算法的改進(jìn),即自適應(yīng)參數(shù)和變異機(jī)制,將其推廣到離散空間,以緩解算法早熟和收斂到局部最優(yōu)解的問題,從而提出了分層自適應(yīng)變異記憶PSO算法。

算法2分層自適應(yīng)變異記憶PSO算法

輸出未接訂單集O中各訂單在車輛集上的分配情況D,車輛集中各車輛b的節(jié)點(diǎn)訪問順序rb

1)生成N個(gè)訂單層粒子。

2)將所有未接訂單逐一隨機(jī)分配得到一個(gè)訂單層初始解,重復(fù)N次即可得到N個(gè)O的分配。

5)根據(jù)2.3.2節(jié)粒子更新規(guī)則更新路徑層粒子直至迭代輪次達(dá)到算法設(shè)定次數(shù)。

6)根據(jù)2.3.2節(jié)粒子更新規(guī)則更新訂單層粒子直至迭代輪次達(dá)到算法設(shè)定次數(shù),返回訂單分配情況和該分配情況下各車輛的路徑。

下面,本文將分別介紹動態(tài)公交粒子群分層方法、粒子解的更新規(guī)則和變異規(guī)則。

2.3.1 動態(tài)公交粒子群分層方法

上文定義了動態(tài)公交問題的解S由兩部分構(gòu)成:訂單在車輛間的分配情況D,給定車輛的節(jié)點(diǎn)訪問順序Rb。粒子群分層方法的核心,就是將D的求解與Rb的求解過程分離,并對Rb的求解結(jié)果進(jìn)行分類、保存、重用和繼承,從而減小問題的解空間和時(shí)間復(fù)雜度,加快搜索速度,減少計(jì)算時(shí)間。

在同一時(shí)間片的不同粒子解之間,以及在不同時(shí)間片下的粒子解之間,都有很高的概率會存在兩車所接的訂單種類的集合相同或相近。為避免重復(fù)計(jì)算,考慮根據(jù)一定原則對車輛的解Rb進(jìn)行分類,下面將依次給出訂單和車輛的種類的定義。將訂單的種類Θo定義為僅由其起點(diǎn)與終點(diǎn)決定的變量,若起點(diǎn)在計(jì)算時(shí)已經(jīng)過,則將起點(diǎn)設(shè)為空。以表示由v1和v2構(gòu)成的點(diǎn)對,NA表示該值不存在,ΘO表示訂單集的種類,則有:

ΘO={Θo,?o∈O}

將車輛的種類Θb定義為其已接訂單集的種類,則有:

設(shè)有粒子初始化方法Init,粒子群求解過程為PSO,該過程接受一個(gè)初始解和一個(gè)新增訂單集作為參數(shù)。歷史訂單集為O,新增訂單集即分配集為A,所有已發(fā)生計(jì)算訂單集及其對應(yīng)的路徑層粒子群構(gòu)成字典D,則可將分層PSO算法表示如下:

由此,可以將一個(gè)訂單種類集合所對應(yīng)的粒子群及其最優(yōu)解保存在以訂單集為鍵的字典D中。在計(jì)算具有相同類型訂單的車輛時(shí),可以調(diào)用之前記錄的最優(yōu)解,在其基礎(chǔ)上進(jìn)行計(jì)算,大大節(jié)省了計(jì)算時(shí)間。在沒有對應(yīng)解時(shí),再根據(jù)2.2節(jié)所述方法生成路徑層初始解。

2.3.2 粒子解的更新規(guī)則

在每個(gè)時(shí)間片中,算法將當(dāng)前訂單池中訂單隨機(jī)分配生成訂單層初始解,再根據(jù)2.3.1節(jié)所述規(guī)則生成路徑層解,每個(gè)路徑層粒子的解代表一輛車在給定訂單集下的一條路徑,路徑的終點(diǎn)是距最后一名乘客下車點(diǎn)最近的可用停放點(diǎn)。在此基礎(chǔ)上,根據(jù)本小節(jié)規(guī)則更新路徑層粒子群,迭代直至達(dá)到迭代停止條件。此時(shí),每個(gè)訂單層粒子的解的代價(jià)是該訂單層粒子對應(yīng)的路徑層粒子的解的代價(jià)之和,隨后訂單層粒子再根據(jù)本小節(jié)規(guī)則進(jìn)行更新。每次更新時(shí)如產(chǎn)生已計(jì)算的路徑層粒子解構(gòu)成的字典D中不存在的訂單情況,則根據(jù)2.3.1節(jié)規(guī)則生成新的車輛路徑解Rb并加入字典D。

設(shè)v為訂單層或路徑層粒子的速度,x為訂單層或路徑層粒子的當(dāng)前解,x′為訂單層或路徑層粒子的加速解,x″r為路徑層變異解,x″o為訂單層變異解,xglobal為訂單層或路徑層粒子的全局最優(yōu)解,xhistorical為訂單層或路徑層粒子的歷史最優(yōu)解,σ0、σ1、σ2為3個(gè)0～1的隨機(jī)數(shù)或固定為1,w為慣性系數(shù),α、β為學(xué)習(xí)率,γ為變異率,則粒子更新公式為:

v=σ0wv0+σ1α(xglobal-x)+σ2β(xhistorical-x)

(22)

x′=x+v

(23)

x″r=x′+γ|Rb|Insert

(24)

x″o=x′+γ|O|Reassign

(25)

其中:式(22)為速度更新步;式(23)為位置更新步;式(24)、式(25)為變異步。

在連續(xù)空間的PSO算法中,存在一類被廣泛應(yīng)用的粒子群范式——自適應(yīng)變異粒子群。其中,自適應(yīng)指的是速度更新步的參數(shù)w、α、β會隨著迭代進(jìn)行一定的變化,變異則是指變異步中γ不恒等于0,會在一定條件下使粒子變異,跳躍至離當(dāng)前位置較遠(yuǎn)的解,避免出現(xiàn)多個(gè)粒子在一個(gè)較小的解空間中探索,而其他解空間區(qū)域中則缺乏探索,從而導(dǎo)致PSO算法陷入局部最優(yōu)的情況。為將自適應(yīng)變異機(jī)制引入離散空間,作出如下定義:

w=0.5-0.003hnow

(26)

(27)

βx=hnow-hhistorical+1

(28)

(29)

式(26)中的hnow表示當(dāng)前輪次,該式表示慣性系數(shù)會隨迭代輪次提高而減小;式(27)表示距離最優(yōu)解越遠(yuǎn)的解將會越快地向最優(yōu)解迭代;式(28)中的hhistorical表示該粒子上次刷新最優(yōu)解的輪次,該式表示離上次取到局部最優(yōu)解的時(shí)間越久,局部最優(yōu)解對當(dāng)前解產(chǎn)生的影響越大;式(29)中的count函數(shù)接受一個(gè)表達(dá)式作為輸入,返回符合該表達(dá)式的粒子個(gè)數(shù),該式表示粒子群越密,隨機(jī)擾動概率就越大,有助于粒子群在收縮至局部最優(yōu)后跳出。

3 實(shí)驗(yàn)結(jié)果分析

本文實(shí)驗(yàn)分為3個(gè)部分:1)在真實(shí)日訂單集上選取6個(gè)連續(xù)的時(shí)間片,檢驗(yàn)本文提出的分層PSO算法對比單層PSO算法在時(shí)間上的優(yōu)勢;2)構(gòu)建小規(guī)模訂單集,在充分迭代的前提下進(jìn)行消融實(shí)驗(yàn),對本文針對動態(tài)公交問題改造的自適應(yīng)機(jī)制和變異機(jī)制對算法的收斂過程及最終結(jié)果的影響進(jìn)行分析和比較;3)在完全仿真環(huán)境中,限制計(jì)算時(shí)間在真實(shí)計(jì)算時(shí)間的要求內(nèi)即5 s內(nèi)處理當(dāng)前時(shí)間片的所有訂單,至多約200條訂單,使用區(qū)域真實(shí)日訂單集對本文算法及PSO算法、貪婪插入(GI)算法、VNS算法、蟻群(AC)算法和固定公交進(jìn)行比較,并分析本文算法的有效性。

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

本文實(shí)驗(yàn)環(huán)境基于重慶市北碚區(qū)蔡家崗街道的道路搭建,蔡家崗街道人口約16.45萬人,面積約45.75 km2,使用蔡家崗街道范圍內(nèi)的80個(gè)公交車站作為圖結(jié)構(gòu)的節(jié)點(diǎn),構(gòu)建公交站點(diǎn)間202條有向邊,使用公交車站間的最短路徑的實(shí)時(shí)通行時(shí)間作為動態(tài)道路圖結(jié)構(gòu)的邊長度,并采用重慶市公交4.38億條歷史GPS數(shù)據(jù)生成動態(tài)道路圖、3 940.7萬條歷史打卡數(shù)據(jù)生成出行數(shù)據(jù)集,作為預(yù)計(jì)算路徑集的輸入數(shù)據(jù)。在實(shí)驗(yàn)區(qū)域,公交運(yùn)營時(shí)間為05:00—23:00,動態(tài)公交服務(wù)器每10 s響應(yīng)之前10 s的所有訂單,即一個(gè)時(shí)間片為10 s,全天共6 480個(gè)時(shí)間片。單時(shí)間片實(shí)驗(yàn)截取了一個(gè)有32個(gè)新加入訂單的時(shí)間片;部分時(shí)間片實(shí)驗(yàn)截取了6個(gè)時(shí)間片進(jìn)行實(shí)驗(yàn);全天仿真實(shí)驗(yàn)使用數(shù)據(jù)集中一天約50 000條真實(shí)出行需求作為訂單集,該訂單集中訂單的平均里程為6.4 km,當(dāng)天固定公交平均行駛速度為20 km/h。采用當(dāng)?shù)毓还?39輛所有在庫公交車作為車輛上限,并設(shè)置每車同時(shí)接受的訂單數(shù)至多為公交車的實(shí)際座位數(shù)31座。本文的實(shí)驗(yàn)運(yùn)行于Inter 12700CPU和Win 11系統(tǒng),算法采用Python 3.10進(jìn)行開發(fā),主要調(diào)用了numpy包。

3.2 實(shí)驗(yàn)參數(shù)與指標(biāo)設(shè)置

根據(jù)模型的目標(biāo)函數(shù),動態(tài)公交在運(yùn)營過程中主要關(guān)心4個(gè)指標(biāo),即接單率、乘客候車時(shí)間、乘客在車時(shí)間和運(yùn)營里程。在本文的實(shí)驗(yàn)結(jié)果中也將體現(xiàn)這些運(yùn)營指標(biāo),并設(shè)置最大可用車輛數(shù)這一參數(shù)用于體現(xiàn)所需的司機(jī)工時(shí)。在本文算法及各對比算法中,為保證最壞乘客體驗(yàn),設(shè)置了每個(gè)訂單的最長在車時(shí)間為1.2倍的直接從訂單出發(fā)地到目的地的預(yù)計(jì)時(shí)間。對除固定公交以外的算法均設(shè)置了訂單等待接單時(shí)間窗,訂單發(fā)起后的10 min內(nèi)若仍無法將訂單分配給車輛,則自動拒絕訂單。

經(jīng)使用不同系數(shù)測試,將改進(jìn)PSO算法與原始PSO算法的初始慣性系數(shù)設(shè)為0.5,靜態(tài)全局學(xué)習(xí)系數(shù)設(shè)為0.4,靜態(tài)局部學(xué)習(xí)系數(shù)設(shè)為0.2。限制本文算法、原始PSO算法、變鄰域搜索算法和蟻群算法的迭代輪次最多為100輪。設(shè)改進(jìn)PSO算法的路徑層在檢索到相同解時(shí)的迭代輪次,即圖2中的“較少次數(shù)”為20輪;無相關(guān)解時(shí)的迭代輪次,即圖2中的“較多次數(shù)”為100輪。

3.3 分層粒子群對算法計(jì)算時(shí)間的影響分析

本文針對原始PSO算法計(jì)算耗時(shí)較長的問題,結(jié)合動態(tài)公交問題的解包含兩部分的特點(diǎn),以及動態(tài)公交問題在不同時(shí)間片之間路徑層的解具有可復(fù)用、可繼承性的特點(diǎn),提出了分層PSO算法。分層PSO算法在單時(shí)間片內(nèi)能復(fù)用車輛種類一致的車輛粒子解的結(jié)果、繼承車輛種類相近的粒子解、加速新粒子求解過程,并能在不同時(shí)間片間復(fù)用、繼承,從而減小PSO算法的開銷。本文截取6個(gè)時(shí)間片用于對比分層與不分層PSO算法的實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖3所示。實(shí)驗(yàn)結(jié)果表明,在動態(tài)公交問題中將粒子解劃分為多層可以有效節(jié)約單時(shí)間片及跨時(shí)間片的計(jì)算時(shí)間開銷,整體上降低了PSO算法的計(jì)算開銷。

圖3 多層與單層PSO算法在多時(shí)間片下的計(jì)算時(shí)間Fig.3 Calculation time of multi-layer PSO algorithm and single-layer PSO algorithm under multiple time slices

3.4 自適應(yīng)變異機(jī)制對算法收斂過程和結(jié)果的影響分析

本文通過提出編輯距離的概念將連續(xù)空間中的自適應(yīng)變異機(jī)制引入離散空間。為研究自適應(yīng)變量和隨機(jī)擾動變異機(jī)制的作用,設(shè)計(jì)了基于單個(gè)時(shí)間片的消融實(shí)驗(yàn)用于測試這兩點(diǎn)改進(jìn)的有效性,結(jié)果如圖4、圖5所示。

圖4 自適應(yīng)變異機(jī)制對算法收斂的影響Fig.4 The impact of adaptive mutation mechanism on algorithm convergence

圖5 自適應(yīng)變異機(jī)制對算法結(jié)果的影響Fig.5 The impact of adaptive mutation mechanism on algorithm results

實(shí)驗(yàn)結(jié)果顯示:在對算法收斂過程的影響上,隨機(jī)擾動算子能有效擴(kuò)大算法的搜索范圍,而動態(tài)參數(shù)可以在收斂早期加快收斂速度,隨后有效避免算法早熟;在算法結(jié)果上,僅使用隨機(jī)擾動在所選實(shí)驗(yàn)參數(shù)下,算法反而過快收斂于局部最優(yōu),動態(tài)參數(shù)的使用則能有效提高算法的性能。

3.5 全天時(shí)間片實(shí)驗(yàn)數(shù)據(jù)分析

為充分驗(yàn)證本文算法的有效性,在全天時(shí)間片真實(shí)訂單集上進(jìn)行了實(shí)驗(yàn),并與原始PSO算法、GI算法、VNS算法、AC算法和固定公交進(jìn)行比較,實(shí)驗(yàn)結(jié)果見表1。

表1 全天時(shí)間片實(shí)驗(yàn)結(jié)果Table 1 Whole day time slice experiment results

表1結(jié)果顯示:固定公交在運(yùn)營里程方面具有優(yōu)勢,但在不允許超載的情況下,大量乘客需要進(jìn)行超長時(shí)間的等待才能上車,或由于運(yùn)營時(shí)間結(jié)束也未能上車而被被動拒單;在設(shè)置的100輪迭代過程中,原始PSO算法所求得的路徑較差,而蟻群算法所求得的路徑較優(yōu),但滿足的訂單數(shù)相對較少;相較于GI算法、VNS算法,本文算法在高接單率、低運(yùn)營里程的前提下,在乘客體驗(yàn)方面也仍有較好的表現(xiàn),具有相當(dāng)?shù)膶?shí)用價(jià)值。

本文算法、PSO、VNS和AC算法均有迭代過程,因此可能運(yùn)行時(shí)間較長,故限制算法的最大迭代輪次為100輪。在全天時(shí)間片上,上述4個(gè)需要迭代的算法運(yùn)行時(shí)長統(tǒng)計(jì)見表2。

表2 全時(shí)間片運(yùn)行時(shí)長對比Table 2 Full time slice runtime comparison 單位:s

表2結(jié)果顯示,本文算法在運(yùn)行時(shí)長方面相對其他需要迭代的算法具有一定的優(yōu)勢。在最長單時(shí)間片計(jì)算時(shí)間上,PSO、VNS和AC算法均超過了10 s,由于算法運(yùn)行中單時(shí)間片需要響應(yīng)在該時(shí)間片的10 s內(nèi)的所有訂單,單時(shí)間片運(yùn)行時(shí)間超過10 s實(shí)際上表示該算法無法適用于該片區(qū)的動態(tài)公交問題,而本文算法能在10 s內(nèi)完成響應(yīng),因此具有實(shí)用價(jià)值。

4 結(jié)束語

本文針對城市公交的新模式——動態(tài)公交,具體地分析了它所涉及的限制條件,并構(gòu)建了模型。隨后,本文針對動態(tài)公交問題搜索范圍大、易陷入局部最優(yōu)等特點(diǎn),引入了PSO算法對其進(jìn)行求解。本文針對動態(tài)公交問題的解空間是離散空間的情況,提出了解的編輯距離的概念,并在此基礎(chǔ)上設(shè)計(jì)了新的動態(tài)收斂系數(shù)和隨機(jī)擾動系數(shù);針對動態(tài)公交解具有兩部分的特點(diǎn),創(chuàng)新性地提出了分層粒子群,并提出路徑層粒子的復(fù)用和繼承方法。最后,本文設(shè)計(jì)了3類實(shí)驗(yàn),分別測試、對比了算法的計(jì)算效率和結(jié)果收斂性。5個(gè)時(shí)間片上的實(shí)驗(yàn)結(jié)果表明,本文提出的粒子群分層、復(fù)用、繼承機(jī)制能降低算法80%的計(jì)算耗時(shí);單個(gè)時(shí)間片實(shí)驗(yàn)結(jié)果表明,引入的自適應(yīng)變異機(jī)制能有效優(yōu)化算法的收斂過程,避免算法早熟現(xiàn)象、避免陷入局部最優(yōu);全天時(shí)間片實(shí)驗(yàn)結(jié)果表明,本文算法相較于固定公交能在同等運(yùn)力限制下,提高22%的乘客接單率并節(jié)省39.1%的乘客出行時(shí)間,相較于其他算法,本文算法平均縮短85.3%的計(jì)算用時(shí),降低20%里程數(shù),并提高超12%的接單率。整體結(jié)果表明,本文算法能夠滿足當(dāng)前動態(tài)公交運(yùn)營的需要。在未來的研究方向上,可以嘗試結(jié)合其他啟發(fā)式算法設(shè)計(jì)混合算法對動態(tài)公交問題進(jìn)行求解,從而進(jìn)一步提升求解速度和準(zhǔn)確性。