網(wǎng)絡(luò)中供需匹配與多批次取送貨車輛路徑問題研究.pdf

1、本論文研究了供需匹配與多批次取送貨車輛路徑問題。在此問題中，客戶點(diǎn)之間的供需匹配關(guān)系事先未知；每個(gè)客戶點(diǎn)的取貨請求和送貨請求允許通過多次訪問該客戶點(diǎn)來分批次滿足；需做供需匹配決策和車輛路徑?jīng)Q策。此問題是經(jīng)典車輛路徑問題的一種復(fù)雜衍生體，普遍存在于國際原油運(yùn)輸、煙草制造行業(yè)中的生產(chǎn)原料調(diào)撥、零售行業(yè)中的商品庫存重新布局及共享單車系統(tǒng)中的自行車重新分配等網(wǎng)絡(luò)中?；诖藛栴}高度復(fù)雜且受到的關(guān)注較少，本文分別從模型建立、啟發(fā)式算法求解和精確算法

2、求解的角度對此問題進(jìn)行深入研究。本文的主要研究成果呈現(xiàn)如下：
　　（1）本文所研究的問題包含了兩個(gè)相互影響的決策：供需匹配和車輛路徑。先建立一個(gè)混合整數(shù)線性規(guī)劃模型作為基礎(chǔ)模型。然后，通過消除兩個(gè)決策變量之間的耦合關(guān)系，提出一個(gè)新穎的單元化模型。緊接著，提出一系列多項(xiàng)式型有效不等式來加強(qiáng)單元化模型。實(shí)驗(yàn)結(jié)果表明，單元化模型比基礎(chǔ)模型更容易求解，且所提出的有效不等式顯著地提高了單元化模型的性能。最后，驗(yàn)證了所提出的模型和不等式對文獻(xiàn)

3、中相關(guān)問題的有效性。
　　（2）為快速求解現(xiàn)實(shí)中的較大規(guī)模的問題，基于所提出的單元化模型，先設(shè)計(jì)一個(gè)貪婪式算法來構(gòu)建初始解。然后，基于優(yōu)化供需匹配決策和車輛路徑?jīng)Q策的思想，提出7個(gè)高效的鄰域結(jié)構(gòu)。緊接著，提出一個(gè)禁忌搜索算法來改善初始解的質(zhì)量。為驗(yàn)證該算法的效果，借助于CPLEX設(shè)計(jì)求解問題下界的方法。實(shí)驗(yàn)結(jié)果表明，本文所提出的禁忌搜索算法在較短時(shí)間內(nèi)能夠?qū)Ρ疚乃芯康膯栴}提供高質(zhì)量的解。最后，驗(yàn)證了本文所提出的啟發(fā)式算法求解文獻(xiàn)