發(fā)布時間：2020-03-28 14:20

【摘要】：“互聯(lián)網(wǎng)+”和“工業(yè)4.0”的提出帶動了傳統(tǒng)制造業(yè)往智能制造方面發(fā)展。各個物流企業(yè)紛紛引入自動引導(dǎo)車(Automated Guided Vehicle,AGV)來替代傳統(tǒng)的“傳送帶+人工”,實現(xiàn)全自動智能分揀。用AGV來進行包裹的分揀,引發(fā)了多AGV路徑規(guī)劃問題,需要給場地中的所有AGV規(guī)劃互不沖突的路徑,并且盡可能地使分揀效率得到提升。這也就是本文所要研究的問題,針對該問題,本文主要完成了以下幾方面的工作:依據(jù)應(yīng)用特點,本文選用了已有的多Agent路徑規(guī)劃模型作為問題模型,并以最小化路徑代價和為優(yōu)化目標。在該模型下,本文提出了兩種基于CBS算法改進的并行算法:PCBS與它的增強型EPCBS。并行算法理論上可以用任意多的線程來對問題進行求解,因此可以更好地利用實際環(huán)境提供的計算性能。通過登記正在擴展結(jié)點的代價值使得并行算法可以有條件選取待擴展結(jié)點,最終求得問題的近似最優(yōu)解;利用隨機化的沖突選擇策略,讓結(jié)點之間找到解的概率盡可能相互獨立,使得并行算法帶來實質(zhì)上的效率提升�？紤]到物流分揀場景的動態(tài)特性,本文提出了動態(tài)多Agent路徑規(guī)劃問題模型,在其中加入了對環(huán)境中執(zhí)行任務(wù)的Agent數(shù)量變化的考慮。針對該問題,本文基于CBS設(shè)計了一種增量搜索算法LPCBS來求,并證明了其最優(yōu)性。增量搜索通過復(fù)用CBS前一次搜索過程中產(chǎn)生的約束樹實現(xiàn)了給“新到達”Agent規(guī)劃路徑的同時快速調(diào)整“在途中”Agent的路徑。同時在LPCBS中我們給出了CBS中約束樹的一種新的實現(xiàn),該實現(xiàn)有效節(jié)省了搜索過程中所需要的內(nèi)存。最后,本文在不同大小、不同Agent數(shù)量的場景下,將本文中設(shè)計的并行算法與改進前的串行算法在不同方面進行了對比。發(fā)現(xiàn)并行算法在應(yīng)對Agent數(shù)量的增長上,搜索時間增長的幅度比串行算法更小,而且并行算法利用多個線程來搜索獲得的效率提升明顯。為了驗證本文設(shè)計的增量搜索算法LPCBS,本文模擬了一個物流分揀的場景。通過模擬多個Agent在環(huán)境中進行任務(wù)分揀,實驗結(jié)果從多方面解釋了LPCBS在求解動態(tài)問題上比CBS效率要高,并且所求解的質(zhì)量相對于典型的分布式求解器HCA*有著明顯優(yōu)勢。
【圖文】：

哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文，操作人員通過將快件身上的條碼給 AGV 中央控制系統(tǒng)進行掃描，快件將要發(fā)往的位置；隨后由系統(tǒng)給 AGV 規(guī)劃路徑，將路徑傳輸給 A來，AGV 按照規(guī)劃好的路徑行走；最后到達目的點完成快件的投遞，。因此，AGV 的路徑好壞是影響分揀作業(yè)效率的關(guān)鍵，，本課題著手于背景之下，研究物流分揀作業(yè)中的多 AGV 路徑規(guī)劃。通過優(yōu)化多個 徑，使得分揀效率可以得到提升。
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：F253;TP23

【相似文獻】

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

1 黃建華,方毅,黃樟燦,吳方才;基于演化計算的廣義路徑規(guī)劃問題[J];武漢理工大學(xué)學(xué)報(信息與管理工程版);2001年02期

2 朱光宇;;面向鉆削路徑規(guī)劃問題的微粒群優(yōu)化算法研究[J];信息與控制;2008年01期

3 李梅娟;陳雪波;張梅鳳;;基于群集智能算法的路徑規(guī)劃問題[J];清華大學(xué)學(xué)報(自然科學(xué)版);2007年S2期

4 孫麗君;胡祥培;王征;;車輛路徑規(guī)劃問題及其求解方法研究進展[J];系統(tǒng)工程;2006年11期

5 陳剛,沈林成;復(fù)雜環(huán)境下路徑規(guī)劃問題的遺傳路徑規(guī)劃方法[J];機器人;2001年01期

6 譚超;徐志鵬;�？�;;采煤機記憶切割路徑規(guī)劃問題研究[J];現(xiàn)代礦業(yè);2009年12期

7 付春菊;吳成東;雷寒;劉彥輝;;基于遺傳算法的車輛路徑規(guī)劃問題研究[J];科技廣場;2008年10期

8 于銳;曹介南;朱培棟;;車輛運輸路徑規(guī)劃問題研究[J];計算機技術(shù)與發(fā)展;2011年01期

9 曾紀鈞;梁哲恒;;監(jiān)督式強化學(xué)習(xí)在路徑規(guī)劃中的應(yīng)用研究[J];計算機應(yīng)用與軟件;2018年10期

10 徐磊;陳璐;;道路養(yǎng)護中的帶隨機時間變量的弧路徑規(guī)劃問題[J];工業(yè)工程;2017年01期

相關(guān)會議論文 前10條

1 賈永基;張麗娜;王長軍;;帶充電設(shè)施的電動汽車路徑規(guī)劃問題研究[A];管理科學(xué)與工程學(xué)會2016年年會論文集[C];2016年

2 裴振奎;劉健;華夏;;求解隨機車輛路徑規(guī)劃問題的混合微粒群算法[A];2008通信理論與技術(shù)新進展——第十三屆全國青年通信學(xué)術(shù)會議論文集（上）[C];2008年

3 唐校輝;黎旭成;劉松靈;陳振武;王卓;;車輛路徑規(guī)劃問題主流求解框架對比分析[A];品質(zhì)交通與協(xié)同共治——2019年中國城市交通規(guī)劃年會論文集[C];2019年

4 馬華偉;范奉偉;胡笑旋;;基于禁忌搜索算法的甩掛運輸路徑規(guī)劃問題研究[A];第十八屆中國管理科學(xué)學(xué)術(shù)年會論文集[C];2016年

5 劉寧琳;唐們;;基于最小繞行網(wǎng)絡(luò)的城市與建筑復(fù)合功能空間路徑生成方法研究[A];數(shù)字技術(shù)·建筑全生命周期——2018年全國建筑院系建筑數(shù)字技術(shù)教學(xué)與研究學(xué)術(shù)研討會論文集[C];2018年

6 張煒;王原;何永明;邢立寧;;基于先排序后聚類原則下解決CARP問題的分割算法[A];第十七屆中國管理科學(xué)學(xué)術(shù)年會論文集[C];2015年

7 馬華偉;胡明明;胡笑旋;;基于模擬退火算法的甩掛運輸路徑規(guī)劃[A];第十八屆中國管理科學(xué)學(xué)術(shù)年會論文集[C];2016年

8 王哲;高峰;;基于地面分類的車輛行駛通過性及路徑規(guī)劃研究[A];中國宇航學(xué)會深空探測技術(shù)專業(yè)委員會第二屆學(xué)術(shù)會議論文集[C];2005年

9 程小軍;崔祜濤;崔平遠;;深空探測器復(fù)雜約束姿態(tài)機動規(guī)劃[A];中國宇航學(xué)會深空探測技術(shù)專業(yè)委員會第五屆學(xué)術(shù)年會論文集[C];2008年

10 王壯;蔡杰進;;基于改進粒子群算法的輻射環(huán)境路徑規(guī)劃研究[A];中國核科學(xué)技術(shù)進展報告（第五卷）——中國核學(xué)會2017年學(xué)術(shù)年會論文集第5冊（核材料分卷、輻射防護分卷）[C];2017年

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

1 耿娜;考慮被困人員生命強度的機器人救援路徑規(guī)劃[D];中國礦業(yè)大學(xué);2016年

2 孟令航;洲際航空編隊飛行路徑規(guī)劃的理論方法研究[D];天津大學(xué);2016年

3 王沛棟;改進蟻群算法及在路徑規(guī)劃問題的應(yīng)用研究[D];中國海洋大學(xué);2012年

4 曾麥脈;城市應(yīng)急路網(wǎng)疏散規(guī)劃的模型與算法研究[D];華中科技大學(xué);2010年

5 朱劍;WSN中節(jié)點布局、定位及移動節(jié)點路徑規(guī)劃問題研究[D];東北大學(xué);2010年

6 孫巖;基于運輸情景的多式聯(lián)運路徑規(guī)劃優(yōu)化建模方法研究[D];北京交通大學(xué);2017年

7 羅亞中;空間最優(yōu)交會路徑規(guī)劃策略研究[D];國防科學(xué)技術(shù)大學(xué);2007年

8 張興;信使機制UAV/UGV多點動態(tài)集結(jié)的協(xié)同規(guī)劃方法研究[D];北京理工大學(xué);2015年

9 武心安;未知環(huán)境下自主式水下潛器路徑規(guī)劃問題研究[D];哈爾濱工程大學(xué);2010年

10 楊鵬;基于自動分治的智能優(yōu)化方法及其應(yīng)用研究[D];中國科學(xué)技術(shù)大學(xué);2017年

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

1 萬千;基于CBS算法的物流分揀多AGV路徑規(guī)劃的研究[D];哈爾濱工業(yè)大學(xué);2018年

2 楊欣潼;社區(qū)居家養(yǎng)老隨機路徑規(guī)劃問題研究[D];廣東工業(yè)大學(xué);2019年

3 崔少華;移動充電服務(wù)的路徑規(guī)劃與設(shè)計問題研究[D];北京交通大學(xué);2019年

4 資元星;區(qū)分任務(wù)緊急性的居家養(yǎng)老預(yù)約調(diào)度與路徑規(guī)劃問題研究[D];華南理工大學(xué);2019年

5 張慧敏;任務(wù)均衡下的快遞末端配送區(qū)域劃分及路徑優(yōu)化研究[D];北京交通大學(xué);2019年

6 葉馥榕;基于Spark的帶三維裝載與時間窗約束的車輛路徑規(guī)劃問題研究[D];廈門大學(xué);2017年

7 楊彥明;基于模因算法的物流車輛路徑規(guī)劃問題求解及實現(xiàn)[D];深圳大學(xué);2018年

8 李松林;AGV路徑規(guī)劃問題設(shè)計與研究[D];廣東工業(yè)大學(xué);2018年

9 劉致遠;擁堵情形下的污染路徑問題研究[D];中國科學(xué)技術(shù)大學(xué);2018年

10 徐俊;帶時間窗和送取貨的車輛路徑規(guī)劃問題研究[D];暨南大學(xué);2018年

本文編號：2604568