發(fā)布時間：2021-08-13 11:04

　　物流配送是一個耗費大量人力物力的領(lǐng)域,有較大的優(yōu)化空間。本文研究的是最后一公里配送中的不確定性車輛路徑問題。實際情況中企業(yè)的配送需求是隨機的,其隨機因素包括訂單位置、服務(wù)時間等。另一方面,配送員對配送路徑的熟悉程度會直接影響其配送效率,配送員在配送區(qū)域的服務(wù)時間會影響客戶的體驗。因此,企業(yè)需要規(guī)劃出多天隨機需求下的魯棒車輛路徑。本文則提供了一個描述多場景下車輛路徑魯棒性問題的通用框架。首先,本文在考慮隨機因素下車輛路徑的魯棒性時,引入各場景計劃一致性的概念,提出了帶主計劃一致性的車輛路徑模型。模型旨在給出一個主計劃和每一天的日常計劃。模型的目標(biāo)函數(shù)是最小化所有計劃的加權(quán)總成本。除了確定性模型會包含的許多約束外,本文提出的模型還包括主計劃一致性約束以確保每天的日常計劃與主計劃中同一車輛時空路徑的偏離程度較小。本文將區(qū)域質(zhì)心作為需求點的單位。區(qū)域質(zhì)心匯總了此區(qū)域內(nèi)的需求。模型的隨機因素是區(qū)域在不同場景下的隨機總需服務(wù)時間、時間窗和總重量。其次,車輛路徑問題本身就是一個NP難題,引入不確定性因素后問題變得更為復(fù)雜。不確定性問題的約束既包含確定性問題中的整數(shù)約束及大量邊際約束,也包含主計劃與子... 

【文章來源】：北京交通大學(xué)北京市 211工程院校 教育部直屬院校

【文章頁數(shù)】：97 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖１車輛路徑問題的車輛路徑方案示例??Ｆｉｇ．?１?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ａ?ｓｏｌｕｔｉｏｎ?ｔｏ?ｔｈｅ?ｖｅｈｉｃｌｅ?ｒｏｕｔｉｎｇ?ｐｒｏｂｌｅｍ??

態(tài)網(wǎng)將車輛路徑問題的大量邊際約束（包括車輛能力約束、服務(wù)時間約束、時間??窗約束等）內(nèi)嵌。最后，本文采用前向動態(tài)規(guī)劃法求解分解后的單車車輛路徑子??問題。詳細(xì)的問題分解過程見圖２。??多場景的帶主計劃一致性約束??的魯棒車輛路徑問題??原問題??、．．?＿???＿一／??子計劃對比主計劃的?＼??一致性約束?＼??拉格朗日松弛法?＼??各場景?邊際約束??主計劃?子計劃?（車輛能力約束、??——ｊ?１?：?ｙ?ｉ?時間窗約束等）??區(qū)域訪問約束?區(qū)域訪問約束?＼??★?觶???１??顯Ｍ?……［２１?１??Ｉ?問題分解?＼??多個?多個?＼??單車車輛路徑子問題單車車輛路徑子問題?１??（．圭蝴—?｜?（各場錄子計劃〉??＊???－?時空狀態(tài)網(wǎng)??前向動態(tài)規(guī)劃法求解??圖２問題分解過程示意圖??Ｆｉｇ．?２?Ｓｋｅｔｃｈ?ｍａｐ?ｏｆ?ｐｒｏｂｌｅｍ?ｄｅｃｏｍｐｏｓｉｔｉｏｎ?ｐｒｏｃｅｄｕｒｅ??本研宄所采用的技術(shù)路線借鑒了大量相關(guān)研宄，有著扎實的研宄基礎(chǔ)。下文??對比說明了其他相關(guān)研宂所采用的研究方法，驗證了本文研究方法的適宜性。??首先，文章通過主計劃和子計劃之間的一致性約束描述車輛路徑的魯棒性。??此建模方法借鑒了跨領(lǐng)域的研宄方法。在鐵路時刻表領(lǐng)域中，學(xué)者們通過引入主??計劃，并將其用做每一個日常計劃的參考，確保主計劃和日常計劃的一致性。Ｌｕ??等人在２０１７年求解鐵路時刻表問題時應(yīng)用了主計劃和子計劃的概念。他通過制定??一個主計劃并根據(jù)每天的實際情況調(diào)整當(dāng)天的子計劃使得變化幅度較小

此實例主要是用來描述不同程度的一致性約束是如何影響車輛路徑方案的。??３．２多場景車輛路徑魯棒性問題描述??本文模型所用的網(wǎng)絡(luò)如圖３所示。圖３左半部分表示一個帶２個區(qū)域的物理??網(wǎng)絡(luò)，節(jié)點〇和ｓ分別代表車輛的起終點。圖３的右半部分將左半部分的區(qū)域節(jié)點??拆分成區(qū)域的服務(wù)開始節(jié)點和區(qū)域的服務(wù)結(jié)束節(jié)點。現(xiàn)考慮兩個場景，每個區(qū)域??有兩種不同的總需服務(wù)時間。因此，每個區(qū)域有一個區(qū)域服務(wù)開始節(jié)點和兩個不??同的區(qū)域服務(wù)結(jié)束節(jié)點。如區(qū)域１拆分為１Ａ、１丨和Ｉ，２。其中６是ｂｅｇｉｎ的縮寫，表??示車輛到達(dá)區(qū)域并開始服務(wù)，／是ｌｅａｖｉｎｇ的縮寫表示即車輛服務(wù)結(jié)束并離開此區(qū)??域，右上角的數(shù)字１和２是一個區(qū)域不同服務(wù)結(jié)束節(jié)點的編號。連接區(qū)域服務(wù)開??始節(jié)點和區(qū)域服務(wù)結(jié)束節(jié)點的虛線是服務(wù)路段。虛線上的數(shù)字表示車輛經(jīng)過此路??段時在區(qū)域的實際服務(wù)時長，單位是分鐘。實線表示的是物理路段。實線上數(shù)字??表示車輛在此路段的旅行時間

【參考文獻(xiàn)】：
期刊論文
[1]行駛時間和服務(wù)時間隨機的集配貨一體的分批配送車輛路徑優(yōu)化[J]. 石建力,張錦.  控制與決策. 2018(04)
[2]隨機旅行時間的外賣O2O配送車輛路徑問題[J]. 王帥,趙來軍,胡青蜜.  物流科技. 2017(01)
[3]考慮交通擁堵及工作量平衡性的一致性車輛路徑問題[J]. 劉恒宇,汝宜紅.  西南交通大學(xué)學(xué)報. 2016(05)
[4]基于模糊時間窗的多中心開放式車輛路徑問題[J]. 楊翔,范厚明,張曉楠,李陽.  計算機集成制造系統(tǒng). 2016(07)
[5]求解多維背包問題的蟻群-拉格朗日松弛混合優(yōu)化算法[J]. 任志剛,趙松云,黃姍姍,梁永勝.  控制與決策. 2016(07)
[6]需求不確定的車輛路徑魯棒優(yōu)化模型[J]. 管峰,鐘銘,韋達(dá).  上海海事大學(xué)學(xué)報. 2015(04)
[7]求解隨機旅行時間的C-VRP問題的混合遺傳算法[J]. 李鋒,魏瑩.  系統(tǒng)管理學(xué)報. 2014(06)
[8]一種新的求解多目標(biāo)隨機需求車輛路徑問題的算法[J]. 趙燕偉,李川,張景玲,陸游,王萬良.  計算機集成制造系統(tǒng). 2012(03)
[9]基于模糊聚類與車輛協(xié)作策略的隨機車輛路徑問題[J]. 劉長石,賴明勇.  管理工程學(xué)報. 2010(02)
[10]帶時間窗和隨機時間車輛路徑問題:模型和算法[J]. 李相勇,田澎.  系統(tǒng)工程理論與實踐. 2009(08)

博士論文
[1]隨機車輛路徑問題研究[D]. 謝秉磊.西南交通大學(xué) 2003

碩士論文
[1]基于蟻群算法的一致性車輛路徑問題的研究[D]. 卞晨.安徽理工大學(xué) 2017
[2]隨機行駛時間車輛調(diào)度問題研究[D]. 周柏松.大連海事大學(xué) 2005



本文編號：3340311