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

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

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

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

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

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

本文編號：2882929