（武漢理工大學(xué)，湖北 武漢 430063）

1 引言

在物流理論體系中，車輛路徑問題（Vehicle Routing Problem,VRP）是一類經(jīng)典的組合優(yōu)化問題。有能力約束的車輛路徑問題[1](Capacitated Vehicle Routing Problem，CVRP)是最基礎(chǔ)的VRP模型，隨著理論發(fā)展與實際環(huán)境的不斷結(jié)合，越來越多的VRP問題模型得以在此基礎(chǔ)上發(fā)展，而帶時間窗車輛路徑問題（Vehicle Routing Problem with Time Windows,VRPTW）[2]是其中的經(jīng)典問題。更多的研究者傾向運用智能優(yōu)化算法來求解VRPTW，比較普遍的智能優(yōu)化算法主要包括遺傳算法[3]、蝙蝠算法[4]、蟻群算法[5]以及粒子群算法[6]等。

在解決VRPTW時，針對傳統(tǒng)啟發(fā)式算法在求解時容易出現(xiàn)無法收斂和陷入局部最優(yōu)等不足，越來越多的學(xué)者通過改進(jìn)優(yōu)化單一啟發(fā)式算法或融合多種啟發(fā)式算法來提高算法的尋優(yōu)能力。

在改進(jìn)優(yōu)化單一算法方面，學(xué)者們主要通過改進(jìn)算法的某些規(guī)則或者引入某因子實現(xiàn)改進(jìn)的目的。朱杰、張培斯等[7]運用改進(jìn)蟻群算法來求解MVRPTW，通過改進(jìn)轉(zhuǎn)移概率公式，采用鄰域搜索策略提高解的質(zhì)量，借鑒模擬退火算法的思想對信息素更新，加快收斂速度。孫小軍、介科偉[8]也是運用改進(jìn)蟻群算法來求解DVRPTW，通過引入交通擁堵因子，并改進(jìn)揮發(fā)因子的選擇策略，以此有效地提高了蟻群算法的尋優(yōu)能力。陳成[9]則是提出一種改進(jìn)的遺傳算法來求解VRPTW，通過改變算法的編碼結(jié)構(gòu)和交叉變異策略來提升算法的收斂效果和解的質(zhì)量。Sivaramkumar V，Thansekhar M R等[10]針對帶時間窗的多目標(biāo)車輛路徑問題，設(shè)計了一種聚合適應(yīng)度函數(shù)的改進(jìn)遺傳算法（FAGA）。針對同樣的問題，Dong、Zhou等人[11]設(shè)計了一種基于MOEA的多細(xì)胞組織算法（PDVA），在新的算法中充分利用離散螢火蟲演化機(jī)制（DGEM）和可變鄰域演化機(jī)制（VNEM）兩種機(jī)制，在加快算法求解速度的同時提高算法尋優(yōu)的能力。

在融合多種啟發(fā)式算法方面，學(xué)者們主要通過算法之間的相互混合，充分發(fā)揮各算法的優(yōu)點。黃震、羅中良等[12]提出一種混合蟻群優(yōu)化算法用于解決VRPTW，混合算法結(jié)合了蟻群算法與遺傳算法。宋強(qiáng)[13]提出了一種基于局部搜索的混合遺傳算法來求解VRPTW。Keskin，M、Catay,B[14]針對帶時間窗的電動汽車車輛路徑問題（EVRPTW），設(shè)計了一種融合大領(lǐng)域搜索（ALNS）與精確式算法的智能算法，有效提高了算法的尋優(yōu)能力。Ba?os、Julio等[15]在求解帶時間窗的多目標(biāo)車輛路徑問題時，充分考慮總運輸路程，車輛運力與里程的不平衡，設(shè)計了一種基于Pareto最優(yōu)的進(jìn)化計算和模擬退火的混合算法。

上述學(xué)者的研究工作體現(xiàn)了傳統(tǒng)算法的可塑性，通過傳統(tǒng)算法間的碰撞延伸出多種效率更佳、尋優(yōu)能力更強(qiáng)的智能算法。算法改進(jìn)是算法研究過程中一個亙古不變的研究方向，為了更好地解決和改善傳統(tǒng)算法在求解VRPTW時收斂速度慢、解的質(zhì)量不高等問題，本文借鑒上述學(xué)者的研究思想，提出一種以改進(jìn)蟻群算法為主體，插入遺傳算法作為局部優(yōu)化方法的混合算法，在蟻群算法轉(zhuǎn)移概率的改進(jìn)中借鑒文獻(xiàn)[12-16]引入時間窗因素，除此之外還引入節(jié)約距離因子，設(shè)置隨機(jī)變量來優(yōu)化算法的迭代過程，在信息素更新機(jī)制中，定義信息素為標(biāo)量，構(gòu)造信息素?fù)]發(fā)因子的階段函數(shù)，然后使用遺傳算法中的交叉變異算子對蟻群算法得到的較優(yōu)解進(jìn)行下一步優(yōu)化，達(dá)到加快算法收斂速度、提高解的質(zhì)量的目的。算法的仿真實驗與結(jié)果對比驗證了混合算法的有效性與優(yōu)越性。

2 問題描述

一般帶時間窗的車輛路徑問題可以描述如下：一個具有若干額定載重和行駛速度已知的配送車輛的配送中心，需要向區(qū)域內(nèi)的多個客戶進(jìn)行貨物配送，各客戶點的坐標(biāo)位置、需求和可以接受服務(wù)的時間窗已知。在這樣的前提下，考慮如何合理安排車輛配送路線，既能在滿足各項約束的條件下，將貨物安全送到客戶的手中，又能實現(xiàn)配送車輛行駛總路徑最短。

VRPTW的時間窗可以分為硬時間窗、軟時間窗和混合時間窗三種類型，這里主要構(gòu)建硬時間窗車輛路徑問題的數(shù)學(xué)模型。

為方便構(gòu)建數(shù)學(xué)模型，需說明以下符號：將配送中心與客戶節(jié)點構(gòu)成的有向網(wǎng)絡(luò)圖集合設(shè)為G(N,A) ，其中：N=N0?NC，N0表示配送中心，NC={1,2,...,n}為客戶節(jié)點的集合；A={(i,j)| i,j∈N,且i≠j}表示節(jié)點i與j的有向線段集合。dij表示節(jié)點i與節(jié)點j之間的距離，節(jié)點i可以接受服務(wù)的時間窗為[ETi,LTi]，qi表示節(jié)點i的需求量，完成節(jié)點i的服務(wù)需要的時間為STi，K={1,2,...,m} 表示車輛集合，配送車輛的額定載重量為Q，車輛k到達(dá)節(jié)點i的時刻為Tik，配送車輛從節(jié)點i到節(jié)點j所需時間為Tij，同時還需定義以下兩個0-1變量：

建立帶硬時間窗的車輛路徑問題的數(shù)學(xué)模型，需滿足以下條件：（1）各客戶的需求只能由一輛車一次服務(wù)完成，并且各客戶只在自己規(guī)定的時間窗范圍內(nèi)才接受服務(wù)；（2）所有車輛均從配送中心出發(fā)開始服務(wù)，服務(wù)完畢后返回配送中心；（3）不考慮配送中心的取貨時間窗，即配送中心在任意時間都可以取貨；（4）除貨物數(shù)量外，不考慮貨物的其余屬性，同時各配送車輛的行駛速度固定且不考慮交通狀況。

根據(jù)上述符號說明，建立帶硬時間窗的車輛路徑問題數(shù)學(xué)模型如下：

式（1）為車輛總行駛路徑最小目標(biāo)函數(shù)；式（2）為配送車輛的載重約束；式（3）表示每個客戶只能由一輛車進(jìn)行服務(wù)；式（4）表示車輛服務(wù)某節(jié)點后必須從此節(jié)點出發(fā)去下一節(jié)點約束；式（5）和（6）表示每個客戶節(jié)點只允許被服務(wù)一次；式（7）為消去子回路約束；式（8）和（9）為時間窗約束。

3 GA-ACO混合算法

3.1 GA-ACO混合算法策略提出

遺傳算法能夠在大范圍內(nèi)進(jìn)行快速全局搜索，但是不能充分利用系統(tǒng)反饋的信息，所以在求解進(jìn)行到一定范圍后，會有大量的重復(fù)迭代，這大大降低了算法的優(yōu)化效率；而蟻群算法是采用分布式、并行的方式進(jìn)行搜索，并且還具有正反饋的特點，正反饋使得它能夠很好地運用系統(tǒng)反饋的信息，但是由于前期信息素匱乏，求解速度很慢。遺傳算法和蟻群算法的優(yōu)勢正好可以互補(bǔ)，混合在一起形成的混合算法可以提高單一算法的優(yōu)化性能。

目前，蟻群算法和遺傳算法進(jìn)行混合的研究很多，總結(jié)下來，其混合形式主要有以下四種：

（1）蟻群算法為主體，前期使用遺傳算法求解問題的可行解，利用這些可行解進(jìn)行蟻群算法路徑上的信息素初始化，后期使用蟻群算法求解。

（2）遺傳算法為主體，前期使用蟻群算法求解問題較優(yōu)解，作為遺傳算法初始種群，再使用遺傳算法進(jìn)行求解。

（3）融合方式，即在遺傳算法交叉變異操作后，再使用蟻群算法進(jìn)行優(yōu)化。

（4）插入的方式，即在蟻群算法優(yōu)化得到問題可行解后，選取若干可行解作為初始種群進(jìn)行遺傳優(yōu)化。

為了能夠充分利用遺傳算法的快速全局搜索特性以及蟻群算法的分布式計算、正反饋的特點，本文采用第四種插入的方式，即在蟻群算法的每一迭代過程中引入遺傳算法的交叉變異操作，將蟻群算法與遺傳算法融為一體，它們之間通過更新每次迭代過程中的最優(yōu)解來相互指導(dǎo)。首先是蟻群算法在每次迭代后得到問題的若干可行解，從這些可行解中選出相對較優(yōu)的幾個組合成遺傳算法的父代，父代通過復(fù)制、交叉以及變異過程產(chǎn)生子代，使用子代中的較優(yōu)解來更新蟻群迭代可行解中的較差解，作為當(dāng)次迭代的路徑來更新蟻群算法中各路徑上的信息素。使用遺傳算法中的交叉變異算子對蟻群算法得到的較優(yōu)解進(jìn)行進(jìn)一步優(yōu)化，可以有效的避免蟻群算法陷入局部最優(yōu)。

3.2 GA-ACO混合算法的基本規(guī)則設(shè)計

（1）轉(zhuǎn)移規(guī)則設(shè)計。在求解VRPTW的蟻群遺傳混合算法中，蟻群算法部分的螞蟻轉(zhuǎn)移規(guī)則采用確定性選擇和隨機(jī)選擇相結(jié)合的過程，首先對螞蟻選擇下一個節(jié)點的轉(zhuǎn)移概率公式進(jìn)行改進(jìn)。定義如下參數(shù)：節(jié)點數(shù)量為n，人工蟻群的螞蟻數(shù)目為m，節(jié)點i與節(jié)點j之間的距離為dij，節(jié)點i與節(jié)點j之間路上的信息素濃度為τij；節(jié)點i與節(jié)點j之間的可見度（或者親密濃度）為ηij，ηij=1/dij；wij表示時間窗系數(shù)，wij=1waitij；螞蟻k可訪問節(jié)點的集合為allowedk。

則螞蟻k在t時刻從節(jié)點i轉(zhuǎn)移至節(jié)點j的概率pkij為：

其中，α為信息啟發(fā)式因子，β為期望啟發(fā)式因子，θ為時間窗啟發(fā)式因子，γ為節(jié)約距離值啟發(fā)式因子，Uij為節(jié)約距離，其計算公式見式（11），考慮當(dāng)螞蟻從配送中心出發(fā)時，節(jié)約距離設(shè)定為定值1：

時間窗系數(shù)wij中的waitij是一個與車輛行駛時間和各客戶點服務(wù)時間窗相關(guān)的變量，其表達(dá)式為：

為了解決算法過早收斂這一問題，在螞蟻選擇下一個節(jié)點過程中引入變量q0，螞蟻按式（13）的規(guī)則選擇下一個節(jié)點。

其中q為隨機(jī)變量，q∈(0,1)，即在隨機(jī)變量q小于變量q0時，螞蟻選擇計算的轉(zhuǎn)移概率最大的節(jié)點進(jìn)行訪問，否則，就隨機(jī)選擇一個可訪問的節(jié)點進(jìn)行訪問。變量q0的值會隨著迭代次數(shù)的增加而發(fā)生改變，其變化公式為：

其中，NC代表當(dāng)前的迭代次數(shù)，根據(jù)q0的變化可知，隨著迭代的進(jìn)行，q0的值先變大再變小。這就意味著，在前期各螞蟻以較大的概率采用隨機(jī)選擇機(jī)制選擇下一個訪問節(jié)點，有助于各螞蟻在全局范圍內(nèi)搜索最優(yōu)解；中期則以較大的概率采用確定性選擇機(jī)制選擇下一個訪問節(jié)點，使得各螞蟻向著遍歷過的最優(yōu)路徑上靠攏，使得算法收斂；而后期各螞蟻則以較大的概率采用隨機(jī)選擇機(jī)制選擇下一節(jié)點，進(jìn)行全局搜索，有助于跳出局部最優(yōu)。

（2）信息素更新規(guī)則設(shè)計?；鞠伻核惴ㄖ形浵伨€路上的信息素更新規(guī)則如下：

其中：ρ為信息素?fù)]發(fā)因子，ρ∈(0,1) ，即：τij(t)表示t時刻節(jié)點i到節(jié)點j之間的路徑上的信息素含量，它隨時間的推移而不斷的減少；Δτij(t)表示在當(dāng)次循環(huán)中節(jié)點i到節(jié)點j之間路徑上的信息素增量，其表達(dá)式為：

其中：Q表示每只螞蟻攜帶的信息素總量，Lk為螞蟻當(dāng)次迭代走過的總路徑。

本文對蟻群算法的信息素更新規(guī)則中的全局信息素更新規(guī)則和信息素殘留因子ρ進(jìn)行如下改進(jìn)，而局部信息素更新按照式（15）進(jìn)行。

①全局信息素更新機(jī)制的改進(jìn)。算法在每一次迭代結(jié)束時，對當(dāng)次迭代下的最優(yōu)路徑按照式（17）進(jìn)行信息素的更新，式（17）中的Lk為當(dāng)次迭代下最優(yōu)路徑的長度。根據(jù)式（16）可以計算出每一次迭代運算后各路徑上的信息素增量。

與基本蟻群算法不同，定義信息素為標(biāo)量，即信息素不具方向性，同時認(rèn)為節(jié)點i至j與j至i增加的信息素在數(shù)值上具有一致性。所以改進(jìn)的信息素更新規(guī)則如下：

②信息素?fù)]發(fā)因子ρ的改進(jìn)。在基本蟻群算法中，信息素?fù)]發(fā)因子ρ是一個常量，各路徑上信息素的積累速度與ρ值的大小息息相關(guān)。研究發(fā)現(xiàn)，在算法前期，為避免陷入局部最優(yōu)，需要設(shè)置較大的ρ值，可以擴(kuò)大搜索范圍，使螞蟻能夠在更大的范圍內(nèi)訪問各線路；而在算法后期，需要加快算法的收斂，設(shè)置較小的ρ值，放大各路徑上的信息素含量差異，使螞蟻逐步向優(yōu)勢路徑集聚。為此，ρ值隨著迭代的進(jìn)行，應(yīng)該是一個由大到小的變化過程，本文提出使用下列階段函數(shù)模擬ρ值的變化：

（3）局部優(yōu)化規(guī)則。為了避免算法陷入局部最優(yōu)，在每次迭代結(jié)束后，使用遺傳算法對當(dāng)次迭代的較優(yōu)解進(jìn)行局部優(yōu)化，以增加解的多樣性。

3.3 染色體編碼與解碼

遺傳算法處理的直接對象是染色體，所以在使用遺傳算法對VRPTW等實際問題進(jìn)行優(yōu)化時，需要通過編碼建立實際問題與遺傳算法的染色體之間的聯(lián)系。在遺傳算法中可以使用的編碼方式有二進(jìn)制編碼、實數(shù)編碼、符號編碼、自然數(shù)編碼等多種形式，其中二進(jìn)制編碼和自然數(shù)編碼是最常用的。

本文選用自然數(shù)編碼方式對染色體進(jìn)行編碼，由所有的客戶點的編號組成染色體的基因，所有基因的一個排列就是一個染色體結(jié)構(gòu)。比如VRPTW共有14個客戶點，需要有3輛車進(jìn)行配送，由蟻群算法求解的一個可行解（解中的1代表配送中心）為：

去掉可行解中的配送中心編號，只保留客戶節(jié)點編號，并且客戶節(jié)點編號的序列保持不變即為可行解對應(yīng)的染色體結(jié)構(gòu)。則該可行解轉(zhuǎn)換而來的染色體結(jié)構(gòu)為：在同一限定條件下，編碼能夠保證所有染色體的長度都是一樣的，方便后續(xù)的交叉變異。

父代染色體經(jīng)過復(fù)制、交叉、變異處理后，得到子代的染色體結(jié)構(gòu)，進(jìn)一步對子代染色體進(jìn)行解碼，轉(zhuǎn)換成問題的可行解。解碼時按照VRPTW模型里面的約束條件，依次將同時符合車輛載重約束和客戶點時間窗約束的客戶分配給配送車輛。以下面的染色體結(jié)構(gòu)為例：結(jié)合VRPTW模型中的約束，對其進(jìn)行染色體解碼：首先將客戶5分配給車輛1，更新車輛1的時間和載重，再將其后的節(jié)點10分配給車輛1，檢驗載重約束和時間窗約束，如果載重和時間窗約束中有一個及以上不滿足，則形成子路徑（1,5,1），即車輛1只為客戶點5配送貨物；若都符合要求，則將客戶10也由車輛1配送，再依次檢驗后面的客戶，只要車輛超載或是不滿足時間窗約束，則啟動下一輛車，依次檢驗下去，直到染色體結(jié)構(gòu)中所有的客戶點都被分配完。上述子代染色體解碼出來的可行解可能為：

即共需要三輛車完成配送，其路徑分別為（1,5,10,6,9,3,1），（1,8,7,14,2,4,1）和（1,12,13,11,1）。

3.4 遺傳算子

遺傳算法中的核心遺傳算子主要有選擇算子、交叉算子和變異算子三個，它們與遺傳算法的性能息息相關(guān)。

（1）選擇算子。選擇也稱之為復(fù)制，就是按照一定的原則或方法，選擇種群中優(yōu)秀的個體作為父代來繁衍子代的過程。在基本遺傳算法中，使用的選擇策略有精華選擇和比例選擇兩種形式。精華選擇就是每次從種群中選取適應(yīng)度最好的個體作為父代中的一個，直到選出組成種群需要的個體數(shù)目；而比例選擇就是每次隨機(jī)從種群中選取一個，不一定每次都是最好的那個，直到選出構(gòu)建種群需要的個體數(shù)。

本文設(shè)計的蟻群遺傳混合算法，是以蟻群算法為主體，將遺傳算法融入到蟻群算法的每一次迭代計算中，使用遺傳算法對蟻群算法求得的解進(jìn)行局部優(yōu)化。所以本文采用的是精華選擇策略，即從每次迭代得到的路線中，選取總路徑相對較小的若干只螞蟻的行駛路徑作為遺傳算法中的種群。

（2）交叉算子。交叉也叫重組，是自然進(jìn)化過程中新個體或物種產(chǎn)生的主要方式。在遺傳算法中常用的交叉算子有一點交叉、兩點交叉、異位交叉、基于次序的交叉等多種形式。前兩種交叉方式主要用于使用二進(jìn)制編碼的遺傳算法中，后面的幾種形式常用于使用自然數(shù)編碼的遺傳算法中。

本文選用的是異位交叉的形式。其主要步驟為：①隨機(jī)生成兩個交叉點x和y，假設(shè)x≤y；②父代1中的交叉區(qū)域基因為第x到y(tǒng)位，父代2中的交叉區(qū)域基因為第1到y(tǒng)-x+1位，并交換父代中交叉區(qū)域的基因；③對于交換區(qū)域外的重復(fù)基因，根據(jù)交叉區(qū)域中的基因?qū)?yīng)關(guān)系進(jìn)行替換，替換完成后得到子代。

（3）變異算子。在遺傳算法中通過增加變異算子來模擬自然界中基因突變這一環(huán)節(jié)，變異算子的作用雖然小于交叉算子，但也是遺傳算法所必須的，它能夠有效地增強(qiáng)遺傳算法的局部搜索能力，避免算法優(yōu)化得到的解陷入局部最優(yōu)，發(fā)生過早收斂現(xiàn)象。遺傳算法中常用的變異算子有反轉(zhuǎn)變異、2-opt變異等多種形式。

本文選用的變異算子是反轉(zhuǎn)變異方式。首先隨機(jī)確定兩個基因位，然后把這兩個基因位之間的染色體基因進(jìn)行反序排列，即得到子代個體的染色體結(jié)構(gòu)。

4 GA-ACO混合算法的實現(xiàn)

4.1 算法步驟

帶硬時間窗的VRPTW混合算法的具體流程描述如下：

Step1：初始化各參數(shù)。設(shè)初始迭代次數(shù)NC=1，設(shè)置算法最大迭代次數(shù)NCmax，初始化蟻群算法部分的相關(guān)系數(shù)α、β、γ、θ，螞蟻數(shù)量m，信息素Q，初始化Tabu表以及Tau表；設(shè)置遺傳算法部分的交叉概率Pc和變異概率Pm。計算ηij，初始化各路徑上的信息素為1。

Step2：將m只螞蟻初始化到各節(jié)點上，并將各螞蟻的初始化城市編號放入Tabu表中。

Step3：對于從節(jié)點i出發(fā)的螞蟻，按照轉(zhuǎn)移概率式（10）計算并得到螞蟻k將要轉(zhuǎn)移的下一個節(jié)點j。

Step4：判斷螞蟻k是否遍歷完成所有節(jié)點或是滿足載重和時間窗約束，若不滿足約束，則回到配送中心，轉(zhuǎn)到Step3；若遍歷完成所有客戶節(jié)點，則轉(zhuǎn)到Step5；否則，螞蟻k成功轉(zhuǎn)至節(jié)點j，將節(jié)點j加入Tabu表中并轉(zhuǎn)到Step3。

Step5：判斷螞蟻k是否回到配送中心，若沒有回到配送中心，則將節(jié)點1加入到Tabu表，并轉(zhuǎn)至Step6；否則直接轉(zhuǎn)至Step6。

Step6：判斷k是否大于螞蟻數(shù)m，若k＞m，轉(zhuǎn)到Step7；否則k=k+1，轉(zhuǎn)至Step3。

Step7：計算各螞蟻所走路徑的長度，按路徑長短選取路徑短的若干只螞蟻的行駛路徑，初始化為蟻群算法的初始種群，并轉(zhuǎn)至Step8；

Step8：依次隨機(jī)從種群中選取兩個個體作為父代，使用遺傳算法進(jìn)行優(yōu)化，直到種群中所有的可能都被選擇完畢，得到子代并轉(zhuǎn)至Step9。

Step9：對子代染色體進(jìn)行解碼，并計算各子代個體染色體解碼后的路徑長度，用路徑短的線路更新掉原來螞蟻走過的路徑較長的線路，更新Tabu表和相應(yīng)的路徑長度，以及每次迭代的最佳路徑。

Step10：進(jìn)行信息素更新，更新Tau表，得到當(dāng)前迭代次數(shù)中的最優(yōu)解，并初始化相關(guān)數(shù)據(jù)表。

Step11：判斷迭代次數(shù)NC是否超過設(shè)置的最大迭代次數(shù)NCmax，若超過最大迭代次數(shù)NCmax，則算法終止，輸出問題的最優(yōu)路徑和最優(yōu)路徑長度。否則NC=NC+1，跳到Step2。

4.2 算法流程

根據(jù)上面所述的步驟，使用GA-ACO混合算法求解VRPTW問題的流程圖如圖1所示。

4.3 算例分析

選取文獻(xiàn)[12]和文獻(xiàn)[16]中的共同算例作為本文計算算例，在MATLAB軟件中編寫上述GA-ACO混合算法的程序?qū)ι鲜鏊憷M(jìn)行仿真運算。

該仿真算例有一個配送中心節(jié)點，20個客戶節(jié)點，共21個節(jié)點，配送車輛的額定載重為8t，車輛的行駛速度為60km/h，各節(jié)點的坐標(biāo)位置、需求、允許服務(wù)時間窗等數(shù)據(jù)見表1（節(jié)點編號1指配送中心，其余的為各客戶節(jié)點的編號）。

圖1 GA-ACO混合算法的流程圖

編寫算法程序，在MATLAB軟件中多次仿真運算，對仿真結(jié)果和參數(shù)進(jìn)行統(tǒng)計，結(jié)果表明，本文設(shè)計的混合蟻群算法在下列參數(shù)設(shè)置下，算法具有較好的性能。

按照上述參數(shù)對改進(jìn)蟻群算法進(jìn)行初始化設(shè)置，在MATLAB軟件中運行本文改進(jìn)的蟻群算法100次，取其中較好的10次數(shù)據(jù)作為展示，見表2。

由上述結(jié)果可知，使用本文改進(jìn)的蟻群算法計算文獻(xiàn)中算例得到的最優(yōu)路徑長度為1 170.68km，最優(yōu)路徑車輛行駛線路如圖2所示，最優(yōu)路徑出現(xiàn)時的混合算法收斂曲線圖如圖3所示。

將使用本文設(shè)計的混合算法求解20個客戶節(jié)點算例得到的最優(yōu)結(jié)果與文獻(xiàn)中的算法求解同樣算例的結(jié)果進(jìn)行比較，見表3。

表1 算例中各節(jié)點的位置坐標(biāo)與需求量

表2 算例運行結(jié)果

表3 最優(yōu)值比較

由表3中的對比結(jié)果可以看出，運用本文設(shè)計的蟻群遺傳混合算法求解20個客戶節(jié)點的帶硬時間窗的VRPTW算例，得到的最優(yōu)結(jié)果比文獻(xiàn)[12]中的結(jié)果優(yōu)化了6.29%，比文獻(xiàn)[16]中的結(jié)果優(yōu)化了7.53%，可見本文設(shè)計的混合算法是有效的，并且具有一定的優(yōu)越性。

圖2 最優(yōu)結(jié)果路線圖

圖3 最優(yōu)路徑時算法收斂圖

5 結(jié)語

本文針對車輛路徑問題中的經(jīng)典變型—帶時間窗的車輛路徑問題，設(shè)計了一種以改進(jìn)蟻群算法為主體、插入遺傳算法作為局部優(yōu)化手段的改進(jìn)混合算法。充分考慮問題的實際情境，結(jié)合時間窗等相關(guān)約束條件建立VRPTW問題的數(shù)學(xué)模型，設(shè)計改進(jìn)混合算法，通過對文獻(xiàn)中的算例進(jìn)行仿真運算，仿真結(jié)果證明改進(jìn)混合算法可有效提高收斂速度并提高解的質(zhì)量。通過與其它文獻(xiàn)中的最優(yōu)結(jié)果進(jìn)行對比分析，驗證了本文設(shè)計的GA-ACO改進(jìn)混合算法在求解帶時間窗的車輛路徑問題上的有效性和優(yōu)越性。同時需要說明的是，隨著約束條件的變化，算法的構(gòu)造就更為復(fù)雜，同時算法求解時的群體屬性也是可以變化的，這些都可以作為以后的研究方向。