帶時間窗車輛路徑問題及其啟發(fā)式算法研究.pdf

1、車輛路徑問題是研究如何通過合理規(guī)劃行駛路線來實現(xiàn)運輸成本優(yōu)化的一類優(yōu)化調(diào)度問題，其相關理論和算法對于降低物流成本具有重要的應用價值，因此一直是運籌學和組合優(yōu)化領域的研究熱點。 多年來車輛路徑問題己衍生出眾多研究分支，如開放式車輛路徑問題、多站點車輛路徑問題、裝卸貨車輛路徑問題、帶時間窗車輛路徑問題和周期性車輛路徑問題等，并取得了大量的研究成果，同時車輛路徑問題也廣泛應用于生產(chǎn)和生活的各個方面，如信件投遞、貨物配送、車輛調(diào)度等，產(chǎn)

2、生了巨大的經(jīng)濟效益。 在實際生活中，常常存在這樣一類車輛路徑問題：用戶對時間有較為嚴格的要求，他們希望在事先指定的時間區(qū)間內(nèi)進行服務，因此在規(guī)劃車輛的行駛路線時，不僅要考慮車輛的負載限制，還要同時考慮用戶時間要求的滿足。這一類問題可以抽象為帶時間窗的車輛路徑問題，其中用戶指定的時間區(qū)間稱為時間窗。由于時間窗約束的引進，帶時間窗的車輛路徑問題的求解更加困難，因此帶時間窗的車輛路徑問題一直是車輛路徑問題中最重要的研究分支之一。本文對

3、帶時間窗問題及其擴展問題的建模與求解算法進行了研究，主要研究成果如下： (1)提出了“最先過期用戶優(yōu)先”規(guī)則用于求解帶時間窗問題及其擴展問題。帶時間窗的車輛路徑問題及其擴展問題已被證明是NP-Hard問題，因此通常采用啟發(fā)式算法求取滿意解。本文從研究基本的單時間窗、非時變問題入手，在分析多種常見算法的基礎上提出了“最先過期用戶優(yōu)先”的路徑構(gòu)造規(guī)則用于問題求解，并進一步改進算法處理帶時間窗問題的擴展問題，實驗證明該算法在大部分情況

4、下都具有更優(yōu)的性能。 (2)建立了多時間窗的車輛路徑問題的數(shù)學模型，并利用啟發(fā)式算法進行求解。實際生活中如包裹派送等常常存在用戶的時間窗不止一個的情形，目前關于這種多時間窗問題的研究極少，常見的單時間窗模型無法正確處理多時間窗問題，本文分析多時間窗問題的基本性質(zhì)，引入“虛擬用戶”的概念實現(xiàn)了多時間窗問題向單時間窗問題的轉(zhuǎn)換，建立了多時間窗問題的車輛流模型，并提出了啟發(fā)式求解算法。 (3)建立了時變的帶時間窗車輛路徑問題的

5、數(shù)學模型，并利用啟發(fā)式算法進行求解。基本的帶時間窗問題將車輛行駛過程考慮成理想狀態(tài)下的勻速過程，然而實際生活中車輛的行駛速度會隨著不同時間段車流量的不同而不同，即速度時變的車輛路徑問題。由于時變問題更能準確反映現(xiàn)實情況，目前對它的研究正引起越來越多學者的關注。本文首先將車輛速度定義為時變分段函數(shù)，由此將時變問題描述成為分段非時變問題，并基于時變分段函數(shù)建立了時變問題的車輛流模型，然后利用啟發(fā)式算法對時變問題進行求解。 (4)引入