車輛路徑問題的算法綜述

周祺森

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

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

中圖分類號(hào)：U116.2 文獻(xiàn)標(biāo)志碼：A

0引言

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

1VRP綜述

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

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

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

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

2.1遺傳算法

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

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

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

2.2蟻群算法

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

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

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

2.3禁忌搜索算法

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

其基本思路如下：假設(shè)一群兔子要尋找珠穆朗瑪峰，它們?cè)趯ふ疫^程中遇到了泰山，它們就會(huì)留一只在泰山，其余兔子繼續(xù)尋找，最終找到珠穆朗瑪峰。當(dāng)兔子們?cè)俅螌ふ抑槟吕尸敺鍟r(shí)，因?yàn)橛幸恢煌米恿羰靥┥?，它們就?huì)避開泰山，這就是禁忌解。但是，當(dāng)它們搜尋的地方是平原時(shí)，泰山就成了不可避開的存在，這就是“特赦準(zhǔn)則”。

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

2.4粒子群算法

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

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

2.5模擬退火算法

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

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

3結(jié)束語

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