鄭小雪

（福建農(nóng)林大學(xué) 交通學(xué)院，福建 福州 350002）

物流配送運(yùn)輸，一般是指配送中心按照不同客戶多頻度、小批量的訂貨要求進(jìn)行組織配送，即根據(jù)貨物量進(jìn)行車輛的分配和配送線路的生成，也就是研究車輛的路徑問題。由于從事城市配送汽車貨運(yùn)工作條件復(fù)雜，不僅貨運(yùn)點(diǎn)多、貨物種類繁多、道路網(wǎng)復(fù)雜，而且運(yùn)輸服務(wù)地區(qū)內(nèi)運(yùn)輸網(wǎng)點(diǎn)分布不均勻。因此，如何應(yīng)用現(xiàn)代數(shù)學(xué)方法及計(jì)算機(jī)快速求解路線優(yōu)化方案，是國(guó)內(nèi)外專家學(xué)者普遍探索的重要課題。

1 VRP問題描述及分類

從配送中心 (物流據(jù)點(diǎn)) 用多輛車向多個(gè)需求點(diǎn) (客戶) 送貨，每個(gè)需求點(diǎn)的位置和需求量為已知，每輛車的載重量一定，要求合理安排車輛路線，達(dá)到一定的目標(biāo) (如路程最短、費(fèi)用最少、時(shí)間盡量少、使用車輛盡量少等) 即為VRP問題[1]。并滿足以下條件：每條配送路徑上各需求點(diǎn)的需求量之和，不超過車輛載重量；每條配送路徑的長(zhǎng)度不超過車輛一次配送的最大行駛距離；每個(gè)需求點(diǎn)必須滿足，且只能有一輛車送貨；每輛車均從中心出發(fā)，完成任務(wù)后又全部回到中心。

根據(jù)VRP問題的條件可分為以下分類：

（1）按照運(yùn)輸任務(wù)分為純裝問題、純卸問題以及裝卸混合問題。

（2）按車輛載貨狀況分滿載問題和非滿載問題。

（3）按照車輛類型分為單車型問題和多車型問題。

（4）按照車輛是否返回配送中心車場(chǎng)，劃分為車輛開放問題和車輛封閉問題。

（5）按照優(yōu)化的目標(biāo)可分為單目標(biāo)優(yōu)化問題和多目標(biāo)優(yōu)化問題。

（6）按照有無時(shí)間要求可分為有時(shí)間窗問題和無時(shí)間窗問題。

實(shí)際中的車輛優(yōu)化調(diào)度問題可能是以上分類中的一種或幾種的綜合。目前國(guó)內(nèi)外用于解決該問題的現(xiàn)代數(shù)學(xué)方法，主要有以下幾類[1]：精確優(yōu)化方法、啟發(fā)方法、模擬方法、交互優(yōu)化法。

2 VRP問題的數(shù)學(xué)模型

VRP問題在現(xiàn)實(shí)的物流系統(tǒng)中可由服務(wù)區(qū)、倉庫、分布在服務(wù)區(qū)內(nèi)的服務(wù)點(diǎn)組成。要把經(jīng)典的VRP問題抽象成一個(gè)數(shù)學(xué)模型，需要設(shè)定一些前提：只有一個(gè)倉庫，所有車輛從這里裝載貨物出發(fā)，運(yùn)送完貨物返回倉庫；所有的車輛能力都是一樣的；每一個(gè)服務(wù)點(diǎn)只能由一輛車提供服務(wù)[2]。

設(shè)配送中心需向L個(gè)客戶送貨，每個(gè)客戶的需求量是g，每輛車的載重量是q，cij表示從i點(diǎn)到j(luò)點(diǎn)的運(yùn)輸成本，其含義可以是距離、費(fèi)用、時(shí)間等，設(shè)配送中心編碼為0，客戶編碼為1,2,…,L，數(shù)學(xué)模型如下。

建立數(shù)學(xué)模型：

其中：式⑴保證了總成本Z最?。皇舰茷檐囕v的載重量約束；式⑶保證了每個(gè)客戶點(diǎn)的運(yùn)輸任務(wù)僅由一輛車來完成，而所有的運(yùn)輸任務(wù)則由K輛車共同完成；式⑷和式⑸保證每個(gè)客戶能且只能被一輛車服務(wù)一次。

3 蟻群算法在求解VRP中的應(yīng)用

3.1 螞蟻的轉(zhuǎn)移策略

螞蟻的轉(zhuǎn)移策略是蟻群算法的重要組成部分，是螞蟻構(gòu)造路徑的過程，它在很大程度上決定了算法的性能。在求解TSP (旅行者問題) 時(shí)，由于每只螞蟻需要遍歷所有的結(jié)點(diǎn)，因此，初始狀態(tài)下，螞蟻可以位于任意結(jié)點(diǎn)，且在螞蟻轉(zhuǎn)移過程中，該只螞蟻沒有經(jīng)過的所有結(jié)點(diǎn)，均可作為轉(zhuǎn)移目標(biāo)。而在求解VRP時(shí)，每只螞蟻遍歷路徑應(yīng)是：僅包含部分結(jié)點(diǎn)；包含且僅包含一次配送中心；路徑必須滿足車輛容量和行駛距離的限制。因此，在求解時(shí)，螞蟻的初始位置與轉(zhuǎn)移策略如下。

（1）所有螞蟻的初始位置均為配送中心，每只螞蟻在滿足車輛容量和行駛距離限制的情況下，盡可能多地遍歷結(jié)點(diǎn)，并最終返回配送中心。此時(shí)，每只螞蟻的禁忌表中存放除配送中心以外的所有該螞蟻已經(jīng)遍歷的結(jié)點(diǎn)。

（2）螞蟻從任意結(jié)點(diǎn)出發(fā)，在完成一個(gè)包含配送中心，且滿足車輛容量和行駛距離限制的回路后，結(jié)束遍歷。此時(shí)，若某只螞蟻的初始位置不是配送中心，則該螞蟻的禁忌表中存放該螞蟻已經(jīng)遍歷的所有結(jié)點(diǎn)，否則存放除配送中心以外的該螞蟻已經(jīng)遍歷的所有結(jié)點(diǎn)。

3.2 可行解構(gòu)造

當(dāng)使用蟻群算法求解VRP時(shí)，每只螞蟻只遍歷部分結(jié)點(diǎn)，因此，當(dāng)所有螞蟻遍歷完成時(shí)，從中選擇滿足車輛數(shù)限制的若干條螞蟻遍歷路徑，即①這些螞蟻恰好遍歷了所有結(jié)點(diǎn)，且除配送中心外，每個(gè)結(jié)點(diǎn)僅被一只螞蟻遍歷；②這些螞蟻遍歷的路徑覆蓋了所有結(jié)點(diǎn)，但是除了配送中心以外，有的結(jié)點(diǎn)被多只螞蟻遍歷；③這些螞蟻遍歷的路徑并沒有覆蓋所有的結(jié)點(diǎn)，其中①中的路徑構(gòu)成一個(gè)可行解，但是這種情況出現(xiàn)的概率極小，而②和③中的路徑均不能構(gòu)成可行解，這就需要進(jìn)行可行解構(gòu)造，即刪除除配送中心外被多只螞蟻遍歷的結(jié)點(diǎn)和插入未被螞蟻遍歷的結(jié)點(diǎn)。

3.3 算法優(yōu)化

通過“3.1”和“3.2”節(jié)的操作后，蟻群算法可用于求解VRP，但是算法的求解性能可能并不好?？梢詮囊韵聨追矫嫣岣咚惴ǖ那蠼庑阅?。

（1）為每個(gè)結(jié)點(diǎn)引入K鄰域以限制螞蟻在選擇轉(zhuǎn)移目標(biāo)時(shí)，只在距當(dāng)前結(jié)點(diǎn)較近的結(jié)點(diǎn)中選擇。但是可能存在一個(gè)結(jié)點(diǎn)的K鄰域中的結(jié)點(diǎn)均處于一只螞蟻的禁忌表中的情況，此時(shí)需要另外設(shè)計(jì)轉(zhuǎn)移規(guī)則，以防止該只螞蟻不能完成回路構(gòu)造。

（2）在“3.2”節(jié)中，刪除結(jié)點(diǎn)和插入結(jié)點(diǎn)時(shí)設(shè)計(jì)有利于算法收斂的規(guī)則。例如，刪除結(jié)點(diǎn)可按節(jié)約最大的原則，即保留重復(fù)結(jié)點(diǎn)中的一個(gè)而刪除其他所有重復(fù)結(jié)點(diǎn)，使刪除后總路徑長(zhǎng)度減小最大；而插入結(jié)點(diǎn)可按增加最小的原則，即將在所有路徑中均未出現(xiàn)的結(jié)點(diǎn)插入到一條路徑的恰當(dāng)位置，使插入后總路徑長(zhǎng)度增加最小，如果節(jié)點(diǎn)不惟一時(shí)，任選一結(jié)點(diǎn)。

（3）設(shè)計(jì)有利于算法收斂的信息素更新策略。信息素更新策略是決定蟻群算法收斂與否的重要因素，傳統(tǒng)的信息素更新策略對(duì)所有螞蟻遍歷的路徑均增加信息素，而實(shí)際上，有些螞蟻遍歷的路徑對(duì)最優(yōu)解根本沒有貢獻(xiàn)，這樣導(dǎo)致傳統(tǒng)的信息素更新策略不利于蟻群算法的收斂。在信息素更新時(shí)，為了防止邊上信息素的過分懸殊會(huì)導(dǎo)致算法快速收斂于局部最優(yōu)解，為此，可以將信息素量限制于特定的范圍內(nèi)，對(duì)信息素量大于上限的邊，直接將該邊上的信息素量置為上限，而對(duì)信息素量小于下限的邊，直接將該邊上的信息素量置為下限。

（4）啟發(fā)函數(shù)的設(shè)計(jì)。設(shè)計(jì)更有利于信息素向存在于最優(yōu)解中的邊集中的啟發(fā)函數(shù)，從而加速算法的收斂速度。

4 引入啟發(fā)式函數(shù)

在蟻群算法的基礎(chǔ)上，采用啟發(fā)函數(shù)中的節(jié)約算法來提高算法的求解性能。節(jié)約算法屬于啟發(fā)式算法[3]，它的基本思想是首先把各個(gè)客戶單獨(dú)與車場(chǎng)相連，構(gòu)成n條“0→i→0”(i,j=1,2,…,n)，計(jì)算連接后費(fèi)用的節(jié)約值。

s(i,j) 越大，說明把客戶i和客戶j連接在一起時(shí)總費(fèi)用節(jié)約值越多，因此應(yīng)優(yōu)先連接s(i,j) 值大的點(diǎn)i和j。基于這一原則，Clarke和Wright在1964年提出C-K節(jié)約算法。約定把只有一個(gè)客戶的線路 (如“0→i→0”) 稱為初始化線路，把包含兩個(gè)或兩個(gè)以上客戶的線路 (如“0→...i→...→0”) 稱為已構(gòu)成線路。

4.1 轉(zhuǎn)移規(guī)則細(xì)化

應(yīng)用節(jié)約算法對(duì)蟻群算法進(jìn)行細(xì)化，定義如下形式的螞蟻轉(zhuǎn)移概率[4]：

其中：τij代表邊 (i,j) 上的信息素；ηij表示邊 (i,j) 上的啟發(fā)信息，常取邊(i,j)長(zhǎng)度的倒數(shù)，即ηij=1/dij。

應(yīng)用節(jié)約算法，首先將各點(diǎn)單獨(dú)與源點(diǎn)0相連，構(gòu)成1條僅含一個(gè)點(diǎn)的線路；然后計(jì)算將點(diǎn)i與j在滿足車輛載重量約束的基礎(chǔ)上，連接在同一條線路上的費(fèi)用節(jié)約值，即μij=di0+d0j-dij，顯然，μij越大，收益越大，而選擇結(jié)點(diǎn)vj的概率也就越大。μij的值需要作最大值和最小值限制，以免μij過大或過小而影響整個(gè)路徑轉(zhuǎn)移概率，如,當(dāng)μij等于0時(shí)，轉(zhuǎn)移概率為0，使得整個(gè)轉(zhuǎn)移概率公式的其他影響因素失去意義。kij= (qi+qj) /Q是考慮車輛容量約束和車輛載重量利用率而引入的變量。α,β,λ,γ為權(quán)重參數(shù)。p是個(gè)隨機(jī)數(shù)，取值在 (0,1) 區(qū)間內(nèi)。r0為取值在 (0,1) 區(qū)間內(nèi)的一個(gè)固定值。

4.2 信息素更新原則

采用全局更新規(guī)則，當(dāng)所有螞蟻?zhàn)咄晁械目蛻酎c(diǎn)，也就是完成一次遍歷后，各路徑上的信息素濃度要根據(jù)下式進(jìn)行調(diào)整：

其中：ρ∈(0,1), (1?ρ)為信息素濃度的衰減系數(shù)，在本次遍歷（t,t+1）時(shí)間段中信息素濃度的增量?τij(t,t+1)表示為：

其中：?τij表示螞蟻k在本次遍歷（t,t+1）時(shí)間段中留在路徑（i，j）上的信息濃度，可用下式表示：

其中：Q為常數(shù)；Lk表示螞蟻k在本次遍歷中所走過的路徑的長(zhǎng)度。

4.3 Min-Max思想的引入

Min-Max蟻群系統(tǒng)(MMAS)是德國(guó)學(xué)者Stützle等提出的一種ACO算法的改進(jìn)方案[5]。由于信息素隨時(shí)間衰減因素的存在，在搜索陷入局部最優(yōu)時(shí),某段路徑弧段的信息素相對(duì)其他路徑弧段的信息素而言,在數(shù)量上占據(jù)絕對(duì)的優(yōu)勢(shì)，以至于引起算法過早地收斂。因此本算法對(duì)各路徑弧段上的信息素,設(shè)定了最大和最小值的限制,從而避免了某段路徑的信息素過大或過小。即τij(t)∈τmin,τmax) ，若τij>τmax,則τij=τmax；若τij<τmin,則τij=τmin。

4.4 算法步驟

步驟1:初始化各參數(shù),輸入基礎(chǔ)數(shù)據(jù),給定n個(gè)客戶和每個(gè)客戶的需求量，得出各需求點(diǎn)之間的距離，將m個(gè)螞蟻平均分配到n個(gè)需求點(diǎn)，設(shè)定α、β、τij（0）車輛的額定載重量、最大循環(huán)次數(shù)Ncmax，計(jì)算出ηij,μij,kij的值并存放于相應(yīng)的數(shù)組中，設(shè)置μij的最大值和最小值。

步驟2：將m個(gè)螞蟻置于初始點(diǎn)(即配送中心)，并將初始點(diǎn)置于當(dāng)前解集中。

步驟3：對(duì)每只螞蟻k，隨機(jī)選擇除初始點(diǎn)外的任意節(jié)點(diǎn)f，并將f置于當(dāng)前解集中。

步驟4：對(duì)每只螞蟻k，根據(jù)不同的p值選取相應(yīng)的pijk,并根據(jù)剩余載重量選擇下一結(jié)點(diǎn)j,將j置于當(dāng)前解集中。

步驟5：重復(fù)步驟4，直到每只螞蟻都訪問了每一結(jié)點(diǎn)，受到車輛載重量的限制，每只螞蟻將得到若干條由配送中心為起點(diǎn)的回路，每條回路就相當(dāng)于一輛運(yùn)輸車所經(jīng)過的路徑。

步驟6：計(jì)算每只螞蟻所走過的每條回路的路徑長(zhǎng)度，按照全局更新規(guī)則對(duì)各邊的信息素進(jìn)行更新。

步驟7：按照各螞蟻所得到的可行解，得出最優(yōu)解。

步驟8：依式τij(t+1) =ρτij(t) +?τij(t,t+1) 進(jìn)行信息素的全局更新。

步驟9：Nc=Nc+1，所有螞蟻又回到初始位置，重復(fù)步驟2、3、4、5、6、7、8。每次迭代獲得的最優(yōu)解要與前面獲得的解比較，若優(yōu)于之前的解，則替換成當(dāng)前最優(yōu)解。

步驟10：直至Nc>Ncmax或者出現(xiàn)退化行為(即每次迭代找到的都是相同的解)，則結(jié)束，輸出最優(yōu)路徑及路徑長(zhǎng)度。否則轉(zhuǎn)步驟2。

5 應(yīng)用分析

表1 實(shí)例計(jì)算結(jié)果

本文參照文獻(xiàn)[6]中的示例利用后的蟻群算法進(jìn)行優(yōu)化。設(shè)某物流中心有5臺(tái)配送車輛,車輛的最大載重量均為8 t，一次配送的最大行駛距離均為50 km，需要向20個(gè)客戶送貨，物流中心的坐標(biāo)為(14.5 km，13. 0 km)，20個(gè)客戶的坐標(biāo)及其貨物需求量。

第一次蟻群算法控制參數(shù)為:

第二次蟻群算法控制參數(shù)為:M2=5,Ncmax2=30,τij2=1,τmax2=20,τmin2=1,α2=1,β2=5,Q2=50

程序運(yùn)行10次，各次搜索結(jié)果如表1所示。

從表1中可以看出，采用本文的算法求解上述VRP均得到質(zhì)量很高的解。其平均配送最小距離為111. 6 km，平均使用的車輛數(shù)為4輛。從計(jì)算效率來看，10次求解的平均程序運(yùn)行時(shí)間為345.4ms。在10次求解中，平均與最優(yōu)的差值比最優(yōu)解多3.522%，可見，該算法在求解VRP可得到較好的結(jié)果。算法找到的最好解的配送距離為107.8 km，對(duì)應(yīng)的4條配送路線為I:0→8→19→15→16→13→6→0;II:0→5→14→2→12→9→10→7→1→0;III:0→4→3→17→11→20→0; IV:0→18→0。文獻(xiàn)[6]所設(shè)計(jì)的混合蟻群算法找到的最好解的配送距離為108.62 km，對(duì)應(yīng)的4條配送路線為I: 0→5→14→2→12→9→10→7→1→0;II:0→8→19→15→16→13→6→0; III:0→18→20→11→17→3→0; IV: 0→4→0。相比之下，本算法能夠找到更好的可行解，比其最優(yōu)解少0.072 1%。

本文在傳統(tǒng)蟻群算法的基礎(chǔ)上，針對(duì)傳統(tǒng)算法的不足，引入啟發(fā)函數(shù)中的節(jié)約算法來對(duì)蟻群算法進(jìn)行優(yōu)化，并借鑒Min-Max的思想，使算法得到優(yōu)化，通過實(shí)例證明了算法的優(yōu)良性，能夠較好地解決車輛路徑問題，而且計(jì)算出來的結(jié)果更穩(wěn)定。

[1] 彭 揚(yáng)，伍 蓓. 物流系統(tǒng)優(yōu)化與仿真[M]. 北京：中國(guó)物資出版社，2007.

[2] 黃天赦，葉春明. 基于混合粒子群算法的車輛路徑優(yōu)化問題研究[J]. 物流科技，2008 (9)：26-27.

[3] 繆興鋒，秦明森. 物流運(yùn)籌學(xué)方法[M]. 廣州：華南理工大學(xué)出版社，2007.

[4] 王俊鴻，修桂華. 二次蟻群算法在運(yùn)輸調(diào)度問題中的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用與軟件，2008 (7)：71-73.

[5] Stützle T, HoosH. Improvements on the ant system:introducingMax-min ant system[A]. Proc. Int. Con.f ArtificialNeuralNetwork and GeneticAlgorithm,W ien:SpringerWerlag,1997.

[6] 李卓君. 混合蟻群算法求解物流配送路徑問題[J]. 武漢理工大學(xué)學(xué)報(bào)，2006 (2)：306-309.