基于離散多元宇宙算法求解車輛路徑問題

張 強，姜慧清，王 穎，劉 馨

（東北石油大學計算機與信息技術學院 黑龍江 大慶 163318）

帶模糊時間窗的多配送中心車輛路徑問題（multi-depot vehicle routing problem with fuzzy time windows, MDVRPFTW）是經典車輛路徑問題（vehicle routing problem, VRP）的擴展問題之一，同樣屬于NP-hard 問題。MDVRPFTW 主要是指配送中心數量為多個，模糊化處理開始服務時間窗，加入了客戶最大容忍時間窗，優化目標不僅有車輛配送的總成本，還有客戶對服務時間的滿意度。與傳統的車輛路徑問題相比，MDVRPFTW 更貼合實際。隨著物流運輸業的興起，車輛路徑問題演化為多種類型，對于多配送中心車輛路徑問題（multi-depot vehicle routing problem, MDVRP），學者們應用不同的群智能算法尋找MDVRP 的近似最優解。文獻[1]設計了一種改進多蟻群算法來求解帶時間窗的半開放式MDVRP，引入2-opt 鄰域搜索算法更新可行解并作為初始解。文獻[2]設計一種混合遺傳算法，并提出一種自適應搜索范圍策略，為求解聯合MDVRP提供一種新思路。文獻[3]針對MDVRP的4 個擴展問題，設計混沌遺傳變鄰域搜索算法、改進的蟻群算法、兩階段禁忌搜索算法求解模型。文獻[4]針對帶軟時間窗的開放式MDVRP，提出了一種新改進的離散螢火蟲算法。文獻[5]針對問題和模型特點，設計了基于雙層編碼模式的改進遺傳算法求解隨機需求下帶時間窗的動態MDVRP。文獻[6]通過結合2-opt 局部優化算法的自適應多態蟻群算法求解基于車輛共享的MDVRP。文獻[7]根據MDVRP 的具體特征，模擬狼群捕食行為并設計了求解該問題的狼群算法。文獻[8]將基本的蟻群優化與具有快速全局搜索能力的遺傳算法相結合，構成一種混合自適應蟻群優化算法解決基于VIP 客戶的MDVRP。文獻[9]通過對遺傳算法改進求解MDVRPTW，結果表明改進的遺傳算法對求解此類優化問題有很大的提高。文獻[10]研究了一個多車場多配送中心半開放式滿載車輛路徑問題，給出了該問題的數學模型和求解算法。

多元宇宙優化算法（multi-verse optimizer, MVO）是文獻[11]于2016 年設計的一種基于物理學中多元宇宙理論的群智能優化算法。通過模擬白洞、黑洞和蟲洞之間的相互作用來完成尋優過程的數學建模。由于該算法具有框架簡單、易于理解、參數較少、性能穩定、搜索效率高等優點，受到關注。但傳統多元宇宙算法是針對連續問題設計的，無法直接應用于離散車輛路徑問題。因此，本文提出一種離散多元宇宙算法，重新定義了對于離散車輛路徑問題下的更新策略，尋找更優解。

1 問題描述及建模

1.1 問題描述

模糊時間窗約束下多中心車輛路徑問題可以描述為：擁有多個配送中心，車輛從配送中心出發，擁有客戶最大容忍時間窗，客戶點的需求量已知，需要合理的規劃路徑使目標函數最優。模糊時間窗約束下多中心車輛路徑問題考慮如下假設：1） 配送中心到客戶節點距離以及客戶點之間的距離是已知的；2） 配送車輛必須以所屬配送中心為起始點，任務完成后以所屬配送中心為返回點；3） 每輛車可以對多個客戶節點進行服務，但每個客戶節點有且僅有一輛車為其服務；4） 物流配送中心和客戶節點之間以及客戶節點之間都是可以連通的道路；5） 客戶節點貨物需求量小于配送車輛的最大承載量。6） 配送路徑數不能大于配送中心配送車輛總數；7） 配送車輛的到達時間不能早于和晚于客戶最大容忍時間窗。

1.2 數學建模

在MDVRPFTW 中，P={1,2,···,p}為配送中心的集合；N={1,2,···,n}為所有客戶節點的集合；Kp為 配送中心p的車輛數；Ktotal為 車輛總數；qi為客戶節點i的貨物需求量，i∈N；Q為配送車輛的最大容量；c1為單個配送車輛完成配送任務的固定費用；c2為 單位距離的行駛成本；c3為由于客戶不滿意帶來的業務損失成本；di j為節點i到 節點j之間的距離；Si為 開始服務時間；Kpm為配送中心p參與配送車輛數。本文采用的模糊時間窗[12][EET, ET,LT, ELT]相應隸屬函數圖像如圖1 所示。

圖1 梯形模糊時間窗隸屬函數

多配送中心情況下的客戶滿意度函數[13]可把客戶i對配送服務的滿意度定義為其服務開始時間的隸屬度函數：

其中，式（2）表示目標函數是配送總成本的最小化；式（3）表示平均顧客滿意度的最大化；式（4）表示總的優化目標為配送總成本最小化與客戶不滿意度最小化的和；式（5）表示車輛k的載重量不允許超過該車輛的額定載重量；式（6）表示每一個顧客點都被服務到且只被服務一次；式（7）表示使用的車輛總數不超過配送系統中所擁有的車輛數；式（8）表示車輛服務完客戶后，必須返回其所出發的配送中心；式（9）表示決策變量為0-1 變量。

2 離散多元宇宙算法

2.1 標準多元宇宙算法

多元宇宙算法[14]是2016 年提出的一種新型智能優化算法。而MVO 算法主要是模擬多元宇宙的種群在黑洞、白洞和蟲洞共同作用下的運動行為。與其他算法相比，MVO 算法主要分為探測和開采兩個階段。多元宇宙個體的位置由內部物體的運動改變。構建數學模型時，一個宇宙被視為優化問題的一個解，每個宇宙中的物體可作為相應解的分量。定義單個宇宙的膨脹率為候選解的適應度值。宇宙膨脹率，即適應度的計算方法在不同問題中有不同的定義，在本文MDVRPFTW 中，適應度函數定義為總成本函數式（4）的倒數。

初始化宇宙種群U，公式如下：

式中，r1為 [0, 1]范圍內隨機數；xkj表示通過輪盤賭選擇出來的第k個宇宙的第j個分量； NI(Ui)表示第i個宇宙的歸一化膨脹率。白洞/黑洞轉移是將物體從高膨脹率的宇宙發送到低膨脹率的宇宙中。因此在整個迭代過程中，宇宙種群的平均膨脹率會不斷提高。

為了保證宇宙種群的多樣性和改進宇宙個體自身膨脹率，宇宙個體會通過蟲洞和最優宇宙之間進行物質傳輸，公式如下：

式中，L為最大迭代次數；l為當前迭代次數；WEPmin= 0.2； WEPmax= 1；p為開發準確性，值為6。WEP 在迭代過程中線性增大，保證了在迭代后期進行更多的開采。TDR 在迭代過程中非線性減小，減小速率先快后慢。這是因為迭代前期選出最優宇宙的適應度不高，需要用更大的移動距離來加快開采速度，而在迭代后期，最優宇宙具有較高的適應度，所以需要減小移動距離來增加開采的精度。

2.2 多元宇宙算法離散化

標準多元宇宙算法只適用于在連續的解空間中尋優。但VRP 的解空間是離散的，需要將MVO進行離散化，使其適用于求解車輛路徑問題。

2.2.1 編碼與解碼

應用多元宇宙求解MDVRPFTW 時，每個宇宙代表了一種配送方案，宇宙中的分量代表節點的編號。客戶點、配送中心和車輛等節點的編號是離散且唯一的，為了便于理解和表示，用連續的自然數對節點進行編號。假設有n個配送中心，每個配送中心有ki輛車，客戶數為m。具體編碼解碼規則如下：

首先為所有節點進行編號。配送中心的編號從0 開始到n-1 結束。符號0 即代表第一個配送中心；配送車輛節點的編號從n開始到n+（k0+···+kn-1）-1 結束。隸屬于第一個配送中心的車輛的編號從n開始到n+k0-1 結束，以此類推；客戶點編號從n+（k0+···+kn-1）開始到n+（k0+···+kn-1）+m-1 結束。每個解中只包含車輛節點和客戶節點，即解的長度由配送車輛總數和客戶點總數確定。然后先將配送車輛隨機排列，再把客戶點隨機插入形成一個初始解。配送車i的配送路徑中包含的客戶點為配送車i與 配送車i-1 之間的所有客戶點，并在客戶點兩端加上配送車i所屬的配送中心編號構成完整配送路徑，配送順序即客戶點排列順序。例如有n=2，k=2，k=2，m=7，則初始編碼為：

其中編號為2,3 的配送車輛屬于0 號配送中心，編號為4,5 的配送車輛屬于1 號配送中心。隨機順序為：

則所有配送路徑為：{0, 8, 10, 11, 12, 0}, {1, 6,1}, {1, 7, 9, 1}。

通過配送車輛的編號可推出所屬的配送中心，配送車輛在解中的位置可推出該配送車的配送路徑，所以目標函數值的計算不會受亂序的影響。同時每一輛配送車輛的配送路徑由一段連續片段指定，給鄰域搜索策略的設計提供了思路。

2.2.2 位置更新策略

1） 白洞/黑洞轉移

在標準多元宇宙算法中，對于Ui的 第j個分量，如果隨機數r1小 于Ui的歸一化膨脹率，則用Uk的 第j個分量取代Ui的 第j個分量。但這種更新方式在車輛路徑問題中會使更新后的解不合法，因為節點編號是唯一的。對于離散車輛路徑問題，在Ui的 第j個分量更新后，需要與對應的分量進行交換，以保證解的合法性，具體操作如下：

在標準多元宇宙中，通過向最優宇宙移動來保持群多樣性和激發每個宇宙的膨脹率。但標準多元宇宙中的移動距離為實數，不適用于車輛路徑問題。所以將移動距離取整。如果Ui的 第j個分量更新后的值超出了最大節點編號，則將其置為最大節點編號。為了保證解的合法性，需要在更新后對解進行調整。離散后的向最優宇宙移動公式如下：

2） 向最優宇宙移動

2.3 改進策略

2.3.1 原子操作

首先定義宇宙交換物體的原子操作。無論是白洞黑洞轉移還是向最優宇宙移動，都是基于原子操作。本文將原子操作分為3 種：交換、插入和反轉。

1）交換操作

2.3.3 向最優宇宙移動重定義

其中{8, 10, 11, 12}是編號為3 的配送車的配送路徑。

2.4 算法步驟

1） 初始化多元宇宙種群，初始化 WEPmin、WEPmax、 開發精度p、 最大迭代次數M axIter、當前迭代次數C urIter等參數；

2） 計算每個宇宙個體的適應度，宇宙個體歸一化膨脹率 NI(U)，用輪盤賭機制選擇一個宇宙個體Uk；

7） 如果達到最大迭代次數，輸出最優解，算法結束；否則，返回步驟2）。

3 實驗與分析

本文使用Solomon 數據集[15]對標準多元宇宙算法（MVO）、鯨魚算法（whale optimization algorithm,WOA）[16]、海鷗算法（seagull optimization algorithm,SOA）[17]、粒子群算法（particle swarm optimization,PSO）[18]、飛 蛾 撲 火 算 法（moth-flame optimization,MFO）[19]、灰 狼 優 化 算 法（grey wolf optimization,GWO）[20]以及本文提出的離散多元宇宙算法（discrete multi-verse optimizer, DMVO）進行了對比實驗。由于Solomon 標準數據集的時間窗為硬時間窗且只有一個配送中心，所以對Solomon 數據集進行了擴展。配送中心數目增加至3，另新增了左、右容忍時間窗。考慮到顧客對于不同貨物的期望服務時間窗不同，其最大容忍程度也不盡相同，設置顧客可提前接受服務的時間窗 [EETi,ETi)和顧客可延遲接受服務的時間窗 (LTi,ELTi]分別為顧客期望接受服務的時間窗 [ ETi,LTi]的一半，能更加客觀地描述實際顧客的等待情況。容忍時間窗按如下公式得出：

式中，EET 為左容忍時間窗；ELT 為右容忍時間窗；ET 為左時間窗；LT 為右時間窗。

實驗中的最大迭代次數為2 000，種群數量為300。表1 為各個算法在Solomon 數據集上的總成本對比結果?？偝杀緸楣潭ǔ杀?、距離成本與時間懲罰成本之和。為了避免不同初始化對算法造成的影響，隨機生成了10 組初始種群，取10 組數據的平均值作為對比結果。

表1 實驗結果

通過表1 結果可以看出，改進后的離散多元宇宙算法在求解帶模糊時間窗的多配送中心車輛路徑問題時，與MVO 相比結果更優。而MVO 總成本普遍優于PSO、SOA、WOA、GWO 和MFO 算法。為了直觀地展示迭代過程中成本的變化情況，下面以Solomon 數據集中的C101、C102、R205、R207、RC202、RC208 為例，展示總成本和用戶滿意度在迭代過程中的變化曲線圖。

通過圖2～圖13 可以看出，總成本和客戶滿意度隨著迭代次數的增加都在不斷得到優化。由于在迭代過程中要綜合考慮成本與客戶滿意度，導致圖像曲線出現波動。但隨著迭代次數的增加，結果達到平衡，整體損失趨于收斂。

圖2 C101 總成本迭代圖

圖3 C102 總成本迭代圖

圖4 R205 總成本迭代圖

圖5 R207 總成本迭代圖

圖6 RC202 總成本迭代圖

圖7 RC208 總成本迭代圖

圖8 C101 滿意度迭代圖

圖9 C102 滿意度迭代圖

圖10 R205 滿意度迭代圖

圖11 R207 滿意度迭代圖

圖12 RC202 滿意度迭代圖

圖13 RC208 滿意度迭代圖

DMVO 與MVO 相比，在迭代前期收斂速度略低。這是因為對于求解MDVRPFTW，MVO 算法在向最優宇宙移動時，Ui的 第j個分量有可能變為任一分量。而改進后的DMVO 在向最優宇宙移動時，分量變化被限定在某個配送車的配送路徑中，相當于在最優宇宙的鄰域進行搜索。在迭代前

期，隨機搜索有助于MVO 可以快速跳出局部最優，收斂較快。而改進后的DMVO 由于前期的最優宇宙的適應度不高，在其鄰域難以搜索到更優解，導致收斂較慢。但隨著迭代進行，最優宇宙的適應度逐漸提高，最優宇宙鄰域搜索的優勢逐漸大于隨機搜索，所以改進后的DMVO 具有更強的尋優能力。

為了確定不同配送中心數目和客戶節點數對各個算法的影響，將Solomon 數據集進一步擴展，生成了一組新數據集。新數據集的配送中心數目和客戶節點數分別為（3, 50）、（3, 80）、（3, 200）、（1, 100）、（5, 100）、（10, 100）。以C101，C201，R201，R202，RC208 為例，各算法在新數據集上的對比結果如下。

通過表2 和表3 可以看出，在不同配送中心數目和不同客戶節點數目的情況下，改進后的離散多元宇宙算法的尋優能力都優于標準MVO、PSO、SOA、WOA、GWO 和MFO 等算法，證明了DMVO在求解MDVRPFTW 問題時具有很好的魯棒性。

表2 不同客戶點實驗結果

表3 不同配送中心實驗結果

4 結 束 語

本文在解決模糊時間窗約束下的多配送中心車輛路徑問題時，以總成本最低、顧客滿意度最大為多目標函數，構建出相應的模型。將連續多元宇宙進行了離散化，并改進了多元宇宙的更新策略。通過離散多元宇宙算法來求解Solomon 數據集中部分算例，更具有參考價值。而對于車輛路徑問題，仍然有很多不確定因素，接下來將繼續研究多元宇宙算法在其他車輛路徑問題上的應用。