車輛路徑問題的算法綜述

周祺森

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

關(guān)鍵詞：VRP;元啟發(fā)式算法;文獻綜述

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

0引言

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

1VRP綜述

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

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

2VRP元啟發(fā)式算法綜述

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

2.1遺傳算法

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

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

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

2.2蟻群算法

蟻群算法是由Dorigo和Maniezzo等人提出的仿生算法，他們發(fā)現(xiàn)單只或少量的螞蟻在尋找食物路徑時無特別技巧，但是當蟻群數(shù)量上升到一定程度時，他們卻可以找到最優(yōu)路徑，甚至在認為改變環(huán)境后，他們?nèi)阅苷业阶顑?yōu)路徑，如圖3所示。

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

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

2.3禁忌搜索算法

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

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

然而，當禁忌表范圍過小時，容易陷入循環(huán)搜索;當禁忌表范圍過大時，容易陷入局部最優(yōu)化，所以合理確定禁忌表范圍是使用Ts的關(guān)鍵。通?？梢圆捎绵徲蜃儞Q規(guī)則（neighborhoods changed rules，NCR）來決定禁忌搜索算法的禁忌解范圍和解的質(zhì)量，或者將遺傳算法和禁忌搜索算法混合，通過遺傳算法的交叉算子擴大搜索的范圍。

2.4粒子群算法

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

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

2.5模擬退火算法

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

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

3結(jié)束語

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