基于GA-ACO的帶時(shí)間窗車(chē)輛路徑問(wèn)題研究

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

1 引言

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

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

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

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

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

2 問(wèn)題描述

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

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

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

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

根據(jù)上述符號(hào)說(shuō)明，建立帶硬時(shí)間窗的車(chē)輛路徑問(wèn)題數(shù)學(xué)模型如下：

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

3 GA-ACO混合算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）信息素更新規(guī)則設(shè)計(jì)。基本蟻群算法中螞蟻線路上的信息素更新規(guī)則如下：

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

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

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

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

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

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

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

3.3 染色體編碼與解碼

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

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

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

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

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

3.4 遺傳算子

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

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

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

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

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

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

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

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

4.1 算法步驟

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

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

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

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

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

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

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

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

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

Step9：對(duì)子代染色體進(jìn)行解碼，并計(jì)算各子代個(gè)體染色體解碼后的路徑長(zhǎng)度，用路徑短的線路更新掉原來(lái)螞蟻?zhàn)哌^(guò)的路徑較長(zhǎng)的線路，更新Tabu表和相應(yīng)的路徑長(zhǎng)度，以及每次迭代的最佳路徑。

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

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

4.2 算法流程

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

4.3 算例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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