基本信息
副題名
外文題名
論文作者
馬華偉著
導師
楊善林指導
學科專業
計算機套用
學位級別
博士論文
學位授予單位
合肥工業大學
學位授予時間
2008
關鍵字
物資企業 物流 運輸調度 車輛路徑 最最佳化算法
館藏號
F253.4
館藏目錄
2009\F253.4\13
中文摘要
車輛路徑問題是研究如何通過合理規划行駛路線來實現運輸成本最佳化的一類最佳化調度問題，其相關理論和算法對於降低物流成本具有重要的套用價值，因此一直是運籌學和組合最佳化領域的研究熱點。多年來車輛路徑問題已衍生出眾多研究分支，如開放式車輛路徑問題、多站點車輛路徑問題、裝卸貨車輛路徑問題、帶時間窗車輛路徑問題和周期性車輛路徑問題等，並取得了大量的研究成果，同時車輛路徑問題也廣泛套用於生產和生活的各個方面，如信件投遞、貨物配送、車輛調度等，產生了巨大的經濟效益。 在實際生活中，常常存在這樣一類車輛路徑問題：用戶對時間有較為嚴格的要求，他們希望在事先指定的時間區間內進行服務，因此在規劃車輛的行駛路線時，不僅要考慮車輛的負載限制，還要同時考慮用戶時間要求的滿足。這一類問題可以抽象為帶時間窗的車輛路徑問題，其中用戶指定的時間區間稱為時間窗。由於時間窗約束的引進，帶時間窗的車輛路徑問題的求解更加困難，因此帶時間窗的車輛路徑問題一直是車輛路徑問題中最重要的研究分支之一。本文對帶時間窗問題及其擴展問題的建模與求解算法進行了研究，主要研究成果如下： (1)提出了“最先過期用戶優先”規則用於求解帶時間窗問題及其擴展問題。帶時間窗的車輛路徑問題及其擴展問題已被證明是NP-Hard問題，因此通常採用啟發式算法求取滿意解。本文從研究基本的單時間窗、非時變問題入手，在分析多種常見算法的基礎上提出了“最先過期用戶優先”的路徑構造規則用於問題求解，並進一步改進算法處理帶時間窗問題的擴展問題，實驗證明該算法在大部分情況下都具有更優的性能。 (2)建立了多時間窗的車輛路徑問題的數學模型，並利用啟發式算法進行求解。實際生活中如包裹派送等常常存在用戶的時間窗不止一個的情形，目前關於這種多時間窗問題的研究極少，常見的單時間窗模型無法正確處理多時間窗問題，本文分析多時間窗問題的基本性質，引入“虛擬用戶”的概念實現了多時間窗問題向單時間窗問題的轉換，建立了多時間窗問題的車輛流模型，並提出了啟發式求解算法。 (3)建立了時變的帶時間窗車輛路徑問題的數學模型，並利用啟發式算法進行求解。基本的帶時間窗問題將車輛行駛過程考慮成理想狀態下的勻速過程，然而實際生活中車輛的行駛速度會隨著不同時間段車流量的不同而不同，即速度時變的車輛路徑問題。由於時變問題更能準確反映現實情況，目前對它的研究正引起越來越多學者的關注。本文首先將車輛速度定義為時變分段函式，由此將時變問題描述成為分段非時變問題，並基於時變分段函式建立了時變問題的車輛流模型，然後利用啟發式算法對時變問題進行求解。 (4)引入模擬退火算法求解帶時間窗問題的擴展問題。本文改進基本的模擬退火算法用於求解帶時間窗問題及其擴展問題，並簡化鄰域構造技術以提高算法效率，實驗表明改進的模擬退火算法能夠有效地求解帶時間窗問題及其擴展問題。
