發(fā)布時間：2020-04-15 03:53

【摘要】：車輛路線問題是管理科學(xué)的一個重要研究課題,其優(yōu)化技術(shù)是現(xiàn)代物流配送 的一項關(guān)鍵技術(shù)。本文對車輛路線問題,以帶時間窗的車輛路線問題(VRPTW) 為研究對象提出一種二階段啟發(fā)式算法,并設(shè)計一種結(jié)合路線編輯、算法調(diào)整及 系統(tǒng)改進(jìn)的人機(jī)交互優(yōu)化模式;最后對現(xiàn)代物流系統(tǒng)的配送路線問題進(jìn)行研究。 車輛路線問題研究總成本最小的車輛路線,在合適的時間以合適的方式將正 確的貨物運送到正確的地點。物流配送則要求在正確的時間以正確的方式將正確 的貨物送到正確的地方。車輛路線問題在物流配送中有著廣泛的應(yīng)用背景。 在各種車輛路線問題中,一個基本問題是帶時間窗口的車輛路線問題 (VRPTW)。其主要內(nèi)容是:以成本最小的目標(biāo)安排多輛車有序地前往配量給定 的各配送點而構(gòu)成的配送路線,其中每輛車必須從同一車站出發(fā)并最后返回車 站,每個配送點只能安排一個車次在限定的時間窗內(nèi)配送,且每一條配送路線不 得超過車輛的裝載容量和車輛的最后返回時間;如果車輛提前到達(dá)配送點,則需 要等待,直到在時間窗內(nèi)才能配送。 VRPTW 問題屬于 NP-難問題,其算法通常采用了從初始狀態(tài)出發(fā)進(jìn)行鄰域 搜索的啟發(fā)式算法。其中,鄰域搜索被定義為以邊的替換,或者點的交換或重新 定位等為基本操作的搜索。為了使解不過早地陷入局部最優(yōu),現(xiàn)代啟發(fā)式算法引 入了禁忌搜索、遺傳算法、蟻群算法、模擬退火算法等技術(shù)。 本文以 VRPTW 問題為研究對象,提出一種二階段啟發(fā)式算法。主要內(nèi)容有: 1)提出一種新的邊替換搜索方法。即在搜索的一次操作中替換多條路線的 多條邊。其中,限制參與邊替換的路線條數(shù)、每條路線的被替換邊數(shù),以及被替 換邊選自解的一個邊子集。其特點是:在邊子集中可以考慮所有替換組合;如果 選取所有路線的所有邊考察其替換選擇,則這種搜索方法便是一種窮舉優(yōu)化法。 2)提出一種新的點重新定位搜索方法。即在搜索的一次操作中選取多條路 線的多個點,根據(jù)最小成本插入法進(jìn)行重新定位。其中,限制參與點重新定位的 路線條數(shù)、每條路線的被重新定位的點數(shù),以及被重新定位的點選自一個點子集。 3)應(yīng)用掃除法原理設(shè)計 VRPTW 問題的路線構(gòu)造算法。算法考慮了車輛和 WP=4 點的優(yōu)先級配送,并在出現(xiàn)運力不足時用虛擬車輛填補(bǔ)運力缺口。 4)在以上創(chuàng)新性研究的基礎(chǔ)上,提出一種二階段啟發(fā)式算法。本文應(yīng)用這 種算法,并采用小鄰域搜索的參數(shù)設(shè)置,對國際上公認(rèn)的標(biāo)準(zhǔn)測試問題進(jìn)行計算 試驗。結(jié)果顯示:應(yīng)用以上兩種搜索方法對初始解有顯著改進(jìn);將計算試驗獲得 的解與目前世界上公認(rèn)的最好啟發(fā)式解相比較,一部分解達(dá)到最好啟發(fā)式解,少 部分解的總路長低于最好啟發(fā)式解的總路長,其它解則接近最好解。 這種算法的特點適合人機(jī)交互優(yōu)化。通過人機(jī)交互,應(yīng)用這種算法能夠進(jìn)一 步獲得更好的解。 車輛路線問題是一類非常復(fù)雜的優(yōu)化問題。在配送決策系統(tǒng)中,采用人機(jī)交 互的方式求解車輛路線問題是非常必要的。本文提出了一種結(jié)合路線編輯、算法 調(diào)整及系統(tǒng)改進(jìn)的人機(jī)交互優(yōu)化模式。其中,通過點的人工重新定位,進(jìn)行路線 的編輯;通過路線或點的鎖定,限制系統(tǒng)改進(jìn)的搜索鄰域;通過各種啟發(fā)式方法 的取舍及其參數(shù)設(shè)置,調(diào)整系統(tǒng)改進(jìn)的算法。采用這種模式,不但可彌補(bǔ)啟發(fā)式 算法的不足,提高算法的搜索效率,而且可在突發(fā)情況下人工參與決策。 最后,本文對現(xiàn)代物流系統(tǒng)的配送路線問題,做了以下研究: 1)在不同配送環(huán)境不同配送要求下,對 VRPTW 問題的推廣進(jìn)行啟發(fā)式方 法的研究。這些推廣包括:多車型、多貨艙、多品種、混合裝卸、多時間窗、拆 分配送、分優(yōu)先級配送、臨時增減配送、跨區(qū)域配送、流量分配、運輸管制、交 通約束、有限運力、有限庫存/庫容、工作量平衡以及成本的廣義定義。 2)研究配送路線決策系統(tǒng)與 GIS 系統(tǒng)以及物流信息系統(tǒng)的數(shù)據(jù)交換。 3)研究油品配送、零售配送和快遞配送的配送路線問題。它們分別屬于散 裝品配送、包裝品配送和帶時間目標(biāo)的配送。其中,在油品配送中主要研究了寬 時間窗的啟發(fā)式方法;在零售配送中分析了多倉庫配送;而在快遞配送中重點研 究了快件收取的車輛路線問題,其中提出三個路線決策準(zhǔn)則,并進(jìn)行模擬試驗研 究。
【圖文】：

圖 1.7 第一類型的 3-opt 搜索的邊替換方法。圖 1.8 第二類型的 3-opt 搜索的邊替換方法。pt*，Potvin和Rousseau[121]提出一種兩條路線之間的邊替換方法——條路線中各取一條邊，在不改變路線方向的前提下用新的兩條邊2-opt*的邊替換方法。圖中用新的兩條邊(i, j+1)和(j, i +1)替換兩

PTW 問題的路線構(gòu)造算法法原理掃除法構(gòu)造車輛路線，是指優(yōu)先將處于同一方位的點分配給同一輛：對一輛車，首先從未分配點中選取一個種子點（seed node），并，從車站向種子點發(fā)出的射線為極軸，將所有未分配點的直角坐標(biāo)；然后，按極角從小到大（或從大到�。┲饌�選點插入路線，，直到力極限或其他限制為止(如圖 2.1)。
【學(xué)位授予單位】：復(fù)旦大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2004
【分類號】：F250

【引證文獻(xiàn)】

相關(guān)期刊論文 前7條

1 李惠珠;宋海清;;基于GIS的物流配送車輛調(diào)度實現(xiàn)與應(yīng)用[J];長春師范學(xué)院學(xué)報;2011年04期

2 王洋;范劍英;林立軍;于舒春;于貴江;;物流配送路徑優(yōu)化理論在立體匹配技術(shù)中的應(yīng)用研究[J];哈爾濱理工大學(xué)學(xué)報;2011年02期

3 孫學(xué)農(nóng);徐輝增;;物流配送車輛調(diào)度問題方法綜述[J];科技信息(學(xué)術(shù)研究);2007年12期

4 徐劍;牟燕妮;張尹聰;王中穎;;物流配送車輛調(diào)度優(yōu)化方法比較研究[J];物流科技;2006年02期

5 姜艷;關(guān)雪;;快遞路徑優(yōu)化模型研究[J];物流技術(shù);2008年03期

6 王旭坪;牛君;胡祥培;許傳磊;;車輛路徑問題的受擾救援策略[J];系統(tǒng)工程理論與實踐;2007年12期

7 仝青山;王定杰;任濤;王艷群;;啟發(fā)式算法在送貨線路設(shè)計中的應(yīng)用[J];公路與汽運;2012年02期

相關(guān)博士學(xué)位論文 前5條

1 錢潤華;軍事力量水路輸送轉(zhuǎn)運系統(tǒng)建模優(yōu)化與仿真研究[D];清華大學(xué);2010年

2 尹傳忠;鐵路行包物流配送系統(tǒng)優(yōu)化若干問題研究[D];西南交通大學(xué);2006年

3 井祥鶴;陸路物流物資配載及輸送路徑優(yōu)化問題的模型與算法[D];南京理工大學(xué);2007年

4 王旭坪;物流配送調(diào)度的干擾管理研究[D];大連理工大學(xué);2010年

5 傅成紅;多周期庫存路徑問題及其算法研究[D];中南大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 歐陽濤;物流車輛路徑問題算法研究[D];吉林大學(xué);2011年

2 張韜;基于多種網(wǎng)絡(luò)的數(shù)據(jù)挖掘研究[D];哈爾濱工業(yè)大學(xué);2010年

3 李楠;大規(guī)模實時動態(tài)車輛路徑問題研究[D];清華大學(xué);2010年

4 林立軍;物流配送路徑優(yōu)化理論在立體匹配中的應(yīng)用研究[D];哈爾濱理工大學(xué);2011年

5 盧美紅;規(guī)模動態(tài)增長的車輛路徑優(yōu)化問題[D];華東理工大學(xué);2012年

6 王惠;引入顧客滿意度求解車輛優(yōu)化調(diào)度問題[D];大連海事大學(xué);2006年

7 孫培昕;農(nóng)資配送支持系統(tǒng)設(shè)計與關(guān)鍵模塊實現(xiàn)[D];東北農(nóng)業(yè)大學(xué);2007年

8 牛君;VRPTW中車輛受損問題建模及多車救援策略[D];大連理工大學(xué);2007年

9 蔣文霞;有時間窗車輛路徑問題的模型及算法[D];武漢理工大學(xué);2007年

10 衛(wèi)田;物流配送中車輛路徑問題的多目標(biāo)優(yōu)化算法研究[D];清華大學(xué);2007年

本文編號：2628100