車輛路徑問題

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