鄭峰峻（西安建筑科技大學 管理學院，陜西 西安 710055）

配送中心作為物流活動中專職從事配送工作的組織者，具有規(guī)模大、配送能力強的特點，從而使得由配送中心對用戶進行需求物品配送成為物流配送的主要形式，而其中配送車輛的路徑合理與否，對于配送速度、配送費用、運力配備以及配送成本與效益的影響均很大，采用科學合理的方法來確定車輛路徑便成為配送中心進行配送活動的一項重要工作。車輛路徑問題（Vehicle Routing Problem，VRP）是由G·Dantzig和J·Ramser于1959年首先提出來的，由于該問題具有與實際生活密切聯(lián)系的特點，吸引了無數(shù)學者為之探索，取得了大量的研究成果，如Clark和Wright提出的節(jié)約算法、Gillett和Miller提出的Sweep算法、Lin提出的2-opt和3-opt交換算法，以及模擬退火算法、遺傳算法、禁忌搜索算法、神經(jīng)網(wǎng)絡算法等。蟻群算法最早是由意大利科學家M·Dorigo于1991年提出，是一種基于群體、用于求解復雜組合優(yōu)化問題的能用搜索技術(shù)，首先被成功應用于TSP問題，隨后在一系列諸如二次分配、圖著色問題、機器人路徑以及通信網(wǎng)絡負載等離散優(yōu)化問題中取得了廣泛應用。

蟻群算法獨特的空間隨機搜索機制、信息素指導機制、信息素揮發(fā)機制以及天然的并行特性使得其自身具有廣闊的發(fā)展前景。本文通過蟻群算法在TSP問題中的應用，給出了求解VRP問題的蟻群算法，取得了較好的效果。

1 蟻群算法簡介

1.1 蟻群算法原理

蟻群算法是對自然界螞蟻的尋徑方式進行模擬而得出的一種仿生算法。在蟻群找到食物時，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素，當它們碰到一個沒有走過的路口時，就隨機地挑選一條路徑前行，與此同時釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的信息素濃度越低，當后來的螞蟻再次碰到這個路口時，選擇信息素較高路徑的概率就會相對較大。這樣形成了一個正反饋，最優(yōu)路徑上的信息素濃度越來越大，而其它的路徑上的信息素會隨著時間的流逝而消減，最終整個蟻群會找出最優(yōu)路徑。在整個尋徑過程中，雖然單個螞蟻的選擇能力有限，但是通過信息素的作用，整個蟻群之間交換著路徑信息，最終找出最優(yōu)路徑。

1.2 蟻群算法的實現(xiàn)

下面以蟻群算法在TSP問題中的應用來對蟻群算法的實現(xiàn)過程進行說明。設m為蟻群的總數(shù)；dij表示城市i到城市j的距離；τij表示城市i到城市j之間的信息素量；Δτij表示螞蟻從城市i到城市j后產(chǎn)生的信息素增量；表示第k只螞蟻在從城市i向城市j轉(zhuǎn)移時的轉(zhuǎn)移選擇概率。

螞蟻在選擇下一個城市時會先計算轉(zhuǎn)移選擇概率，allowedk代表第k只螞蟻尚未訪問過的城市；α表示信息啟發(fā)式因子，它代表在選擇路徑中信息素的作用程度；β表示期望啟發(fā)式因子，它代表成本在路徑選擇中的作用程度。螞蟻將會選擇轉(zhuǎn)移概率最大的城市進行移動。

當一只螞蟻完成一次遍歷后，需要對這只螞蟻經(jīng)過的路徑進行信息素的更新。在M·Dorigo提出的蟻群算法中提出了三種信息素增量模型，分別是ant-quantity system、ant-density system和ant-cycle system，本文采用的是ant-cycle system模型。

Lk表示第k只螞蟻在一次遍歷中所行走的路徑，Q代表螞蟻所攜帶的固定的信息素量。在螞蟻完成一次遍歷后，根據(jù)下式對局部的信息素量進行更新。

1.3 改進的蟻群算法

由于蟻群算法采用的隨機搜索機制，因此在可行解的搜索過程中比較容易達到局部最優(yōu)解而導致算法停滯的現(xiàn)象。所以在基本的蟻群算法上給出以下幾點改進方法，使蟻群算法可以在加快收斂速度的同時保持其搜索路徑的隨機性，以使算法性能有所提高。

（1）隨機化初始位置。初始化螞蟻位置時，將螞蟻隨機放入各個節(jié)點而不是均從一個節(jié)點出發(fā)，這樣有利于搜索路徑的多樣性，為找到比較好的可行解提供了可能。

（2）信息素設置上下限。由于信息素揮發(fā)機制，在一些不常經(jīng)過的路徑上信息素的量會非常小，這樣會使算法陷入局部優(yōu)解的情況，因此算法中引入信息素上限與下限可以增加蟻群搜索路徑時的隨機性，而不會因為信息素量過小或過大而使算法陷入局部最優(yōu)。

（3）動態(tài)設置期望啟發(fā)式因子β值。期望啟發(fā)式因子是計算轉(zhuǎn)移概率時一個很重要的參數(shù)，它反映了啟發(fā)式信息在指導蟻群搜索過程中的相對重要程度。其值越大，則螞蟻在某個局部點上選擇局部最短路徑的可能性越大，算法的收斂速度會加快，同時蟻群搜索最優(yōu)路徑的隨機性降低，易于陷入局部最優(yōu)。因此，在算法初期，可以將β值設為比較大的值，這樣會加快算法的收斂速度，而在算法進行過程中，通過迭代次數(shù)去調(diào)整β值，這樣可以在保證收斂速度的同時使蟻群在搜索路徑時的隨機性加大。

2 改進的蟻群算法在VRP中的實現(xiàn)

2.1 VRP問題與TSP問題的區(qū)別

從本質(zhì)上說，TSP[1-3]是VRP[4]的基本問題，也就是VRP問題的一種特殊情況。二者既相似又存在許多的差別，因此在設計求解VRP的蟻群算法時，既要注意吸收用于求解TSP的蟻群算法的經(jīng)驗，又要充分考慮VRP的具體要求。VRP的復雜程度遠高于TSP，VRP與TSP的區(qū)別主要體現(xiàn)在下面三個方面：

（1）子路徑構(gòu)造過程的區(qū)別。在TSP中，每只螞蟻均要經(jīng)過所有節(jié)點；而在VRP中，每只螞蟻并不需要遍歷所有節(jié)點。因此，在求解VRP的每次迭代中，每只螞蟻移動次數(shù)是不確定的，只能將是否已回到原點作為路徑構(gòu)造完成的標志。

（2）Allowedk的區(qū)別。Allowedk的確定是螞蟻構(gòu)造路徑過程中一個十分關(guān)鍵的問題。在TSP中，螞蟻轉(zhuǎn)移時只需考慮路徑距離和信息量；而在VRP中，螞蟻轉(zhuǎn)移時不但要考慮上述因素，還需考慮車輛容量的限制或者時間窗的限制等。

（3）可行解結(jié)構(gòu)的區(qū)別。在TSP中，每只螞蟻所構(gòu)造出來的路徑均是一個可行解；而在VRP中，每只螞蟻所構(gòu)造的回路僅是可行解的“零部件”，各螞蟻所構(gòu)造的回路可能能夠組合成一些可行解，也可以一個可行解都得不到。因此，研究如何設計算法以盡量避免無可行解現(xiàn)象的出現(xiàn)及如何獲取可行解是蟻群算法在VRP領域中應用的關(guān)鍵。

2.2 VRP問題的算法實現(xiàn)

根據(jù)上面的分析可以看出在求解VRP問題的可行解與TSP存在著一些不同，下面就VRP的求解給出蟻群算法用于求解VRP問題的偽代碼：

Step1：對參數(shù)進行初始化。Set信息啟發(fā)式因子α=1；每條邊的信息素量τij=0.1，每條邊的信息素增量Δτij=0；將m只螞蟻隨機放到各個客戶點上；配送中心車輛的載重量Load=0；設置迭代次數(shù)NC=0；將Allowedk的值初始值設置為true即各客戶尚未訪問，均可以被訪問。

Step2：將螞蟻的初始點放到tabuk中即說明此節(jié)點已經(jīng)被訪問，不能再被訪問。對于每個螞蟻k做如下操作：通過轉(zhuǎn)移規(guī)則選擇下一個訪問j，如果這個城市的需求量沒有超過車輛的載重量，則選擇該客戶點j，否則重新選擇客戶點j。將螞蟻轉(zhuǎn)移到客戶點j，將客戶點j放入tabuk中，并將客戶點的載重量加入Load中，即：Load=Load+demand[]j；判斷Load是否超過車輛的最大載重量，如果未超過則繼續(xù)選擇下一個客戶點，否則返回配送中心。

Step3：判斷Allowedk中是否還有未訪問的客戶點，如果還有其它尚未訪問的客戶點則設置從配送中心出發(fā)，跳轉(zhuǎn)到Step2；如果Allowedk中的客戶點已全部訪問完畢，則第k只螞蟻完成一次遍歷，繼續(xù)下一步。

Step4：從tabuk中計算第k只螞蟻的解集中所經(jīng)過的路徑的長度lengthk。

Step5：根據(jù)各只螞蟻經(jīng)過的路徑利用局部信息素更新機制來更新各只螞蟻所經(jīng)過的路徑的信息素量； Δτij=Q，其中Q代表螞蟻所產(chǎn)生的信息素增量。

Step6：從m只螞蟻中所經(jīng)過的路徑長度得出最短路徑。

Step7：從每次迭代的最短路徑中得出目前最優(yōu)的路徑，然后根據(jù)全局信息素更新機制來更新目前最優(yōu)路徑的信息素。

Step8：NC++；根據(jù)迭代次數(shù)動態(tài)更新期望啟發(fā)式因子β值。

Step9：當NC＞NCmax即迭代次數(shù)超過設置的最大迭代次數(shù)時，輸出可行解。

3 算例分析

為了檢驗算法的有效性，本文從國際上公認的VRPLIB問題庫中選取了兩個（eil30和eil22）進行了算例檢驗，得到了比較滿意的結(jié)果如圖1、圖2所示。

圖1 Eil30仿真結(jié)果

圖2 Eil22仿真結(jié)果

Eil30容量限制為4 500，最優(yōu)配送路徑的長度為：553.0731。

路徑分別為：1->->27->->29->->28->->30->->26->->25->->2->->7->->5->->6->->1；

1->->3->->4->->23->->21->->20->->19->->24->->1；

1->->13->->12->->11->->16->->17->->14->->8->->18->->10->->9->->15->->1；

1->->22->->1。

Eil22容量限制為6 000，最優(yōu)配送路徑的長度為：400.4821。

路徑分別為：1->->14->->12->->9->->7->->5->->4->->1；

1->->2->->3->->6->->8->->10->->11->->1；

1->->13->->16->->19->->21->->18->->1；

1->->22->->20->->17->->15->->1。

4 結(jié) 論

在物流配送系統(tǒng)中，合理安排車輛路徑是減少浪費、提高經(jīng)濟效益的重要手段，然而由于問題本身的NP完全的性質(zhì)，精確求解非常困難，啟發(fā)式算法不失為一種可行的方向。本文通過蟻群算法在TSP中的應用，分析TSP與VRP的異同，給出求解VRP問題的蟻群算法，并對蟻群算法存在的過早收斂問題，通過隨機化初始位置、信息素設置上下限以及動態(tài)設置期望啟發(fā)式因子β值三種措施，對求解VRP問題的蟻群算法進行改進，最后由powerbuilder仿真實驗對算法進行實現(xiàn)并得出了比較滿意的結(jié)果。

[1]畢軍，付夢印，張宇河.一種改進的蟻群算法求解最短路徑問題[J].計算機工程與應用，2003,39(3):107-109.

[2]儲理才.基于MATLAB的遺傳算法設計及TSP問題求解[J].集美大學學報，2001(3):14-19.

[3]趙學峰.一種求解TSP的混合蟻群算法[J].西北師范大學學報，2003,39(4):31-34.

[4]劉云忠，宣慧玉.螞蟻算法在車輛路徑問題中的研究[J].信息與控制，2004,33(2):249-252.