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

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

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

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

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

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