周祺森
摘要:物流與國(guó)民經(jīng)濟(jì)及生活的諸多領(lǐng)域密切相關(guān),在物流成本方面,運(yùn)輸費(fèi)用占大約50%,比重最大。因此,物流成了企業(yè)創(chuàng)造利潤(rùn)的重要途徑。要降低配送成本,縮短并優(yōu)化車輛路徑是關(guān)鍵所在。然而,車輛路徑問題(vRP)是物流領(lǐng)域中的一個(gè)強(qiáng)NP問題,國(guó)內(nèi)外學(xué)者近年來不斷提出多種車輛路徑優(yōu)化問題及求解方法以解決愈加復(fù)雜的問題。為進(jìn)一步理清國(guó)內(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ì)遺傳算法的缺陷,國(guó)內(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)是需要較長(zhǎng)的搜索時(shí)間,計(jì)算效率低下,當(dāng)應(yīng)用于求解靜態(tài)車輛路徑問題時(shí),求解耗時(shí)的長(zhǎng)短對(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)鍵。通常可以采用鄰域變換規(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),所以常被國(guó)內(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í)間較長(zhǎng)。
針對(duì)其求解精度低的缺點(diǎn),國(guó)內(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)方法。