隨著現(xiàn)代智慧物流的發(fā)展,傳統(tǒng)的車輛路徑問題(VRP)模型已經(jīng)很難滿足現(xiàn)在客戶多元化的需求。因此,動(dòng)態(tài)車輛路徑問題(DVRP)的研究對于現(xiàn)代智慧物流的發(fā)展至關(guān)重要。本文在國內(nèi)外DVRP研究基礎(chǔ)上,重點(diǎn)研究了新的DVRP模型和求解算法。本文主要研究工作如下:(1)結(jié)合前人對DVRP的研究,對動(dòng)態(tài)車輛路徑問題的研究現(xiàn)狀進(jìn)行了闡述,并總結(jié)了存在的問題與不足。同時(shí),根據(jù)不同的約束條件,對車輛路徑問題進(jìn)行了歸類與分析。此外,還對求解DVRP常用的算法進(jìn)行分類介紹。(2)對動(dòng)態(tài)單車場車輛路徑問題進(jìn)行了數(shù)學(xué)建模,設(shè)計(jì)了混合蟻群算法進(jìn)行求解。算法首先使用改進(jìn)的K-means聚類算法進(jìn)行K值確定和配送區(qū)域劃分,然后使用蟻群算法生成初始路徑和最佳路徑交叉優(yōu)化算法進(jìn)行路徑全局優(yōu)化,最后采用2-Opt算法進(jìn)行局部路徑優(yōu)化。實(shí)驗(yàn)部分,不僅基于不同規(guī)模的數(shù)據(jù)集進(jìn)行結(jié)果直接比較,同時(shí)還對車輛使用率、動(dòng)態(tài)度以及算法收斂性進(jìn)行分析,以此來驗(yàn)證模型和算法的有效性。(3)對動(dòng)態(tài)多車場車輛路徑問題(DMDVRP)進(jìn)行了建模與求解。按照DMDVRP特征建立對應(yīng)的數(shù)學(xué)模型,同時(shí)設(shè)計(jì)了蟻群禁忌算法和實(shí)時(shí)添加優(yōu)化算法對問題進(jìn)行求解。蟻群禁忌算法采用蟻群算法框架,融合了遺傳算法的變異操作和禁忌搜索算法。對于新客戶的添加和優(yōu)化部分,設(shè)計(jì)了新的實(shí)時(shí)添加優(yōu)化算法實(shí)現(xiàn)添加和優(yōu)化同步進(jìn)行。實(shí)驗(yàn)部分,經(jīng)過與最新出版的學(xué)術(shù)論文實(shí)驗(yàn)結(jié)果對比,證明了提出的算法可以高效地解決DMDVRP。此外,本文還比較了實(shí)時(shí)添加優(yōu)化算法的優(yōu)化效果,實(shí)驗(yàn)表明這是一種高效的添加優(yōu)化算法。
【學(xué)位單位】：杭州電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2019
【中圖分類】：U116.2;F252;TP18
【部分圖文】：

車輛路徑問題的基本定義：以路程最短為目標(biāo)函數(shù)，安排一輛或者多輛車按??照給定的配送線路和客戶服務(wù)順序，在滿足車輛最大載荷約束條件下，完成所有??客戶點(diǎn)的配送服務(wù)［２４］。圖２．１是一個(gè)簡單ＶＲＰ配送示意圖，紅色矩形代表配送??中心，黑色圓形代表客戶，箭頭為規(guī)劃的配送路徑，圖中有三輛車分別按照規(guī)劃??的路線為１０個(gè)不同的客戶服務(wù)。??魯客戶?■?配送中心?——＞?規(guī)劃路線??圖２．１簡單ＶＲＰ示意圖??２．１．２靜態(tài)車輛路徑問題組成要素??靜態(tài)車輛路徑問題主要由七個(gè)要素組成，分別是配送中心、車輛、貨物、客??戶、運(yùn)輸網(wǎng)絡(luò)、目標(biāo)函數(shù)和約束條件［２５］。??（１）

況、突發(fā)事件等，這種帶著大量隨機(jī)性且需要及時(shí)處理的車輛路徑問題屬于動(dòng)態(tài)??車輛路徑問題。??圖２．２是一個(gè)簡單的ＤＶＲＰ示意圖，其中黑點(diǎn)代表己知的客戶，藍(lán)色三角形??為新客戶，紅色方塊為配送中心，紅色箭頭和黑色箭頭分別代表己經(jīng)完成的路線??和未來即將服務(wù)的路線，黑色虛箭頭表示加入新客戶后生成的新路線。其中圖（ａ）??表示所有客戶都是已知的，系統(tǒng)按照既定的路線開始安排配送服務(wù)。圖（ｂ）表示??—些新的客戶開始動(dòng)態(tài)地發(fā)起服務(wù)請求，需要等待系統(tǒng)安排服務(wù)。圖（ｃ）圖表示系??統(tǒng)根據(jù)目前的服務(wù)狀態(tài)，將新客戶加入調(diào)度系統(tǒng)，并重新規(guī)劃路線進(jìn)行服務(wù)，最??終車輛完成所有服務(wù)回到配送中心。??⑻?（ｂ）?（ｃ）??？?已知客戶?△?新增客戶?＿?配送中心??——＞?已完成路線?——＞?規(guī)劃路線?——＞?新路線??圖２．２動(dòng)態(tài)車輛路徑問題示意圖??在現(xiàn)實(shí)物流配送過程中，可能出現(xiàn)客戶請求的服務(wù)時(shí)間與實(shí)際可執(zhí)行的服務(wù)??時(shí)間沖突，部分客戶配送任務(wù)被安排到下一個(gè)工作日。可以使用給工作日設(shè)置服??務(wù)請求截止時(shí)間７；。方式處理該類問題

這些新的客戶需求應(yīng)該立刻被分配給正在為其他客戶服務(wù)的車輛，或者安排新的??車輛單獨(dú)處理新需求。因此，在配送服務(wù)過程中，總存在一些己經(jīng)被服務(wù)完的客??戶和一些等待被服務(wù)的客戶。一個(gè)ＤＶＲＰ示意圖如圖３．１所示，其中黑點(diǎn)代表已??知需求的客戶，紅線和黑線分別代表己經(jīng)完成的路線和未來即將服務(wù)的路線，紅??線與黑線的組合表示為已知需求客戶設(shè)計(jì)的初始路線。隨著時(shí)間的推移，新產(chǎn)生??的客戶需求（藍(lán)色三角形）被添加到系統(tǒng)中，新客戶被插入到現(xiàn)有路線中，并將??產(chǎn)生新的配送路線（紅線＋黑色虛線）［５２］。??＃?已知客戶?Ａ?新增客戶?■?配送中心???灸己完成路線?灸規(guī)劃路線－－－－＞?新路線??圖３．１動(dòng)態(tài)車輛路徑問題示意圖??２２??
【參考文獻(xiàn)】

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

1 楊弋,顧幸生;物流配送車輛優(yōu)化調(diào)度的綜述[J];東南大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年S1期

本文編號：2882929