車輛路徑問題

車輛路徑問題模型及算法研究摘要4：輛路徑問題(VehicleRoutingProblem-VRP)是組合優(yōu)化和運(yùn)咎學(xué)領(lǐng)域研究的熱點(diǎn)問題Z—，其耍研究滴扯約束條件的最優(yōu)車輛便川方案以及繪優(yōu)的車輛路徑方案。羞于基本午輛粘徑問遊的框架.研究滿足生產(chǎn)經(jīng)會(huì)和運(yùn)作需要的各種車輛路徑問題，并構(gòu)建八有高質(zhì)吊和高碼棒性(roubustness)的問題求解算法對(duì)J：提高工產(chǎn)經(jīng)背管理水平和降低運(yùn)作成木具有重要的理論意義和現(xiàn)實(shí)價(jià)值。木文以車輛路徑問題為研究對(duì)盤，綜合運(yùn)用組合優(yōu)化和現(xiàn)代啟發(fā)式算法等工具，對(duì)兒類亜要的車輛路徑問題模世及氏優(yōu)化算法進(jìn)行了系統(tǒng)的研究，卞更研究工作及成果總結(jié)如?綜述了車輛路徑問題在定義車輛路徑問題分類和擴(kuò)展標(biāo)準(zhǔn)的堪礎(chǔ)上，給岀了乍輛州徑問題的研究綜述。尿于不同的分類標(biāo)準(zhǔn)，汗先討論了主要的標(biāo)準(zhǔn)乍輛路徑問題擴(kuò)展問題。在此械礎(chǔ)上詳細(xì)地綜述了求解標(biāo)旌牟納路徑問題的現(xiàn)代啟發(fā)式算法，系統(tǒng)地描述了并種知法的實(shí)現(xiàn)機(jī)理以及#種笄法的性能比較結(jié)果。2?綜述了求解組仟優(yōu)化問題的現(xiàn)代啟發(fā)式殊法在給出組介優(yōu)化問題和計(jì)算復(fù)雜性定義的基礎(chǔ)上，綜述了求解以雜組合優(yōu)化問題的各種現(xiàn)代門發(fā)式算法。研究了開放式車輛路徑問趣通過(guò)松弛標(biāo)準(zhǔn)午輛路栓問題中車輛路線為哈密爾頓巡冋(Hamiltonianlour)的假設(shè)，研究了乍輛路線為哈密爾頓路徑(Hamiltonianpath)的開放式乍輛路徑問題。該問題中卞輛在服務(wù)完故肓一個(gè)顧客點(diǎn)后不礙要冋到牟場(chǎng)，若要求冋到車場(chǎng)，則必須沿原路返冋。在斤先給出問題數(shù)學(xué)模型的基礎(chǔ)上，捉出了求解開放式乍輛路徑問題的蚊群優(yōu)化并法。該舜法王體是一個(gè)在超立方橢架下執(zhí)廳螞蟻泵統(tǒng)，算法混合了祭總搜索57法作為局部?jī)?yōu)化算法，同時(shí)集成了?個(gè)后優(yōu)億過(guò)程來(lái)進(jìn)一步優(yōu)化放優(yōu)解。肚丁卑準(zhǔn)測(cè)試問題.系統(tǒng)地研究了笄法性能。同尖它算法的性能比較結(jié)果農(nóng)明本文提出的蟻群優(yōu)化算法足有效的求解開放式乍輔路徑問題的方法。研究了帯時(shí)間窗和帶時(shí)間期限開放式乍輛路徑問題通過(guò)引入時(shí)何約束.研究了兩類新的滿足時(shí)效性要求的開放式車輛路徑問題一帶時(shí)間窗和帶時(shí)間期限開放式乍輛路徑問題。首先構(gòu)建了兩類問題的數(shù)學(xué)模型，同時(shí)提出了求解兩上海交通人學(xué)冊(cè)十學(xué)位論文類制題的基于禁忌捜索的迭代局部搜索算法.該尊法集成了不同的解接曼標(biāo)準(zhǔn)以及-個(gè)基J??閾値接受的忘優(yōu)化過(guò)程。呈『僦機(jī)產(chǎn)生的測(cè)試問題的實(shí)驗(yàn)結(jié)果衷明：基于禁忌搜索的迭代局部搜索算法町以有效地求解帶時(shí)間陽(yáng)和帶時(shí)間期限開放式車輛路徑問題。研究了帶時(shí)間窗和葩機(jī)旅行?時(shí)間車輛路徑問題通過(guò)對(duì)標(biāo)準(zhǔn)車輛路徑問題的拓展，引入新的邊約束條件：時(shí)間修.碗機(jī)旅行時(shí)間和JM務(wù)時(shí)間，研究了-類新的隨機(jī)乍輛路徑問題一帶時(shí)間謝和Ki機(jī)旅行時(shí)間乍輛路徑問題V根據(jù)不同的優(yōu)化標(biāo)準(zhǔn)，分別構(gòu)建了何題的機(jī)會(huì)約東規(guī)劃模型以及帶修正葩機(jī)規(guī)劃模熨。機(jī)會(huì)約束規(guī)劃模型是在冏機(jī)約束以?定的玄信水平成立的條件卜?赧小化運(yùn)輸費(fèi)川。帶修正的Ki機(jī)規(guī)劃模型是一個(gè)兩階段優(yōu)化問題，兀確定笫一階段的路線集以放小化第二階段（隨機(jī)變駅實(shí)現(xiàn)厲）的期望運(yùn)輸M用。鑒于問題的隨機(jī)特件，為了仃效求解該問逢提出了某于隨機(jī)模擬的禁忌搜索算法。同時(shí)棊于隨機(jī)產(chǎn)生的測(cè)試問題通過(guò)實(shí)驗(yàn)檢驗(yàn)了算法有效性。6?研究了固定車輛數(shù)異型車輛路徑問題加午輛路徑問題經(jīng)典文獻(xiàn)嘰 般均假設(shè)車輛同質(zhì)目.車輛數(shù)無(wú)限。然而在實(shí)際運(yùn)作中，車輛集一般是由具刃不同屬性（裝戦能力、固定成木以及址位公里町變費(fèi)用）的午軻組成，且受運(yùn)作成木的約束車輛數(shù)也是固定的。通過(guò)對(duì)車輛同質(zhì)及車輛數(shù)無(wú)凰的假設(shè)條件的放松，研究了固定乍輛數(shù)的牙型乍輛路徑問題。九廿先給出問題數(shù)學(xué)模型的基礎(chǔ)I:,提出了求鯽該問題的多起點(diǎn)自適應(yīng)id憶規(guī)劃算法?堆于文獻(xiàn)中的甚準(zhǔn)測(cè)試問題，系統(tǒng)地研究了算法在不同多樣化策略F的性能。同文獻(xiàn)中其它算法的比較結(jié)果衣明：捉出的多起點(diǎn)自適應(yīng)記憶規(guī)劃邛法是較好的求解同定午輛數(shù)異型午輛路徑問題的算法，對(duì)丁其中五個(gè)測(cè)試問題，并法發(fā)現(xiàn)了新的垠優(yōu)解。7.研究了年輛路徑問題的應(yīng)用問題以城市H常報(bào)汕配送問題為例，進(jìn)行了午輛路徑問邀的應(yīng)用研究。星于報(bào)品配送的實(shí)際數(shù)據(jù)，運(yùn)用木文研究的兒類車輛路徑問題的檻架，研究了不同類旳的最優(yōu)報(bào)品配送加輛辟?gòu)椒桨傅闹贫▎栴}。執(zhí)行木文提出的優(yōu)化算法，給出了不同爻熨的報(bào)品配送的擬優(yōu)午輛路徑方案。通過(guò)實(shí)驗(yàn)驗(yàn)證了論文提出的牟輛路徑問題優(yōu)化算法的育效性，實(shí)齡結(jié)果表明論文提出的算法可以用于生產(chǎn)管理中最優(yōu)4輛路線方案的制定。本文創(chuàng)新性研究成果及貢獻(xiàn)主耍包括以下幾方面：I.松弛了標(biāo)準(zhǔn)vr沖乍輛路線為哈密爾頓巡冋的假設(shè)，研究了乍輛路線為哈密爾-III--III-領(lǐng)路徑的丿F放式午輛路徑何題。構(gòu)建了求解問題的蟻橢優(yōu)化算法，該算法是?個(gè)集成了后優(yōu)化過(guò)用的在超立方梃架卜?執(zhí)行?的系統(tǒng)。同文獻(xiàn)中英它算法性能的比較結(jié)果證明本文提出的蟻群優(yōu)化飪法是有效的求解開放式車輛路徑問題的方法，算法改進(jìn)了文獻(xiàn)中其它算法發(fā)現(xiàn)的最優(yōu)解'引入時(shí)間約束，研究了兩類新的滿足時(shí)效性耍求的車輛路徑問題一帶時(shí)間囪和帶時(shí)何期限開放式車輛路徑問題。提出了求解上述兩類問趣的迭代局部搜索算法，并基于隨機(jī)產(chǎn)生的測(cè)試問系統(tǒng)研究了算法的求解性能?3?引入時(shí)間陽(yáng).碗機(jī)旅行時(shí)間和眼務(wù)時(shí)間約束，研究了帶時(shí)間窗和甌機(jī)旅行時(shí)何車輛路徑問題.根據(jù)不同的優(yōu)化杯準(zhǔn)，分別構(gòu)建了問題的機(jī)會(huì)約束規(guī)劃?？找约皫拚齅機(jī)規(guī)劃模型。提出了基于同機(jī)模擬的禁忌搜索算法，基于隨機(jī)機(jī)產(chǎn)生的測(cè)試問題的實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。4.通過(guò)松弛標(biāo)準(zhǔn)VRP中車輛同質(zhì)及車輛數(shù)無(wú)限的假設(shè)，研究f固定車輛數(shù)異型車輛路從問題。提岀了求解何題的多起點(diǎn)白適應(yīng)記憶規(guī)劃算法，同文獻(xiàn)中其它算法的比較結(jié)果表明：多起點(diǎn)自適應(yīng)記憶規(guī)劃算法是較好的求解同定乍輛數(shù)界型車輛路徑問題的算法，對(duì)于任個(gè)基準(zhǔn)測(cè)試問題，算法發(fā)現(xiàn)了新的址優(yōu)解。木文綜合運(yùn)用運(yùn)寫學(xué)和組合優(yōu)化的理論與方法，對(duì)幾類乍輛路徑問題模型及算法進(jìn)行了系統(tǒng)的研究?木文的研究工作拓展了千輸路徑問迦以及組合優(yōu)化的研究空間，豐富了運(yùn)篦學(xué)和管理科學(xué)的理論研究成果?同時(shí)為運(yùn)輪、物流和配送管理等領(lǐng)域中最優(yōu)弔輛捋徑方案的規(guī)劃與設(shè)計(jì)提供了借鑒和參考。關(guān)鍵詞：車輛將徑問題：優(yōu)化模世：現(xiàn)代啟發(fā)式算法VIIIVIII目錄TOC\o"1-5"\h\z\o"CurrentDocument"摘要 1ABSTRACT IV插圖目錄 XII表格目錄 XIII第一章緒論 11.1問題背尿和怠義 11.2研究目標(biāo) 31.3研究?jī)?nèi)容 31.4研究方法 61.5論文創(chuàng)新點(diǎn) 6第二章車輛路徑問題研究綜述 82.1引言 82.2標(biāo)準(zhǔn)車輛路徑問題及英數(shù)學(xué)模型 82.3車輛路徑問題擴(kuò)展問題 11231弔輛路徑問題構(gòu)成要素 H23.2車輛路彳殳問題孑亠展標(biāo)準(zhǔn) 132.33車輛路徑問題擴(kuò)展何題 152.4標(biāo)準(zhǔn)乍輛路徑問題求解口法 22241經(jīng)典啟發(fā)式算法 232.4.2現(xiàn)代啟發(fā)式算法 272.5小結(jié) 37第三章組合優(yōu)化及現(xiàn)代啟發(fā)式算法 393.1組合優(yōu)化問題 393.2計(jì)算復(fù)雜性 4033組合優(yōu)化問題求解 413.4現(xiàn)代啟發(fā)式舁法 413.4.1迭代改進(jìn)算法 433.4.2模擬退火缺法 433.4.3禁忌搜索算法 443.4.4貪委隨機(jī)自適應(yīng)捜索過(guò)程 463.4.5變鄰域搜索算法 463.4.6引導(dǎo)財(cái)部搜索貝法 473.4.7迭代局部搜索算法 48348進(jìn)化計(jì)算 493.4.9蟻群優(yōu)化算法 50車輛路徑問題(vehideRoutingProblem，vRP)是組合優(yōu)化和運(yùn)籌學(xué)領(lǐng)域研究的熱點(diǎn)問題之一，其主要研究滿足約束條件的最優(yōu)車輛使用方案以及最優(yōu)的車輛路徑方案?；诨拒囕v路徑問題的框架，研究滿足生產(chǎn)經(jīng)營(yíng)和運(yùn)作需要的各種車輛路徑問題，并構(gòu)建具有高質(zhì)量和高魯棒性 (roubustuess)的問題求解算法對(duì)于提高生產(chǎn)經(jīng)營(yíng)管理水平和降低運(yùn)作成木具有重要的理論意義和現(xiàn)實(shí)價(jià)值。本文以車輛路徑問題為研究對(duì)象，綜合運(yùn)用組合優(yōu)化和現(xiàn)代啟發(fā)式算法等工具，對(duì)幾類重要的車輛路徑問題模型及其優(yōu)化算法進(jìn)行了系統(tǒng)的研究，主要研究工作及成果總結(jié)如下:綜述了車輛路徑問題在定義車輛路徑問題分類和擴(kuò)展標(biāo)準(zhǔn)的基礎(chǔ)上，給出了車輛路徑問題的研究綜述。基于不同的分類標(biāo)準(zhǔn)，首先討論了主要的標(biāo)準(zhǔn)車輛路徑問題擴(kuò)展問題。在此基礎(chǔ)上詳細(xì)地綜述了求解標(biāo)準(zhǔn)車輛路徑問題的現(xiàn)代啟發(fā)式算法，系統(tǒng)地描述了各種算法的實(shí)現(xiàn)機(jī)理以及各種算法的性能比較結(jié)果。綜述了求解組合優(yōu)化問題的現(xiàn)代啟發(fā)式算法在給出組合優(yōu)化問題和計(jì)算復(fù)雜性定義的基礎(chǔ)上，綜述了求解復(fù)雜組合優(yōu)化問題的各種現(xiàn)代啟發(fā)式算法。研究了開放式車輛路徑問題通過(guò)松弛標(biāo)準(zhǔn)車輛路徑問題中車輛路線為哈密爾頓巡回(Hamiltoniantour)的假設(shè)，研究了車輛路線為哈密爾頓路徑(Hamiltonianpath)的開放式車輛路徑問題。該問題中車輛在服務(wù)完最后一個(gè)顧客點(diǎn)后不需要回到車場(chǎng)，若要求回到車場(chǎng)，則必須沿原路返回。在首先給出問題數(shù)學(xué)模型的基礎(chǔ)上，提出了求解開放式車輛路徑問題的蟻群優(yōu)化算法。該算法主體是一個(gè)在超立方框架下執(zhí)行的側(cè)只刃一側(cè)工加尸螞蟻系統(tǒng)，算法混合了禁忌搜索算法作為局部?jī)?yōu)化算法，同時(shí)集成了一個(gè)后優(yōu)化過(guò)程來(lái)進(jìn)一步優(yōu)化最優(yōu)解。基于基準(zhǔn)測(cè)試問題，系統(tǒng)地研究了算法性能。同其它算法的性能比較結(jié)果表明本文提出的蟻群優(yōu)化算法是有效的求解開放式車輛路徑問題的方法。研究了帶時(shí)間窗和帶時(shí)間期限開放式車輛路徑問題通過(guò)引入時(shí)間約束，研究了兩類新的滿足時(shí)效性要求的開放式車輛路徑問題—帶時(shí)間窗和帶時(shí)間期限開放式車輛路徑問題。首先構(gòu)建了兩類問題的數(shù)學(xué)模型，同時(shí)提出了求解兩上海交通大學(xué)博十學(xué)位論文類問題的基于禁忌搜索的迭代局部搜索算法，該算法集成了不同的解接受標(biāo)準(zhǔn)以及一個(gè)基于閡值接受的后優(yōu)化過(guò)程。基于隨機(jī)產(chǎn)生的測(cè)試問題的實(shí)驗(yàn)結(jié)果表明:基于禁忌搜索的迭代局部搜索算法可以有效地求解帶時(shí)間窗和帶時(shí)間期限開放式車輛路徑問題。研究了帶時(shí)間窗和隨機(jī)旅行時(shí)間車輛路徑問題通過(guò)對(duì)標(biāo)準(zhǔn)車輛路徑問題的拓展，引入新的邊約束條件:時(shí)間窗、隨機(jī)旅行時(shí)間和服務(wù)時(shí)間，研究了一類新的隨機(jī)車輛路徑問題—帶時(shí)IbJ窗和隨機(jī)旅行時(shí)間車輛路徑問題。根據(jù)不同的優(yōu)化標(biāo)準(zhǔn)，分別構(gòu)建了問題的機(jī)會(huì)約束規(guī)劃模型以及帶修正隨機(jī)規(guī)劃模型。機(jī)會(huì)約束規(guī)劃模型是在隨機(jī)約束以一定的置信水平成立的條件下最小化運(yùn)輸費(fèi)用。帶修正的隨機(jī)規(guī)劃模型是一個(gè)兩階段優(yōu)化問題，其確定第一階段的路線集以最小化第二階段(隨機(jī)變量實(shí)現(xiàn)后)的期望運(yùn)輸費(fèi)用。鑒于問題的隨機(jī)特性，為了有效求解該問題提出了基于隨機(jī)模擬的禁忌搜索算法。同時(shí)基于隨機(jī)產(chǎn)生的測(cè)試問題通過(guò)實(shí)驗(yàn)檢驗(yàn)了算法有效性。研究了固定車輛數(shù)異型車輛路徑問題在車輛路徑問題經(jīng)典文獻(xiàn)中，一般均假設(shè)車輛同質(zhì)目‘車輛數(shù)無(wú)限。然而在實(shí)際運(yùn)作中，車輛集一般是由具有不同屬性(裝載能力、固定成本以及單位公里可變費(fèi)用 )的車輛組成，且受運(yùn)作成本的約束車輛數(shù)一也是固定的。通過(guò)對(duì)車輛同質(zhì)及車輛數(shù)無(wú)限的假設(shè)條件的放松，研究了固定車輛數(shù)的異型車輛路徑問題。在首先給出問題數(shù)學(xué)模型的基礎(chǔ)上，提出了求解該問題的多起點(diǎn)自適應(yīng)記憶規(guī)劃算法?；谖墨I(xiàn)中的基準(zhǔn)測(cè)試問題，系統(tǒng)地研究了算法在不同多樣化策略下的性能。同文獻(xiàn)中其它算法的比較結(jié)果表明:提出的多起點(diǎn)自適應(yīng)記憶規(guī)劃算法是較好的求解固定車輛數(shù)異型車輛路徑問題的算法，對(duì)于其中五個(gè)測(cè)試問題，算法發(fā)現(xiàn)了新的最優(yōu)解。研究了車輛路徑問題的應(yīng)用問題以城市日常報(bào)品配送問題為例，進(jìn)行了車輛路徑問題的應(yīng)用研究。基于報(bào)品配送的實(shí)際數(shù)據(jù)，運(yùn)用本文研究的幾類車輛路徑問題的框架，研究了不同類型的最優(yōu)報(bào)品配送車輛路徑方案的制定問題。執(zhí)行本文提出的優(yōu)化算法，給出了不同類型的報(bào)品配送的最優(yōu)車輛路徑方案。通過(guò)實(shí)驗(yàn)驗(yàn)證了論文提出的車輛路徑問題優(yōu)化算法的有效性，實(shí)驗(yàn)結(jié)果表明論文提出的算法可以用于生產(chǎn)管理中最優(yōu)車輛路線方案的制定。本文創(chuàng)新性研究成果及貢獻(xiàn)主要包括以下幾方面:松弛了標(biāo)準(zhǔn)VRP中車輛路線為哈密爾頓巡回的假設(shè)，研究了車輛路線為哈密爾一工工一頓路徑的開放式車輛路徑問題。構(gòu)建了求解問題的蟻群優(yōu)化算法，該算法是一個(gè)集成了后優(yōu)化過(guò)程的在超立方框架下執(zhí)行的側(cè)只刃一側(cè)工加尸螞蟻系統(tǒng)。同文獻(xiàn)中其它算法性能的比較結(jié)果證明本文提出的蟻群優(yōu)化算法是有效的求解開放式車輛路徑問題的方法，算法改進(jìn)了文獻(xiàn)中其它算法發(fā)現(xiàn)的最優(yōu)解。引入時(shí)間約束，研究了兩類新的滿足時(shí)效性要求的車輛路徑問題—帶時(shí)間窗和帶時(shí)間期限開放式車輛路徑問題。提出了求解上述兩類問題的迭代局部搜索算法，并基于隨機(jī)產(chǎn)生的測(cè)試問系統(tǒng)研究了算法的求解性能。引入時(shí)間窗、隨機(jī)旅行時(shí)間和服務(wù)時(shí)間約束，研究了帶時(shí)間窗和隨機(jī)旅行時(shí)間車輛路徑問題。根據(jù)不同的優(yōu)化標(biāo)準(zhǔn)，分別構(gòu)建了問題的機(jī)會(huì)約束規(guī)劃模型以及帶修正隨機(jī)規(guī)劃模型。提出了基于隨機(jī)模擬的禁忌搜索算法，基于隨機(jī)機(jī)產(chǎn)生的測(cè)試問題的實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。通過(guò)松弛標(biāo)準(zhǔn)VRP中車輛同質(zhì)及