混合蟻群算法求解雙目標(biāo)時(shí)間窗VRP

鄧麗娟，張紀(jì)會

(青島大學(xué)a.復(fù)雜性科學(xué)研究所；b.山東省工業(yè)控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 青島 266071)

0 引言

車輛路徑問題[1]，又稱車輛調(diào)度問題，由Dantzig等學(xué)者于1959年首次提出。該問題的一般提法是：給定配送中心、客戶的位置以及各客戶的需求量，車輛從配送中心出發(fā)，完成配送任務(wù)后回到配送中心，確定合理的配送方案，在滿足車輛裝載能力和行程限制等約束條件下使得某些目標(biāo)達(dá)到最優(yōu)(如總行程最短、使用車輛數(shù)最少、費(fèi)用最小等)。該問題具有廣泛的實(shí)際應(yīng)用背景，也是著名的NP難問題。根據(jù)應(yīng)用背景、目標(biāo)函數(shù)和約束條件的不同，該問題有很多變種。1985年Savelsbergh提出帶時(shí)間窗的車輛路徑問題[2],這類問題更加關(guān)注服務(wù)的時(shí)效性。Solomon將帶有時(shí)間窗的車輛路徑問題定義為：車輛從配送中心出發(fā)，在滿足各個(gè)客戶的服務(wù)時(shí)間約束下，將貨物運(yùn)送到客戶手中，最后返回配送中心，使行駛的總行程最短[3]。在實(shí)際配送問題中，除了運(yùn)輸成本外，還需要考慮許多其它的要求，因此，現(xiàn)實(shí)中的車輛調(diào)度問題往往是多目標(biāo)優(yōu)化問題，求解難度更大。研究帶有時(shí)間窗的多目標(biāo)車輛路徑問題具有重要意義。

眾所周知，VRPTW是典型的NP難問題，還沒有一種有效的算法能完全解決它。目前的主要求解方法可分為：精確算法和啟發(fā)式算法。精確算法有動(dòng)態(tài)規(guī)劃法、分支定界法、兩階段法、最短路徑算法等，Christofides[4]用動(dòng)態(tài)規(guī)劃求解VRP，Laporte和Nobert[5]提出了分支定界法，F(xiàn)isher[6]提出兩階段法求解VRPTW，Azi[7]提出最短路徑算法。只有小規(guī)模問題才能用精確算法在較短的時(shí)間內(nèi)尋求其精確解。因此，設(shè)計(jì)有效的啟發(fā)式算法來尋求大規(guī)模車輛路徑問題的近似解是一個(gè)重要的研究方向。啟發(fā)式算法包括經(jīng)典啟發(fā)式算法和智能啟發(fā)式算法。經(jīng)典啟發(fā)式算法采用局部搜索尋求滿意解，算法易實(shí)現(xiàn)但容易陷入局部最優(yōu)。如Clarke和Wright[8]使用節(jié)約法求解VRP，適用于小規(guī)模的VRP問題，Glover[9]將禁忌搜索法用于VRP的求解，但其求解速度較慢。智能啟發(fā)式算法采用全局搜索來尋求滿意解，能避免陷入局部最優(yōu)，但算法設(shè)計(jì)較為復(fù)雜，參數(shù)設(shè)置對算法影響較大。如近年來發(fā)展起來的現(xiàn)代優(yōu)化算法：遺傳算法[10-14]、粒子群算法[15-19]、蝙蝠算法[20]、蟻群算法[21-26]等越來越多地應(yīng)用于VRP領(lǐng)域。然而在實(shí)際應(yīng)用中，粒子群優(yōu)化算法和人工神經(jīng)網(wǎng)絡(luò)在迭代后期易陷入局部最優(yōu)，遺傳算法初始種群敏感易早熟，蟻群算法雖然尋優(yōu)能力較強(qiáng)卻依賴于參數(shù)設(shè)置，故啟發(fā)式優(yōu)化算法的實(shí)用性、尋優(yōu)效率及應(yīng)用價(jià)值均有待提高。

大多數(shù)VRP問題都將成本作為主要優(yōu)化目標(biāo)，但許多基于成本優(yōu)化的解決方案被證明是不可能在實(shí)踐中應(yīng)用的。因?yàn)槿绻麤]有其他性能度量進(jìn)行平衡，只考慮成本最小可能產(chǎn)生反效果[27]。因此，本文設(shè)置的目標(biāo)是以對物流企業(yè)來說達(dá)到總成本最小，對客戶來說達(dá)到服務(wù)的滿意度最高，以此實(shí)現(xiàn)企業(yè)與客戶的雙贏，有利于長期合作。

本文提出一種混合蟻群算法(HACO)來求解VRPTW。設(shè)計(jì)了更符合實(shí)際情況的寬松配送時(shí)間窗。利用精英螞蟻策略分別探索兩個(gè)目標(biāo)函數(shù)，獲取更好的非支配解，通過重新定義自適應(yīng)揮發(fā)因子及加入變鄰域搜索算法來平衡算法的局部和全局搜索能力。使用NSGA-Ⅱ獲得Pareto解集。通過Solomon標(biāo)準(zhǔn)算例對算法性能進(jìn)行測試,并對車速進(jìn)行了靈敏度分析。仿真結(jié)果表明，HACO能找到質(zhì)量更好的解，能有效減少物流配送成本，提高服務(wù)質(zhì)量。

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

本文所考慮的優(yōu)化目標(biāo)為：最小化總成本和最大化客戶滿意度。總成本包括車輛離開倉庫的固定成本、車輛在行駛過程中產(chǎn)生的運(yùn)輸成本以及車輛未在時(shí)間窗內(nèi)服務(wù)的懲罰成本。

1.1 基本假設(shè)

1)已知配送中心及客戶的位置以及各客戶的需求量。

2)已知各客戶的配送時(shí)間窗。

3)配送車輛數(shù)充足，所有車輛的屬性(油耗、載重、速度)一致。

4)每個(gè)客戶的需求量不超過車輛運(yùn)載能力，每個(gè)客戶只能由一輛車配送。

5)每輛車所服務(wù)的客戶需求之和不超過車輛的載重量。

1.2 滿意度函數(shù)

在帶時(shí)間窗的車輛路徑問題中，時(shí)間窗往往設(shè)置為單時(shí)間窗，但由于物流企業(yè)需要降低成本，客戶需要及時(shí)服務(wù)。為有效提高服務(wù)質(zhì)量，本文設(shè)計(jì)了寬松時(shí)間窗，使之更符合實(shí)際情況。假定客戶i的服務(wù)時(shí)間窗為[EETi,LLTi]，若車輛為客戶i服務(wù)的時(shí)間在此時(shí)間窗外，則客戶i的滿意度為0，且會對物流企業(yè)帶來不良影響，產(chǎn)生懲罰成本?？蛻鬷的最滿意的服務(wù)時(shí)間窗為[ETi,LTi](其中，[ETi,LTi]?[EETi,LLTi])，若車輛在該時(shí)間窗內(nèi)為客戶i服務(wù)，則客戶i的滿意度為1；車輛為客戶i服務(wù)的時(shí)間離該時(shí)間窗越遠(yuǎn)，客戶i的滿意度就越低。假設(shè)μi為配送過程中客戶i的服務(wù)滿意度，則客戶滿意度函數(shù)表示為:

(1)

其中，ti表示車輛到達(dá)客戶i的時(shí)刻。若車輛早于EETi到達(dá)客戶i，則需等待，并且產(chǎn)生等待成本。若晚于LLTi到達(dá)客戶i，會產(chǎn)生懲罰成本。

1.3 懲罰函數(shù)

客戶的最優(yōu)配送時(shí)間窗由客戶指定。配送車輛在配送時(shí)間窗[EETi,LLTi]內(nèi)完成任務(wù)，不予處罰。若配送車輛早于或晚于時(shí)間窗配送，則影響服務(wù)質(zhì)量，給予一定懲罰。懲罰成本函數(shù)設(shè)計(jì)如式(2)：

(2)

其中,EETi為客戶i的最早服務(wù)時(shí)間，LLTi為客戶i的最晚服務(wù)時(shí)間，ti為車輛到達(dá)客戶i的實(shí)際時(shí)刻；p為單位時(shí)間等待成本，q為單位時(shí)間懲罰成本。

1.4 建模

1.4.1 參數(shù)和變量

節(jié)點(diǎn)集記為V={0,1,2，…,n}，其中節(jié)點(diǎn)0表示配送中心，是配送車輛的起點(diǎn)和終點(diǎn)，客戶節(jié)點(diǎn)集為{1,2，…,n}。K={1,2,…,k}為配送車輛集合。其它參數(shù)定義為:dij：客戶i和j之間的距離；qi：客戶i的需求量；W：車輛的最大承載能力；C：車輛行駛單位距離產(chǎn)生的成本；tij：車輛從客戶i行駛到客戶j所需要的時(shí)間；fij：車輛從客戶i到客戶j的行駛成本；c：車輛離開配送中心的固定成本；Ti：客戶i的服務(wù)時(shí)長；ti：車輛到達(dá)客戶i的時(shí)刻；v：車輛的速度；Qk:車輛k的服務(wù)客戶集；[EETi,LLTi]：客戶i的服務(wù)時(shí)間窗；[ETi,LTi]：客戶i的最滿意服務(wù)時(shí)間窗；決策變量：

(3)

(4)

1.4.2 目標(biāo)函數(shù)

基于以上假設(shè)，所研究的VRPTW的目標(biāo)函數(shù)為

(5)

(6)

目標(biāo)函數(shù)(5)表示最小化總成本，包括車輛離開倉庫的固定成本、運(yùn)輸成本、車輛未在時(shí)間窗內(nèi)送達(dá)的懲罰成本；目標(biāo)函數(shù)(6)表示最大化客戶的平均滿意度。

1.4.3 約束條件

(7)

(8)

fij=Cdij?i,j∈V

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

約束條件(7)表示滿足車輛容量限制，每輛車不能超過其最大載重量；約束條件(8)表示車輛行駛時(shí)間與距離成正比；約束條件(9)表示車輛行駛成本與距離成正比；約束條件(10)表示每個(gè)客戶只能由一輛車配送；約束條件(11)表示滿足車輛數(shù)量限制；約束條件(12)表示服務(wù)時(shí)間限制，其中M是充分大的正數(shù)；約束條件(13)～(15)表示車輛從配送中心出發(fā)又回到配送中心，形成一個(gè)回路。約束(16)和(17)定義了決策變量的性質(zhì)。

2 混合蟻群算法

蟻群算法由意大利學(xué)者M(jìn)arco Dorigo提出，是用來探索優(yōu)化路徑的概率型算法。傳統(tǒng)蟻群算法的魯棒性較好，且具有優(yōu)良的分布式計(jì)算能力，易與其它算法結(jié)合使用，但易陷入局部最優(yōu)。為增強(qiáng)搜索能力，本文引入變鄰域搜索算法，將NSGA-Ⅱ算法用于雙目標(biāo)的擇優(yōu)過程，同時(shí)將精英螞蟻分為兩部分，分別探索兩個(gè)目標(biāo)，達(dá)到同時(shí)優(yōu)化雙目標(biāo)的目的；并將揮發(fā)因子設(shè)置為自適應(yīng)變化。

2.1 Pareto解集

定義1：(最小化問題的Pareto最優(yōu))對于兩個(gè)決策變量a,b∈X，稱a支配b，記為a?b，當(dāng)且僅當(dāng)?i∈{1,2,3…,n},fi(a)≤fi(b),?j∈{1,2,3…,n},fj(a)

2.1.1 非支配排序

為了解決雙目標(biāo)優(yōu)化問題并保證Pareto解集的多樣性，用NSGA-Ⅱ來處理雙目標(biāo)的擇優(yōu)過程。它具有以下兩個(gè)特點(diǎn):非支配排序和擁擠度設(shè)計(jì)。對每次迭代后得到的解進(jìn)行非支配排序，解集中的每個(gè)不被其他解支配的解，記為第一層F1，其非支配序值irank為1；然后從所有解集中刪除該層解，在其余解中找到非支配解集，記為第二層F2，其非支配序值irank為2；以此類推，直至每個(gè)解都分層完畢，其中，同一分層內(nèi)的解的非支配序值irank相同。

2.1.2 擁擠度設(shè)計(jì)

擁擠度是指在解集中每個(gè)解周圍所包含的解的密度，解的擁擠度是相同分層的兩個(gè)相鄰解的目標(biāo)函數(shù)的距離差。擁擠度能衡量解的多樣性。其算法描述如下：

1)令擁擠度nd=0,n∈1,2,…,n。

2)對每個(gè)目標(biāo)函數(shù)fm：

當(dāng)螞蟻選擇路徑及進(jìn)行局部搜索時(shí)，根據(jù)以下規(guī)則判斷兩個(gè)解的優(yōu)劣：

1)當(dāng)兩個(gè)解不在同一非支配等級時(shí)，非支配序值irank較低的解更優(yōu)。

2)當(dāng)兩個(gè)解在同一非支配等級時(shí)，擁擠度較大的解更優(yōu)。即此解周圍的其他解較少，所在區(qū)域解的分布較為分散。

2.2 算法流程

2.2.1 偽隨機(jī)概率選擇規(guī)則

為避免搜索陷入停滯，螞蟻在選擇下一個(gè)客戶時(shí)采用確定性與隨機(jī)性相結(jié)合的選擇策略，引入偽隨機(jī)因子q0，位于客戶i的螞蟻k按式(18)選擇下一個(gè)客戶。

(18)

其中，q為區(qū)間(0,1)內(nèi)的均勻分布隨機(jī)數(shù),q0為可調(diào)參數(shù)且q0∈[0,1]。每當(dāng)螞蟻選擇下一個(gè)客戶時(shí)，就隨機(jī)產(chǎn)生一個(gè)在[0,1]內(nèi)的數(shù)，根據(jù)隨機(jī)數(shù)q的值按式(18)確定螞蟻選擇下一個(gè)客戶。當(dāng)q

每只螞蟻考慮以下兩個(gè)因素來確定選擇下一個(gè)客戶的概率：信息素及時(shí)間窗。螞蟻本身根據(jù)信息素濃度的高低來選擇下一個(gè)客戶，同時(shí)考慮到達(dá)下一個(gè)客戶的時(shí)間以及時(shí)間窗的大小，優(yōu)先選擇時(shí)間窗較小且到達(dá)時(shí)間較合適的客戶。

(19)

其中，Jk表示t時(shí)刻螞蟻k下一步允許服務(wù)的客戶集(即還沒有服務(wù)的客戶)；ξ和ψ為權(quán)重系數(shù)，滿足0≤ξ,ψ≤1，且ξ+ψ=1。α為信息啟發(fā)式因子，反映了殘留的信息量在蟻群的探索過程中的相對重要程度；β為期望啟發(fā)式因子，反映了路徑期望值在蟻群的探索過程中的相對重要程度；ηij表示由客戶i轉(zhuǎn)移到客戶j的期望程度，其計(jì)算公式為：

(20)

2.2.2 自適應(yīng)揮發(fā)因子

在實(shí)際情況中，揮發(fā)因子ρ的值往往是隨機(jī)設(shè)定的，且揮發(fā)因子ρ的大小會影響算法的全局搜索能力以及收斂速度；若ρ過大，則路徑上的信息素總量快速減少，會降低了算法的收斂速度，但利于尋找全局最優(yōu)解；若ρ過小，則路徑上的信息素總量增加，能提高算法的收斂速度，但易陷入局部最優(yōu)解，全局搜索能力較差。為平衡算法的局部和全局搜索能力，避免陷入早熟，本文將揮發(fā)因子ρ設(shè)置為如式(21)的自適應(yīng)調(diào)整方式：

(21)

2.2.3 信息素的設(shè)置

為避免由于某條路徑上的信息素濃度過高而導(dǎo)致搜索陷入局部最優(yōu)。將每條路徑上的信息素τij(t)的界限設(shè)置為[τmin,τmax]，若τij(t)>τmax,則τij(t)=τmax;若τij(t)<τmin,則τij(t)=τmin。其中，τmax和τmin的計(jì)算公式為

(22)

(23)

其中，f為當(dāng)前解中的最小成本，u為當(dāng)前解中的最大滿意度，σ為精英螞蟻的個(gè)數(shù)。

2.2.4 信息素的更新

信息素的更新方法設(shè)置為兩種：局部信息素更新和全局信息素更新。

局部信息素更新規(guī)則為：每只螞蟻訪問完一個(gè)客戶后對各條路徑上的信息素濃度進(jìn)行更新，其計(jì)算公式為

(24)

其中，

(25)

全局信息素更新規(guī)則為：在每次迭代結(jié)束后，對精英螞蟻經(jīng)過的路徑進(jìn)行信息素更新。由于本文為雙目標(biāo)優(yōu)化問題，因此在仿真時(shí)將精英螞蟻分為兩部分，一部分對應(yīng)成本最低，另一部分對應(yīng)滿意度最高。通過調(diào)整兩部分精英螞蟻對信息素的影響來達(dá)到同時(shí)降低成本和提高客戶滿意度的目的。信息素計(jì)算公式為:

(26)

(27)

其中，將成本按升序排序，f為所有路徑中的最小成本，u為所有路徑中的最大滿意度，fμ為排名第μ的路徑花費(fèi)的成本，該路徑上的信息素增加量為△τij(t)。

2.2.5 局部搜索

變鄰域搜索(VNS)由Hansen等[28]學(xué)者于1997年提出，基本思想是通過不同的鄰域結(jié)構(gòu)進(jìn)行搜索，不斷提高解的質(zhì)量，具有較強(qiáng)的局部搜索能力。當(dāng)所有螞蟻搜索完之后，對當(dāng)前最優(yōu)解進(jìn)行局部搜索。由于本文考慮的是雙目標(biāo)優(yōu)化問題，因此當(dāng)所有螞蟻搜索完之后，找出當(dāng)前解中成本最小及滿意度最大的兩條路徑，分別對其進(jìn)行變鄰域搜索，擴(kuò)大搜索空間。

結(jié)合所研究問題的特點(diǎn)，本文設(shè)計(jì)了3種鄰域結(jié)構(gòu)，分別為：1)2-opt算子，隨機(jī)將路徑中兩點(diǎn)間的客戶反序；2)Swap算子，隨機(jī)交換路徑中兩個(gè)客戶的位置；3)Insert算子，隨機(jī)選取路徑中兩個(gè)客戶，將后面位置的客戶插入到前面客戶的前面。

基于上述3種鄰域結(jié)構(gòu)的變鄰域搜索的步驟如下：

1)確定鄰域結(jié)構(gòu)LYk,k∈{1,2,3}，設(shè)置最大循環(huán)次數(shù)itermax，令當(dāng)前循環(huán)次數(shù)iter=1。

2)若達(dá)到最大循環(huán)次數(shù)，則輸出最優(yōu)解；否則令k=1。

3)對當(dāng)前最優(yōu)解進(jìn)行局部搜索，若搜索后的新解比當(dāng)前最優(yōu)解更優(yōu)，則更新當(dāng)前最優(yōu)解；否則k=k+1。

4)若k≤3則轉(zhuǎn)入第3步；否則iter=iter+1，轉(zhuǎn)入第2步。

需要說明的是，子路徑間的鄰域結(jié)構(gòu)有可能會破壞解的可行性,即可能會違反車輛容量限制，因此,在進(jìn)行變鄰域搜索前，去掉路徑中的配送中心，將路徑轉(zhuǎn)換為只有客戶的路徑，再進(jìn)行變鄰域搜索，搜索完的路徑再按照車輛容量來劃分子路徑，分配車輛。

2.2.6 算法步驟

綜上所述，利用HACO算法求解帶時(shí)間窗的車輛路徑問題的流程如圖1所示。

圖1 HACO算法流程圖

3 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證HACO算法求解帶時(shí)間窗的車輛路徑問題上的有效性，利用Matlab R2015b軟件進(jìn)行兩組仿真實(shí)驗(yàn)，操作系統(tǒng)為Windows 10，處理器為Intel Core i7-8550U，主頻為1.8GHz，內(nèi)存為8GB。

3.1 參數(shù)設(shè)定

表1 正交組合及測試結(jié)果表

表2 參數(shù)水平取值表

表3 參數(shù)平均響應(yīng)值表

由表3可知，參數(shù)ξ對算法的影響最為顯著，其次是參數(shù)α和β，由圖2可知，算法中合適的參數(shù)組合為α=4，β=1，ξ=0.9。

圖2 各參數(shù)對算法性能的影響趨勢

3.2 評價(jià)標(biāo)準(zhǔn)

為衡量算法的性能，選用以下常用的性能標(biāo)準(zhǔn)：

1)非支配解的數(shù)量(NPS)：算法所得非支配解越多，說明算法能保持較好的解的多樣性。

2)解集間的覆蓋率(C)[29]：C(E,F)表示集合F中至少被集合E中的一個(gè)解支配的解所占比例，其計(jì)算公式如式(28)：

(28)

C(E,F)的取值范圍為[0,1]，值越大，則說明F中有更多的解被E中的解支配，而E中解的質(zhì)量比F更好，需要注意的是：C(E,F)與C(F,E)需要分別計(jì)算，C(E,F)≠1-C(F,E)。

3.3 仿真實(shí)驗(yàn)1

仿真實(shí)驗(yàn)1以文獻(xiàn)[20]中的算例進(jìn)行仿真實(shí)驗(yàn)，在算例中增加了寬松時(shí)間窗。算例參數(shù)設(shè)置如下：由一個(gè)配送中心為20個(gè)客戶服務(wù)，配送中心位于各客戶的中間位置，坐標(biāo)為[70,70]，客戶分布為輻射型。配送車輛最大載重為8 t，所有配送車輛規(guī)格一致，平均車速為40 km/h，車輛使用成本為100元，行駛成本為2元/km。等待成本為10元/h，懲罰成本為40元/h。由于如今加油站隨處可見，將配送車輛的最大行駛路程設(shè)為無限制。客戶信息如表4所示(其中編號0為配送中心，編號1～20為需要服務(wù)的客戶)。

表4 客戶信息表

將本文所講算法與傳統(tǒng)蟻群算法及NSGA-Ⅱ算法進(jìn)行對比。種群大小等于客戶數(shù)，最大迭代次數(shù)NCmax=500。每個(gè)算法獨(dú)立運(yùn)行40次，結(jié)果如表5所示，圖4為HACO算法求解的最優(yōu)路徑。

圖4 最優(yōu)路徑

表5 與改進(jìn)前算法比較結(jié)果

表5為改進(jìn)的HACO算法與改進(jìn)前的ACO算法、NSGA-Ⅱ算法比較結(jié)果，從表中可知：HACO的平均值、最優(yōu)值、最差值均優(yōu)于ACO算法及NSGA-Ⅱ算法。HACO算法獲得的非支配解的數(shù)量最多，NSGA-Ⅱ算法獲得的非支配解的數(shù)量高于ACO算法，但是解的質(zhì)量低于ACO算法及HACO算法。這主要是由于HACO算法相比于NSGA-Ⅱ算法增加了對當(dāng)前最優(yōu)解進(jìn)行局部探索，HACO算法相比于ACO算法不僅增強(qiáng)了其局部探索能力、再加上揮發(fā)因子ρ在陷入局部最優(yōu)解的時(shí)候自動(dòng)衰減，有助于跳出局部最優(yōu)，能找到更多高質(zhì)量的解，且精英螞蟻策略針對兩個(gè)目標(biāo)分別進(jìn)行搜索的方式可以保證解的多樣性。表6為3種算法兩兩配對計(jì)算得到的覆蓋率，表格對應(yīng)C(E,F)，其中E為行對應(yīng)的算法，F(xiàn)為列對應(yīng)的算法。如C(HACO,ACO)=0.826 1,說明ACO獲得的非支配解中有82.61%的解被HACO的非支配解所支配；C(HACO,NSGA-Ⅱ)=0.866 7,說明NSGA-Ⅱ的非支配解中有86.67%的解被HACO的非支配解所支配，而C(ACO,NSGA-Ⅱ)=0.666 7，說明NSGA-Ⅱ的非支配解中有66.67%的解被ACO的非支配解所支配。表6的實(shí)驗(yàn)結(jié)果也證實(shí)了本文所提的HACO算法的有效性。從圖3可以直觀地看出HACO的性能顯著優(yōu)于初始的ACO算法及NSGA-Ⅱ算法，其Pareto解占據(jù)明顯的支配地位。ACO及NSGA-Ⅱ的解呈交叉式，即成本較高的NSGA-Ⅱ的非支配解優(yōu)于ACO的非支配解，成本較低的則呈現(xiàn)相反的狀態(tài)。實(shí)驗(yàn)結(jié)果顯示：三種算法均沒有找到滿意度為1的路徑，這并不代表不存在滿意度為1的配送方案，而是因?yàn)楸疚难芯康臑殡p目標(biāo)車輛路徑問題，算法在運(yùn)行過程中會同時(shí)兼顧兩個(gè)目標(biāo)探索方向，不存在不顧成本地提高滿意度以及單純降低成本而不顧客戶滿意度的情況。

表6 與改進(jìn)前算法的覆蓋率(C)比較結(jié)果

圖3 Pareto前沿

表7為本文算法與文獻(xiàn)[30]的文化狼群算法、文獻(xiàn)[31]的改進(jìn)離散花朵授粉算法、文獻(xiàn)[32]的單點(diǎn)單親遺傳混合蟻群算法以及文獻(xiàn)[20]所提算法中性能最優(yōu)的單點(diǎn)重組精英遺傳混合蝙蝠算法就仿真實(shí)驗(yàn)1的結(jié)果進(jìn)行對比。從最少車輛數(shù)來說，只有單點(diǎn)單親遺傳混合蟻群算法的最少車輛數(shù)為7，其余的均為6。從最短路徑來說，HACO算法的最短距離為999.26 km，比文化狼群算法減少了0.64%，比改進(jìn)離散花朵授粉算法減少了5.27%，比單點(diǎn)單親遺傳混合蟻群算法減少了13.66%，比單點(diǎn)重組精英遺傳混合蝙蝠算法減少了8.34%。HACO算法求得的平均最短路徑長度也優(yōu)于其余4種算法，說明HACO具有更好的穩(wěn)定性。在5種算法的比較中，HACO算法求得的解質(zhì)量更好，而且更穩(wěn)定，說明HACO算法能有效減少物流配送成本，提高服務(wù)質(zhì)量。

表7 與其他算法比較結(jié)果

靈敏度分析。帶時(shí)間窗的車輛配送受車輛行駛速度的影響。從平均20 km/h的車速開始，以5 km/h的速度增加，不斷改變車輛平均行駛速度并分別運(yùn)行算法20次，記錄最小總成本及最大客戶滿意度。比較不同車速下的總成本及滿意度最優(yōu)值的變化如圖5所示。

由圖5可知，車速的提高在一定程度上能降低物流企業(yè)的成本并保持較高的客戶滿意度，但當(dāng)車速增長過大時(shí)，會導(dǎo)致成本增加并降低滿意度，其原因是由于車速的增加，車輛在路上行駛的時(shí)間較短，過早到達(dá)客戶處，導(dǎo)致在客戶處的等待時(shí)間增加，增加了車輛的等待成本并降低了滿意度，且過快的行駛速度易導(dǎo)致交通事故，造成重大的財(cái)產(chǎn)和人員損失。因此，控制車輛合適的行駛速度對物流企業(yè)至關(guān)重要。

圖5 平均車速對最優(yōu)解的影響

3.4 仿真實(shí)驗(yàn)2

為進(jìn)一步驗(yàn)證本文所提HACO算法求解不同類型和規(guī)模問題的性能，本文選用Solomon標(biāo)準(zhǔn)測試集中的R101、C101、RC101三個(gè)算例作為測試問題，其中R101中的客戶坐標(biāo)為隨機(jī)分布，C101中的客戶坐標(biāo)為聚類分布，RC101中的客戶坐標(biāo)為混合隨機(jī)聚類分布，每個(gè)算例的客戶數(shù)量為100。為滿足本文時(shí)間窗設(shè)定，對算例中的時(shí)間窗做出調(diào)整。將HACO算法與ACO算法、NSGA-Ⅱ算法進(jìn)行性能比較，不同算法的比較結(jié)果如表8所示，圖6為C101算例的優(yōu)化結(jié)果。

表8 算例對比結(jié)果

從表7可以看出，在最小總成本、最大滿意度方面，HACO明顯優(yōu)于初始的ACO與NSGA-Ⅱ算法。HACO算法在ACO中加入了局部搜索算法，綜合提高了HACO算法的局部搜索和全局搜索能力，并通過NSGA-Ⅱ算法更快地選擇出更好的解?？傮w來說，本文提出的HACO算法能穩(wěn)定地獲得更優(yōu)的解，能有效解決帶時(shí)間窗的車輛路徑問題，求解性能明顯提高。

4 結(jié)論

在帶時(shí)間窗的車輛路徑問題中，影響配送成本的因素主要是客戶的位置及時(shí)間窗，客戶位置不可變動(dòng)，客戶時(shí)間窗分布較為復(fù)雜但可變。當(dāng)客戶根據(jù)自身需求提出服務(wù)時(shí)間窗時(shí)，物流企業(yè)可根據(jù)路徑規(guī)劃對客戶反饋，對能及時(shí)服務(wù)的客戶協(xié)調(diào)好服務(wù)時(shí)間，對不能及時(shí)服務(wù)的客戶調(diào)整至下一時(shí)間段優(yōu)先配送。從而達(dá)到物流企業(yè)與客戶的雙贏。本文對更大客戶規(guī)模的算例實(shí)驗(yàn)不足,今后可以通過改進(jìn)算法、提高程序的運(yùn)行效率、提升硬件環(huán)境來解決更復(fù)雜的大規(guī)模求解問題。