張延 葛斌

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

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

中圖分類號(hào)：TP181 ?文獻(xiàn)標(biāo)識(shí)碼：A ?文章編號(hào)：1673-260X（2021）07-0009-04

1 引言

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

2 VRPSTW問題描述

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

2.1 符號(hào)定義

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

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

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

3.1 蟻群算法

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

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

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

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

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

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

3.2 變異操作

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

3.3 解的評(píng)估

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

3.4 混合蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)及其結(jié)果分析

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)：

〔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〕范厚明，劉文琪，徐振林，等.混合粒子群算法求解帶軟時(shí)間窗的VRPSPD問題[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（19）：221-229.

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

〔5〕凌海峰，谷俊輝.帶軟時(shí)間窗的多車場(chǎng)開放式車輛調(diào)度[J].計(jì)算機(jī)工程與應(yīng)用，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〕黃震，羅中良，黃時(shí)慰.一種帶時(shí)間窗車輛路徑問題的混合蟻群算法[J].中山大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，54（01）：41-46.