張延 葛斌

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

關(guān)鍵詞：VRPSTW;蟻群優(yōu)化;變異算子;精英解

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

1 引言

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

2 VRPSTW問題描述

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

2.1 符號定義

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

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

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

3.1 蟻群算法

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

（1）構(gòu)建解：通過計算狀態(tài)轉(zhuǎn)移概率逐步構(gòu)建完整解。狀態(tài)轉(zhuǎn)移概率公式如下：

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

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

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

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

3.2 變異操作

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

3.3 解的評估

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

3.4 混合蟻群算法

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

輸入：螞蟻數(shù)量m，0≤q0≤1等。

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

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

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

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

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

Step5將計數(shù)器設(shè)置為nc=1。

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

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

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

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

Step10設(shè)置nc=nc+1，進入步驟6。

4 實驗及其結(jié)果分析

4.1 實驗環(huán)境及參數(shù)設(shè)置

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

4.2 模型試驗結(jié)果與分析

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

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

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

5 結(jié)語

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

參考文獻：

〔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].計算機集成制造系統(tǒng)，2021，03（09）：1-20.

〔5〕凌海峰，谷俊輝.帶軟時間窗的多車場開放式車輛調(diào)度[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.