帶軟時間窗VRP及其混合蟻群算法

張延 葛斌

摘 要：為了解決帶軟時間窗車輛路徑這一類典型的NP-hard問題，減少總配送成本，本文提出一種混合蟻群算法，通過蟻群優化技術與遺傳算法中的變異算子結合增加解的多樣性，根據適應度函數評估解的質量獲得精英解來對構建的模型求解，采用眾所周知的基準所羅門數據集，設置25和100不同的客戶規模仿真結果對比評估性能，得到全局平均解的優化率都達到10%以上的結果。仿真結果顯示，高效地求解了VRPSTW問題，在收斂速度和尋優結果兩方面均有明顯優化。

關鍵詞：VRPSTW;蟻群優化;變異算子;精英解

中圖分類號：TP181 ?文獻標識碼：A ?文章編號：1673-260X（2021）07-0009-04

1 引言

帶軟時間窗的車輛路徑問題（VRPSTW），是基本VRP的延伸，時間窗約束被放寬為“軟”，如果車輛未按客戶提前預定的時間窗要求到達客戶點，允許時間有所偏離，但必須付出一定懲罰成本。帶軟時間窗車輛路徑問題在考慮帶硬時間窗車輛路徑問題會對車輛資源浪費和配送服務窗口要求過于強硬兩方面存在優勢。近年對VRPSTW的研究，Xu等人[1]采用了將貪婪策略和自適應策略結合的非支配排序遺傳算法;Beheshti等人[2]提出了一種高效的混合列生成-元啟發式方法;范厚明等人[3]將變領域下降搜索應用于粒子群算法的擾動，提高了算法的搜索性能;李國明等人[4]提出一種修正算法和禁忌搜索算法結合的兩階段改進算法;凌海峰等人[5]將蟻群算法與2-opt結合求解MDOVRPSTW。蟻群優化算法在求解VRP及其擴展問題上，因為其自身較強的自組織性和正反饋特點，擁有較好收斂效果同時容易陷入“早熟”，學者們于是通過引入精英保留方法、領域搜索或混合其他經典啟發式算法優勢[6]來改進蟻群算法。在此對VRPSTW首先進行了介紹和建模，目的在于降低總配送成本;其次，為了產生高質量的解決方案，將蟻群元啟發式算法與利用鄰域搜索空間的變異算子進行了混合求解。

2 VRPSTW問題描述

帶軟時間窗的車輛路徑問題實質上相當于一個運輸網絡G（N，A），N={0，1，…，n，n+1}是對應于N位客戶的節點集，V={1，…，k}是可用車輛的集合，每輛車容量有限為Qv，其使用時產生的固定成本為fv，每位客戶i具有在配送服務時間內的需求dj，并且由一輛車在要求的時間窗[ei，li]內一次服務完成，目標是找到合適的路線同時減少總配送成本。

2.1 符號定義

運輸車v在邊（i，j）上的路線成本用cij表示，運輸車v在路徑（i，j）的行駛時間用tijv表示，Ri為提前配送給客戶的懲罰成本，Hi是延誤配送給客戶懲罰成本，C是控制參數，W為客戶需求點的任意子集，xijv作為決策變量取為1，否則為0，Eiv表示當車輛v提前到達客戶點時情況的決策變量，Liv表示車輛v延誤到達客戶點時情況的決策變量。

式（1）中的目標函數是最小化總路線成本，式（2）和式（3）表示每個客戶只得到車輛服務一次，式（4）為車輛從運輸點出發最終返回運輸點，式（5）確保每條路線在倉庫開始和結束，式（6）為保證不超過車輛容量，式（7）為車輛離開的時間和開始節點計算每個節點的到達時間要求，式（8）為了將多余子路排除，式（9）為決策變量取值要求，式（10）參數約束為非負。

3 求解帶軟時間窗車輛路徑問題的混合蟻群算法

3.1 蟻群算法

蟻群算法（ACO）受螞蟻搜索食物機制的啟發，使得每個智能體都是一只人工螞蟻。蟻群算法能夠以非常有效的方式解決像TSP和VRP這樣的NP難問題。具體如下：

（1）構建解：通過計算狀態轉移概率逐步構建完整解。狀態轉移概率公式如下：

其中，Pijw（t）表示選擇選擇下一節點的轉移概率，？子ij為邊（i，j）上釋放的信息素濃度，？濁ij為邊（i，j）的信息啟發式因子，？琢和？茁分別表示信息素和啟發式因子的影響程度，Ni為螞蟻向下一節點訪問的節點集。

（2）當螞蟻在每次迭代中找到最佳解時，通過以下方式執行全局更新：

在這個等式中，？駐？子ijw（t）表示在t時刻邊（i，j）上的信息素的值，由螞蟻w來釋放。？籽為信息素揮發系數，Q為全局信息素常量。

在這個公式中，Q代表信息素的蒸發率，而cost（i，j）代表螞蟻w在前一次重復中進行分配的成本。由于依照目標函數是降低配送總成本，則將表示路徑（i，j）上的成本cost（i，j）加入改進信息素更新公式。信息素更新的目的是降低次優解的價值，增加最佳解的數量。當使用ACO算法求解VRPSTW時，每只螞蟻從倉庫出發，在一定的約束條件下，通過逐步選擇下一訪問節點來構建路徑。當前路線中的下一個選擇不滿足條件時，螞蟻返回倉庫，通過分配未被路由的節點來構建另一條路線。重復這個過程，直到所有節點都被訪問，并且可以獲得一個可行的解決方案。

3.2 變異操作

蟻群算法和遺傳算法進行混合的方法在目前的研究很多，但基本都是局限在基本車輛路徑問題上，在此采用了新的方式并應用在帶軟時間窗車輛路徑上，變異算子定義為：在0到1之間選擇一個隨機數c，判斷c是否小于等于變異概率q1;如果滿足，便隨機產生幾對基因變異位;然后交換這幾對變異位置的基因。為了形象描述變異操作，我們在圖1中給出了一個示例解決方案，它是由實際車輛路徑解決方案轉換而來的序列代碼。變異操作在圖2所示變異前的序列代碼上實現，其通過從圖1所示的序列解去除去0（倉庫）而獲得。本變異操作首先隨機選擇多對客戶，例如3和8，1和10。通過交換客戶對，我們獲得了一個新解決方案序列。結果如圖2變異后所示。最后將0（倉庫）插回獲得的新序列解中，便得到新的解決方案。交換次數n=n/3，n為客戶數量。

3.3 解的評估

利用公式⒁作為評價解質量的適應度函數。假設應用變異操作得到K個后代解，那么解的個數為M+K個（其中M為螞蟻數，M≤K）。根據公式（14）得出其每一個的適應度函數值進行排序，適應度值大的，解的質量就比較好，排序就靠前。

3.4 混合蟻群算法

該混合算法利用蟻群優化算法和變異算子來獲得一個具有良好平衡的探索-開發行為的搜索過程。此算法由兩個階段組成。第一階段，每個螞蟻基于蟻群優化框架生成可行解，第二階段，利用變異算子產生隨機選擇的解決方案，獲得一定個數新的解決方案。然后，將這些新解結合第一步改進蟻群算法獲得的可行解，隨后，信息素軌跡將被更新以探索螞蟻的搜索空間并產生更好的后續解決方案。通過這個過程重復，直到達到預定的迭代次數。提出的HACO的算法具體步驟如下：

輸入：螞蟻數量m，0≤q0≤1等。

輸出：一組針對VRPSTW的精英解決方案。

Step1初始化：對于l=1，2，…，m，將m只螞蟻隨機放在調度中心，初始化訪問節點集合Ni=？覬及候選集Taub表，初始化各參數，設置l=1。

Step2根據公式（11）選擇下一個要訪問的節點j（j？埸Ni）并更新螞蟻l的Ni和Taub表。

Step3如果Taub=？覬，進入步驟3;否則，請轉到步驟2。

Step4停止標準：如果l>M，則停止，記錄進全局可行解集M;否則，轉到步驟2。

Step5將計數器設置為nc=1。

Step6生成解：如果nc≤maxiter，使用全局可行解集M里的M個解;否則，算法終止并輸出M。

Step7突變：設置l=l+1，在[0，1]中均勻生成一個隨機數c，如果c≤q1，則對螞蟻l生成的解進行變異操作;否則，請轉到步驟7。設置l=l+1并重復步驟7，直到l>M。

Step8解的評估：使用公式（14）計算的適應度降序排列M+K解（由m螞蟻獲得的M解和使用變異操作獲得的K個新解），并接受第一個M解。

Step9根據式（12）和（13），更新信息素。

Step10設置nc=nc+1，進入步驟6。

4 實驗及其結果分析

4.1 實驗環境及參數設置

本實驗采用國際上通用的Solomon標準算例。該算法在Matlab R2010a中實現，并在一臺搭載Intel i5-8265U雙核處理器，CPU 3.60GHz、8GB RAM的計算機上執行。算例參數在多次調試后最終設置為：種群螞蟻規模m=40，？琢=1，？茁=3，？酌=2，？籽=0.85，全局信息素常量Q=20，變異概率q1=0.5。

4.2 模型試驗結果與分析

選取Solomon標準數據集的3類數據中有客戶規模25的C101-25、R101-25、RC101-25和客戶規模100的C101-100、R101-100、RC101-100共6組算例，設置相同的參數和實驗條件，對傳統蟻群算法與提出的混合蟻群算法都進行200次迭代，由于混合蟻群算法[7]同樣分為25和100兩種客戶規模，和該混合蟻群算法具有可比性，因此將其與本文迭代200次實驗結果的平均值一起分析，統計結果見表1。我們選取C101-25算例傳統蟻群算法和該混合蟻群算法的算法迭代曲線圖對比效果如圖3。

根據表1的實驗數據結果對比可知，所提出的混合蟻群算法相比同等條件下的傳統蟻群算法，不僅在使用車輛數，還有花費路程和總成本平均值上都有顯著的優化，其在C101-25、R101-25、RC101-25和客戶規模100的C101-100、R101-100、RC101-100這6組算例，全局平均解優化率分別為12%、14%、12%、14%、13%、13%，全局優化解的質量最高達到了14%，所有算例的全局平均解優化率誤差不超過2%。通過對比黃震[7]的混合蟻群算法實驗結果，該算法在車輛數和總路程上都有明顯效果，不僅在25的客戶規模還是100的客戶規模上，使用的配送車輛數都有減少1-3輛，使用車輛帶來的成本也得到減少，表現了很好的適應性，有效減少配送車輛，優化了路線的同時在有限條件下使目標函數配送總成本減少。通過圖3在同樣進行200次迭代下，該混合蟻群算法在迭代開始總成本為4282元對比傳統蟻群算法的最開始成本4800元少，表明該混合蟻群算法提高解的質量，同時由圖3可知，該混合蟻群算法達到迭代最優的速度比傳統蟻群算法迭代達到最優速度快，保持的收斂性較好，也體現了算法的穩健性和求解性能良好，所提出的HACO方法獲得的結果在解的質量和計算收斂迭代方面都得到優化。

下面選擇客戶規模小的25名客戶的C101-25和相對大的100名客戶的RC101-100算例最優解的路徑規劃情況，以及其最優配送方案路線圖，如表2、表3和圖4、圖5。

5 結語

為了更適用于現實生活中的實際問題，將經典蟻群算法作為基本框架，引用遺傳算法中的變異算子，增強了局部探索解的能力，并結合隨機全局探索，避免了蟻群算法陷入局部最優解。所提出的HACO在仿真實驗中不同的客戶規模下對比。與傳統蟻群算法和其他混合蟻群算法結果相比，算法的求解能力是相當有效的。并且在接下來的工作，也為相關方向提供了參考依據?，F實需求中，為了滿足更多功能設定，對車輛路徑問題的更多變種，比如帶容量限制的多目標，軟時間窗車輛路徑問題，以及加入隨機、模糊區間等約束，都具有進一步研究的價值。

參考文獻：

〔1〕Xu Z， Elomri A， Pokharel S， et al. A Model for Capacitated Green Vehicle Routing Problem with the Time-varying Vehicle Speed and Soft Time Windows[J].Computers & Industrial Engineering， 2019， 137（Nov.）： 106011.1-106011.14.

〔2〕Beheshti A K ， ?Hejazi S R . A Novel Hybrid Column Generation-metaheuristic Approach for the Vehicle Routing Problem with General Soft Time Window[J].Information Sciences，2015， 316（C）：598-615.

〔3〕范厚明，劉文琪，徐振林，等.混合粒子群算法求解帶軟時間窗的VRPSPD問題[J].計算機工程與應用，2018，54（19）：221-229.

〔4〕李國明，李軍華.帶軟時間窗的隨機需求車輛路徑問題的算法研究[J].計算機集成制造系統，2021，03（09）：1-20.

〔5〕凌海峰，谷俊輝.帶軟時間窗的多車場開放式車輛調度[J].計算機工程與應用，2017，53（14）：232-239.

〔6〕JIANG，GENGL.Hybridizing Variablen Eighbor-hoodserch with Ant Colony Optimization for Solving the Sing Lerow Facility Lay Out Problem[J].Europoean Journal of Operational Reserch，2016，248（03）：899-909.

〔7〕黃震，羅中良，黃時慰.一種帶時間窗車輛路徑問題的混合蟻群算法[J].中山大學學報（自然科學版），2015，54（01）：41-46.