面向動態公交的離散分層記憶粒子群優化算法
2024-04-23 10:02:46黃君澤吳文淵李軼石明全王正江
計算機工程 2024年4期
黃君澤,吳文淵,李軼,石明全,王正江
(1.中國科學院重慶綠色智能技術研究院自動推理與認知重慶市重點實驗室,重慶 400714;2.中國科學院大學重慶學院人工智能學院,重慶 400714;3.重慶市鳳筑科技有限公司,重慶 401120)
0 引言
隨著信息技術基礎設施在交通領域的不斷完善,智慧交通——一種集成了信息技術與數據分析的現代交通系統也正快速發展。在運營端,公交信息基礎設施如公交全球定位系統(GPS)、公交智能交互平臺正不斷完善;在乘客端,移動互聯網的發展使得乘客能將自己的需求實時提交給出行服務商。這兩點變化的發生使得一種名為動態公交的新型公交運營模式成為可能,并且動態公交已經成為了許多城市公交企業布局智慧交通的重要落腳點。動態公交融合了傳統公交和網約車[1]的運營模式,乘客可以像預約網約車拼車模式一樣在網上平臺下單,告知運營商自己的上車點、下車點和預計的上車時間,并在約定時間和約定地點上車,在無換乘的前提下前往目的地;但與網約車不同的是,前來接上乘客的不是小型轎車,而是相對較大的面包車、大客車等,并且一車可以同時接送多人。
在動態公交的運營機制和所需考慮的運營指標上,已經有了較多研究[2],運營機制方面的改動包括添加換乘點[3]、設置多車場[4]、使用電動車[5]、設置充電站[6]、訂單設置軟時間窗[7]等;而運營指標方面包括著眼于提升居民出行滿意度、減少政府在公共交通領域的開支、緩解城市擁堵現象、降低出行帶來的碳排放等。但在對動態公交數學建模、對動態公交問題求解這兩方面的研究尚有不足。
動態公交問題從路徑規劃問題的角度而言,屬于電召問題(DARP)的一類子問題。電召問題是一種區別于車輛路徑問題(VRP),每個訂單有兩個或更多個需要依序經過的途徑點的路徑規劃問題,并且在車載客量大于2人時是NP難問題[8]。而動態公交問題在電召問題的基礎上,要求訂單隨機生成(Stochastic)、允許根據新信息更新在途車輛的路徑(Dynamic)。需要指出的是,另一種常見的新型公交——定制公交,則是電召問題中確定訂單(Deterministic)、不允許更新在途車輛路徑(Static)的另一子類型問題,所建立的模型和使用的求解算法與動態公交存在巨大的差異。
需要指出的是,本文提出的動態公交問題具有一定的特殊性:1)動態公交問題的解空間是離散空間,這使得在連續問題上的求解算法不適用,并且動態公交問題的解由兩個子問題的解構成,還存在大量相似或相同的子問題;2)動態公交問題的離散狀態較多,動態公交問題中車輛數、可訪問點數和訂單數決定了動態公交問題的解空間的大小,在實際問題中,相較于之前的研究,這三者都較多,因此離散狀態較多,許多算法無法很好地進行求解;3)動態公交問題的實時性要求較高。在動態公交問題的實際應用中,以本文后續實驗所選定區域為例,高峰期訂單數平均可達180個/min,而服務器需要在一定時間內為用戶反饋計算結果。
目前,電召問題求解算法可以分為求精確解算法與啟發式算法兩大類,其中多數算法不能滿足上述動態公交問題的具體要求。求精確解算法以分支定界法[3]和約簡法[9]及其變種為主,但目前,求精確解算法的計算復雜度都較高,因而可解決問題規模較小,一般僅能解決使用車輛數在10車以內、訂單數在100單以內的問題[10],不能滿足上述實時性的要求,難以在現實場景中應用。啟發式算法包括神經網絡[11]、仿生算法[12]、插入算法[13]、模擬退火算法[6,14]、多方逼近算法[15]、禁忌搜索(Tabu Search)算法[3,16]、變鄰域搜索(VNS)算法[4]和大鄰域搜索(ALNS)算法[5,13]等,當解空間離散且離散狀態較多時,大多數啟發式算法對初始解高度敏感,并且都會面對探索和利用的平衡問題。
由于現有算法都存在一定的問題,因此有必要探索新的求解算法。在求解優化問題時,粒子群優化(PSO)算法是一種被長期驗證有效和使用的算法。PSO算法是一種將問題的解視為粒子,并使多個粒子依一定規則相互作用以探索解空間、尋找最優解的優化算法。國內早在2004年就有基于PSO算法求解多目標問題的研究[17],并一直得到研究者的廣泛關注[18-19]。在連續空間下,PSO算法的參數設置和改進方向[20]都較為成熟,但相關的研究無法簡單地套用在離散空間PSO算法上[21]。
在路徑規劃領域,PSO算法也長期得到廣泛的研究與應用。國內同樣于2004年就有學者研究了PSO算法求解車輛路徑問題[22],王飛在帶時間窗的車輛調度問題上應用了改進的PSO算法[23],近期的車輛路徑問題綜述[24]中也對PSO算法近年來的研究進行了總結。在面對多目標問題時,PSO算法也展現出了較好的適用性[19,25]。然而,目前較少有將PSO算法應用到動態公交問題上的研究[21]。
原始的PSO算法不能較好地適用于動態公交問題,有以下原因:1)在粒子群迭代的過程中,多個粒子會重復計算相同或相似訂單集的最優路徑,造成冗余計算;2)相對于其他啟發式算法,PSO算法較為不依賴初始解,但優質的初始解也可以幫助算法快速收斂;3)PSO算法在離散空間存在容易早熟的問題。
針對以上問題,基于相關領域的研究現狀,結合動態公交問題的解的形式的特點,本文提出了動態公交問題的模型,并在此基礎上對基礎的PSO算法做出了以下創新:
1)將PSO算法也針對性地拆分成兩層分別進行迭代優化,并提出可復用、可繼承的低層粒子結構,避免重復計算的開銷,提高算法的實時性。
2)提出基于出行偏好的初始解生成算法,從而利用數據生成在未來時間片更優的初始解,同時幫助算法快速收斂。
3)引入自適應變異機制,在離散空間上重新設計自適應參數和變異概率,避免算法早熟,減少收斂到局部最優的情況。
1 動態公交問題
動態公交問題是一種多車路徑規劃問題,源于動態公交這一公交運營模式。動態公交區別于傳統公交,其由乘客先發起一個包含該乘客的起終點、上下車時間窗等信息的訂單,隨后公交公司結合訂單信息和當前公交車輛狀態將該訂單指定到一輛公交車,由其完成該乘客的需求,并且公交車可以部分或完全不沿公交線路行駛;動態公交也區別于定制公交,其允許訂單實時發起、允許乘客期望上車時間接近發起時間,因此需要能夠實現實時計算并分配訂單;動態公交還區別于網約車,每輛公交上可以搭載超過5名乘客,這對算法的復雜度提出了一定的挑戰。動態公交運營模式示意圖如圖1所示。
圖1 動態公交運營模式示意圖Fig.1 Schematic diagram of dynamic public transport operation mode
在動態公交問題中,每個訂單都具有兩個途徑點,并且要求以給定的先后順序訪問這兩個途徑點,這使得動態公交問題模型區別于傳統的路徑規劃問題。但在其他路徑規劃問題如旅行商問題(TSP)、車隊尋徑問題(VRP)中,也存在一些目標函數、變量和限制條件的設置具有一定的參考價值。在過往的動態公交模型的研究中則探索了動態公交的運營機制,包括是否設立實體站點、是否允許換乘[26]等。在現實問題中,設立實體站點、存在多車場[4]、允許訂單超時[11]是較為普遍的情況,并且一般不允許換乘。因此,本文所構建模型也包括多車場,并在單目標模型下設置了訂單時間窗。
1.1 目標函數建模
針對動態公交所應關注的運營指標,也已有了較多的討論。動態公交服務有3個主要的相關方:乘客,公交服務運營商,其他社會組織。這三方具有各自不同的關心點:公交服務運營商希望盡可能降低凈支出;乘客希望能接受公交服務,并希望最小化自身的總出行時間;其他社會組織則希望通過推廣公共交通緩解城市擁堵和降低燃油消耗和碳排放。根據以上三方的實際關系構建目標函數,其中:與乘客相關的指標包括接單率、乘客候車時間和乘客在車時間3項;與運營方相關的指標包括服務訂單數、所需司機工時和運營里程3項,其中,服務訂單數在訂單數不可控的情況下等價于接單率,司機工時與最大可用車數呈正相關;其他社會組織關心的指標包括服務訂單數、燃油消耗和碳排放量3項,其中,服務訂單數越多,城市道路車輛數就越少,對城市擁堵現象的緩解就越明顯,而燃油與碳排放量一般都與運營里程呈正比。因此,最終構建的目標函數旨在實現最大化接單率、最小化平均乘客候車時間、最小化平均乘客在車時間和最小化運營里程,具體公式如下:
(1)
(2)
(3)
(4)
多目標問題的求解方法主要包括引入博弈機制[11]和轉化為單目標2種,本文將采用將多目標問題中的目標一部分通過加權和的方式轉化為新的單目標,另一部分轉化為約束條件的方式將動態公交問題建模為單目標問題進行求解。具體地,本文對上述目標函數進行轉化,合并式(1)與式(4),并將式(2)與式(3)轉化為約束條件,如下式所示:
(5)
(6)
(7)
本文通過新增每單收入常量、每里程代價常量合并了對接單率和里程的目標;通過新增比例約束和常量約束來限制乘客在車和等車時間。在式(5)中:po表示接受該訂單帶來的收入;co表示車輛的支出。在式(6)中:Ttravel表示訂單可接受的最長在車時間。在式(7)中:Twait表示訂單可接受的最長候車時間。這一形式下,式(6)、式(7)即一般意義上的時間窗約束。
1.2 約束條件建模
動態公交具有的訂單是動態、隨機生成的,因此動態公交的訂單分配過程也需要分時間片進行,并且滿足訂單約束。具體到某一輛公交,其任意時刻的路徑都應是滿足車輛路徑約束的,并且在公交往往具有多車場的現實背景下,公交路徑的起終點也應滿足一定約束。
1.2.1 訂單約束
訂單約束包括分配約束與載客量約束。其中,分配約束表示訂單在車輛間的分配情況,載客量約束則限制車輛的最大接單數。設b載客量為vb,vo表示訂單的人數,Tnow表示算法中的當前時刻,則:
(8)
(9)
(10)
(11)
式(8)表示所有訂單都被歸入一個分配集,其中分配集0為下一時刻的待分配集;式(9)表示所有分配集間交集為空,即訂單不能重復分配;式(10)表示車輛的接受訂單集為車輛在當前時刻之前的所有時刻的分配集的并集;式(11)表示車輛的接受集的載客量之和不能大于車輛的額定載客量。
1.2.2 車輛路徑起終點約束
在動態公交實際運營過程中,在車輛沒有訂單時停靠在何處是一個具有實際意義的問題。如果要求公交每次接單后都必須回到集中停放的車場,可能會產生不必要的成本;但公交車輛也不能停放在任意的道路或公交車站邊,否則會引起交通堵塞。為此,根據公交運營的實際情況,本文提出可以將部分暫時無訂單車輛臨時停放在道路邊的臨時停車位,避免車輛不必要地返回車場。此外,在新能源公交車需要充氣、充電時,需要前往指定的停放點進行充氣、充電。為對以上情況進行建模,設置車輛路徑起終點約束。
車輛路徑具有一個起點,是車輛當前所處或出站車輛當前正要前往的站點;車輛路徑具有一個終點,是滿足約束條件下離車輛的最后一個途徑節點最近的可行停放點;車輛終點的約束條件包括是否需要充電、充氣、加油,以及是臨時停放還是長時間停放。
(12)
(13)
(Eb≤Elimit)=Cb
(14)
(15)
(16)
其中:路徑及其后的中括號表示路徑中的指定下標位置的元素,下標從0開始標號。式(12)、式(13)表示車輛路徑起終點,分別指車輛路徑經過的第一個站點與最后一個站點;式(14)表示當車輛能源低于給定值時,車輛需要充能;式(15)表示若車輛需要充能,則車輛路徑的終點需要可以為車輛提供對應的能源補充;式(16)表示若車輛需要退出運營,則車輛路徑終點需要支持長時間停放車輛。
1.2.3 車輛路徑約束
(17)
(18)
(19)
(20)
Lb=distance(rb)
(21)
式(17)、式(18)約束了訂單起點在巴士路徑中的位置;式(19)、式(20)約束了訂單終點在巴士路徑中的位置;式(21)表示車輛里程數,即車輛全天路徑的長度。
2 離散分層記憶粒子群優化算法
本章分為3個部分:第1個部分介紹離散空間中的動態公交問題的解的結構及基礎運算的定義;第2個部分介紹基于出行偏好的初始解生成算法,該算法首先在給定城市道路圖上生成名為路網的圖結構,隨后在該圖結構上依一定規則游走產生符合要求的隨機路徑;第3個部分介紹分層自適應變異記憶PSO算法,該算法基于離散空間中動態公交問題解的編輯距離動態調整粒子收斂速度、控制粒子隨機擾動的方法,同時基于對車輛種類的定義給出將粒子群分層、記憶、繼承和復用的方法。
本文算法整體流程如圖2所示,其中訂單層粒子單次迭代流程如下:對每輛車所分配到的訂單集,首先在以訂單集為鍵的路徑層解字典中檢索其對應的粒子群;若檢索到,將對應的粒子群進行相對于正常次數而言較少的次數的迭代;若未檢索到,則根據2.3.1節所述規則進行求解,并迭代正常次數。此處的迭代次數具體值為超參數,本文所用迭代次數詳見3.2節實驗參數。完成路徑層求解后,通過在路徑層解的最后一個訂單結束的站點最近的符合約束的停放點加入路徑,即可得到一個車輛的路徑及其對應的代價,由此訂單層的每個粒子可以計算得出其所對應的所有車輛的代價和,從而可以進行粒子位置優劣的比較,并進行速度和位置的更新。
圖2 分層自適應變異PSO算法流程Fig.2 Procedure of discrete hierarchical memory PSO algorithm
2.1 動態公交問題解的結構及運算的定義
PSO算法在迭代過程中需要計算兩個解間的距離,但在動態公交問題中,解空間為離散空間,因此不能直接使用連續空間中對解的距離的定義[27]。本文采用定義解及對解的操作的方式解決這一問題。動態公交問題的解包括以下兩部分:訂單在車輛間的分配情況,車輛行駛路徑中對節點的訪問順序。設點全集為V,有k個可用車輛,則粒子的解S為一個包含k+1個分量的向量,其中,第一個分量D表示訂單的分配狀況,包含|O|個有k種取值的變量d;其后的k個分量Rb分別表示其右下角標所指示的車輛經過的點的序,包含l個在點集V中取值的變量v,l的取值范圍為0～2|O|。可將動態公交問題的解S表示如下:
S=
D={do∈D}
Rb=
由于動態公交問題中不同的解可以通過使用上述兩個算子進行轉化,因此可以根據兩個不同解間變換所需的基礎操作定義解與操作算子的加減法。設V為粒子的速度,μ1、μ2分別為兩種操作的操作次數,則有:
S1+μ1Reassign+μ2Insert=S2
S2-S1=μ1Reassign+μ2Insert
將兩解間變化所需基礎操作的次數定義為兩解間的編輯距離ΔS1,S2,則有:
ΔS1,S2=|S2-S1|=μ1+μ2
需要注意的是,由于將解S1變化為解S2所需的操作次數與將解S2變換為解S1所需的操作次數可能不一致,因此ΔS1,S2?ΔS2,S1。
2.2 基于出行偏好的初始解生成算法
本文提出基于從歷史數據中總結的出行偏好的初始解生成算法。初始解的生成關系到算法的收斂速度,并且會在很大程度上影響算法最終的收斂結果。在動態公交問題中,由于訂單生成的隨機性,當前時間片的最優路徑可能不利于后續訂單的接收,因此需要一定的設計來使得算法生成的路徑能盡可能地滿足未發起訂單的需求[15]。盡管在動態公交問題中訂單的生成是隨機的,但在實際場景下,這種隨機并非是無規律的。在某一地區,訂單的生成一定是遵循某種規律的,這也是智慧交通領域研究的課題之一[28],但這種規律的探索不在本文的研究范圍之內,下述初始解生成算法將基于已有的出行偏好。出行偏好的表示形式是一個以公交站點為行索引和列索引的矩陣,矩陣中的元素表示行索引所對應的公交站點出發到列索引所對應的公交站點的出行偏好。
近年來,基于數據的預計算路徑集方法逐漸受到研究者的重視[29]。本文提出了將出行數據歸約到路網,并通過對路網進行掃描生成備選路徑集的路網掃描算法。該算法可以分開利用帶權路網上的點信息與邊信息,也可以將點信息與邊信息進行加權綜合利用,得到符合要求的備選路徑。其中:點信息是指公交車打卡上車數據、住宅區居民人數、商圈人流量及蜂窩網絡網點使用人數等,描述一個在給定問題規模下可被抽象為一點的區域的與動態公交問題中需求數具有直接關系的信息;邊信息是指以各種方式統計或計算得到的兩服務點間的客流量,或出行軌跡數據集中兩服務點相鄰的次數。
下面將介紹路網掃描算法的具體流程。路網掃描算法基于深度優先遍歷算法,首先選定初始節點,隨后從初始節點向其鄰居節點延伸路徑,若路徑各邊的訪問概率之和大于路徑訪問次數下限a,則將其加入結果集;若路徑長度超過從初始節點到路徑末端節點的最短路徑距離的b倍,則不繼續延伸該路徑。具體算法流程見算法1。
算法1路網掃描算法
輸入點集V,V上的邊集E,E上的邊訪問次數P,E上的邊長度L,路徑訪問次數下限a,路徑繞路上限b
輸出預計算路徑集R
1)初始化預計算路徑集R。
2)從V中取出一個未訪問過的點v。
3)初始化棧結構stack,將一條僅含v的路徑壓入棧。
4)從棧stack中彈出頂元素,記為路徑r。
5)檢查路徑r上各邊的訪問次數之和,若該和大于路徑訪問下限a,則將路徑r加入預計算路徑集R。
6)取r的最后一個訪問節點的未訪問過的鄰居節點u。
7)記在訪問完路徑r的所有節點后,再訪問節點u的路徑為路徑r′,若路徑r′中所有節點間沿路徑的距離均不超過其在地圖上的距離的b倍,則將r′壓入棧stack。
8)若路徑r的最后一個訪問節點尚有未訪問過的鄰居節點,回到步驟6)。
9)若棧stack非空,回到步驟4)。
10)若V中還有未訪問過的節點,回到步驟2)。
11)算法結束。
在后續的PSO算法中,通過在預計算路徑集中檢索出全部對當前訂單可行的路徑,并以每條路徑的長度除以全部可行路徑的長度之和作為各路徑被選中的概率,通俗來說,在路徑均有較高概率滿足較多需求的情況下,路徑越短,被選中概率越高。設預計算路徑集為R,則其中一條路徑r被選中的概率為:
2.3 分層自適應變異記憶PSO算法
上文引言中提到,在將PSO算法應用在動態公交問題上時存在以下問題:
1)在動態公交問題中,由于車輛數、地圖中存在的可訪問點以及同時存在的訂單數較多,因此問題解空間較大、等價狀態較多,基礎的PSO算法難以平衡探索與利用的過程。
2)使用不完全隨機的初始解算法固然可以提高收斂速度,但可能將粒子解局限在特定區域,使得粒子解缺乏隨機性,容易收斂到局部最優。
3)動態公交需要在多個時間片上重復計算具有相似訂單的車輛的最優路徑,尤其是PSO算法迭代輪次多、計算耗時長,容易在高峰期不能及時求解。
針對以上問題,本文提出根據動態公交問題的解的結構將粒子解進行拆分,并將路徑層的結果保存復用,同時使當前時間片中的其他粒子和之后時間片的粒子計算在繼承、復用之前計算結果的基礎上縮短計算時間;此外,引入連續空間PSO算法所常見的兩大PSO算法的改進,即自適應參數和變異機制,將其推廣到離散空間,以緩解算法早熟和收斂到局部最優解的問題,從而提出了分層自適應變異記憶PSO算法。
算法2分層自適應變異記憶PSO算法
輸出未接訂單集O中各訂單在車輛集上的分配情況D,車輛集中各車輛b的節點訪問順序rb
1)生成N個訂單層粒子。
2)將所有未接訂單逐一隨機分配得到一個訂單層初始解,重復N次即可得到N個O的分配。
5)根據2.3.2節粒子更新規則更新路徑層粒子直至迭代輪次達到算法設定次數。
6)根據2.3.2節粒子更新規則更新訂單層粒子直至迭代輪次達到算法設定次數,返回訂單分配情況和該分配情況下各車輛的路徑。
下面,本文將分別介紹動態公交粒子群分層方法、粒子解的更新規則和變異規則。
2.3.1 動態公交粒子群分層方法
上文定義了動態公交問題的解S由兩部分構成:訂單在車輛間的分配情況D,給定車輛的節點訪問順序Rb。粒子群分層方法的核心,就是將D的求解與Rb的求解過程分離,并對Rb的求解結果進行分類、保存、重用和繼承,從而減小問題的解空間和時間復雜度,加快搜索速度,減少計算時間。
在同一時間片的不同粒子解之間,以及在不同時間片下的粒子解之間,都有很高的概率會存在兩車所接的訂單種類的集合相同或相近。為避免重復計算,考慮根據一定原則對車輛的解Rb進行分類,下面將依次給出訂單和車輛的種類的定義。將訂單的種類Θo定義為僅由其起點與終點決定的變量,若起點在計算時已經過,則將起點設為空。以
ΘO={Θo,?o∈O}
將車輛的種類Θb定義為其已接訂單集的種類,則有:
設有粒子初始化方法Init,粒子群求解過程為PSO,該過程接受一個初始解和一個新增訂單集作為參數。歷史訂單集為O,新增訂單集即分配集為A,所有已發生計算訂單集及其對應的路徑層粒子群構成字典D,則可將分層PSO算法表示如下:
由此,可以將一個訂單種類集合所對應的粒子群及其最優解保存在以訂單集為鍵的字典D中。在計算具有相同類型訂單的車輛時,可以調用之前記錄的最優解,在其基礎上進行計算,大大節省了計算時間。在沒有對應解時,再根據2.2節所述方法生成路徑層初始解。
2.3.2 粒子解的更新規則
在每個時間片中,算法將當前訂單池中訂單隨機分配生成訂單層初始解,再根據2.3.1節所述規則生成路徑層解,每個路徑層粒子的解代表一輛車在給定訂單集下的一條路徑,路徑的終點是距最后一名乘客下車點最近的可用停放點。在此基礎上,根據本小節規則更新路徑層粒子群,迭代直至達到迭代停止條件。此時,每個訂單層粒子的解的代價是該訂單層粒子對應的路徑層粒子的解的代價之和,隨后訂單層粒子再根據本小節規則進行更新。每次更新時如產生已計算的路徑層粒子解構成的字典D中不存在的訂單情況,則根據2.3.1節規則生成新的車輛路徑解Rb并加入字典D。
設v為訂單層或路徑層粒子的速度,x為訂單層或路徑層粒子的當前解,x′為訂單層或路徑層粒子的加速解,x″r為路徑層變異解,x″o為訂單層變異解,xglobal為訂單層或路徑層粒子的全局最優解,xhistorical為訂單層或路徑層粒子的歷史最優解,σ0、σ1、σ2為3個0～1的隨機數或固定為1,w為慣性系數,α、β為學習率,γ為變異率,則粒子更新公式為:
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)為變異步。
在連續空間的PSO算法中,存在一類被廣泛應用的粒子群范式——自適應變異粒子群。其中,自適應指的是速度更新步的參數w、α、β會隨著迭代進行一定的變化,變異則是指變異步中γ不恒等于0,會在一定條件下使粒子變異,跳躍至離當前位置較遠的解,避免出現多個粒子在一個較小的解空間中探索,而其他解空間區域中則缺乏探索,從而導致PSO算法陷入局部最優的情況。為將自適應變異機制引入離散空間,作出如下定義:
w=0.5-0.003hnow
(26)
(27)
βx=hnow-hhistorical+1
(28)
(29)
式(26)中的hnow表示當前輪次,該式表示慣性系數會隨迭代輪次提高而減小;式(27)表示距離最優解越遠的解將會越快地向最優解迭代;式(28)中的hhistorical表示該粒子上次刷新最優解的輪次,該式表示離上次取到局部最優解的時間越久,局部最優解對當前解產生的影響越大;式(29)中的count函數接受一個表達式作為輸入,返回符合該表達式的粒子個數,該式表示粒子群越密,隨機擾動概率就越大,有助于粒子群在收縮至局部最優后跳出。
3 實驗結果分析
本文實驗分為3個部分:1)在真實日訂單集上選取6個連續的時間片,檢驗本文提出的分層PSO算法對比單層PSO算法在時間上的優勢;2)構建小規模訂單集,在充分迭代的前提下進行消融實驗,對本文針對動態公交問題改造的自適應機制和變異機制對算法的收斂過程及最終結果的影響進行分析和比較;3)在完全仿真環境中,限制計算時間在真實計算時間的要求內即5 s內處理當前時間片的所有訂單,至多約200條訂單,使用區域真實日訂單集對本文算法及PSO算法、貪婪插入(GI)算法、VNS算法、蟻群(AC)算法和固定公交進行比較,并分析本文算法的有效性。
3.1 實驗環境設置
本文實驗環境基于重慶市北碚區蔡家崗街道的道路搭建,蔡家崗街道人口約16.45萬人,面積約45.75 km2,使用蔡家崗街道范圍內的80個公交車站作為圖結構的節點,構建公交站點間202條有向邊,使用公交車站間的最短路徑的實時通行時間作為動態道路圖結構的邊長度,并采用重慶市公交4.38億條歷史GPS數據生成動態道路圖、3 940.7萬條歷史打卡數據生成出行數據集,作為預計算路徑集的輸入數據。在實驗區域,公交運營時間為05:00—23:00,動態公交服務器每10 s響應之前10 s的所有訂單,即一個時間片為10 s,全天共6 480個時間片。單時間片實驗截取了一個有32個新加入訂單的時間片;部分時間片實驗截取了6個時間片進行實驗;全天仿真實驗使用數據集中一天約50 000條真實出行需求作為訂單集,該訂單集中訂單的平均里程為6.4 km,當天固定公交平均行駛速度為20 km/h。采用當地公交公司139輛所有在庫公交車作為車輛上限,并設置每車同時接受的訂單數至多為公交車的實際座位數31座。本文的實驗運行于Inter 12700CPU和Win 11系統,算法采用Python 3.10進行開發,主要調用了numpy包。
3.2 實驗參數與指標設置
根據模型的目標函數,動態公交在運營過程中主要關心4個指標,即接單率、乘客候車時間、乘客在車時間和運營里程。在本文的實驗結果中也將體現這些運營指標,并設置最大可用車輛數這一參數用于體現所需的司機工時。在本文算法及各對比算法中,為保證最壞乘客體驗,設置了每個訂單的最長在車時間為1.2倍的直接從訂單出發地到目的地的預計時間。對除固定公交以外的算法均設置了訂單等待接單時間窗,訂單發起后的10 min內若仍無法將訂單分配給車輛,則自動拒絕訂單。
經使用不同系數測試,將改進PSO算法與原始PSO算法的初始慣性系數設為0.5,靜態全局學習系數設為0.4,靜態局部學習系數設為0.2。限制本文算法、原始PSO算法、變鄰域搜索算法和蟻群算法的迭代輪次最多為100輪。設改進PSO算法的路徑層在檢索到相同解時的迭代輪次,即圖2中的“較少次數”為20輪;無相關解時的迭代輪次,即圖2中的“較多次數”為100輪。
3.3 分層粒子群對算法計算時間的影響分析
本文針對原始PSO算法計算耗時較長的問題,結合動態公交問題的解包含兩部分的特點,以及動態公交問題在不同時間片之間路徑層的解具有可復用、可繼承性的特點,提出了分層PSO算法。分層PSO算法在單時間片內能復用車輛種類一致的車輛粒子解的結果、繼承車輛種類相近的粒子解、加速新粒子求解過程,并能在不同時間片間復用、繼承,從而減小PSO算法的開銷。本文截取6個時間片用于對比分層與不分層PSO算法的實驗,實驗結果如圖3所示。實驗結果表明,在動態公交問題中將粒子解劃分為多層可以有效節約單時間片及跨時間片的計算時間開銷,整體上降低了PSO算法的計算開銷。
圖3 多層與單層PSO算法在多時間片下的計算時間Fig.3 Calculation time of multi-layer PSO algorithm and single-layer PSO algorithm under multiple time slices
3.4 自適應變異機制對算法收斂過程和結果的影響分析
本文通過提出編輯距離的概念將連續空間中的自適應變異機制引入離散空間。為研究自適應變量和隨機擾動變異機制的作用,設計了基于單個時間片的消融實驗用于測試這兩點改進的有效性,結果如圖4、圖5所示。
圖4 自適應變異機制對算法收斂的影響Fig.4 The impact of adaptive mutation mechanism on algorithm convergence
圖5 自適應變異機制對算法結果的影響Fig.5 The impact of adaptive mutation mechanism on algorithm results
實驗結果顯示:在對算法收斂過程的影響上,隨機擾動算子能有效擴大算法的搜索范圍,而動態參數可以在收斂早期加快收斂速度,隨后有效避免算法早熟;在算法結果上,僅使用隨機擾動在所選實驗參數下,算法反而過快收斂于局部最優,動態參數的使用則能有效提高算法的性能。
3.5 全天時間片實驗數據分析
為充分驗證本文算法的有效性,在全天時間片真實訂單集上進行了實驗,并與原始PSO算法、GI算法、VNS算法、AC算法和固定公交進行比較,實驗結果見表1。
表1 全天時間片實驗結果Table 1 Whole day time slice experiment results
表1結果顯示:固定公交在運營里程方面具有優勢,但在不允許超載的情況下,大量乘客需要進行超長時間的等待才能上車,或由于運營時間結束也未能上車而被被動拒單;在設置的100輪迭代過程中,原始PSO算法所求得的路徑較差,而蟻群算法所求得的路徑較優,但滿足的訂單數相對較少;相較于GI算法、VNS算法,本文算法在高接單率、低運營里程的前提下,在乘客體驗方面也仍有較好的表現,具有相當的實用價值。
本文算法、PSO、VNS和AC算法均有迭代過程,因此可能運行時間較長,故限制算法的最大迭代輪次為100輪。在全天時間片上,上述4個需要迭代的算法運行時長統計見表2。
表2 全時間片運行時長對比Table 2 Full time slice runtime comparison 單位:s
表2結果顯示,本文算法在運行時長方面相對其他需要迭代的算法具有一定的優勢。在最長單時間片計算時間上,PSO、VNS和AC算法均超過了10 s,由于算法運行中單時間片需要響應在該時間片的10 s內的所有訂單,單時間片運行時間超過10 s實際上表示該算法無法適用于該片區的動態公交問題,而本文算法能在10 s內完成響應,因此具有實用價值。
4 結束語
本文針對城市公交的新模式——動態公交,具體地分析了它所涉及的限制條件,并構建了模型。隨后,本文針對動態公交問題搜索范圍大、易陷入局部最優等特點,引入了PSO算法對其進行求解。本文針對動態公交問題的解空間是離散空間的情況,提出了解的編輯距離的概念,并在此基礎上設計了新的動態收斂系數和隨機擾動系數;針對動態公交解具有兩部分的特點,創新性地提出了分層粒子群,并提出路徑層粒子的復用和繼承方法。最后,本文設計了3類實驗,分別測試、對比了算法的計算效率和結果收斂性。5個時間片上的實驗結果表明,本文提出的粒子群分層、復用、繼承機制能降低算法80%的計算耗時;單個時間片實驗結果表明,引入的自適應變異機制能有效優化算法的收斂過程,避免算法早熟現象、避免陷入局部最優;全天時間片實驗結果表明,本文算法相較于固定公交能在同等運力限制下,提高22%的乘客接單率并節省39.1%的乘客出行時間,相較于其他算法,本文算法平均縮短85.3%的計算用時,降低20%里程數,并提高超12%的接單率。整體結果表明,本文算法能夠滿足當前動態公交運營的需要。在未來的研究方向上,可以嘗試結合其他啟發式算法設計混合算法對動態公交問題進行求解,從而進一步提升求解速度和準確性。
