多隔間車輛路徑優化問題的局部搜索混合果蠅優化算法求解

吳劍來,劉加林

(湖南人文科技學院 商學院,湖南 婁底 417000)

現代物流業中,物流配送具有運輸貨物種類繁多和運輸需求快速增長兩個重要特點。 為提高運輸效率和降低配送成本,配送系統必須對車輛行進路線進行規劃和優化,盡可能減少車輛行進的路徑長度。 這引發了針對車輛路徑問題(Vehicle Routing Problem, VPR)的研究。 VRP 主要研究在確保車隊從配送中心向客戶運送貨物的同時,盡可能減少車隊所走的路徑總長度,以最低運輸成本滿足客戶需求。 在實際操作過程中,物流配送需要考慮車輛容量的限制,于是引發了對容量受限車輛的路徑問題(Capacity Constraints VRP, CVRP)的研究。CVRP 假設每輛車都有一個恒定的容量Q,每輛車對每個客戶只訪問一次,并且任何一條路徑需要運送的貨物總量都不會超過車輛的總容量;每個客戶需要運送的貨物不同,運輸中不同類型的貨物存放在同一輛車的不同隔間中,每輛車都有固定數量的隔間,每個隔間都有容量限制。

在CVRP 研究的基礎上,近年來業界逐漸關注具有容量約束的多隔間車輛路徑問題(Multi-Compartment VRP, MCVRP)[1]。 MCVRP 研究的目的是在車輛存在多個隔間約束下,找到車隊配送貨物的最小總距離。 多隔間對運輸不能混合在一起的貨物是非常重要的。 例如,MCVRP 方式常用于食品配送,將冷藏食品和非冷藏食品儲存在同一輛車的不同隔間。 Chajakis 和Guignard 探討了兩廂車的規劃模型, 并討論了車輛的配送路徑[2]。MCVRP 也被應用于燃料運輸,多種不同類型的燃料儲存在不同容量的儲罐中[3-4]。 為了獲得更好的效果,MCVRP 經常通過本地搜索和啟發式算法進行增強,如迭代局部搜索算法[5-6]、仿生優化算法中的蟻群算法[7-8]以及蟻群算法與插值方法[9]、禁忌搜索算法[10]和2-opt 方法[11]形成的融合算法。

綜上可知,仿生優化算法已逐漸成為解決MCVRP 更好的選擇。 相比于其他仿生優化算法,果蠅優化算法(Fruit-fly Optimization Algorithm,FOA)是一種新興的進化算法,易于理解、操作和實現[11-15]。 然而,常規的FOA 容易陷入局部收斂,而且在搜索后期收斂速度特別慢。 為了解決這一缺陷,一些學者通過采用混沌理論等方法來改善FOA[16-17]。 盡管FOA 及其改善版本效果良好,但現有對FOA 的研究多集中在解決空間連續優化問題上,對離散優化問題(如組合優化問題)的研究則相對較少。

本文利用混合果蠅優化算法(Hybrid FOA,HFOA),并引入局部搜索策略,解決多隔間車輛路徑優化問題。 受Reed 等人的啟發,本文使用多重比較法將MCVRP 擴展到新的問題中。 本研究設定車隊中的所有車輛都從配送中心出發將各種類型的貨物運輸到客戶處,所有車輛的容量都是相同的,每輛車都可以訪問特定的一組客戶,每個客戶只能被訪問一次。 本文通過局部搜索來提高FOA的搜索能力,確定每輛車所訪問的客戶,以及訪問的先后順序,從而形成車輛路徑。

一、MCVRP 問題的描述與分析

圖1 給出了一個物流配送網絡。 從圖1 可以看出MCVRP 包含以下要素:配送中心(唯一的)、多隔間車輛(MCV)車隊和多個需要配送的客戶。每個客戶的貨物是不同的,每個貨物的配送地點是已定的,每個車輛的隔間都有固定的容量。 每輛車離開配送中心、訪問一些客戶后,最后又返回配送中心,每個客戶只能被訪問一次。 在給定配送點之間的距離后,車輛路徑問題就是要是優化每輛車的路徑,使所有車輛的總行駛距離最短。

圖1 MCV 網絡示意圖

二、利用局部搜索混合果蠅算法求解MCVRP 問題

類似于粒子群算法,FOA 同時考慮當前最優個體和個體狀態更新過程中的最優個體。 通過這種方式,該算法確保果蠅最終聚集在全局最優解的周圍,并同時繼承了每一次迭代的局部最優。 在迭代的過程中,一旦一個個體到達了一個更好的全局最優位置,其他個體會聚集到該個體的周圍。 這樣的個體更新方式降低了種群的多樣性,因為個體信息沒有被共享和繼承,增加了局部最優值和早熟的風險[18-19]。 Zheng 提出了混合果蠅優化算法(HFOA)[20],該算法的每次進化分為4 個階段:嗅覺搜索、視覺搜索、合作進化和退火。 HFOA 通過以下步驟實現。

步驟1:創建初始解并初始化路徑強度。

步驟2:重復以下操作,直到達到終止條件。

步驟2.1:為每只果蠅創建路徑。

步驟2.2:進行局部搜索,以改善每只果蠅生成的解。

步驟2.3:更新最優解。

11月16日，云南電網公司解除了金沙江白格堰塞湖泄洪自然災害Ⅱ級響應，轉入災后重建階段。自11月14日金沙江白格堰塞湖潰泄進入云南，兩天來，一路氣勢洶洶，迪慶、麗江遭受重創，麗江更是遭遇了有水文記錄以來的最大洪災，沿江兩岸數萬名群眾緊急轉移安置。

步驟2.4:根據最優解更新所有邊的路徑強度。

步驟3:終止算法并記錄最佳解決方案。

可以看出,HFOA 算法本質是利用果蠅的覓食原理來構建MCVRP 的路徑解。 在建立路徑的每次迭代中每只果蠅輪流進行5 項基本活動。 第一,果蠅基于路徑吸引概率選擇下一個客戶,該概率由味覺強度和路徑強度組成。 第二,果蠅訪問當前路徑的客戶禁忌列表。 第三,果蠅更新車輛隔間的剩余容量。 第四,果蠅更新已訪問的路徑強度,其中,果蠅將采取局部搜索的方法來提高解的質量。 第五,刪除禁忌列表,并標記下一次迭代開始。

基于上述算法流程,利用局部搜索HFOA 求解MCVRP 問題的4 個主要環節設計如下。

(一)初始化

HFOA 首先生成初始解,并初始化每個解的路徑強度。 初始解分兩步生成。 首先,根據網絡的拓撲結構隨機生成客戶;其次,如果車輛容量足以滿足客戶需求,將客戶隨機添加到車輛的行進路徑中,否則車輛會在接近下一個客戶之前返回配送中心。

(二)路徑創建

假設HFOA 中的每一只果蠅都生成一條完整的路徑(完整的MCVRP 解)。 為了實現解的多樣化,每只果蠅應該在離開配送中心后隨機選擇第一個客戶。 接下來,每只果蠅都應該基于路徑的吸引概率轉移到下一個客戶。 味覺強度是當前位置到果蠅起點之間距離的倒數。 因此,果蠅傾向選擇離出發地更近的客戶以實現最小化路徑長度。

根據以上的論述,標號為ij的邊的吸引力包括兩部分:路徑強度τij(取該條邊在迭代過程中被訪問的頻率)和味覺強度μij(即邊長的倒數)。 味覺強度也代表果蠅從i移動到j的趨勢。 因此,路徑吸引力可以表示為:

其中,α和β分別是路徑強度指數和味覺強度指數。 客戶i在客戶j之后被果蠅訪問的概率記為Pij:

其中,Ni是當前車輛尚未訪問的所有客戶,其總需求不超過車輛容量。 根據式(10),下一個客戶的選擇概率與邊ij的吸引力成比例。

每只果蠅都根據上述規則繼續增加客戶,直到沒有客戶剩余。 然后,果蠅回到配送中心,并啟動新路徑。 根據式(10)果蠅選擇新路徑上的第一個客戶,必須是配送中心的相鄰頂點。

(三)局部搜索

果蠅每次旅行本質上可表征為數學領域的旅行商問題(Traveling Salesman Problem, TSP),旨在在確保每條路徑的總需求不超過容量限制的前提下,盡可能縮短旅行距離。 在創建所有路徑后,為提高解的質量,需要進行局部搜索,局部搜索包括2-opt、交換和插入。

2-opt:在路徑上選兩個點將路徑分為三個部分,將中間線段反向。 將所有線段連接起來進行重建。 假設i和j是一條路徑上的兩個不相鄰的客戶,i+和j+是路徑中的下一個相鄰頂點。 2-opt 表示刪除邊(i,i+)和(j,j+),添加邊(i,j)和(i+,j+),這樣可以得到一條新的道路。

交換:當前路徑上的客戶i和j的位置被交換以生成新的一組路徑。 交換后客戶i和j可能會也可能不會落在同一條路徑上。

插入:客戶i從p1位置移動到位置p2以通過當前路徑生成一組新的可行路徑。p1和p2可能會也可能不會落在同一條路徑上。

通過上述局部搜索操作,可獲得所有可行解,并從中選擇最短路徑。

(四)路徑強度更新

該步驟基于在局部搜索過程中得到的最優解進行路徑更新。 為了模擬實際情況,假設路徑強度隨著時間的推移而衰減。 路徑強度分兩步更新。首先,路經的強度都因時間的推移而衰減;其次,增加最佳路徑的強度,以驅使果蠅走最短路徑。 設為路徑持久性系數,滿足0≤ρ＜1,1-ρ為在迭代過程中的路徑強度衰減比,則邊ij的強度可以通過下式進行更新:

其中,Lbest是每次迭代中最佳路徑的總長度,路徑強度與ρ的乘積是衰減后路徑的剩余強度。

三、求解結果與分析

本節首先利用基準問題對HFOA 方法的算法優勢進行驗證,為后續應用驗證提供技術準備;然后對HFOA 方法處理MCVRP 問題的有效性與優越性進行驗證。

(一)算法優勢驗證

為了驗證HFOA 方法的有效性和優勢,利用Laporte[21]提出的7 個基準問題展開研究,將HFOA算法與混合AC 算法(HAC)[22]進行了對比,并將問 題 記 為 VRPNC1—VRPNC7。 VRPNC1—VRPNC5 中的客戶服從隨機均勻分布,而VRPNC6—VRPNC7 中的客戶服從聚集分布。 這些問題共涉及50—199 名客戶。

假設每輛車有2 個隔間,其容量比為1∶3,即如果車輛容量為Q,那么兩個車廂的容量分別為0.25Q和0.75Q。 HFOA 中的果蠅數量記為m,該數值直接關系到最佳路徑質量和計算時間,經過反復測試,被設置為20。 其他參數如下:α=1,β=2,ρ=0.9,q0=0.9,實驗進行100 次迭代。

對HAC 和HFOA 進行對比仿真的結果見表1。 從表1 中可以看出,采用HAC 和HFOA 算法,得到的平均總路徑長度為分別為986.99 和985.60,采用HAC 算法得到的平均總路徑長度改善了6.36%,而采用HFOA 算法得到的平均總路徑長度改善了6.49%,且HFOA 總路徑長度的改善率隨著客戶數量的增加提高得更快,改善率從50 個客戶的3.21%提高到199 個客戶的9.21%。這表明當問題越復雜時,HFOA 比HAC 效果更好。進一步計算分析可知,在解決大規模的路徑問題上,HFOA 的總路徑長度逐漸變短,從572.69 收斂到551.27,能夠解決大規模問題,而且相對于HAC,HFOA 具有更高的改善程度,這主要歸因于其強大的局部搜索能力。

表1 HFOA 算法與HAC 算法對比

進一步,為了說明HFOA 解決多隔間車輛(Multi-Compartment Vehicle, MCV)問題的優勢,本文使用兩種模式解決基準問題。 第一種模式使用容量為Q的單隔間車輛(Single-Compartment Vehicle,SCV),而第二種模式采用擁有2 個隔間的車輛,2 個隔間的容量分別為Q1和Q2;兩輛車的總容量相同,即Q=Q1+Q2。 要交付給客戶的貨物有兩種不同類型,分別表示為1 和2,這兩種貨物必須分開存儲,可以通過不同的路徑訪問客戶兩次以運輸貨物1 和2。 在這種情況下,車輛路徑問題(VRP)可分解為兩個子問題分別求解,將它們的最短路徑相加得到結果。 7 個基準問題運用兩種模式解決的結果如表2 所示。 從表2 可以看出,當只有1 個隔間時,車輛行駛的總路徑長度顯著增加,這是因為為了運輸某個客戶不同類型的貨物,同一位客戶需要被拜訪兩次,重復訪問增加了總旅行距離。 在第二種模式中,車輛可以在每條路徑上為更多的客戶提供服務,從而減少總行程長度。MCV 的優勢體現在兩隔間車輛的總行程比單隔間 車輛的總行程平均縮短49.26%。

表2 兩種模式下車輛路徑長度對比

(二)MCVRP 問題的應用有效性驗證

將HFOA 應用于前文所提出的MCVRP 問題求解,同時為了測試HFOA 的局部搜索效果,運用局部搜索操作的不同組合來解決MCVRP,并將結果與沒有局部搜索的FOA 所得到的結果進行比較。 第一種組合是FOA 與2-opt 結合,第二種組合是FOA 與2-opt 和交換相結合,第三種組合是FOA與2-opt、交換和插入相結合。 每種組合都進行不同數量的迭代次數,以保證計算時間相等。 根據表3 中的結果,混合局部搜索操作可以縮短MCVRP的最佳路徑長度。 第一種組合使解的質量提高了11.86%,但2-opt 操作的效果還不夠好,因為它只適用于一次旅行操作;在第二種組合中,解的質量改善率從11.86%增加到13.04%,表明交換操作可以將客戶轉移到兩條路徑;第三種組合將解的質量從13.04%提高到17.16%,這證明了混合局部搜索對解的質量有積極影響。

表3 不同結合方式的改善率

四、結論

本文采取基于局部搜索的果蠅優化算法來解決物流配送中具有容量約束的車輛路徑優化問題。其中,局部搜索操作是解決組合優化問題的基礎,本文將三種局部搜索方法與常規的FOA 相結合,形成混合優化算法來處理MCVRP。 通過7 個基準問題驗證了該算法的效果。 數值實驗表明,HFOA算法提高了解的質量,尤其是在大規模問題上。 研究證明了將局部搜索與FOA 算法相結合的必要性,并分析了FOA 算法的優點。 通過仿真將所提出的算法有效性和穩定性與其他算法進行比較可知,HFOA 算法的整體性能較好。