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

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

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

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

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

【部分圖文】：

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

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

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

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

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

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



本文編號：3340311