車輛路徑問題的算法綜述

周祺森

摘要：物流與國民經濟及生活的諸多領域密切相關，在物流成本方面，運輸費用占大約50%，比重最大。因此，物流成了企業創造利潤的重要途徑。要降低配送成本，縮短并優化車輛路徑是關鍵所在。然而，車輛路徑問題（vRP）是物流領域中的一個強NP問題，國內外學者近年來不斷提出多種車輛路徑優化問題及求解方法以解決愈加復雜的問題。為進一步理清國內外研究現狀，就VRP進行總結分析，然后對車輛路徑求解方法進行了介紹，特別地對元啟發式算法進行了較為詳細的綜述。

關鍵詞：VRP;元啟發式算法;文獻綜述

中圖分類號：U116.2 文獻標志碼：A

0引言

隨著電子商務的快速發展，物流業作為連接生產者與消費者的橋梁，發揮著越來越重要的作用。然而，物流在給人們生活帶來極大便利的同時，也給相關企業帶來了逐年增高的物流費用。伴隨著競爭日益白熱化的商業環境，降低物流成本成了物流企業存活和發展所必須重視的環節。在降低物流成本方面，最關鍵的途徑之一是解決車輛路徑問題（vehicle routing prob-lem，VRP）。

1VRP綜述

車輛路徑問題于1959年由丹齊格和拉姆澤提出，最早源于旅行商問題（TsP）的研究。TsP可以簡單理解為在給定的m個城市里，從一個城市出發，經過每個城市，并且每個城市只經過一次，最后回到出發點，找出最短回程路徑問題。

在TsP的研究基礎上，出現了能力約束車輛路徑問題（CVRP），CVRP相對于TsP的“一對多”，可以理解為“多對多”，如圖1所示。

2VRP元啟發式算法綜述

基于車輛路徑模型，其求解算法基本可分為精確式算法、啟發式算法、元啟發式算法和機器學習算法，如圖2所示。

2.1遺傳算法

遺傳算法是由J.Holland教授在1975年首先提出，它借鑒了生物進化論中的遺傳、雜交、變異以及自然選擇等現象，利用計算機模擬生物進化的過程，根據優勝劣汰、適者生存的自然法則規定搜索方向，以此迭代，最終獲得具有最大適應度個體，該個體就作為最優解輸出。

遺傳算法的優點是求解結果穩定，計算效率高，但是存在局部搜索能力很弱，在接近最優解后，達到最優解還需要一段時間的缺陷。另外，如果適應度函數選擇不當，遺傳算法常常收斂于局部最優，無法實現全局最優。

針對遺傳算法的缺陷，國內外學者提出了很多優化方法。比如H.Bersini和G.Seront提出將遺傳算法與單一方法結合起來，獲得除母體以外的新個體，通過計算發現，三交叉算子的性能較原先兩母體有了較大提升。

2.2蟻群算法

蟻群算法是由Dorigo和Maniezzo等人提出的仿生算法，他們發現單只或少量的螞蟻在尋找食物路徑時無特別技巧，但是當蟻群數量上升到一定程度時，他們卻可以找到最優路徑，甚至在認為改變環境后，他們仍能找到最優路徑，如圖3所示。

經過研究發現，螞蟻在行進過程中會釋放一定量的信息素，周圍的螞蟻在感知到該信息素時會優先選擇該路徑，當選擇該路徑的螞蟻越來越多時，即單位時間內走過該路徑的螞蟻越來越多，則該路徑上信息素的濃度也越來越高，就會有越來越多的螞蟻選擇該路徑，形成正反饋，從而實現路徑最優化。蟻群算法最大優點是對最優解具有強大的搜索能力，此外還有原理簡單，具有并行性和魯棒性，易于實現等優點。缺點是需要較長的搜索時間，計算效率低下，當應用于求解靜態車輛路徑問題時，求解耗時的長短對實際應用幾乎不產生影響，但是，當應用于動態車輛路徑時，求解耗時成了實用性的重要指標。此外，參數的設置（如信息素揮發因子）對結果有很大的影響，設置不當會使運行陷于局部最優，出現停滯現象，無法搜索最優解。

針對蟻群算法的這個缺陷，常見的優化策略是將遺傳算法的遺傳、雜交和變異等遺傳算子引入蟻群算法，使得在滿足迭代次數的情況下，仍能保持較快的計算效率，同時每次迭代后局部最優解也能逐步逼近全局最優解。除此之外，還能在每次搜索的過程中，用鄰域算法對每只螞蟻求出的最優解進行二次搜索，比如在迭代過程中發現選擇同一條路徑的螞蟻數量超過了螞蟻總數的1/4，則可以通過降低該路徑上的信息素濃度，避免信息素濃度對算法的極端影響，從而提高原來最優解的質量。

2.3禁忌搜索算法

TS，也被稱為爬山啟發式算法，不同于蟻群算法，TS通過模擬人的記憶和經驗，通過禁忌表記憶之前進行的優化過程，禁忌某些解，以避免走回頭路和剔除某些極端解，從而避免陷入局部最優解。

其基本思路如下：假設一群兔子要尋找珠穆朗瑪峰，它們在尋找過程中遇到了泰山，它們就會留一只在泰山，其余兔子繼續尋找，最終找到珠穆朗瑪峰。當兔子們再次尋找珠穆朗瑪峰時，因為有一只兔子留守泰山，它們就會避開泰山，這就是禁忌解。但是，當它們搜尋的地方是平原時，泰山就成了不可避開的存在，這就是“特赦準則”。

然而，當禁忌表范圍過小時，容易陷入循環搜索;當禁忌表范圍過大時，容易陷入局部最優化，所以合理確定禁忌表范圍是使用Ts的關鍵。通常可以采用鄰域變換規則（neighborhoods changed rules，NCR）來決定禁忌搜索算法的禁忌解范圍和解的質量，或者將遺傳算法和禁忌搜索算法混合，通過遺傳算法的交叉算子擴大搜索的范圍。

2.4粒子群算法

粒子群算法是由Kenndv和Eberhart提出的新型進化算法，不同于遺傳算法，粒子群算法沒有交叉、變異算子，以及復雜多樣的編碼方式，他是通過個體位置和速度信息的不斷更新，通過個體之間的相互聯系和影響在解空間中不斷進行搜索，最終求得全局最優解。該算法受到了鳥群捕食的啟法，假設一群鳥在隨機搜索食物，每只鳥都為一個粒子，它們與食物的距離已知，則搜尋食物最優的策略就是搜尋離食物最近的鳥的周圍區域，這只鳥就是當前最優解，其他鳥通過追尋它來找尋食物，以此獲得全局最優解。

該算法的優點是結構構造簡單、需要調節的參數較少、涉及的專業知識少、容易實現，所以常被國內外大量研究人員應用于許多實際問題中。但是，粒子群算法解的可行性處理不好，其結果往往無法收斂或者結果為空集。常見的優化方法有：一是采用多層Pareto排序機制來產生優良粒子，利用這些優良的粒子來決定其他粒子的搜索范圍和方向，從而提高搜索效率;二是通過混合遺傳算法，引入自然選擇機制，基本思路為：首先計算粒子的適應度值，并由該指標對粒子進行排序。然后由排序的結果，選出原來粒子個體的最優位置信息，再用粒子群中最好的一半粒子替換粒子群中最差的另一半粒子;三是通過混合模擬退火算法，引入模擬退火機制，基本的思路是隨著迭代次數的增加，溫度會逐漸下降，接受不良解的概率也會逐漸下降，從而改良粒子群算法收斂性差的缺陷，并且也在很大程度上提高了解的精度。

2.5模擬退火算法

模擬退火算法最早是由N.Metropolis等人基于固體退火原理提出，其基本思路為，當固體加熱至充分高的溫度，隨著溫度的升高固體內部的粒子變為無序狀，內能增大，再讓其徐徐冷卻，在冷卻過程中粒子重新變得有序，這樣就令每個溫度都能達到了平衡態，最后在常溫時達到基態，內能減為最小。在1983年，s.Kirk-patrick等人基于Monte-Carlo迭代求解策略將退火思想引入到組合優化領域，也就是在“產生新解一計算新解—計算新解與原解的差值—是否接受”的重復迭代過程中，接受部分不好的解，這樣就可以從整體上考慮，求出最優解，跳出局部最優的陷阱。所以，模擬退火算法的優點是全局搜索能力較強、原理簡單、運算效率高、受到初始條件的約束較少、具有并行性等。缺點是求解精度低，尤其是當降溫系數過低時，而當降溫系數過大時，求解精度高但求解效率低，算法運行時間較長。

針對其求解精度低的缺點，國內外專家常采用求解精度高的蟻群算法與其混合。組合算法的思想是先使用模擬退火算法獲得相對最優解，并將最優解作為蟻群的初始信息素，設置蟻群算法參數，然后使用蟻群算法找出精確解。

3結束語

元啟發式算法不借助于某種問題的特有條件，從而能夠運用于更廣泛的方面。本論述主要選取了元啟發式算法中4種經典的算法，對它們的基本含義、優點以及改進方案等進行了概述。希望能給研究學者提供參考，給物流行業人員提供知識框架和指導方法。