《車輛路徑問題模型及算法研究》是李相勇2007年發表的一則博士論文。
基本信息,中文摘要,
基本信息
副題名
外文題名
論文作者
李相勇著
導師
田澎指導
學科專業
管理科學與工程
學位級別
博士論文
學位授予單位
上海交通大學
學位授予時間
2007
關鍵字
物流 運輸調度 最最佳化算法 車輛
館藏號
F253.4
館藏目錄
2009\F253.4\10
中文摘要
車輛路徑問題(Vehicle Routing Problem，VRP)是組合最佳化和運籌學領域研究的熱點問題之一，其主要研究滿足約束條件的最優車輛使用方案以及最優的車輛路徑方案。基於基本車輛路徑問題的框架，研究滿足生產經營和運作需要的各種車輛路徑問題，並構建具有高質量和高魯棒性(roubustness)的問題求解算法對於提高生產經營管理水平和降低運作成本具有重要的理論意義和現實價值。 本文以車輛路徑問題為研究對象，綜合運用組合最佳化和現代啟發式算法等工具，對幾類重要的車輛路徑問題模型及其最佳化算法進行了系統的研究，主要研究工作及成果總結如下： 1．綜述了車輛路徑問題 在定義車輛路徑問題分類和擴展標準的基礎上，給出了車輛路徑問題的研究綜述。基於不同的分類標準，首先討論了主要的標準車輛路徑問題擴展問題。在此基礎上詳細地綜述了求解標準車輛路徑問題的現代啟發式算法，系統地描述了各種算法的實現機理以及各種算法的性能比較結果。 2．綜述了求解組合最佳化問題的現代啟發式算法 在給出組合最佳化問題和計算複雜性定義的基礎上，綜述了求解複雜組合最佳化問題的各種現代啟發式算法。 3．研究了開放式車輛路徑問題 通過鬆弛標準車輛路徑問題中車輛路線為哈密爾頓巡迴(Hamiltonian tour)的假設，研究了車輛路線為哈密爾頓路徑(Hamiltonian Dath)的開放式車輛路徑問題。該問題中車輛在服務完最後一個顧客點後不需要回到車場，若要求回到車場，則必須沿原路返回。在首先給出問題數學模型的基礎上，提出了求解開放式車輛路徑問題的蟻群最佳化算法。該算法主體是一個在超立方框架下執行的MAX-MIN螞蟻系統，算法混合了禁忌搜尋算法作為局部最佳化算法，同時集成了一個後最佳化過程來進一步最佳化最優解。基於基準測試問題，系統地研究了算法性能。同其它算法的性能比較結果表明本文提出的蟻群最佳化算法是有效的求解開放式車輛路徑問題的方法。 4．研究了帶時間窗和帶時間期限開放式車輛路徑問題 通過引入時間約束，研究了兩類新的滿足時效性要求的開放式車輛路徑問題——帶時間窗和帶時間期限開放式車輛路徑問題。首先構建了兩類問題的數學模型，同時提出了求解兩類問題的基於禁忌搜尋的疊代局部搜尋算法，該算法集成了不同的解接受標準以及一個基於閾值接受的後最佳化過程。基於隨機產生的測試問題的實驗結果表明：基於禁忌搜尋的疊代局部搜尋算法可以有效地求解帶時間窗和帶時間期限開放式車輛路徑問題。 5．研究了帶時間窗和隨機旅行時間車輛路徑問題 通過對標準車輛路徑問題的拓展，引入新的邊約束條件：時間窗、隨機旅行時間和服務時間，研究了一類新的隨機車輛路徑問題——帶時間窗和隨機旅行時間車輛路徑問題。根據不同的最佳化標準，分別構建了問題的機會約束規劃模型以及帶修正隨機規劃模型。機會約束規劃模型是在隨機約束以一定的置信水平成立的條件下最小化運輸費用。帶修正的隨機規劃模型是一個兩階段最佳化問題，其確定第一階段的路線集以最小化第二階段(隨機變數實現後)的期望運輸費用。鑒於問題的隨機特性，為了有效求解該問題提出了基於隨機模擬的禁忌搜尋算法。同時基於隨機產生的測試問題通過實驗檢驗了算法有效性。 6．研究了固定車輛數異型車輛路徑問題 在車輛路徑問題經典文獻中，一般均假設車輛同質且車輛數無限。然而在實際運作中，車輛集一般是由具有不同屬性(裝載能力、固定成本以及單位公里可變費用)的車輛組成，且受運作成本的約束車輛數也是固定的。通過對車輛同質及車輛數無限的假設條件的放鬆，研究了固定車輛數的異型車輛路徑問題。在首先給出問題數學模型的基礎上，提出了求解該問題的多起點自適應記憶規划算法。基於文獻中的基準測試問題，系統地研究了算法在不同多樣化策略下的性能。同文獻中其它算法的比較結果表明：提出的多起點自適應記憶規划算法是較好的求解固定車輛數異型車輛路徑問題的算法，對於其中五個測試問題，算法發現了新的最優解。 7．研究了車輛路徑問題的套用問題 以城市日常報品配送問題為例，進行了車輛路徑問題的套用研究。基於報品配送的實際數據，運用本文研究的幾類車輛路徑問題的框架，研究了不同類型的最優報品配送車輛路徑方案的制定問題。執行本文提出的最佳化算法，給出了不同類型的報品配送的最優車輛路徑方案。通過實驗驗證了論文提出的車輛路徑問題最佳化算法的有效性，實驗結果表明論文提出的算法可以用於生產管理中最優車輛路線方案的制定。 本文創新性研究成果及貢獻主要包括以下幾方面： 1．鬆弛了標準VRP中車輛路線為哈密爾頓巡迴的假設，研究了車輛路線為哈密爾頓路徑的開放式車輛路徑問題。構建了求解問題的蟻群最佳化算法，該算法是一個集成了後最佳化過程的在超立方框架下執行的MAX-MIN螞蟻系統。同文獻中其它算法性能的比較結果證明本文提出的蟻群最佳化算法是有效的求解開放式車輛路徑問題的方法，算法改進了文獻中其它算法發現的最優解。 2．引入時間約束，研究了兩類新的滿足時效性要求的車輛路徑問題——帶時間窗和帶時間期限開放式車輛路徑問題。提出了求解上述兩類問題的疊代局部搜尋算法，並基於隨機產生的測試問系統研究了算法的求解性能。 3．引入時間窗、隨機旅行時間和服務時間約束，研究了帶時間窗和隨機旅行時間車輛路徑問題。根據不同的最佳化標準，分別構建了問題的機會約束規劃模型以及帶修正隨機規劃模型。提出了基於隨機模擬的禁忌搜尋算法，基於隨機機產生的測試問題的實驗結果驗證了算法的有效性。 4．通過鬆弛標準VRP中車輛同質及車輛數無限的假設，研究了固定車輛數異型車輛路徑問題。提出了求解問題的多起點自適應記憶規划算法，同文獻中其它算法的比較結果表明：多起點自適應記憶規划算法是較好的求解固定車輛數異型車輛路徑問題的算法，對於五個基準測試問題，算法發現了新的最優解。 本文綜合運用運籌學和組合最佳化的理論與方法，對幾類車輛路徑問題模型及算法進行了系統的研究。本文的研究工作拓展了車輛路徑問題以及組合最佳化的研究空間，豐富了運籌學和管理科學的理論研究成果，同時為運輸、物流和配送管理等領域中最優車輛路徑方案的規劃與設計提供了借鑑和參考。
