求解雙目標(biāo)VRPTW的改進(jìn)混合蟻群算法

朱曉東，王 鼎

(鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州 450001)

0 引言

車輛路徑問(wèn)題[1](vehicle routing problem，VRP)是指使用一組車輛從配送中心出發(fā)給已知客戶進(jìn)行配送服務(wù)，在滿足一定約束條件下，求解最短路徑的線路。帶時(shí)間窗的車輛路徑問(wèn)題(vehicle routing problem with time window，VRPTW)是VRP的拓展，它在VRP的基礎(chǔ)上增加了服務(wù)時(shí)間的限制，即每個(gè)客戶都有接受服務(wù)的時(shí)間范圍，稱為時(shí)間窗，車輛必須在時(shí)間窗內(nèi)對(duì)客戶進(jìn)行服務(wù)。良好的路徑規(guī)劃不僅可以節(jié)省運(yùn)輸成本，提高配送效率，還可以提升服務(wù)質(zhì)量，帶來(lái)巨大的經(jīng)濟(jì)效益。

由于VRPTW是一個(gè)非確定性多項(xiàng)式難題(NP-Hard)，精確算法無(wú)法在有效時(shí)間內(nèi)完成求解，使用啟發(fā)式算法求解大規(guī)模客戶VRPTW問(wèn)題受到專家學(xué)者的廣泛關(guān)注，比如遺傳算法[2-3]、差分進(jìn)化算法[4]、粒子群優(yōu)化算法[5]、布谷鳥搜索算法[6]等。

蟻群算法[7]在解決VRPTW問(wèn)題上取得了眾多成果，如Yu等[8]提出了蟻群算法和禁忌搜索混合的算法，該算法先使用蟻群算法得到一個(gè)局部最優(yōu)解，然后使用一次禁忌搜索算法來(lái)跳出局部最優(yōu)；Ding等[9]對(duì)蟻群系統(tǒng)作了進(jìn)一步改進(jìn)，在計(jì)算轉(zhuǎn)移概率時(shí)考慮了節(jié)點(diǎn)之間的節(jié)約值，同時(shí)采用λ-interchange作為局部?jī)?yōu)化方法，提升了算法的收斂速度；朱杰等[10]將模擬退火算法和蟻群算法結(jié)合，改進(jìn)了蟻群算法中狀態(tài)轉(zhuǎn)移公式和信息素更新策略，提高算法搜索能力；劉云等[11]將單親遺傳算法和蟻群算法相結(jié)合，提升了傳統(tǒng)蟻群算法的計(jì)算效率和收斂速度，并通過(guò)實(shí)際算例說(shuō)明算法的實(shí)用性；柴獲等[12]采用一種混合蟻群算法來(lái)解決雙目標(biāo)帶時(shí)間窗車輛路徑問(wèn)題，提出了一種新的搜索空間構(gòu)建方法，并改進(jìn)了蟻群算法的狀態(tài)轉(zhuǎn)移公式；孫小軍等[13]提出一種動(dòng)態(tài)混合蟻群優(yōu)化算法，該算法將蟻群算法和遺傳算法進(jìn)行融合，自適應(yīng)控制蟻群算法參數(shù)；葛斌等[14]提出了一種動(dòng)態(tài)混合改進(jìn)蟻群算法，該算法在對(duì)客戶分區(qū)的基礎(chǔ)上，引入了交通擁堵因子來(lái)改進(jìn)傳統(tǒng)算法中的狀態(tài)轉(zhuǎn)移公式，并將揮發(fā)因子設(shè)置為隨機(jī)變量，使算法更穩(wěn)定地收斂到全局最優(yōu)解。

上述文獻(xiàn)通過(guò)對(duì)傳統(tǒng)蟻群算法的改進(jìn)，促進(jìn)了蟻群算法在VRPTW問(wèn)題上的應(yīng)用及發(fā)展，但仍存在不足。如Yu等[8-10]提出的算法均是以最短路徑為目標(biāo)，但是在實(shí)際問(wèn)題中還要考慮車輛數(shù)等多個(gè)目標(biāo)，單目標(biāo)優(yōu)化無(wú)法滿足實(shí)際需求。劉云等[11-12]提出了解決實(shí)際問(wèn)題的多目標(biāo)改進(jìn)蟻群算法，但所解決問(wèn)題中節(jié)點(diǎn)數(shù)較少，在解決大規(guī)模節(jié)點(diǎn)問(wèn)題上存在搜索能力不足、收斂速度慢等缺點(diǎn)。針對(duì)這些問(wèn)題，筆者提出一種用于解決大規(guī)模雙目標(biāo)VRPTW的改進(jìn)混合蟻群算法。

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

記G=(V,E)為賦權(quán)圖，V為頂點(diǎn)集，V=V0∪Vc，其中V0={0}表示配送中心，Vc={1,2,…,n}表示配送節(jié)點(diǎn)；E為邊集，E={(i,j)|i,j∈V,i≠j}表示節(jié)點(diǎn)i和j之間的有向線段。設(shè)dij表示節(jié)點(diǎn)i、j之間的距離，tij表示車輛從i到j(luò)的時(shí)間。節(jié)點(diǎn)i的需求量為di，接受服務(wù)的時(shí)間窗為[ETi,LTi]，服務(wù)時(shí)長(zhǎng)為STi。K={1,2,…,m}表示車輛編號(hào)，每輛車載重恒定為D，車輛k到達(dá)節(jié)點(diǎn)i的時(shí)間Tik，若車輛k在時(shí)間窗開始之前到達(dá)，則需等待一段時(shí)間wik，wik=max(0,ETi-Tik)。定義變量：

本文中VRPTW的雙目標(biāo)數(shù)學(xué)模型可表述為：

(1)

(2)

s.t:

(3)

(4)

(5)

(6)

(7)

Tik

(8)

Tik+wik+STi+tij

(9)

其中，式(1)、(2)為目標(biāo)函數(shù)，表示以路徑的最短距離和最小車輛數(shù)為目標(biāo)；約束條件(3)表示每條線路上的客戶需求量不能超過(guò)車輛容量限制；約束條件(4)表示每個(gè)客戶只能被訪問(wèn)一次；約束條件(5)表示車輛在服務(wù)節(jié)點(diǎn)j之前只服務(wù)了一個(gè)節(jié)點(diǎn)i；約束條件(6)表示車輛在服務(wù)節(jié)點(diǎn)i后只服務(wù)了一個(gè)節(jié)點(diǎn)j，避免線路內(nèi)部產(chǎn)生回路；約束條件(7)表示每輛車的起點(diǎn)和終點(diǎn)都必須是配送中心；式(8)～(9)為時(shí)間窗約束。

2 基本混合蟻群算法求解VRPTW

2.1 可行解的構(gòu)建

使用基本蟻群算法求解VRPTW時(shí)，首先令每只螞蟻從配貨中心出發(fā)，根據(jù)狀態(tài)轉(zhuǎn)移概率隨機(jī)地從候選節(jié)點(diǎn)集合中選擇下一節(jié)點(diǎn)來(lái)構(gòu)建可行線路，若線路上無(wú)可行節(jié)點(diǎn)添加時(shí)，該螞蟻返回配貨中心，完成一條可行線路的構(gòu)建。接著重復(fù)上述過(guò)程，繼續(xù)從剩余節(jié)點(diǎn)中構(gòu)建可行線路，直到所有節(jié)點(diǎn)都被訪問(wèn)，完成一個(gè)可行解的構(gòu)建。

假設(shè)當(dāng)前節(jié)點(diǎn)為i，下一個(gè)節(jié)點(diǎn)的候選集合為W0，螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移至節(jié)點(diǎn)j的轉(zhuǎn)移概率為：

(10)

當(dāng)所有螞蟻完成可行解的構(gòu)建后，按照下式進(jìn)行全局信息素更新。

(11)

(12)

式中：ρ(0<ρ<1)為常數(shù)，表示信息素的揮發(fā)速率；Δτij為信息素累計(jì)量；m為螞蟻數(shù)量；L(u)為第u只螞蟻的路徑，dis(u)表示第u只螞蟻的總距離；Q為常數(shù)，表示每只螞蟻釋放信息素的總量。

2.2 局部?jī)?yōu)化算法

車輛路徑問(wèn)題中常用的局部?jī)?yōu)化算法有2-interchange和or-interchange。2-interchange用于兩條路徑間的鄰域搜索，該算法從兩條路徑分別選取a和b個(gè)節(jié)點(diǎn)進(jìn)行交換來(lái)產(chǎn)生鄰域解(a,b∈{0,1,2}且a和b不同時(shí)為0)。圖1表示了a=1、b=1時(shí)的一個(gè)樣例：將路徑l中的1個(gè)節(jié)點(diǎn)x與路徑k中的1個(gè)節(jié)點(diǎn)y進(jìn)行交換產(chǎn)生鄰域解。

圖1 a=1、b=1時(shí)2-inerchange變換Figure 1 2-inerchange transformation when a=1，b=1

or-interchange用于單條線路的鄰域搜索，將線路內(nèi)部?jī)蓚€(gè)節(jié)點(diǎn)交換位置來(lái)產(chǎn)生鄰域解。圖2表示將路徑l中x、z兩個(gè)節(jié)點(diǎn)交換產(chǎn)生鄰域解。

圖2 or-interchange變換過(guò)程Figure 2 or-interchange transform process

3 改進(jìn)的混合蟻群算法

在面對(duì)大規(guī)模VRPTW時(shí)，由于較多的節(jié)點(diǎn)數(shù)量和復(fù)雜的約束，上述基本混合蟻群算法收斂速度慢，搜索效率低，并且無(wú)法滿足多目標(biāo)的需求。筆者從候選節(jié)點(diǎn)的選擇、轉(zhuǎn)移概率和信息素疊加機(jī)制等方面對(duì)基本蟻群算法進(jìn)行改進(jìn)，并提出了一種新的局部?jī)?yōu)化方法來(lái)提升算法的搜索能力。

3.1 候選節(jié)點(diǎn)集合的改進(jìn)

(1)周邊搜索策略。在解決大規(guī)模節(jié)點(diǎn)問(wèn)題時(shí)，基本蟻群算法產(chǎn)生的候選節(jié)點(diǎn)集合中節(jié)點(diǎn)數(shù)量較多，算法難以搜索到最優(yōu)解。筆者結(jié)合VRPTW的問(wèn)題特點(diǎn)，采用周邊搜索策略來(lái)縮小候選節(jié)點(diǎn)搜索范圍。該策略是從下一個(gè)可行節(jié)點(diǎn)的集合中，選擇距離當(dāng)前節(jié)點(diǎn)最近的若干節(jié)點(diǎn)作為候選節(jié)點(diǎn)集合W，如圖3所示。

(2)首節(jié)點(diǎn)的選擇。在可行線路的構(gòu)建過(guò)程中，線路上首節(jié)點(diǎn)的選擇將會(huì)影響接下來(lái)整條路徑的節(jié)點(diǎn)選擇，對(duì)全局規(guī)劃來(lái)說(shuō)非常重要。面對(duì)大規(guī)?？蛻舻腣RPTW問(wèn)題，線路上的首個(gè)節(jié)點(diǎn)相對(duì)于其他節(jié)點(diǎn)來(lái)說(shuō)約束較少，可行節(jié)點(diǎn)的數(shù)量遠(yuǎn)多于路徑中的節(jié)點(diǎn)，為了能夠從眾多可行節(jié)點(diǎn)中選擇最合適的節(jié)點(diǎn)，筆者提出一種首節(jié)點(diǎn)選擇策略來(lái)提升算法的收斂性。該策略可表述為：迭代初期，每條可行線路上的首個(gè)節(jié)點(diǎn)按概率從候選節(jié)點(diǎn)中隨機(jī)選取,當(dāng)?shù)M(jìn)度達(dá)到一定條件時(shí)，首節(jié)點(diǎn)為候選節(jié)點(diǎn)中轉(zhuǎn)移概率最大的節(jié)點(diǎn)。線路的首節(jié)點(diǎn)用i1表示，其選取規(guī)則如下：

(13)

式中：p0i1表示配貨中心到i1的轉(zhuǎn)移概率；it表示當(dāng)前迭代次數(shù)；itm表示最大迭代次數(shù)；ε表示迭代的進(jìn)行程度的參數(shù)；W為候選節(jié)點(diǎn)集合。

3.2 轉(zhuǎn)移概率公式改進(jìn)

在解決大規(guī)模復(fù)雜約束的車輛路徑問(wèn)題時(shí)，基本蟻群算法的轉(zhuǎn)移概率公式中包含節(jié)點(diǎn)的特征信息較少，導(dǎo)致算法搜索能力不足，收斂速度慢。為了提升算法的收斂性，將節(jié)約算法[15]加入轉(zhuǎn)移概率公式。節(jié)約算法首先將兩個(gè)節(jié)點(diǎn)i、j分別分配到一條空余的線路上，再計(jì)算將兩個(gè)節(jié)點(diǎn)合并到一條線路上后可節(jié)省的節(jié)約值Sij。式(14)為節(jié)約值計(jì)算公式。

Sij=d0i+d0j-dij，

(14)

式中：d0i、d0j和dij分別表示配貨中心到i、j節(jié)點(diǎn)的距離和i、j兩節(jié)點(diǎn)的距離。改進(jìn)后的狀態(tài)轉(zhuǎn)移公式如下:

(15)

3.3 信息素疊加公式的改進(jìn)

基本蟻群算法在疊加信息素時(shí)僅考慮路徑的總距離，未對(duì)車輛數(shù)進(jìn)行優(yōu)化。為了在優(yōu)化距離的同時(shí)降低車輛數(shù)，本文算法對(duì)基本蟻群算法的信息素疊加公式進(jìn)行了改進(jìn)，如式(16)所示，使其能夠完成雙目標(biāo)的優(yōu)化。

(16)

和式(12)相比，式(16)中增加了和車輛數(shù)相關(guān)的函數(shù)f(k)。f(k)如式(17)所示。

(17)

式中：V(k)為第k只螞蟻求得可行解的車輛數(shù)；Vglobalbest為當(dāng)前迭代種群中的最小車輛數(shù)；Vlocalbest為全局最小車輛數(shù)。f(k)可以根據(jù)當(dāng)前解的車輛數(shù)對(duì)它的信息素濃度進(jìn)行獎(jiǎng)勵(lì)或懲罰：若當(dāng)前迭代種群中的最小車輛數(shù)大于全局最小車輛數(shù)，則對(duì)V(k)>Vlocalbest的解進(jìn)行懲罰；若當(dāng)前迭代種群中最小車輛數(shù)小于全局最小車輛數(shù)，那么對(duì)V(k)>Vglobalbest的解進(jìn)行懲罰，對(duì)V(k)

由于蟻群算法中信息素疊加是一個(gè)正反饋過(guò)程，為了避免搜索停滯，筆者采用最大最小蟻群算法將信息素濃度限定于[τmax,τmin]，如式(18)所示

(18)

式中：τinitial表示信息素的初始值。

3.4 改進(jìn)的局部?jī)?yōu)化算法

筆者通過(guò)實(shí)驗(yàn)研究發(fā)現(xiàn)，在處理大規(guī)模節(jié)點(diǎn)和復(fù)雜約束的VRPTW問(wèn)題時(shí)，基本蟻群算法構(gòu)建的可行解中會(huì)產(chǎn)生客戶數(shù)量比較少的線路，這將極大降低車輛的利用率，傳統(tǒng)的局部?jī)?yōu)化算法對(duì)此類問(wèn)題考慮不夠。因此筆者提出了一種新的局部?jī)?yōu)化方法，將插入算法和2-interchange結(jié)合，在優(yōu)化距離同時(shí)降低車輛數(shù)，提高車輛的利用效率。算法步驟如下。

Step1將當(dāng)前解分為節(jié)點(diǎn)數(shù)量不小于3的線路集合RM和節(jié)點(diǎn)數(shù)量小于3的線路集合RN，如圖4所示。

Step2使用2-interchange和or-interchange對(duì)RM進(jìn)行局部?jī)?yōu)化z次。迭代初期z取較大值可以加速解的收斂，隨著迭代進(jìn)行，算法產(chǎn)生更優(yōu)鄰域解的難度逐漸加大，通過(guò)z取值逐漸減小來(lái)提升算法效率。在本文算法中，z初始值為6，每經(jīng)過(guò)10次迭代減小1。

Step3設(shè)l(i)為RN中第l條線路上的第i個(gè)節(jié)點(diǎn)，初始化l=1，i=1。

Step4將l(i)插入到RM中的所有節(jié)點(diǎn)之間。若l(i)插入RM中第k條線路的第j個(gè)節(jié)點(diǎn)后產(chǎn)生了可行解，根據(jù)式(19)計(jì)算插入后的ΔCostlikj。式(19)中，cost為線路的總距離；l、k為插入前的線路；lnew、knew為插入后的線路。直到遍歷RM中所有線路上的所有節(jié)點(diǎn)，計(jì)算所有可行解的ΔCostlikj，跳轉(zhuǎn)Step 6。若l(i)插入RM的所有節(jié)點(diǎn)之間均無(wú)法產(chǎn)生可行解，則轉(zhuǎn)到Step 5。

ΔCostlikj=cost(l)+cost(k)-cost(lnew)-

cost(knew)。

(19)

Step5將l(i)與RM中隨機(jī)一個(gè)節(jié)點(diǎn)進(jìn)行交換，要求交換后不改變解的可行性。然后重復(fù)Step 4。值得注意的是，每個(gè)節(jié)點(diǎn)優(yōu)化時(shí)本步驟僅執(zhí)行一次，若仍無(wú)可行解產(chǎn)生，則跳轉(zhuǎn)至Step 7。

Step6將l(i)插入到ΔCostlikj最大的位置。更新插入后的線路。

Step7令i=i+1，返回至Step 4，繼續(xù)對(duì)下一個(gè)節(jié)點(diǎn)進(jìn)行優(yōu)化，直到線路l上所有節(jié)點(diǎn)完成優(yōu)化。

Step8令l=l+1，轉(zhuǎn)至Step 2，繼續(xù)對(duì)下一條線路進(jìn)行優(yōu)化，直到RN中所有線路完成優(yōu)化。

Step9將RN中剩余節(jié)點(diǎn)使用2-interchange方法優(yōu)化。

3.5 改進(jìn)算法整體過(guò)程

改進(jìn)算法整體流程圖如圖5所示。

圖5 改進(jìn)算法整體流程圖Figure 5 The overall flow chart of the improved algorithm

4 實(shí)驗(yàn)與分析

筆者將改進(jìn)的蟻群算法在Solomon[16]標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。Solomon標(biāo)準(zhǔn)數(shù)據(jù)集有R1、R2、C1、C2、RC1、RC2共6類問(wèn)題。這6類問(wèn)題按節(jié)點(diǎn)分布方式可分為隨機(jī)分布(R)、聚集分布(C)和混合分布(RC)。其中R1、C1、RC1問(wèn)題中節(jié)點(diǎn)的時(shí)間窗較窄，車輛載重較小；R2、C2、RC2問(wèn)題中節(jié)點(diǎn)的時(shí)間窗較寬，車輛載重較大。Solomon數(shù)據(jù)集場(chǎng)景多樣具有代表性，因此其常被文獻(xiàn)用于算法評(píng)估。

4.1 參數(shù)設(shè)置

筆者提出的改進(jìn)混合蟻群算法中主要參數(shù)有式(15)中啟發(fā)因子α、β和式(16)中每只螞蟻信息素總量Q。為了分析這些參數(shù)對(duì)算法的影響，筆者在C101測(cè)試問(wèn)題上進(jìn)行實(shí)驗(yàn)。每組實(shí)驗(yàn)均進(jìn)行5次，取結(jié)果的平均值。實(shí)驗(yàn)最大迭代次數(shù)itm=60，信息素?fù)]發(fā)速率ρ=0.08。α、β與結(jié)果的關(guān)系如圖6所示。每只螞蟻釋放信息素總量Q與結(jié)果的關(guān)系如圖7所示。

圖6 α、β取值與總距離的關(guān)系Figure 6 The relationship between the values of α,β and the total distance

從圖6可以看出，當(dāng)1.5<α<2.5、β=2時(shí)，算法取得較好結(jié)果。從圖7可以看出，60

圖7 Q取值與總距離的關(guān)系Figure 7 The relationship between Q and total distance

4.2 首節(jié)點(diǎn)選擇策略的有效性

為了驗(yàn)證首節(jié)點(diǎn)選擇策略的有效性，在標(biāo)準(zhǔn)數(shù)據(jù)集中C101測(cè)試問(wèn)題上進(jìn)行了相關(guān)實(shí)驗(yàn)。

首先對(duì)式(13)中參數(shù)ε的取值進(jìn)行相關(guān)實(shí)驗(yàn)。若ε過(guò)小，算法會(huì)過(guò)早收斂，陷入局部最優(yōu)；若ε較大，算法收斂速度慢，不能收斂于最優(yōu)解。本實(shí)驗(yàn)中對(duì)每個(gè)ε取值都進(jìn)行5次實(shí)驗(yàn)，結(jié)果取平均值。實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 ε取值與總距離關(guān)系Figure 8 The relationship between ε and total distance

從圖8中可以看出，當(dāng)0.2<ε<0.3時(shí)算法取得較好結(jié)果。

在相同條件下將無(wú)首節(jié)點(diǎn)選擇策略的算法和加入首節(jié)點(diǎn)選擇策略的算法進(jìn)行對(duì)照試驗(yàn)。兩者都運(yùn)行5次，結(jié)果取平均值，實(shí)驗(yàn)結(jié)果如圖9所示。

圖9 添加首節(jié)點(diǎn)選擇策略和無(wú)首節(jié)點(diǎn)選擇策略的比較Figure 9 Comparisons of adding first node selection policy and no-first node selection policy

從圖9中可以看出，雖然兩者算法都收斂于最優(yōu)解，但是加入首節(jié)點(diǎn)選擇策略后算法的收斂速度明顯變快，這也證明筆者提出的首節(jié)點(diǎn)選擇策略可以提高算法的收斂速度。

4.3 標(biāo)準(zhǔn)數(shù)據(jù)集測(cè)試

為了說(shuō)明本文算法具有適應(yīng)性和有效性，筆者從標(biāo)準(zhǔn)數(shù)據(jù)集的每類問(wèn)題中選取一個(gè)進(jìn)行實(shí)驗(yàn)，將實(shí)驗(yàn)結(jié)果與基本蟻群算法和Teymourian等[6]提出的混合蟻群算法、Ghoseiri等[17]提出的混合遺傳算法進(jìn)行比較。實(shí)驗(yàn)用MATLAB 2016a進(jìn)行編程，在Intel Core i5-5200 CPU，4 GB內(nèi)存，windows8.1操作系統(tǒng)的計(jì)算機(jī)上運(yùn)行。實(shí)驗(yàn)參數(shù)螞蟻數(shù)量m=15，最大迭代次數(shù)itm=60，ρ=0.08，根據(jù)參數(shù)設(shè)置的實(shí)驗(yàn)結(jié)果取α=2、β=2、Q=80。本文算法在所選問(wèn)題上運(yùn)行3次取最優(yōu)結(jié)果，實(shí)驗(yàn)結(jié)果如表1所示。其中總距離為TD，車輛數(shù)為VN。為了便于比較算法平均值之間的差異，設(shè)res表示本文結(jié)果的平均值，res′表示其他算法結(jié)果的平均值，Δ表示結(jié)果之間的差距百分比，按式(20)計(jì)算。

(20)

從表1中可以看出，在得出的12個(gè)結(jié)果中，筆者提出的改進(jìn)算法在總距離和車輛數(shù)上都明顯優(yōu)于基本混合蟻群算法；和文獻(xiàn)中算法相比，本文算法75%的結(jié)果取得了最優(yōu)解，文獻(xiàn)[6]算法41.6%的結(jié)果取得最優(yōu)解，文獻(xiàn)[17]算法41.6%的結(jié)果取得最優(yōu)解。從所有結(jié)果的平均值來(lái)看，與基本混合蟻群算法相比，本文算法在總距離上領(lǐng)先了25.0%，在車輛數(shù)上領(lǐng)先了28.3%；與文獻(xiàn)[6]算法相比，本文算法在總距離上落后了1.0%，但是在車輛數(shù)上領(lǐng)先了11.3%；與文獻(xiàn)[17]算法相比，本文算法在總距離上領(lǐng)先了1.4%，在車輛數(shù)上領(lǐng)先了1.9%。此外本文算法在不同類型測(cè)試問(wèn)題上均采用相同參數(shù)進(jìn)行實(shí)驗(yàn)，這也說(shuō)明了本文算法具有較強(qiáng)的適應(yīng)能力。

表1 Solomon數(shù)據(jù)集測(cè)試結(jié)果Table 1 Solomon data set test results

5 結(jié)論

筆者通過(guò)分析傳統(tǒng)混合蟻群算法在求解大規(guī)模帶時(shí)間窗路徑規(guī)劃問(wèn)題(VRPTW)中存在的不足，提出了一種改進(jìn)的雙目標(biāo)混合蟻群算法。該算法有針對(duì)性地采用了首節(jié)點(diǎn)選擇策略和改進(jìn)狀態(tài)轉(zhuǎn)移公式來(lái)加速收斂過(guò)程；考慮到路徑距離與車輛數(shù)量?jī)蓚€(gè)優(yōu)化目標(biāo)，在信息素疊加過(guò)程增加了車輛數(shù)懲罰，同時(shí)改進(jìn)了全局信息素更新策略。本文改進(jìn)算法有效地提高了車輛利用率，擴(kuò)大了搜索空間，能夠在雙目標(biāo)下給出較優(yōu)解。通過(guò)在Solomon標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了筆者所提算法的有效性。