基于改進蟻群算法的CVRP問題*

張海軍 ，徐廷學 ，逯 程 ，韓 玉

（1.海軍航空大學，山東 煙臺 264001；2.海軍航空大學青島校區，山東 青島 266041）

0 引言

配送車輛的路徑問題（Vehicle Routing Problem，VRP）是研究物流配送的關鍵，VRP一直是物流研究領域中的一個具有重要理論意義和現實意義的問題［1-2］。因此，在物流保障過程中，需要制定合理有效的配送路徑，選擇省時省力的方法，在完成保障任務的前提下，盡最大努力滿足客戶對配送的需求。

配送車輛的路徑問題（Vehicle Routing Problem，VRP）是 Dantzig 和 Ramser［3］在 1959 年提出來的。所謂VRP，一般指的是：調用多輛車輛，從車場出發，對客戶組織適當的行車路線，有序地訪問所有客戶并且只訪問一次，在滿足所有設定的約束條件下，力爭實現所設定的目標。帶容量約束的車輛路徑問題（CVRP）是車輛路徑問題（VRP）中的基本問題之一，廣泛應用于資源配置和物流運輸等方面。

求解CVRP的算法大致可以分為精確算法和啟發式算法兩類［4-5］。精確算法（Accurately Arithmetic）在求解規模較小的路徑優化問題時能夠在可承受的空間與時間消耗下得到精確解。但是配送路徑優化問題屬于NP問題，實際求解過程中問題的規模較大，使用精確算法所消耗的空間和時間成本都是比較大的。而啟發式算法（Heuristics）不管是求解小規模的問題還是大規模的問題，都能夠在一定的范圍和較短的時間內給出滿意解或最優解。因此，目前相關領域的專家以及研究人員對于求解算法的主要研究方向是啟發式算法，特別是對現代啟發式算法的研究。蟻群算法作為現代啟發式算法之一，自從被提出之后就受到了廣泛的關注，該算法具有正反饋性、并行性和魯棒性等優點，在解決任務分配、路徑優化等問題時表現出了良好的性能，但同時蟻群算法也存在一定的缺陷，如在解決大規模的問題時，會出現運算時間長、收斂速度慢、容易陷入局部最優解等問題［6］。本文在基本的蟻群算法基礎上進行合理改進，提高了算法的性能，使算法的運算結果更加準確。首先，制定轉移規則，更加科學地初始化車輛的位置，使得車輛有更大概率地走出最佳的路徑；然后，在搜索的過程中與禁忌搜索算法結合，添加新的參數負信息素來記憶已經訪問過的客戶；同時，使用局部信息素更新和全局信息素更新相結合的信息素更新方式，并且，全局信息素更新添加了動態更新的新模式；最后，使用2-opt搜索［7］對結果進行進一步的探索，擴大搜索的范圍，增加了得到最優解的概率。通過仿真實驗，用不同的算法對已知案例進行仿真，結果顯示本文算法相對于其他算法，無論是結果的準確性還是運算時間的長短都表現出了更好的性能。

1 問題描述及數學建模

CVRP是從同一車場出發的多輛車輛訪問多個客戶進行運送貨物的問題。已知出發車場的位置以及需要訪問的客戶的位置，客戶的數量以及需求數量，車輛的數量以及負載數量，對客戶組織適當的行車路線，有序地訪問所有客戶并且只訪問一次，在滿足所有設定的約束條件下，力爭實現所設定的目標（車輛所走的路徑最短或者花費最少）。

將現實問題轉化為數學模型，可以將CVRP描述為m輛車從車場0出發訪問n位客戶進行運送貨物的問題。設di為客戶i的需求數量，cij為車輛從客戶i到客戶j的運輸花費，bk為車輛k的負載數量，而

求解CVRP是為了使車輛走出的總的路徑最短［8-9］，從而令運輸的成本J最小，即

且應滿足以下約束條件：

式（3）表示所有車輛都從同一個車場出發，完成所擔負的任務之后全部返回車場，每一輛車走出的路徑都形成一個哈密爾頓巡回；式（4）和式（5）表示車輛要對所有客戶進行服務，并且只能服務一次；式（6）表示每輛車服務客戶時，自身的負載量不能低于被服務客戶的總的需求量。

2 算法設計

2.1 蟻群算法求解CVRP

使用蟻群算法對CVRP進行求解時，螞蟻會在各路徑上產生信息素，信息素ij表示車輛k在對客戶i服務完成之后，下一個客戶j對車輛k產生的吸引程度。當車輛的負載量能夠滿足客戶的需求時，車輛按照設定好的轉移規則來選定客戶。在選好所有客戶形成回路之后，對各路徑上的信息素實行更新策略，進而實現一次迭代。在迭代達到最大次數時，可以獲得一個Pareto解集。跟其他的啟發式算法相比，蟻群算法具有更高的機能，但在對CVRP的求解過程中還是會有一些不可避免的缺陷。

2.1.1 選取初始客戶過程中的局限

在CVRP中，因為車輛都有一定的負載，訪問多個客戶要滿足客戶需求，而每輛車在訪問客戶時都會有貨物量限制和訪問先后的問題，所以求解CVRP受到選取初始客戶的極大影響。運用蟻群算法求解CVRP時，初始化螞蟻位置的方式有兩種：1）全部放置方式。將所有螞蟻全部放置于每個節點，這樣搜索的范圍會很大，更容易得到全局最優的解，但同時也將造成大量時間的消耗，在處理較大規模的CVRP時，會令問題更加復雜。2）隨機放置方式。將部分螞蟻隨機放置到部分節點，這樣做可以節省時間，降低問題的復雜程度，但是也容易造成得到的結果只是局部最優的，令每次迭代得到的Pareto解差距過大。

2.1.2 信息素更新過程的局限性。

隨著算法的不斷運算，尋找著最優路徑，而信息素在路徑上不停地累積，當前已尋找到的最優路徑上的信息素越來越多，這或許會造成以下的不良后果：1）在當前已尋找到的最優路徑上的信息素過多，造成算法的停滯。2）即便尋找到新的最優路徑，這條路徑上的信息素也遠遠沒有之前得到的最優路徑上的信息素多，幾次迭代之后，這種現象也可能沒有得到緩解?？傊?，在基本蟻群算法中，原有的信息素更新方式會導致信息素的分布不能很好地體現當前最優路徑的變化，這會對算法的求解過程造成很大的影響。

2.2 算法改進

針對在求解CVRP時蟻群算法存在的缺陷，本文改進蟻群算法將提高其求解CVRP的性能。

2.2.1 轉移概率的改進

為了降低算法的復雜程度，同時加強算法的精確程度，在算法選擇初始客戶的過程中，本文將蟻群算法和禁忌搜索進行融合，修正轉移概率，以改進蟻群算法。將禁忌搜索融入蟻群算法主要是利用禁忌搜索長久的記憶能力來加強蟻群算法搜索的開拓性［10-12］。本文結合禁忌搜索記憶之前訪問過的節點，加入了負信息素的概念：

當螞蟻k處于節點i的位置時，根據以下規則選擇下一節點：

2.2.2 信息素更新方式

針對蟻群算法在信息素更新過程中存在的問題，本文使用局部信息素更新和全局信息素更新相結合的信息素更新方式，并且，全局信息素更新添加了動態更新的新模式。

1）局部更新。在構建最優路徑的過程中，螞蟻每經過邊（i，j）都會依照下面的信息素更新公式來更新這條邊上的信息素：

其中，ρ1表示局部更新的揮發系數，表示信息素的初始值，是一個較小的正常量，可以設表示節點數，L表示生成的路徑長度。引入信息素局部更新的目的，是為了使螞蟻在經過邊（i，j）時，會揮發這條邊上一部分的信息素，降低其他的螞蟻同樣選擇這條邊的幾率，可以更多地去探索其他的邊，從而令算法的開拓性大大加強。

2）全局動態更新。當迭代一次完成后，按下式對此次迭代得到的最優路徑上的信息素實行全局更新：

式（11）和式（12）可以依照每次迭代得到的最優路徑的情況，對當前迭代所得的最優路徑上的全局信息素進行動態調整。在x次迭代后，得到了一個最優路徑，相比x-1次迭代，這條路徑要短，L2和L1的差值就為正，說明當前迭代找到的最優路徑比之前尋找到的要好，但此時該路徑上的信息素濃度并不高，而根據式（12），L2和L1的差值越大，就會越大，在之后的迭代中，信息素濃度的積累就會越快；L2和L1的差值越小就會越小，在之后的迭代中，信息素濃度的積累就會越慢；如果在x次迭代后，得到的最優路徑比L2要長，L2和L1的差值就為負，說明當前迭代找到的最優路徑不如之前尋找到的好，而根據式（12），L2和L1的差值越大，就會越大，在之后的迭代中，信息素濃度就會加快揮發；L2和L1的差值越小，就會越小，在之后的迭代中，信息素濃度揮發的就會越慢。這種動態調整是為了讓算法能夠及時修正迭代得到的結果，引導算法可以更快地找到最優的路徑。

2.2.3 局部搜索策略

為了能夠增加算法的開拓性，本文在所有車輛對路徑選擇完成之后選用2-opt搜索作為局部搜索的策略，而2-opt搜索只用于一輛車所選擇的路徑之中。

2.3 算法步驟

根據以上描述的改進策略，改進后的算法步驟如下：

2）初始化車輛的位置。車輛按照式（8）選擇客戶，將所選擇的客戶添加到中，并更新的值。

3）路徑選擇。在滿足車輛負載條件的前提下，車輛按照式（9）進行客戶的選擇；否則車輛返回車場。將所選擇的客戶或車場添加到中，更的值。

4）信息素的局部更新。每當車輛作出一次選擇，便根據式（10）對剛剛走過的路徑（i，j）進行信息素的局部更新。

5）2-opt局部搜索。當所有車輛服務客戶完成之后，尋找路徑完畢時，對每輛車所尋找到的路徑進行2-opt搜索，并更新和；否則返回 3）。

3 仿真實例

在車輛路由公共數據集［13］中選擇標準算例進行測試，使用Matlab進行編程，并在CPU為Intel（R）Core（TM）i5-4460 CPU@3.20 GHz 3.20 GHz，內存 8G的計算機上運行。實驗參數設置為：ρ1=0.1，ρ=0.1，α=1，β=2，γ=1，e=15～30，r0=0.8～0.95，NC=40。

表1 求解各案例結果

表1顯示出運用本文算法求解選擇出來的這部分算例的結果，求解每個算例都運行10次。這里設B為數據集中目前已知的算例最優解，R為運用本文算法求解該案例得到的最優解，P為運用本文算法求解案例得到的最優解對比數據集中已知最優解B的偏移率。從表1可以看出，運用給本文算法求解從數據集中隨機抽選的12個算例中，有7個案例的求解結果和數據集中已知最優解相同，而在剩下5個結果有所偏差的案例中，案例N200K17的偏移率最大，但是偏移率僅為2.67%。以上說明本文算法的性能是值得肯定的。

此外，從數據集中選擇5個案例，運用本文算法與其他算法分別對案例進行求解，得出結果進行比較，表2顯示了對比的結果。從表2可以看出，本文算法求解案例得到的最優解對比數據集中已知最優解的偏移率平均值為0.88%，與其他3種算法相比，僅高于HGA 0.03%。運用給本文算法求解從數據集中隨機抽選的5個算例，有2個案例的求解結果和數據集中已知最優解相同。在求解運算的消耗時間方面，運用本文算法求解N51K5、N76K10所消耗的時間比SA要多一些，而求解另外3個案例的時間都是最短的，而且求解這5個案例所消耗的總時間最短，平均消耗時間也最短。

選擇的5個案例，服務的車輛和被服務的客戶數量都比較多，問題的規模都很大，在這幾個大規模問題中，相對于其他3種算法，本文算法無論是運算結果還是花費的時間都體現出了更佳的性能，而且問題的規模越大，本文算法體現出的性能越好。

表2 各算法對案例求解對比

4 結論

本文首先對VRP問題的理論進行了研究，引出CVRP問題，并且對其進行了數學模型的建立，然后在基本蟻群算法的基礎上，改進算法使其能更好地對所建模型進行求解，最后從數據集中抽取案例，運用改進后的算法進行求解，并與其他的算法進行比較，得出本文算法無論是運算結果還是花費的時間都體現出了更佳的性能和結論。