基于雙重交叉策略的多元宇宙優化算法求解帶時間窗車輛路徑問題

吳秀芹，劉鐵良

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

帶時間窗車輛路徑問題（Vehicle Routing Prob?lem with Time Windows，VRPTW）［1］是由車輛路徑問題（Vehicle Routing Problem，VRP）演化而來的，它是對傳統車輛路徑問題的進一步擴展［2］。VRPTW一直是組合優化和運籌學領域的熱點問題，其在物流配送和車輛路徑規劃等領域具有十分廣泛的應用背景，因此如何有效地解決VRPTW問題具有很高的實際應用和理論研究價值。

隨著啟發式算法的不斷發展，運用群智能優化算法對VRPTW問題進行求解是當前學者們的重要研究方向。劉志偉［3］提出一種結合遺傳算法的改進多目標和聲搜索算法（GA-MOIHSA）求解多目標VRPTW問題，該算法引入和聲模板和多重鄰域搜索策略，提高了算法的全局搜索能力。馬祥麗等人［4］重新設計了蝙蝠算法（BA）的操作算子，提出一種改進的蝙蝠算法求解VRPTW問題。黃震等人［5］提出一種混合蟻群優化算法求解帶時間窗車輛路徑問題（VRPTW）。苗國強等人［6］提出一種自適應大規模鄰域搜索算法求解VRPTW，該算法引入移除和插入規則，并采用局部搜索策略來提高解的質量。王君［7］設計了一種離散差分進化混合算法求解VRPTW問題，該算法通過構造新的變異算子和交叉算子來提高算法的尋優能力。

多元宇宙優化算法［8］（Multi-Verse Optimizer，MVO）是由澳大利亞學者Mirjalili教授于2016年設計的一種新啟發式優化算法。與粒子群算法、蟻群算法等經典的啟發式算法相比，MVO算法操作簡單且參數設置少，同時有良好的全局搜索能力。目前在國外，許多學者利用MVO算法解決經濟調度［9］、工程優化［10］和求解光伏發電機組參數［11］等問題，取得了良好的實際應用效果。但國內對MVO算法在實際工程問題中的研究相對較少。因此，本文提出一種基于雙重交叉策略的多元宇宙優化算法（Multi-Verse Optimizer Algorithm Based on Double Crossover Strategy，DCSMVO），并將其應用于求解VRPTW問題。在DCS-MVO算法中，首先在滿足車輛最大載重的約束條件下，通過訪問概率來構造算法的初始解，提高了初始宇宙群的優良性；其次，引入動態交叉算子，保證迭代后期宇宙種群的多樣性，提高算法的局部探索能力；同時采用基于最優片段的交叉策略，加強宇宙間信息的交互，提高算法的全局開發能力；此外，引入隨機交換搜索、2-opt和3-opt相結合的鄰域搜索策略，以便尋找到更多潛在的優秀解。最后對改進效果進行仿真驗證，并將DCS-MVO與其它5種優化算法在求解本文建立的模型上進行對比，DCSMVO取得了很好的尋優效果。

1 數學模型

本文研究的帶時間窗車輛路徑問題［12］，即有一個配送中心和多個客戶需求點，不僅要滿足車輛最大載重等約束條件，還需要滿足在指定的時間區間內將商品交付到指定客戶點，所有配送車輛完成配送任務后必須返回配送中心。求解VRPTW的目標是在滿足約束條件的基礎上合理安排車輛路線，使配送的總成本最低。

在VRPTW中，N={1 ,…,n}為客戶集合，V={0 ,N}為配送中心（定義為0）和所有客戶集合，K={1 ,2,…,m} 為配送中心的車輛集合，Vk為車輛k訪問客戶點的集合，R為車輛最大載重，ri為各客戶點的需求量，表示車輛k由客戶i行駛到客戶 j（=1 為從 i行駛到 j，=0為不行駛），表示客戶i由車輛k提供服務（=1為由車輛k提供服務，=1表示未提供服務），dij為客戶點i到客戶點j的距離，C為每輛車的固定費用，Pi表示時間懲罰成本，STi表示客戶i接受配送服務的最早開窗時間，ETi表示客戶i接受配送服務的最晚閉窗時間，其中ti是車輛達到客戶i的時間，當配送車輛不在規定的時間范圍內[STi,ETi]為客戶i提供配送服務，將會產生一定的時間懲罰成本，a表示早到懲罰系數，b表示晚到懲罰系數。則VRPTW的數學模型如下：

式（1）為目標函數，F1表示物流總成本（包括車輛固定成本、運輸成本以及時間懲罰成本）；式（2）表示每輛車不得超過其最大載重量；式（3）表示車輛從配送中心出發完成配送任務后必須返回配送中心；式（4）表示車輛服務完客戶i后再去服務客戶j；式（5）表示車輛服務客戶j之前服務客戶i；式（6）表示每個客戶只能被一輛車服務；式（7）表示物流配送中產生的時間懲罰成本；式（8）和式（9）表示決策變量約束條件。

2 基于雙重交叉策略的多元宇宙優化算法

2.1 傳統多元宇宙優化算法

多元宇宙優化算法（MVO）主要依據于物理學中多元宇宙理論，模擬的是宇宙種群在白洞、黑洞和蟲洞相互作用下的運動行為而構建的數學模型。在該數學模型中，每個宇宙被看作優化問題的一個解，宇宙中每個物體代表解的一個分量，宇宙膨脹率則代表目標函數的適應度值。MVO算法在每次迭代時，首先通過輪盤賭原則，根據排序后宇宙種群的膨脹率選擇一個白洞，其更新公式如下：

為了保證宇宙種群的多樣性，宇宙內物體會不斷向當前最優宇宙移動，其更新公式如下：

其中，xj表示目前形成的最佳宇宙中的第j個分量；lbj為第j個分量的下界；ubj為第j個分量的上界；為第i個宇宙的第j個分量；r2,r3,r4是在[0,1]之間的隨機數；WEP表示宇宙中蟲洞存在概率；TDR為旅行距離率。其更新公式如下：

其中，WEPmin為WEP的最小值（取值為0.2），WEPmax為WEP的最大值（取值為1）；l為當前迭代次數；L為最大迭代次數；p為開發的準確性（取值為6）。

2.2 基于雙重交叉策略的多元宇宙優化算法設計

2.2.1 優化個體的編碼與解碼

多元宇宙優化算法求解VRPTW問題時，每個宇宙表示一條配送路徑，宇宙的每個分量表示配送路徑中的客戶點。由于客戶點的編號方式是整數類型，為了使宇宙中個體的位置按照客戶編號規則與VRPTW問題形成一一對應的關系，因此選擇自然數的編碼方式。用一維向量表示一條配送路徑，一維向量中的每個字符代表每一個客戶，向量的長度表示客戶總數。具體的編碼方式如下：

假設客戶數為n，車輛數為m，根據VRPTW模型的特點：“0”認為是配送中心，因此需要在客戶點集合的位置前后分別加上“0”，構成一條完整的VRPTW路徑，即配送車輛從配送中心出發完成配送任務后需返回配送中心，配送車輛達到客戶點的順序構成一臺車輛的訪問路徑。例如：n=9，m=3，由于3輛車配送的客戶點集合分別為{1 ,6,4,5} ，{9,7,3}，{2,8}。因此，3輛車的訪問路徑分別為：{0 ,1,6,4,5,0} ，{0,9,7,3,0}，{0,2,8,0}。

2.2.2 初始解構造

初始宇宙個體對路徑節點的合理選擇，可以提高宇宙群的整體質量。本文采用根據客戶點的訪問概率來構造問題的初始解，允許對客戶點的配送服務時間不在期望的時間窗內，但必須滿足車輛最大載重限制，設配送車輛規格相同，車輛的最大載重量為R，dij為客戶i與客戶j之間的距離，K為配送中心所包含的車輛總數，初始解的構造步驟為：

（1）初始化k=1，且配送中心“0”為配送起點。假設車輛k已經配送的客戶節點集合為Vk，待配送的客戶節點集合為Nk，在集合Nk中隨機選取一點作為訪問路徑的起點。

（3）若客戶i的商品需求量為ri，Rk為車輛k的剩余載重量，則 Rk=Rk-ri，若Rk>0，則 Vk=Vk?{i}，將客戶節點i加入已配送客戶集合中，轉步驟（2）；若Rk<0，則超出最大車輛k的最大載重約束，轉步驟（4）。

（4）添加一個新的配送車輛，k=k+1，且k≤K，重復步驟（1）-（4），直到集合 Nk中沒有待配送的客戶點。

2.2.3 改進方法

（1）基于動態交叉算子的交叉策略

傳統多元宇宙優化算法中，黑洞通過蟲洞在最優宇宙周圍以旅行距離率（TDR）進行局部探索，隨著迭代次數的增加，TDR值逐漸減小，導致迭代后期的旅行距離率較小，算法的局部探索性能大大降低，易造成宇宙種群多樣性的減少，導致算法過早陷入局部最優。為了提高MVO算法的局部尋優性能，本文引入差分進化算法［13］中的交叉算子，通過交叉操作來提高宇宙種群的多樣性，避免算法過早停滯。

其中，CR是交叉算子，也稱交叉常量，通常取[0,1]范圍間的常數。CR取值越大，中分量被選中的概率越大，越接近，反 之越接近。通過閱讀文獻可知，CR較好的取值范圍在0.3到0.9之間。根據VRPTW模型的特點，本文動態選取0.3到0.9之間的值作為交叉常量，隨機選取和中的分量重組成新的宇宙。通過上述交叉策略，豐富了宇宙種群的多樣性，避免算法過早陷入局部最優，提高算法的局部探索能力。基于動態交叉算子的更新策略如圖1所示。

圖1 基于動態交叉算子的更新策略圖

（2）基于最優片段的交叉策略

傳統MVO算法中，通過輪盤賭原則選擇出的白洞基本上就是最優宇宙，由于沒有很好與其它宇宙進行充分的信息交互，這使得算法缺乏跳出局部最優的能力，也容易導致宇宙種群早熟，進而無法進行深度的全局開發。為了提高算法的全局開發能力，本文采用基于最優片段的交叉策略來更新白洞的位置。假設最優宇宙為，當前宇宙為，隨機截取最優宇宙中的部分片段，將其插入到當前宇宙為的尾部，同時將宇宙中重復的分量刪除，得到基于最優片段的新路徑方案。基于最優片段的交叉策略方法如圖2所示。

圖2 基于最優片段的交叉策略圖

如圖2所示，宇宙中的每個分量表示VRPTW問題中的每個客戶點，每個宇宙表示一條配送路徑，通過在最優配送路徑中隨機截取部分片段，如截取客戶9到客戶2之間的配送路徑，將其插入到原配送路徑的尾部，同時將原路徑中重復的客戶刪去，得到一條新的配送路徑。

2.2.4 鄰域搜索策略

根據VRPTW的特點，借鑒文獻［14-16］的鄰域搜索策略，本文提出了隨機交換，2-opt，3-opt相結合的局部搜索策略。

（1）交換搜索：對配送路徑進行交換搜索，隨機選取兩個不同位置的客戶點，將兩個客戶點位置交換。更新方式如圖3所示。

圖3 交換搜索略圖

（2）2-opt搜索：對配送路徑進行2-opt搜索，隨機選取兩個不同位置的客戶點，將兩個客戶點之間的位置全部反轉。更新方式如圖4所示。

圖4 2-opt策略圖

（3）3-opt搜索：對于配送路徑進行3-opt搜索，隨機選取3個位置的客戶點依次交換。更新方式如圖5所示。

圖5 3-opt策略圖

選擇上述的鄰域搜索策略對每次迭代得到的最優解進行變換，產生更多的鄰域解，選擇適應度最小的值作為每代的最優解，本算法的局部搜索策略按照一定的規則來交換客戶的訪問次序，得到的路徑仍然對應著一個完整的VRPTW路徑。

2.3 算法的基本流程

基于雙重交叉策略的多元宇宙優化算法的具體步驟如圖6所示。

圖6 DCS-MVO算法流程圖

3 實驗與分析

本文采用Solomon的6種類型VRPTW算例［13］測試DCS-MVO，然后將DCS-MVO和傳統多元宇宙優化算法（Multi-verse Optimization，MVO）、飛蛾撲火算法（Moth Flame Optimization，MFO）、布谷鳥算法（Cuckoo Search Algorithm，CSA）、粒子群算法（Particle Swarm Optimization，PSO）和蝙蝠算法（Bat Algorithm，BA）進行比較實驗。DCS-MVO的參數設置如下：MaxIt=1000，popnum=100。MVO、MFO、CSA、PSO和BA的基本參數設置同DCS-MVO一致。表1給出部分算例實驗結果，以總成本（車輛固定成本、運輸成本和時間懲罰成本之和）最小為優化目標，求解最優的路徑配送方案。因此求解總成本的值越小，則表明算法在求解VRPTW問題上的性能越好。

通過表1分析可知，DCS-MVO算法求解C型測試集時，由于C型測試集的客戶位置主要成聚類分布，隨機生成的初始種群具有一定的混亂性，容易破壞其原有的路徑結構，造成大量的冗余路徑，而DCS-MVO算法利用訪問概率構造初始種群，相對弱化了VRPTW模型的約束條件。因此DCS-MVO求解得到的總成本要低于其它五種優化算法，相比較傳統MVO算法，DCS-MVO算法對C型問題的求解結果有所改進。對于R1型和RC1型測試集，由于客戶點分布較為均勻，并且每個客戶要求的配送時間范圍比較緊湊，在路徑配送方案規劃中，可能會產生更多的車輛固定費用和時間窗懲罰費用，因此DCS-MVO算法優化得到的總成本略優于其它五種算法；對于R2型和RC2型測試集，客戶的時間窗范圍較大，對配送時間的要求比較寬松，因此相較于其他算法，DCS-MVO算法得到的優化效果更好。

表1 部分算例實驗結果對比

為了具體驗證DCS-MVO算法在求解VRPTW問題的性能，本文分別用DCS-MVO、MVO、MFO、CSA、PSO和BA算法對VRPTW的數學模型進行求解。在Solomon數據集中以C101、C201、RC208三種算例做具體分析，其結果如下所示：

其中，C101算例求解得到的運輸成本為832.170 1元，所需車輛為10輛，總成本為17 901元，與目前最優運輸成本828.94元接近，從而證明DCS-MVO算法在求解C101上有較好的尋優能力；C201算例得到的運輸成本為589.76元，所需車輛為3，總成本為42 202元，與目前最優運輸成本591.56元接近，因此，DCS-MVO算法在求解C201上有良好的尋優效果；RC208得到的最優運輸成本為817.878 9元，所需車輛為3，總成本為7 030元，優于目前最優運輸成本828.94元，證明DCS-MVO算法在求解RC208上有很好的尋優能力。

圖7、8、9表示C101、C201和RC208的最優配送路線圖，圖10、11、12為六種算法在求解C101、C201、RC208算例時的總成本迭代圖，其中，橫坐標表示算法的迭代次數，縱坐標表示總成本（包括車輛固定成本、運輸成本和時間懲罰成本），通過上圖反映了DCS-MVO算法有較好的求解能力。在算法迭代初期，DCS-MVO算法通過訪問概率構造VRPTW模型的初始解，加快了算法的收斂速度；隨著迭代次數的增加，DCS-MVO算法采用雙重交叉變異策略，豐富了宇宙種群的多樣性，使算法能夠充分挖掘搜索空間，有效提高算法跳出局部最優的能力；此外，DCS-MVO利用交換搜索、2-opt搜索和3-opt搜索相結合的鄰域搜索策略對最優解進行變異，可以找到更多的潛在優秀解。因此相較于其它五種算法，DCS-MVO算法求解得到總成本更低。驗證了DCS-MVO算法在求解VRPTW問題時，具有較好的尋優能力，可以得到高質量的結果。

圖7 C101最優路徑圖

圖8 C201最優路徑圖

圖10 C101總成本迭代圖

圖11 C201總成本迭代圖

4 結論

針對VRPTW的求解，本文提出了一種基于雙重交叉策略的多元宇宙優化算法。該算法利用訪問概率來構造問題的初始解；采用兩種交叉策略對宇宙位置的更新策略進行改進，使其更符合求解VRPTW問題的需求；并引入隨機交換搜索、2-opt、3-opt策略對最優路徑進行鄰域變換，增強算法局部搜索能力。算例驗證及分析表明，DCS-MVO能夠有效求解VRPTW，尋優質量優于所對比算法。未來將進一步改進DCSMVO，以加強其在車輛路徑規劃問題上的應用。