廣東工業(yè)大學(xué)自動(dòng)化學(xué)院 湯雅連 蔡延光 趙學(xué)才

1.引言

車輛路徑問題（Vehicle Routing Problem，VRP）最早由Dantzig，F(xiàn)ulkerson和Johnson于1959年提出。VRP問題是一個(gè)組合優(yōu)化問題，而關(guān)聯(lián)物流運(yùn)輸調(diào)度問題（Related Vehicle Routing Problem，RVRP）也是車輛路徑問題的延伸，所以也屬于NP-hard問題。近年來，遺傳算法、模擬退火算法、粒子群算法、蟻群算法等現(xiàn)代啟發(fā)式算法為VRP的求解提供了極大的便利。

蟻群算法[1-3]是解決VRP問題的一種有效的元啟發(fā)式方法，其中改進(jìn)的螞蟻系統(tǒng)[4]有帶精英策略的螞蟻系統(tǒng)（Ant System with elitist strategy，ASelite）、基于優(yōu)化排序螞蟻系統(tǒng)（Rank-Based Version of Ant System，SArank）、蟻群系統(tǒng)（Ant Colony System，ACS）、最大-最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS）以及最優(yōu)-最差螞蟻系統(tǒng)（Best-Worst Ant System，BWAS）。蟻群算法[5]的提出，為解決路徑規(guī)劃問題提供了新的思路和解決方法，但是傳統(tǒng)蟻群算法與其他進(jìn)化算法同樣存在易于陷入局部最優(yōu)、早熟收斂等缺陷，為了提高蟻群算法的全局搜索能力，提高其收斂速度，該文提出了保留每代最優(yōu)解，并自適應(yīng)改變信息素?fù)]發(fā)因子，從而克服傳統(tǒng)蟻群算法的不足。

2.問題描述及數(shù)學(xué)模型的建立

2.1 問題描述

關(guān)聯(lián)物流運(yùn)輸調(diào)度問題也是車輛路徑問題的延伸，所以具有相似性。問題可以簡(jiǎn)單描述為，假設(shè)給定車場(chǎng)信息以及客戶信息（位置和貨物需求量等），貨物之間的關(guān)聯(lián)系數(shù)，車輛信息（載重約束、里程約束和容量約束等），要求合理安排車輛和運(yùn)輸路線，在滿足所有客戶需求的前提下，使配送成本最低。

2.2 數(shù)學(xué)模型

第i個(gè)客戶的貨運(yùn)量為gi（i=1，2，…，l），需要從車場(chǎng)將貨物運(yùn)到客戶手中，有車場(chǎng)派出載重量為q的貨車若干，已知gi＜q。

預(yù)先對(duì)需要車輛數(shù)進(jìn)行估計(jì)?？梢园凑帐剑?）確定車輛數(shù)：

式中，[ ]表示不大于括號(hào)內(nèi)數(shù)字的最大整數(shù)； 0＜α＜ 1，是對(duì)裝車（或卸車）的復(fù)雜程度及約束多少的估計(jì)。

以cij表示為從點(diǎn)i到點(diǎn) j的運(yùn)輸成本（距離、費(fèi)用、時(shí)間等），cij=cji。假設(shè)客戶i， j之間的距離為：dij。車場(chǎng)編號(hào)為0，客戶為：i（i=1，2，…，l）。關(guān)聯(lián)系數(shù)為：r，rij表示點(diǎn)i處的貨物與點(diǎn)j處貨物的關(guān)聯(lián)系數(shù)。目標(biāo)為使車輛的總運(yùn)輸距離最短。

定義變量如下：

目標(biāo)函數(shù)式（4）表示總運(yùn)輸距離最短，以cij表示從點(diǎn)i到點(diǎn)j的運(yùn)輸成本并用客戶i與 j之間的距離dij作為取值。（5）為車輛行駛距離約束，其中dijk表示車輛k行駛了客戶i到 j的路程，n是車輛k服務(wù)的客戶數(shù)目，最大為N。（6）和（7）表示兩個(gè)變量之間的關(guān)系。（8）表示車輛服務(wù)客戶i后直接行駛到j(luò)為其服務(wù)。（9）表示每個(gè)客戶只能由1輛車來服務(wù)且每個(gè)客戶都能得到服務(wù)。（10）表示每輛車所運(yùn)送的貨物重量不能超過車輛載重量的限制。（11）表示保證每輛車的客戶總數(shù)小于等于總客戶數(shù)目。（12）為關(guān)聯(lián)系數(shù)rij的取值約束，當(dāng)i與j的貨物不可用同輛車配送時(shí)，應(yīng)選擇其他客戶的貨物。

3.一種自適應(yīng)蟻群算法

3.1 基本蟻群算法

設(shè)m為螞蟻數(shù)量，dij(i，j=1，2，...，n)表示i與j之間的距離， τij(t)表示t時(shí)刻在ij連線上殘留的信息素強(qiáng)度。初始時(shí)刻，各路徑上信息量相等，設(shè)τij(0)=C（C為常數(shù)）。螞蟻 k(k =1，2，...， m)在運(yùn)動(dòng)過程中，根據(jù)各條路徑上信息量決定轉(zhuǎn)移方向，Pijk表示t時(shí)刻螞蟻k由位置i轉(zhuǎn)移到j(luò)的概率，如式（13）所示。

其中 allowedk為螞蟻k下一步可選擇的城市。 ηijβ為能見度因數(shù)，常取ηij(t)=1/dij。α和β分別反映了螞蟻在運(yùn)動(dòng)過程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對(duì)重要性，α為信息啟發(fā)式因子，β為期望啟發(fā)式因子。

過多殘留信息素會(huì)引起殘留信息素覆蓋啟發(fā)信息，所以在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有城市的遍歷之后，要對(duì)殘留信息進(jìn)行更新處理。t+n時(shí)刻在路徑(i，j)上的信息量可按式（14）和（15）做調(diào)整。

ρ為信息素?fù)]發(fā)因子， ρ∈ （0，1）， Δτij(t)表示本次循環(huán)中信息素增量。表示第k只螞蟻在本次循環(huán)中留下的信息素，計(jì)算方法可以根據(jù)計(jì)算模型而定，本文采用最常用的蟻周模型，如式（16）所示。

式中Q表示信息素強(qiáng)度，會(huì)影響算法的收斂速度，過大會(huì)導(dǎo)致局部收斂，過小會(huì)影響收斂速度。Lk表示在本次循環(huán)中所走路徑的長(zhǎng)度。

3.2 構(gòu)造狀態(tài)轉(zhuǎn)移規(guī)則

本文采用將確定性選擇組合和隨機(jī)性選擇相結(jié)合的策略，為了縮短最好和最差路徑上的信息量差距，適當(dāng)加大隨機(jī)選擇概率，對(duì)解空間進(jìn)行更完全搜索，從而克服傳統(tǒng)蟻群算法缺陷。按照下式確定螞蟻k由i轉(zhuǎn)移到j(luò)的狀態(tài)轉(zhuǎn)移概率。

q是[0，1]內(nèi)的隨機(jī)數(shù)，q0是一個(gè) 參 數(shù) ， q0∈ [0，1]， 一 般 取0.85～0.90。螞蟻在選擇下一客戶時(shí)，根據(jù)先驗(yàn)知識(shí)，如式（17）所示來選擇最好的邊，否則按式（13）來選擇一條邊，將求得的各個(gè)節(jié)點(diǎn)的轉(zhuǎn)移概率進(jìn)行累加，再與產(chǎn)生的隨機(jī)數(shù)相比較，直到滿足要求，螞蟻可轉(zhuǎn)移到下一節(jié)點(diǎn)。

3.3 信息素更新

3.3.1 保留最優(yōu)解

在每次循環(huán)結(jié)束后，保留最優(yōu)解。

3.3.2 自適應(yīng)改變?chǔ)?/p>

通過減小ρ雖然可以提高算法的全局搜索能力，但也會(huì)使收斂速度降低，因此需要自適應(yīng)改變?chǔ)?。ρ的初始?ρ( t0)=1；當(dāng)算法求得最優(yōu)值在N次循環(huán)中無明顯改進(jìn)時(shí)，ρ如式（18）所示。其中ρmin可以防止ρ因過小而降低算法收斂速度。

3.4 蟻群算法求解流程

Step1：初始化參數(shù)，包括Nc，螞蟻總數(shù)m，信息啟發(fā)式因子α，期望啟發(fā)式因子β，信息素?fù)]發(fā)因子 ρ( t0)，信息素強(qiáng)度Q；

Step2：將螞蟻隨機(jī)置于節(jié)點(diǎn)；

Step3：螞蟻根據(jù)轉(zhuǎn)移概率選擇下一節(jié)點(diǎn)，判斷是否超過載重限制，若沒有，加入禁忌表中；否則，選擇另一個(gè)節(jié)點(diǎn)進(jìn)行判斷；

Step4：若沒有滿足條件的節(jié)點(diǎn)，則將車場(chǎng)編號(hào)加入禁忌表中，表示完成子路徑的搜索。重新將載重置0，執(zhí)行Step3；

Step5：直到所有螞蟻都訪問了所有節(jié)點(diǎn)，每條螞蟻將得到若干條以車場(chǎng)為起終點(diǎn)的回路，回路就是一輛車的路徑軌跡；

Step6：計(jì)算每條回路的路徑長(zhǎng)度，得出局部最優(yōu)解；

Step7：進(jìn)行信息素全局更新；

Step8：若滿足終止條件，達(dá)到最大迭代次數(shù)，則結(jié)束，否則，轉(zhuǎn)Step2。

4.仿真分析

某供應(yīng)處有1個(gè)車場(chǎng)，需給32個(gè)客戶送貨，客戶信息表如表1所示。每輛車最大載重為20噸，每輛車最大配送里程為100km。貨物與貨物之間的關(guān)聯(lián)系數(shù)由Matlab7.1隨機(jī)生成。

本文中的實(shí)驗(yàn)是在Intel(R)Core?i3 CPU2.53GHz、內(nèi)存2.0G的PC機(jī)上采用Microsoft Visual C++6.0編程以及Matlab7.1輔助編程實(shí)現(xiàn)。利用VC++6.0進(jìn)行編程，蟻群算法中參數(shù)設(shè)置：蟻群規(guī)模m為100，最大迭代次數(shù)Nc=200，α =1，β=2， ，q0=0. 88，Q=100。運(yùn)行程序30次，得到該算法求解本算例的最優(yōu)結(jié)果，最短運(yùn)輸距離為268.24千米，如表2所示，配送示意圖如圖1所示。

圖1 配送路徑示意圖

表1 客戶信息表

表2 各配送車輛的配送數(shù)據(jù)

5.結(jié)束語

該文對(duì)傳統(tǒng)的蟻群算法進(jìn)行改進(jìn)，通過自適應(yīng)改變信息量的揮發(fā)因子，既保證了收斂速度，又提高了算法的全局搜索能力。運(yùn)用改進(jìn)的蟻群算法對(duì)建立的單車場(chǎng)單車型無時(shí)間窗約束的關(guān)聯(lián)物流運(yùn)輸調(diào)度模型進(jìn)行求解，實(shí)驗(yàn)結(jié)果證明了算法的可行性和有效性。