帶時間窗快遞車輛路徑問題模型及算法研究.pdf

1、隨著電子商務(wù)的飛速崛起，快遞企業(yè)如何合理安排運(yùn)輸車輛以降低運(yùn)輸成本成為一個迫切需要解決的問題?？爝f車輛路徑問題是經(jīng)典的車輛路徑問題(VRP)的變種，也是一個NP難問題。因此，快速的啟發(fā)式求解算法及解好壞的評估是研究中的難點(diǎn)和關(guān)鍵。該問題的研究及應(yīng)用，可以顯著地降低快遞行業(yè)的運(yùn)輸成本，同時也減少車輛的二氧化碳排放量，對經(jīng)濟(jì)和環(huán)境產(chǎn)生積極影響。給定分撥中心的網(wǎng)絡(luò)結(jié)構(gòu)及其服務(wù)時間窗口約束和各個分撥中心之間的貨物流量結(jié)構(gòu)及其時效約束的快遞車輛路

2、徑規(guī)劃，是實(shí)際中最為常見的一類問題。本文主要研究了帶時間窗的快遞車輛路徑問題的建模及求解，具體工作包括以下兩項(xiàng)內(nèi)容:
　　1.固定時間窗快遞車輛路徑問題建模及求解
　　固定時間窗快遞車輛路徑問題就是研究在收件時間窗和派件時間窗固定的情況下，如何安排班車路由使得班車花費(fèi)的總成本最小。本文首先建立了此問題的數(shù)學(xué)模型，然后設(shè)計(jì)了基于貪心啟發(fā)式方法的快速求解算法，并提出了一種新的班車安排方法:環(huán)線班車+單邊車，以此代替原有的效果較差

3、的對稱班車安排方法，最后還給出了評估該問題解的一個下界模型。通過在不同規(guī)模的真實(shí)數(shù)據(jù)集上進(jìn)行計(jì)算實(shí)驗(yàn)，將提出算法的求解結(jié)果與下界模型得到的下界進(jìn)行比較，從而表明了求解算法的精確程度。還將兩種班車安排方法得到的結(jié)果進(jìn)行對比，說明了本文提出的新班車安排方法優(yōu)于原有班車安排方法。此外，對于9城市數(shù)據(jù)和21城市數(shù)據(jù)，求解算法總的計(jì)算時間分別為1秒和54秒。
　　2.可變時間窗快遞車輛路徑問題建模及求解
　　通過分析發(fā)現(xiàn)時間窗對于班車

4、運(yùn)輸成本影響較大，為此需要將時間窗作為可變參數(shù)納入到模型中，我們將該問題稱之為可變時間窗快遞車輛路徑問題。本文在固定時間窗問題的基礎(chǔ)上，采用環(huán)線班車+單邊車的班車安排方法，建立了該問題的數(shù)學(xué)模型。為了評價算法求解結(jié)果的優(yōu)劣，對該問題建立了時間約束松弛的下界模型并加以證明，再采用Lingo軟件求出其一個下界。最后，設(shè)計(jì)了一種兩階段的求解算法，該算法包括時間窗求解和固定時間窗問題求解兩個階段，并且在時間窗求解階段設(shè)計(jì)了時間窗口好壞的一個評價