改進的蟻群算法求解VRP問題

摘 要:為了使蟻群算法針對VRP問題解的搜索更加高效，將變異操作用于蟻群算法，給出了變異概率的設置，合理地改進可見度的計算及信息素更新方法，結合swap局部搜索，獲得了更加穩定的求解VRP問題的蟻群算法。實驗表明，該算法穩定有效。

關鍵詞:VRP; 蟻群算法; 變異; 局部搜索

中圖分類號:TP311 文獻標識碼:B

文章編號:1004-373X(2010)12-0075-03

Improved Ant Colony Algorithm for VRP

SANG Guo-zhen1， WANG Feng2， YANG Rui-chen2

(1.Weinan Teachers University， Weinan 714000， China; 2.Chengde Petroleum College， Chengde 067000， China)

Abstract:A mutation is applied to the ant colony algorithm and the mutation probability is given for solving the VRP problem more efficiently. The formula of visibility and pheromone updating method are set reasonably. Combined with swap local search， a more stable ant colony algorithm for VRP is gained. Experiments show that the algorithm is stable and effective.

Keywords:VRP; ant colony algorithm; mutation; local search

車輛路徑問題[1] (vehicle routing problem，VRP)是組合優化領域中著名的NP-hard問題之一，一般需使用啟發式搜索算法求解。蟻群算法是模擬螞蟻覓食原理的一種仿生學啟發算法，其應用于VRP問題的求解具有更為明顯的優勢，很多人對此進行了研究。

1 VRP問題

采用賦權有向圖G=(V，A，d)來表示配送路徑問題。其中，V={v0，v1，v2，…，vn}為點的集合;v0表示配送中心;vi(i=1，2，…，n)表示各顧客;A={(vi，vj)|vi，vj∈V，i≠j}為弧的集合;dij是與弧(vi，vj)相聯系，表示vi到vj的距離。對于顧客，vi給定了需求量qi(其中q0=0)，在容量及路徑長度的約束下，使用最少車輛完成配送任務，尋找最短配送路徑。假定配送中心最多可用K輛車對顧客點進行配送，每輛車載重量為Qk(k=1，2，…，K)，則設nk為第k輛車所配送的顧客點數(若nk=0表示未使用該車)，此車所走的路徑用集合Rk表示(Rk也可稱為第k條路徑)，其中的元素rki 表示顧客點在路徑k中的順序為i(不包含配送中心)。令rk0  = rk(nk  + 1)  = v0表示配送中心，有如下模型:

min Z=∑ K k=1 ∑ nk i=1 (drk(i-1)rki+drknkrk(nk+1))sign(nk-1) (1)

s.t.∑ nk i=1 qrki≤Qk，k=1，2，…，K (2)

0≤nk≤n，k=1，2，…，K (3)

∑ K k=1 nk=n (4)

Rk={rki|rki∈{1，2，…，n}，i=1，2，…，nk} (5)

Rk∩Rk2=Φ，k1≠k2 (6)

式中:sign(nk-1)=1，nk≥1

0，其他

模型中式(1)為目標函數;式(2)保證每條路徑上各個顧客點的總需求量不超過此路徑的配送車輛載重量;式(3)表明每條路徑上的顧客點數不超過總顧客點數;式(4)要求每個顧客點都得到配送服務;式(5)表示每條路徑上顧客點的組成及排列次序;式(6)限制每個顧客點的需求僅能由輛車完成。……