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

吳秀芹，劉鐵良

（東北石油大學(xué) 計算機與信息技術(shù)學(xué)院，大慶 163318）

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

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

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

1 數(shù)學(xué)模型

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

在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提供服務(wù)（=1為由車輛k提供服務(wù)，=1表示未提供服務(wù)），dij為客戶點i到客戶點j的距離，C為每輛車的固定費用，Pi表示時間懲罰成本，STi表示客戶i接受配送服務(wù)的最早開窗時間，ETi表示客戶i接受配送服務(wù)的最晚閉窗時間，其中ti是車輛達到客戶i的時間，當配送車輛不在規(guī)定的時間范圍內(nèi)[STi,ETi]為客戶i提供配送服務(wù)，將會產(chǎn)生一定的時間懲罰成本，a表示早到懲罰系數(shù)，b表示晚到懲罰系數(shù)。則VRPTW的數(shù)學(xué)模型如下：

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

2 基于雙重交叉策略的多元宇宙優(yōu)化算法

2.1 傳統(tǒng)多元宇宙優(yōu)化算法

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

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

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

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

2.2 基于雙重交叉策略的多元宇宙優(yōu)化算法設(shè)計

2.2.1 優(yōu)化個體的編碼與解碼

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

假設(shè)客戶數(shù)為n，車輛數(shù)為m，根據(jù)VRPTW模型的特點：“0”認為是配送中心，因此需要在客戶點集合的位置前后分別加上“0”，構(gòu)成一條完整的VRPTW路徑，即配送車輛從配送中心出發(fā)完成配送任務(wù)后需返回配送中心，配送車輛達到客戶點的順序構(gòu)成一臺車輛的訪問路徑。例如：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 初始解構(gòu)造

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

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

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

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

2.2.3 改進方法

（1）基于動態(tài)交叉算子的交叉策略

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

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

圖1 基于動態(tài)交叉算子的更新策略圖

（2）基于最優(yōu)片段的交叉策略

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

圖2 基于最優(yōu)片段的交叉策略圖

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

2.2.4 鄰域搜索策略

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

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

圖3 交換搜索略圖

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

圖4 2-opt策略圖

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

圖5 3-opt策略圖

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

2.3 算法的基本流程

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

圖6 DCS-MVO算法流程圖

3 實驗與分析

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

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

表1 部分算例實驗結(jié)果對比

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

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

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

圖7 C101最優(yōu)路徑圖

圖8 C201最優(yōu)路徑圖

圖10 C101總成本迭代圖

圖11 C201總成本迭代圖

4 結(jié)論

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