面向復雜物流配送場景的車輛路徑規劃多任務輔助進化算法

李堅強 蔡俊創 孫 濤 朱慶靈 林秋鎮

車輛路徑規劃問題(Vehicle routing problem,VRP)作為一個經典的組合優化問題,在車輛輔助多無人機監控[1]、機場接送服務[2]、無人駕駛車輛路徑規劃[3-5]、物流[6-8]等領域廣泛應用,因此近年來引起研究者的廣泛關注.一般來說,VRP 的優化目標是最小化車輛從倉庫出發并為多個客戶派送貨物的路徑總成本.VRP 已被證明是NP-難問題[9-10],因此是一個極具挑戰性的組合優化問題.在過去的幾十年中,學者們開展了大量求解VRP 相關問題的研究工作.例如,為更好地優化大規模VRP,文獻[11]提出一種進化多目標路徑分組方法.該方法采用多目標進化算法進行路徑分組,同時優化3 個目標,即組內距離、組間距離和組間大小平衡,然后使用局部搜索方法提高組內路徑的質量.

近年來,復雜物流配送場景的VRP 引起研究人員的廣泛關注.在實際應用中,綠色制造業和物流在現代供應鏈管理中扮演著重要角色[12].制造工廠需要從客戶處收集廢棄產品,以供再次使用或適當處置,這被稱為逆向物流[13].一般來說,逆向物流與貨物的雙向流動有關,即交貨和取貨.前者指向客戶交付貨物,后者指從客戶處收取貨物.由于逆向物流在降低能源消耗和減少環境污染方面的顯著作用,其已應用于各個應用場景的配送系統,如圖書館圖書配送[14]、雜貨配送[15]和包裹配送[16]等.此外,為提高配送效率,取送貨服務需要在預定的時間窗口內完成.這類問題稱為帶時間窗和同時取送貨的車輛路徑問題 (Vehicle routing problem with simultaneous pickup-delivery and time windows,VRPPDT)[17].

VRPPDT 是一個更具挑戰性的組合優化問題,包含經典VRP 中不存在的一些復雜約束,因此也是一個NP-難問題[18-20].在這些約束條件中,時間窗口定義了車輛到達客戶并開始服務的最早和最晚時間,具有軟時間窗和硬時間窗約束.配送服務違反軟時間窗約束將會受到懲罰[21],但不能違反硬時間窗約束,即如果車輛在時間窗口之前到達,則必須等到服務開始時間,而且不允許在時間窗口之后到達[22].本文考慮硬時間窗約束,規劃一隊同質或異質車輛從倉庫出發,為分布在不同地區的客戶提供服務.車輛不僅需要將貨物從倉庫交付給客戶,還需要同時在客戶處收取貨物帶回倉庫,且不能違反車輛裝載容量和客戶指定的時間窗約束[23].一般的數學規劃方法難以求解上述VRPPDT[17],因此研究人員通常設計啟發式算法進行求解,期望在合理計算時間內找到高質量的候選解.目前求解VRPPDT 的啟發式算法包括差分進化[24]、遺傳算法[17]、模擬退火[13]、群體智能[25]、可變鄰域搜索[26]、自適應大鄰域搜索[27]等.

然而,在現實應用中,很少有問題是孤立存在的,正確使用從相關問題中學到的知識,可以提高解決新問題的能力[28-29].因此,相關文獻中提出遷移優化方法,通過從已優化的相似任務中遷移知識到新任務來提高其優化效果[30].這種進化多任務(Evolutional multitasking,EMT)算法已成為進化計算領域的研究熱點,其目的是通過多個相似任務之間的知識遷移,加快全局最優解的搜索速度[31-34].與傳統進化算法求解單個優化任務相比,EMT 算法可以同時求解多個優化任務,且每個任務對應一個特定的優化問題.通過利用優化問題之間潛在的協同作用,EMT 算法在解質量和搜索速度方面的優秀性能已在組合優化問題上得到驗證[35-37].例如,隨著眾包和共享經濟的出現,文獻[35]研究一種具有臨時駕駛員的廣義車輛路徑問題變體,稱為具有異質容量、時間窗和臨時駕駛員的車輛路徑問題(Vehicle routing problem with heterogeneous capacity,time window,and occasional driver,VRPHTO),同時提出一種新的進化多任務算法,使用單個種群同時優化多個VRPHTO.與大多數現有的通過交叉實現跨任務隱式知識遷移的EMT 算法不同,文獻[36]提出一種顯式EMT 算法(Explicit EMT algorithm,EEMTA)用于求解VRP 等組合優化問題.EEMTA 包含用于捕獲遷移映射的加權L1范數正則化學習過程,以及基于解的跨VRP知識遷移過程,其性能在仿真實驗中被證明是有效的.為加快車輛路徑優化的速度,文獻[38]建議通過學習新的客戶表示來捕獲之前優化的路徑規劃解中隱藏的有用特征.這些客戶表示可以作為先驗知識在VRP 之間進行傳遞,從而優化目標VRP.文獻[39]求解只帶有容量約束的一般VRP 時采用Kmeans 方法,將原VRP 分解為多個只包含單條路徑的簡單VRP 作為子任務,并使用模因搜索同時優化子任務和原始任務.最后,所有子任務的解直接疊加組成原始任務的解,以實現子任務優化原始VRP 任務.然而,其知識遷移方式比較簡單,只是使用簡單的分解和合并方法來生成原始VRP 任務的候選解.

受此啟發,為提高VRP 算法的性能,EMT 算法可以在多種形式的VRP 上執行進化搜索,而不僅僅是在單一形式VRP 上.因此,在不同形式的VRP 上搜索得到的有用路徑軌跡可以在多任務之間進行傳遞,以加速車輛路徑規劃的搜索過程.因此,為更好地求解復雜物流配送場景的大規模VRPPDT,本文首先介紹使用EMT 算法求解VRPPDT 的想法,并提出一種面向復雜物流配送場景的車輛路徑規劃多任務輔助進化算法(Multitask-based assisted evolutionary algorithm,MBEA)用于求解大規模VRPPDT.MBEA 首先將原大規模VRPPDT 分解為多個低維子任務,并利用這些子任務使用EMT 算法求解原VRPPDT.MBEA 主要包括3 個操作: 1)子任務生成;2)基于多任務的知識遷移;3)環境選擇.在子任務生成中,MBEA 通過從原任務中隨機選擇一些客戶訂單來創建多個不同的子任務.因為子任務的客戶規模比原任務小,所以更容易求解這些子任務.在基于多任務的知識遷移中,MBEA 使用進化多任務方法用于生成原任務和優化子任務的候選解.在環境選擇中,MBEA 從父代種群和子代種群的混合種群中選擇N個(N是種群大小)最好的個體存活到下一代.經過不斷迭代進化,MBEA 可以快速得到原大規模VRPPDT 的高質量候選解.本文的主要貢獻總結如下.

1)針對復雜物流配送場景的大規模VRPPDT,提出一種多任務輔助進化算法MBEA.MBEA 包括子任務生成、基于多任務的知識遷移和環境選擇等操作,可以在子任務和遷移優化方法的幫助下更快地求解大規模VRPPDT.這是首次應用進化多任務方法用于求解大規模VRPPDT,具有顯著的實際應用與研究價值.

2)MBEA 的優化性能已在實際大規模VRPPDT 數據集上得到驗證.該數據集來自于京東公司的物流配送系統.與最近提出的5 種VRPPDT 算法相比,MBEA 在大多數測試問題上都能取得更好的優化性能,證明了遷移優化對大規模VRPPDT的有效性.

本文的其余部分組織如下.第1 節給出本文研究的VRPPDT 定義,并回顧現有的相關研究.第2 節詳細介紹MBEA 算法,并在第3 節給出其與最新提出的VRPPDT 算法在大規模京東數據集的仿真比較結果.最后,第4 節給出本文的結論并討論未來的研究工作.

1 背景

1.1 帶時間窗和同時取送貨的車輛路徑問題

在復雜物流配送場景里,帶時間窗和同時取送貨的車輛路徑問題VRPPDT 需要在特定時間窗口內提供同時取送貨服務.VRPPDT 的目標是為多輛車規劃路徑,并在滿足約束條件的同時以最低的總成本為客戶提供同時取送貨服務.一般來說,VRPPDT 可以由完全圖G=(V,E)來表示,其中V={0,1,2,···,M}是倉庫和M個客戶節點的集合,E={〈i,j〉|i,j∈V,i≠j}是每個節點之間的弧集.VRPPDT 模型如圖1 所示.為方便表示,倉庫始終表示為0,客戶表示為 1,2,···,M.每條弧〈i,j〉∈E與行駛距離dist(i,j)和行駛時間time(i,j)相關.每個節點i∈V有5 個屬性,即送貨需求di、提貨需求pi、時間窗口[ai,bi] 和服務時間si.di是從倉庫交付給客戶i的貨物數量.pi是從客戶i處取走的必須交付到倉庫的貨物數量.ai和bi分別是客戶i接受取貨服務和送貨服務的開始時間和結束時間.當車輛在開始時間ai之前到達客戶i時,車輛必須等待;車輛不能在結束時間bi之后到達客戶i.最后,si是車輛在客戶i卸載和裝載貨物所需的時間.a0和b0分別是車輛可以離開倉庫0 的最早時間和車輛可以返回倉庫0 的最晚時間,且d0=p0=s0=0.

圖1 VRPPDT 模型Fig.1 The model of the VRPPDT

假設在當前配置中,最初在倉庫0 中有J輛車可以調度,其中每輛車的容量為C,調度成本為u1.每輛車從倉庫出發,為客戶送貨、取貨,最后返回倉庫.因此,VRPPDT 的解S由一組車輛路線表示,即S={R1,R2,···,RK}.每條路線Ri由車輛訪問的一系列節點組成,即Ri=(hi,1,hi,2,···,hi,Li),其中,hi,j表示車輛在路線Ri訪問的第j個節點,Li表示路線Ri的節點長度.為方便介紹,這里省略了Ri中的下標i,即R=(h1,h2,···,hL),則R的總行駛距離記為TD(R),計算式為

車輛到達和離開hj的時間,分別表示為arr(hj)和dep(hj),由以下計算式計算得出

車輛到達hj時的載貨量,記為load(hj),計算式為

解S的總成本記為TC(S),由兩部分組成: 車輛調度成本u1·K和運輸成本u2·TD(S).因此,VRPPDT的優化目標是找到TC值最小的S,計算式為

在目標函數(4)中,u1表示每輛車的調度成本,u2表示單位距離的運輸成本,使用的車輛數K不能超過可用車輛數J.約束(5)表示每條路線必須從倉庫出發并返回倉庫.約束(6)規定每個顧客只能服務一次.約束(7)保證每輛車在運輸過程中不能超載.約束(8)表示必須在規定時間窗口內為客戶服務.約束(9)規定車輛只能在開始時間a0之后離開倉庫,并且必須在結束時間b0之前返回倉庫.

VRPPDT 的主要難點是容量和服務時間受到限制.前者是客戶可以同時有送貨和取貨的需求.由于這兩種需求對車輛負載的影響不同(一個增加負載,另一個減少負載),這樣的特性使得在容量限制下很難確定分配多少車輛服務客戶.后者是每個客戶都與一個硬時間窗口相關聯,進一步增加了為特定車輛規劃訂單服務順序的難度.除上述約束外,還需要考慮VRPPDT 搜索空間的索引.因此,充分平衡候選解的多樣性和收斂性對于算法設計也很重要.

1.2 相關工作

當前求解VRPPDT 的方法通常可以分為兩類:精確方法和啟發式方法[40-42].下面將詳細介紹相關研究工作.

近年來,許多研究人員提出求解VRPPDT的精確算法.文獻[43]首次嘗試使用精確算法求解多達20 個客戶的VRPPDT.文獻[44]研究如何將分支定價技術用于求解VRPPDT,并對比了兩種不同求解定價子問題的方法: 精確動態規劃和狀態空間松弛.通過應用雙向搜索,文獻[44]通過實驗仿真驗證分支定價技術在求解VRPPDT 中的有效性.文獻[45]提出VRPPDT 的兩種混合整數線性模型公式,即車流模型和商品流模型.同時,文獻[45]提出縮小域的預處理技術和有效的切割平面來強化提出的模型,并使用數學優化軟件CPLEX 求解源自實際問題的對稱基準實例和新的不對稱實例.其中,CPLEX 通過將該實例轉化為數學規劃模型以快速獲得候選解.與啟發式算法相比,求解VRPSPD(VRP with simultaneous pickup and delivery)的精確方法很少.因此,文獻[46]首先為VRPSPD 開發一種剪支定價算法.該算法在涉及多達200 個客戶的著名基準問題上進行了測試.然而,精確算法通常只適用于求解客戶數量少于100 的小問題實例,在求解大規模問題上性能仍不理想[47].

在過去十年中,用于求解VRPPDT[43]的啟發式算法相比精確方法更受研究人員的歡迎.這些啟發式方法主要可以分為兩類: 基于單一解的算法和基于群體的算法[48].具體來說,基于單一解的算法,如模擬退火(Simulated annealing,SA)[49]、禁忌搜索(Tabu search,TS)[50]、大鄰域搜索(Large neighborhood search,LNS)[51]等,稱為軌跡方法.軌跡方法只涉及單一解在搜索空間中移動以形成軌跡,被視為局部搜索方法的智能版本.為開發一種有效的啟發式算法來解決VRPPDT,文獻[23]提出一種并行模擬退火算法.該算法包括基于剩余容量和徑向超載的插入啟發式算法.文獻[52]設計一種混合局部搜索算法,用于求解同時取送貨的異構車輛路徑問題.該算法將非單調閾值調整策略與禁忌搜索相結合,且該閾值函數具有能夠自我調整的自適應特性.文獻[53]提出一種基于分解的局部搜索方法用于優化多目標VRPPDT,可以在短時間內獲得高質量的有效候選解.為加快收斂速度,該方法提出了一種使用7 種鄰域算子的新型局部搜索算法.同時,為保持多樣性,該方法采用分解的概念,首先將問題分解為多個單目標問題,然后利用局部搜索對這些子問題進行優化.

另一方面,用于求解VRPPDT 的基于種群的啟發式算法包括進化算法(即遺傳算法[54-55]、模因算法[56-57]、差分進化算法[58]等)和群體智能算法(即粒子群優化算法[59]、蟻群優化算法[60-61]等).在求解VRPPDT 時,基于種群的啟發式算法起著至關重要的作用,并提供良好的VRPPDT 候選解.為求解大規模VRPPDT,文獻[62]提出一種具有高效局部搜索和擴展鄰域的新型模因算法(Memetic algorithm with efficient local search and extended neighborhood,MATE).由于MATE 具有新穎的初始化過程、交叉和大步長的局部搜索算子,與現有算法相比,它能夠更高效地搜索決策空間.此外,由于其評估機制具有常數級時間復雜度,MATE 的局部搜索操作也更加高效.為滿足實際逆向物流中包含的所有復雜約束,文獻[63]構建一種新的數學模型,用于處理具有時間窗和多個決策者的同時取送貨問題.同時,文獻[63]提出一種基于混合優先級的嵌套遺傳算法,結合模糊邏輯控制器和模糊隨機模擬方法用于求解該問題.文獻[64]定義一個通用多目標VRPPDT (Multiobjective VRPPDT,MO-VRPPDT),并用于求解現實世界的一組MOVRPPDT.同時,文獻[64]設計多目標局部搜索算法和多目標模因算法用于求解MO-VRPPDT.為盡可能降低路徑規劃的運營成本,文獻[65]提出一種改進的粒子群優化算法,在滿足客戶取送貨需求的同時最小化路徑的總距離.

2 算法設計

本節詳細介紹面向復雜物流配送場景的車輛路徑規劃多任務輔助進化算法(MBEA),用于解決同時取送貨和時間窗的大規模車輛路徑問題VRPPDT.MBEA 的總體框架圖如圖2 所示.首先,第2.1 節介紹MBEA 的算法流程.接著,第2.2 節介紹子任務生成.然后,第2.3 節介紹基于多任務的知識遷移.最后,第2.4 節介紹MBEA 的環境選擇操作.

圖2 MBEA 總體框架圖Fig.2 The overall framework diagram of MBEA

2.1 MBEA 總體框架

受最近提出的多任務輔助優化方法[31]啟發,MBEA 將一個原VRPPDT 分解為k個較低維度的子任務,并利用這些子任務使用進化多任務方法去優化原VRPPDT.在子任務生成中,MBEA 通過從原始任務中隨機選擇?ran×|V|」(ran∈(0,1),|V|是原始任務的客戶數量)個客戶訂單來創建k個不同的子任務.由于其客戶數量比原任務少,子任務相對容易求解.而且,子任務中的客戶是原任務的子集,所以原任務和子任務具有一定的相似性.因此,通過將子任務的最優解遷移到原任務上可以加快其求解的收斂速度.在基于多任務的知識遷移中,MBEA 使用兩種不同的交叉算子生成子代.當兩個父代個體屬于同一個任務時,MBEA 將使用基于路徑的交叉[66]生成子代;否則,MBEA 將使用順序交叉[67]生成子代.在環境選擇中,MBEA 先評估子代群體中的每個個體.然后,MBEA 會從父代種群和子代種群的混合種群中選出N個(N是種群規模)最好的個體存活到下一代.經過不斷地迭代進化,MBEA 可以得到VRPPDT 的高質量候選解.

為詳細說明MBEA 的步驟,算法1 中給出了它的偽代碼,其中有兩個輸入: 一個要解決的VRPPDT 實例F(V,E)和子任務的數量k.在第1 行,MBEA 首先使用基于序列的統一表示來初始化具有N個個體的種群P,每個個體都有 |V|個變量.圖3 顯示了一個具有10 個客戶的個體編碼方法.然后,MBEA 開始通過多階段進化來優化種群P.在每個階段,子任務生成(Task generation,TG)操作首先創建k個不同的子任務(第3 行).這些子任務的客戶數量遠少于原VRPPDT.然后,當評估次數小于評價次數TE時,MBEA 執行基于多任務的知識遷移(Multitask-based knowledge transfer,MBKT)操作和環境選擇(Environmental selection,ES)操作用于優化種群.在第5 行,MBEA 對父代種群P和 (k+1)個任務使用MBKT 操作生成子代種群Q.然后,在第6 行,MBEA 使用ES 操作從父代種群P和子代種群Q選擇N個個體作為新種群P存活到下一代.當評估次數超過TE時,MBEA 保留種群P中的Nbe個最佳個體,并重新初始化剩余的N-Nbe個個體以適應下一階段的進化(第8 行).

圖3 一個個體的編碼方法Fig.3 The coding method of an individual

算法 1.MBEA 總體框架

2.2 子任務生成操作

本節介紹TG 操作以及進化多任務中使用的一些概念.為闡明子任務生成操作的步驟,下面介紹算法2 中的偽代碼.TG 有3 個輸入: VRPPDTF(V,E)、種群P和子任務數k.在第2 行,TG 首先生成一個隨機數ran(ran∈(lower,1)),其中lower表示子任務的維度相對于原任務的最低比例.然后,在第3 行,TG 通過公式D=?ran×|V|」計算第i個子任務中的客戶數量來確定子任務的維度.在第4 行,TG 從原始任務F(V,E)中選擇索引為1 到D的D個客戶組成節點信息Vi和對應的邊信息Ei作為子任務F(Vi,Ei).圖4 上面的虛框中給出了從維度為10 的候選解 [1,10,2,8,3,6,7,4,9,5] 中生成子任務候選解的示例.若生成的隨機數ran=0.6,則表示子任務的維度是6,這時便從原任務中選擇索引1 到6 的節點作為子任務的候選解[1,2,3,6,4,5].由于子任務是從原任務中隨機選擇D個客戶生成的,這確保了子任務的多樣性,并有助于原任務跳出局部最優解;此外,由于子任務是原任務的子集,其拓撲結構與原任務相似,且相對容易求解,故子任務能夠輔助加快原任務往全局最優解的收斂速度.該子任務生成的有效性將在第3.5節實驗中進行討論與驗證.

算法 2.任務生成(TG)

然后,在第6～11 行,TG 將計算進化多任務中的4 個參數: 因子代價(Factorial cost)、因子排位(Factorial rank)、標量適應度(Scalar fitness)和技能因子(Skill factor)[31].個體p的因子代價fp表示其在特定任務上的適應度或目標值.對于k+1個任務,會有一個長度為k+1 的向量,其中每個維度給出p在相應任務上的適應度.因子排位rp表示個體p在種群成員列表中的索引.該列表是按種群個體在一個特定任務上的因子代價升序排序的.個體p的標量適應度φp是根據其在所有任務中的最佳排名來定義的,即φp=[1/minj∈{0,···,k}].個體p的技能因子τp表示在所有任務中p表現最有效的任務,即τp=arg min,j∈{0,1,···,k}.最后,TG輸出k個子任務F(V1,E1),F(V2,E2),···,F(Vk,Ek)和種群P.從算法2 可以看出,隨機生成k個子任務的時間復雜度是O(k),而計算種群P(種群規模為N)的各個指標的時間復雜度是O(N),故MBEA中的子任務生成操作需要的最壞時間復雜度是O(k+N).

2.3 基于多任務知識遷移

本節介紹基于多任務的知識遷移MBKT 操作.在生成子代過程中,每次通過錦標賽選擇法從父代種群P中選擇兩個父代個體.當兩個父代個體屬于同一個任務時,MBEA 將使用基于路徑的交叉生成子代;否則,MBEA 將使用順序交叉進行知識遷移生成子代.為詳細說明MBKT 的步驟,算法3 中介紹了它的偽代碼.MBKT 有兩個輸入: 種群P和所有任務F(V,E),F(V1,E1),···,F(Vk,Ek).在第1行,MBKT 先將一個空種群Q初始化為子代種群.然后,MBKT 會生成子代個體并將它們添加到Q中,直到Q中的個體數量達到N.為生成子代個體,在第3 行,MBKT 首先通過錦標賽選擇法從父代種群P中選擇兩個父代個體p1和p2.然后,MBKT 會判斷p1的技能因子和p2的技能因子是否相等.如果等于,則p1和p2的解在該任務表現一樣好.然后,在第5 行,MBKT 將根據任務將p1和p2解 碼為.圖4顯示了如何根據或將原始空間中的候選解解碼為子空間.從算法3可以得出,這個基于多任務的知識遷移操作需要的最壞時間復雜度是O(N).

算法 3.基于多任務的知識遷移(MBKT)

在圖4 中,候選解在原空間的維數為10.如果子任務F(V1,E1)中有5 個客戶,那么MBKT 會刪除解 [1,10,2,8,3,6,7,4,9,5] 中大于5 的編碼,從而得到子任務F(V1,E1)的解 [1,2,3,4,5].然后,在第6 行,MBKT 將和的編碼拆分為多條路徑.圖5 顯示了將個體的編碼拆分為多條路徑的過程.假設個體編碼為 [1,2,3,4,5],車輛容量為10,車輛成本為20,客戶服務時間為0.在滿足時間窗和車輛容量約束的條件下,解碼序列可以分為3 種不同的路徑結果:a=[0,1,0,2,0,3,0,4,5,0],b=[0,1,2,0,3,4,0,5,0] 和c=[0,1,0,2,3,0,4,5,0].MBKT 會計算不同路徑的總成本,最終選擇成本最低的路徑.以路徑c中的路線[0,1,0]為例,行程成本為30,車輛成本為20,因此總成本為50.MBKT 計算每條可能路徑的總成本.最后,我們可以得到成本最低的路徑: [0,1,0,2,3,0,4,5,0],總成本為275.

圖5 一個解的切分過程Fig.5 The splitting process of a solution

圖6 基于路徑的交叉過程Fig.6 The operation process of the route-based crossover

如果τp1不等于τp2,則MBKT 將執行知識遷移操作.首先,MBKT 根據原始任務F(V,E)將p1和p2解碼為和(第9 行).然后,MBKT 對兩個父代個體和使用順序交叉算子生成兩個子代個體c1和c2(第10行).順序交叉算子的操作如圖7所示.順序交叉算子先選擇來自父代個體序列的一段[9,2,10,4]作為子代c1對應段的位置.然后,順序交叉算子將中不屬于段[9,2,10,4]的編碼按順序插入到c1中,從而得到子代個體c1.子代個體c2也可以用同樣的方法生成.當子代種群Q中的個體數量達到N時,生成子代的操作結束.最后,MBKT 返回子代種群Q.

圖7 順序交叉操作過程Fig.7 The operation process of the order crossover

2.4 環境選擇

本節介紹環境選擇ES 操作.當得到父代種群P和子代種群Q時,MBEA 將選擇更好的個體存活到下一代.為詳細說明ES 操作的步驟,算法4 給出了它的偽代碼.ES 首先需要評估種群Q中的每個個體.在第2 行,ES 生成一個隨機數ran∈(0,1).然后,在第3～7 行,群體Q中的個體c以50%的概率繼承父代個體p1的技能因子τp1,或以50%的概率繼承父代個體p2的技能因子τp2.在第8 行,ES 根據其技能因子τc對c執行局部搜索操作,并更新c在任務F(Vτc,Eτc)的因子代價fc.接下來,在第9 行,ES 將c在所有未評估任務的因子代價fc設置為∞.在對種群Q中的所有個體進行評估后,在第11 行,ES 將父代種群P和子代種群Q合并為一個新種群R.然后,在第12 行,ES 更新種群R中所有個體的因子排位和標量適應度.在第13 行,根據個體的標量適應度,ES 從種群R中選出最好的N個個體作為新的種群P存活到下一代.最后,算法4 將最終種群P作為結果并輸出.由于種群Q的大小為N,故由算法4 易得,環境選擇的最壞時間復雜度是O(N).

算法 4.環境選擇(ES)

3 仿真實驗

3.1 實驗設置

為驗證所提出的MBEA 算法的有效性,特別是在解決復雜物流配送場景的大規模VRPPDT 方面,本文使用一個大規模京東數據集[62]作為測試問題.在此數據集上,本文將MBEA 與最近提出的5種算法(MATE[62]、EMA[35]、CCMO[68]、GVNS[69]和VNSME[70])進行比較.在這5 種對比算法中,MATE 是由種群進化和局部搜索相結合的模因算法,GVNS 是單個體的元啟發式算法,VNSME是由4 種局部搜索策略和擾動算子構成的元啟發式算法,EMA 是進化多任務遷移學習算法,CCMO是子任務協同優化算法.接著,本文進行消融實驗,驗證基于路徑的交叉 (Route-based crossover,RBX)算子和順序交叉 (Order crossover,OX)算子的有效性.最后,本文討論了MBEA 中參數lower和參數k的設置對性能的影響,參數k代表子任務的數量.參數lower表示子任務的客戶數量的范圍,其范圍在 (N×lower,N)之間.其中k=0 時表示沒有在MBEA 中使用子任務,可以用于驗證子任務對MBEA 性能提升的有效性.對于參數k和lower,本文還將進行參數敏感性分析.

1)數據集.本文使用文獻[62]提出的大規模數據集來評估MBEA 的性能.該數據集來自京東物流配送系統.在該系統中,除需派送客戶購買的商品外,還需要收取客戶商品(例如,有缺陷的商品或需要維修的商品),這兩者都必須在預定的時間窗內提供客戶滿意的服務.因此,本質上京東物流配送問題可以建模為本文研究的VRPPDT.原始數據是從系統中一段時間內產生的多個客戶服務請求中收集得到的.然后,原始數據用于生成具有200、400、600、800 和1 000 個客戶的5 種規模測試問題.對于每種規模問題,會從原始數據中生成4 個實例,最終為本實驗提供包含20 個實例的問題測試集.在這個數據集中,對NV(車輛數量)或TD(行駛距離)的優化沒有優先級.式(4)中的參數u1和u2是根據物流配送系統中的估計值給出的,其目標是最小化TC(總成本),即車輛調度成本和行駛路程成本之和.大規模京東數據集的具體設置如表1 所示.表1 中,|V|為客戶數量,C為車輛容量,J為可使用車輛數量.

表1 京東數據集的特性Table 1 Properties of Jingdong dataset

2)參數設置.本文選用最近提出的5 種算法作為對比算法,包括MATE、EMA、CCMO、GVNS和VNSME.對比算法的參數根據原論文中給出的推薦參數進行設置.所有算法在大規模京東數據集的20 個實例上獨立運行20 次.MBEA 算法的詳細參數如表2 所示.MBEA 有7 個參數需要設置,分別是Evaluation、TE、N、Nre、Nbe、k及lower.Evaluation是總的評價次數,MBEA 和比較算法的評價次數都設置為18 000.MBEA 是一種多階段進化算法,其中種群大小N設置為36,每個階段的評價次數TE設置為3 600,即每一個階段種群進化100 代.MBEA 的階段數Nre設置為5.當MBEA完成一個階段并進入下一個階段時,種群將保留前一階段的Nbe個最好的個體,而種群中的其他個體重新初始化.

表2 MBEA 算法參數設置Table 2 Parameter settings in MBEA

3.2 大規模車輛路徑問題的實驗結果和分析

表3 給出了MBEA 與5 種比較算法(MATE、EMA、CCMO、GVNS 和VNSME)在大規模京東數據集上的對比結果,記錄了車輛數量NV、行駛距離TD、總成本TC(TC=300×NV+TD)和CPU時間.在表3 的20 個測試問題中,MBEA 在18 個測試問題中取得最小的TC值,因此MBEA 是當中優化性能最好的算法.在客戶規模為200 的測試問題上,MBEA 和MATE 取得的優化效果差不多.MBEA 在F202 和F204 問題上表現最好,MATE在F201 和F203 問題上取得最好結果,而EMA、CCMO、GVNS 和VNSME 在以上4 個問題上都表現較差,均未取得最好結果.當測試問題的客戶規模增加到400、600、800 和1 000 時,MBEA 的優化效果明顯好于其他5 種算法.例如,在客戶規模為400 的測試問題上,MBEA 的平均TC值是 124 669,EMA 的平均TC值是149 109,MATE 的平均TC值是136 450,CCMO 的平均TC值是155 794,GVNS 的平均TC值是180 370,而VNSME 的平均TC值是141 789.因此,MBEA 取得了最好的平均TC值.與MATE,EMA,CCMO,GVNS 和VNSME 相比,MBEA 的優化目標值(TC)分別提高了8.63%,16.39%,19.98%,30.88%和12.07%.

在其他客戶規模數據集(600、800、1 000)上,MBEA 的平均TC值分別為188 614,220 804 和327 730;MATE 的平均TC值分別為214 861,243 393 和359 545;EMA 的平均TC值分別為250 678,296 887,443 675;CCMO 的平均TC值分別為241 545,293 280 和 444 823;GVNS 的平均TC值分別為266 184,308 754 和446 854;而VNSME的平均TC值分別為215 069,242 376 和346 777.因此,在這3 個客戶規模數據集上,與MATE 相比,MBEA 的優化目標值(TC)分別提高了12.22%,9.28%和8.85%;與EMA 相比,MBEA 的優化目標值(TC)分別提高了24.75%,25.62%和26.13%;與CCMO 相比,MBEA 的優化目標值(TC)分別提高了21.91%,24.71%和26.32%;與GVNS 相比,MBEA 的優化目標值(TC)分別提高了29.14%,28.48%和26.65%;與VNSME 相比,MBEA 的優化目標值(TC)分別提高了12.30%,8.90%和5.49%.由于MBEA 將原始問題分解為k個輔助問題,所以輔助問題的客戶規模相對較小,因此輔助問題比原問題更容易求解并能更快地獲得較好的收斂解.基于輔助問題與原問題的相似性,求解輔助問題得到的收斂解有助于傳遞優化知識幫助求解原問題.在表3 中,MBEA 得到的結果充分驗證了子任務優化知識遷移的有效性.另一方面,當問題客戶規模達到800 和1 000 時,MBEA 的平均運行時間分別是13 017 s 和9 399 s,然而MATE 的平均運行時間分別為21 838 s 和26 459 s,所以MBEA 的運行效率明顯高于MATE,這也驗證了MBEA 在解決大規模問題上的優勢.

MBEA 在5 種客戶規模的數據集上取得上述實驗結果的原因如下.當測試問題的客戶數量較少(即200)時,對該類問題的求解相對容易,因此與其他對比算法相比,MBEA 使用遷移優化的優勢并不明顯.但是,當測試問題的客戶數量逐步增加到400、600、800 和1 000 時,求解問題的難度急劇增加,對比算法便很難找到最優解.在這種情況下,MBEA利用遷移優化具有顯著優勢.因為MBEA 可以通過從更簡單和相似的子任務中遷移有用的路徑信息到原任務,所以能有效加快原任務的求解速度.因此,MBEA 的優化性能明顯好于其他5 種對比算法.

3.3 收斂速度分析

圖8 給出了MBEA 和其他3 種比較算法(EMA、CCMO、MATE)的進化曲線.由于GVNS 和VNSME的終止條件是當前解經過連續迭代鄰域搜索與多次擾動后依然沒有得到改進,所以按照GVNS 和VNSME 的原始設置,當前最優解所使用的迭代次數并不是固定的.因此,圖8 沒有給出GVNS 和VNSME 的收斂軌跡.從圖8 可以看出,與其他3種算法相比,MBEA 具有更快的收斂速度,并且在大多數問題上都能取得更好結果.

圖8 本文提出的方法和對比算法的平均搜索收斂軌跡Fig.8 Averaged search convergence traces of the proposed method and the compared algorithms

3.4 知識遷移中的交叉算子有效性分析

本文的多任務知識遷移操作使用兩種不同的交叉算子來生成子代種群.當兩個個體來自同一個任務時,MBEA 使用RBX 算子優化該任務;當兩個個體來自不同的任務時,MBEA 使用OX 算子交換兩個個體的有用信息進行遷移優化.表4 給出了MBEA 分別使用OX 算子、RBX 算子和RBX+OX算子的實驗結果.從表4 可以看出,OX 對大規模問題的優化效果較差.特別是當問題客戶規模超過200 時,OX 算子得到的TC值明顯大于RBX 和RBX+OX 算子取得的TC值.另一方面,RBX+OX算子的效果在一定程度上優于RBX 算子.當兩個個體來自不同的任務時,RBX 算子不能對來自不同任務的兩個個體進行操作,而OX 算子可以交換任意兩個個體的信息.因此,與單獨使用RBX 算子相比,使用RBX+OX 算子在知識遷移中更有效.

表4 RBX 和OX 的消融實驗結果Table 4 Ablation experiment results of RBX and OX

3.5 參數敏感性實驗和分析

本節對MBEA 中的參數lower和參數k進行參數敏感性分析實驗,其中k表示子任務的數量,lower表示子任務的客戶數量的范圍,其范圍在(N×lower,N)之間.表5 和表6 分別展示了MBEA在大規模京東數據集上的參數分析結果.表5 分析了子任務規模變化(即客戶數量變化)對MBEA 性能的影響.根據文獻[36],在兩個車輛路徑問題中,如果50%的客戶相同,則可以認為這兩個任務是低度相似的;如果90%的客戶相同,則可以認為這兩個任務是高度相似的.因此本文將參數lower設置為5 組,lower的值分別為0.5、0.6、0.7、0.8 和0.9.然后,將MBEA 的子任務數設置為1,在不同的lower設置下求解20 個大規模京東數據集的優化性能.從表5 可以看出,在lower=0.7 的設置下,MBEA 在20 個測試問題上的整體表現是最好的,可以在9 個(總共20 個)測試問題上取得最好結果.在其他參數設置下,MBEA 分別在3 (lower=0.5)、3 (lower=0.6)、2 (lower=0.8)和3 (lower=0.9)個測試問題上取得最好結果.因此,當參數lower設置為0.7 時,MBEA 可以達到整體最佳性能.具體原因分析如下: 當lower的值設置遠小于0.7 時,子任務與原VRPPDT 之間的相似性相對較低,導致有用的路徑特征很少能被MBEA 從子任務遷移到原VRPPDT.相反,當lower的值設置遠大于0.7 時,子任務與原VRPPDT 的相似度過高,導致生成許多高維的子任務.在這種情況下,子任務也很難在有限的時間內求得較優解.因此,當lower的值設置得遠小于或大于0.7 時,MBEA 都無法將有用的路徑特征從子任務遷移到原VRPPDT.綜上,當lower=0.7 時,MBEA 可以在子任務的求解難度和子任務與原任務的相似度之間取得較好的均衡.

表5 MBEA 中參數lower 的敏感性分析Table 5 Sensitivity analysis of lower in MBEA

表6 MBEA 中參數k 的敏感性分析Table 6 Sensitivity analysis of parameter k in MBEA

另一方面,表6 分析了子任務數量(即參數k)對MBEA 性能的影響.在表6 中,參數lower設置為0.7,子任務的數量k分別設置為0、1、2、3,其中k=0 時直接使用進化算法進行優化,沒有生成子任務進行知識遷移過程.當參數k設置為1 (即只有一個子任務)時,MBEA 在12 個測試問題上取得最好的結果.同時,在參數k=0 的情況下,MBEA 僅在1 個測試問題上取得最好的結果.這表明設置子任務來解決大規模VRPPDT 是有效的.但子任務的數量不宜設置太多.因為每個子任務都需要種群中的一些個體進行優化,所以子任務過多會導致種群中優化原始問題的個體較少,最終無法在有限代數內達到收斂狀態.

4 結束語

本文提出面向復雜物流配送場景的車輛路徑規劃多任務輔助進化算法MBEA,通過對多個簡單且相關的子任務使用知識遷移操作來輔助優化原大規模VRPPDT,加快算法收斂速度.與現有算法相比,MBEA 的創新性表現為兩個方面: 子任務生成和基于多任務的知識遷移.子任務生成操作將原始VRPPDT 劃分為多個簡單且相關的子任務.然后MBEA 在進化多任務遷移中使用兩種不同的交叉算子產生下一代種群.當兩個父代個體來自同一個任務時,使用基于路徑的交叉算子(優化)產生子代個體;否則,使用順序交叉算子(遷移)產生子代個體.在本文的實驗分析中,與最近提出的5 種算法相比,MBEA 在京東大規模VRPPDT 數據集上的路徑規劃結果更優.

在未來的工作中,我們將在MBEA 算法的基礎上進一步探索解決VRPPDT 的有效策略.首先,我們將進一步結合問題特征設計出更高效的子任務生成方法.其次,我們將在MBEA 中探索使用更多高效的局部搜索方法.最后,我們將逐步把MBEA構建成一個通用的路徑規劃算法框架,從而支持求解更多的VRP 變體,例如動態VRP、多站點VRP和電動車隊VRP.