車(chē)輛路徑問(wèn)題求解算法分析綜述目錄TOC\o"1-3"\h\u16918車(chē)輛路徑問(wèn)題求解算法分析綜述 1170631車(chē)輛路徑問(wèn)題 121521.1車(chē)輛路徑問(wèn)題的定義 1232201.2車(chē)輛路徑問(wèn)題的分類(lèi) 1192852車(chē)輛路徑問(wèn)題求解算法 231582.1算法概述 2297792.2遺傳算法 3205572.3模擬退火算法 51車(chē)輛路徑問(wèn)題1.1車(chē)輛路徑問(wèn)題的定義車(chē)輛路徑問(wèn)題（VRP）可以描述為：現(xiàn)有一定數(shù)量的配送中心（供應(yīng)點(diǎn)）和需求點(diǎn)，需要由運(yùn)輸車(chē)輛從配送中心向需求點(diǎn)運(yùn)送貨物。配送中心和需求點(diǎn)的位置、供需貨量等信息已知，需要合理安排行車(chē)路線(xiàn)，使車(chē)輛從配送中心出發(fā)有序訪(fǎng)問(wèn)指定的需求點(diǎn)，在一定約束條件下達(dá)到規(guī)定的目標(biāo)，以滿(mǎn)足客戶(hù)的要求。其中運(yùn)輸目標(biāo)一般包含成本最低、耗時(shí)最短、占用車(chē)輛數(shù)最少等。車(chē)輛路徑問(wèn)題的構(gòu)成要素有配送中心、需求點(diǎn)、運(yùn)輸車(chē)輛、路網(wǎng)狀況、約束條件、目標(biāo)函數(shù)等，各要素的簡(jiǎn)要含義如表2-4所示REF_Ref26017\r\h[8]。表2-4車(chē)輛路徑問(wèn)題構(gòu)成要素構(gòu)成要素簡(jiǎn)要含義配送中心是貨物的供應(yīng)點(diǎn)，也是運(yùn)輸車(chē)輛的出發(fā)點(diǎn)，數(shù)量上可有一個(gè)或多個(gè)。需求點(diǎn)是運(yùn)輸車(chē)輛根據(jù)路線(xiàn)安排依次遍歷的服務(wù)節(jié)點(diǎn)，各種需求類(lèi)型會(huì)形成相應(yīng)的約束條件。運(yùn)輸車(chē)輛是完成貨物從配送中心到需求點(diǎn)的主要運(yùn)輸工具，有載質(zhì)量、運(yùn)行成本等限制。運(yùn)載貨物是運(yùn)輸活動(dòng)的主要對(duì)象，不同貨物會(huì)導(dǎo)致運(yùn)輸要求不同。道路網(wǎng)絡(luò)一般以網(wǎng)絡(luò)圖的形式呈現(xiàn)，由配送中心、需求點(diǎn)和各點(diǎn)之間的路徑弧組成，弧的權(quán)重值可由配送時(shí)間、距離等確定。約束條件是求解問(wèn)題時(shí)必須滿(mǎn)足的條件，對(duì)變量有限制作用。目標(biāo)函數(shù)是進(jìn)行車(chē)輛路徑優(yōu)化的目標(biāo)，針對(duì)不同的目標(biāo)函數(shù)會(huì)設(shè)計(jì)不同的車(chē)輛路線(xiàn)安排，數(shù)量上可有一個(gè)或多個(gè)。1.2車(chē)輛路徑問(wèn)題的分類(lèi)車(chē)輛路徑問(wèn)題包含不同的構(gòu)成要素，各要素的屬性會(huì)形成不同約束條件，本文根據(jù)不同的約束條件對(duì)問(wèn)題進(jìn)行分類(lèi)如下：按照配送中心的數(shù)量可以分為單配送中心問(wèn)題和多配送中心問(wèn)題；按照需求點(diǎn)對(duì)運(yùn)送時(shí)間的要求可分為帶時(shí)間窗問(wèn)題和無(wú)時(shí)間窗問(wèn)題，前者可進(jìn)一步分為硬時(shí)間窗問(wèn)題和軟時(shí)間窗問(wèn)題。帶時(shí)間窗問(wèn)題指需求點(diǎn)要求貨物在一定時(shí)間范圍內(nèi)送達(dá)，其中硬時(shí)間窗表示若在規(guī)定的時(shí)間范圍以外送達(dá)，需求點(diǎn)拒絕接收；軟時(shí)間窗表示需求點(diǎn)可以接收規(guī)定時(shí)間以外送達(dá)的貨物，但是配送工作會(huì)受到一定費(fèi)用懲罰。無(wú)時(shí)間窗問(wèn)題指需求點(diǎn)對(duì)貨物的運(yùn)送時(shí)間沒(méi)有指定要求；按照線(xiàn)路上各點(diǎn)需求量相對(duì)于車(chē)輛載質(zhì)量的情況可分為滿(mǎn)載型問(wèn)題、非滿(mǎn)載型問(wèn)題。前者指需求點(diǎn)的貨物需求量大于或等于運(yùn)輸車(chē)輛的載質(zhì)量；后者指需求點(diǎn)的貨物需求量小于運(yùn)輸車(chē)輛的載質(zhì)量；按照運(yùn)輸車(chē)輛的統(tǒng)一性可分為單車(chē)型問(wèn)題和多車(chē)型問(wèn)題；根據(jù)運(yùn)輸任務(wù)的特征可分為單送貨型問(wèn)題、單取貨型問(wèn)題及取送混合問(wèn)題；根據(jù)運(yùn)輸車(chē)輛走行路徑的封閉性可分為車(chē)輛開(kāi)放問(wèn)題和車(chē)輛封閉問(wèn)題，前者表示車(chē)輛在完成指定配送任務(wù)后可以不返回出發(fā)點(diǎn)，即配送中心；后者規(guī)定車(chē)輛最后必須返回出發(fā)點(diǎn)。2車(chē)輛路徑問(wèn)題求解算法 2.1算法概述車(chē)輛路徑問(wèn)題一般會(huì)有多個(gè)約束條件疊加，這會(huì)增加問(wèn)題求解的復(fù)雜程度，所以此類(lèi)問(wèn)題屬于NP難題，針對(duì)車(chē)輛路徑問(wèn)題的求解算法從早期的精確算法逐漸發(fā)展到大規(guī)模的智能優(yōu)化算法。根據(jù)目前的研究成果，求解此類(lèi)問(wèn)題的方法總體上可分為精確算法和啟發(fā)式算法，具體如圖2-1所示REF_Ref25478\r\h[1]。圖2-1VRP問(wèn)題的常用求解算法精確算法精確算法可以在有限的計(jì)算步驟內(nèi)求出問(wèn)題的最優(yōu)解，但計(jì)算時(shí)間會(huì)隨著問(wèn)題規(guī)模的增加以指數(shù)速度上升，所以只適用于規(guī)模較小的問(wèn)題。由于實(shí)際問(wèn)題具有系統(tǒng)性與復(fù)雜性，尤其是針對(duì)車(chē)輛路徑問(wèn)題等NP難題而言，使用精確算法所產(chǎn)生的成本可能是無(wú)法接受甚至不現(xiàn)實(shí)的，不適合大多數(shù)的配送模型。傳統(tǒng)啟發(fā)式算法為了在可接受的計(jì)算成本范圍內(nèi)進(jìn)行復(fù)雜問(wèn)題的求解，學(xué)者引入了啟發(fā)式算法。此類(lèi)方法要求研究人員通過(guò)經(jīng)驗(yàn)總結(jié)、實(shí)驗(yàn)分析等方式對(duì)求解過(guò)程進(jìn)行引導(dǎo)，使得可以在較短時(shí)間內(nèi)找到可接受的滿(mǎn)意解。傳統(tǒng)啟發(fā)式算法需要針對(duì)具體問(wèn)題模型設(shè)計(jì)相應(yīng)的算法，通常用來(lái)解決組合優(yōu)化問(wèn)題，具有計(jì)算速度快、程序較為簡(jiǎn)單等優(yōu)點(diǎn)。但是由于搜索范圍的局限性，該方法無(wú)法保證求得最優(yōu)解。同時(shí)，傳統(tǒng)啟發(fā)式算法是通過(guò)局部搜索技術(shù)找到滿(mǎn)意解的，容易陷入局部最優(yōu)。亞啟發(fā)式算法亞啟發(fā)式算法又稱(chēng)元啟發(fā)式算法，通過(guò)全局搜索獲取滿(mǎn)意解，找到全局最優(yōu)解的概率更高。此類(lèi)算法是以自然界或人類(lèi)社會(huì)中的一些智能現(xiàn)象為基礎(chǔ)產(chǎn)生的，例如遺傳算法源于自然界中生物的遺傳、自然選擇等進(jìn)化規(guī)律，蟻群算法源于螞蟻在覓食過(guò)程中的群體行為，粒子群算法源于鳥(niǎo)群的捕食行為，模擬退火算法源于熱力學(xué)中固體的退火過(guò)程。2.2遺傳算法算法原理遺傳算法是一種可以實(shí)現(xiàn)全局優(yōu)化的自適應(yīng)概率搜索算法，主要啟于生物進(jìn)化中“適者生存”的規(guī)律，即自然環(huán)境中適應(yīng)能力越高的群體往往會(huì)產(chǎn)生更加優(yōu)秀的后代。通過(guò)模擬個(gè)體交叉和染色體基因突變等現(xiàn)象產(chǎn)生候選解，然后按照一定原則從中選擇較優(yōu)的個(gè)體，不斷重復(fù)上述操作，直至得到達(dá)到終止條件的滿(mǎn)意解。算法組成要素編碼：將優(yōu)化問(wèn)題的解轉(zhuǎn)變成位串的形式，便于解的表達(dá)和計(jì)算。主要方式有二進(jìn)制編碼、格雷編碼、序列編碼和大字符集編碼等。適應(yīng)度函數(shù)：是個(gè)體優(yōu)劣的唯一評(píng)價(jià)指標(biāo)，應(yīng)結(jié)合求解問(wèn)題的要求設(shè)定。該值越大說(shuō)明相應(yīng)個(gè)體的質(zhì)量越好，則被遺傳到下一代群體的概率更高。遺傳算子：包括選擇算子、交叉算子和變異算子。選擇算子是根據(jù)個(gè)體的適應(yīng)度，按照一定規(guī)則選擇性能優(yōu)良的父代，常用方法包括輪盤(pán)賭選擇、超比例選擇、種馬進(jìn)化算法、錦標(biāo)賽選擇等；交叉算子是將群體中挑選出的個(gè)體隨機(jī)搭配成對(duì)，通過(guò)互換個(gè)體間的部分染色體進(jìn)而產(chǎn)生新個(gè)體，常用的交叉方法包括單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉、洗牌交叉等；變異算子是按照變異概率更改個(gè)體數(shù)據(jù)串中的部分值，由此可減少種群規(guī)模較小導(dǎo)致的近親繁殖的情況。變異概率對(duì)算法性能的影響很大，該值過(guò)高會(huì)趨向于隨機(jī)搜索，過(guò)低會(huì)導(dǎo)致近親繁殖等問(wèn)題，難以找到滿(mǎn)意解?？刂茀?shù)：包括初始種群的個(gè)數(shù)、交叉概率、變異概率及遺傳操作的終止條件等。其中，終止條件主要包括：算法進(jìn)化代數(shù)達(dá)到預(yù)定值；遺傳搜索找到較為理想的目標(biāo)值；個(gè)體的適應(yīng)度函數(shù)值趨于穩(wěn)定，即種群難以繼續(xù)優(yōu)化。算法步驟遺傳算法步驟如圖2-2所示。圖2-2遺傳算法步驟算法優(yōu)點(diǎn)并行計(jì)算，全局搜索能力強(qiáng)。遺傳算法是對(duì)由多個(gè)體組成的群體進(jìn)行操作處理，即可以同時(shí)使用多個(gè)搜索點(diǎn)的信息，在一次搜索循環(huán)中可以覆蓋到較大規(guī)模的個(gè)體，在全局搜索方面有明顯的優(yōu)勢(shì)，適合復(fù)雜性問(wèn)題。適用范圍廣。遺傳算法通過(guò)適應(yīng)度函數(shù)即可得到進(jìn)一步的搜索方向和搜索范圍，而且對(duì)目標(biāo)函數(shù)的限制條件極少，因此該算法適合于目標(biāo)函數(shù)無(wú)法求導(dǎo)或?qū)?shù)不存在的優(yōu)化問(wèn)題及優(yōu)化組合問(wèn)題。具有很好的靈活性。遺傳算法的選擇、交叉、變異操作可通過(guò)參數(shù)設(shè)定進(jìn)行控制的，對(duì)操作算子進(jìn)行優(yōu)化，可以引導(dǎo)種群會(huì)產(chǎn)生更多優(yōu)良的個(gè)體。算法缺點(diǎn)容易陷入局部最優(yōu)，出現(xiàn)“早熟”現(xiàn)象。遺傳算法是通過(guò)交叉操作和變異操作產(chǎn)生新個(gè)體的，但在算法后期，優(yōu)勢(shì)個(gè)體可能占據(jù)大部分種群、交叉操作難以產(chǎn)生新個(gè)體；此時(shí)變異操作又受到變異概率的限制，則會(huì)出現(xiàn)過(guò)早收斂的情況，導(dǎo)致算法的最終解并非滿(mǎn)意解。無(wú)法保證每次都收斂到相同的解。由于遺傳算法會(huì)受到隨機(jī)概率的影響，所以無(wú)法保證算法解的良好收斂性。2.3模擬退火算法算法原理模擬退火算法源自于固體退火現(xiàn)象，首先在高溫下進(jìn)行粗略搜索，可以快速進(jìn)入“熱平衡”狀態(tài)，然后隨著溫度逐漸減低，各狀態(tài)出現(xiàn)概率的差距逐漸擴(kuò)大，搜索精度提高，使收斂到全局最小點(diǎn)。該算法的優(yōu)勢(shì)就是具有概率突跳特性，即能夠以一定概率接受差解，在得到局部最優(yōu)解后可以繼續(xù)尋優(yōu)，最終實(shí)現(xiàn)全局最優(yōu)。算法步驟該算法使用Metropolis準(zhǔn)則判斷是否接受新解，即當(dāng)新