【摘要】：如今,自動導(dǎo)引車(Automated Guided Vehicles,AGVs)廣泛用于制造業(yè)和倉儲業(yè)等領(lǐng)域。例如,在自動化倉儲系統(tǒng)中,占總成本最多的是AGV的運(yùn)輸成本,AGV以電能為能源,配合合理的調(diào)度策略和良好的AGV路徑規(guī)劃策略,能顯著降低運(yùn)輸成本、提升運(yùn)輸效率。因此,本文構(gòu)建了一種分布式多AGV系統(tǒng),并針對多AGV的任務(wù)排序問題和路徑規(guī)劃問題提出了解決方案,主要的創(chuàng)新點(diǎn)如下:(1)在AGV任務(wù)排序問題中,對于具有N項(xiàng)任務(wù)的AGV,現(xiàn)有的基于2-opt局部搜索算符的解決方案需要O(N ~3)的復(fù)雜度來評估所有O(N ~2)種可能的2-opt移動,存在復(fù)雜度高、計算時間長等缺點(diǎn)。因此,本文引入一系列輔助數(shù)據(jù)結(jié)構(gòu)將該方法的時間復(fù)雜度從O(N ~3)降低到O(N ~2)。實(shí)驗(yàn)證明,采用輔助數(shù)據(jù)結(jié)構(gòu)的高效2-opt移動算符可以大大降低估算2-opt移動所需的復(fù)雜度,從而顯著提高搜索效率。(2)為了解決AGV的動態(tài)多任務(wù)排序問題,本文提出一種動態(tài)蒙特卡羅樹搜索算法,利用歷史信息來加快排序過程,及時適應(yīng)動態(tài)變化;其次,使用2-opt移動和3-opt移動構(gòu)成的鄰域交替搜索局部空間,優(yōu)化動態(tài)蒙特卡羅樹搜索算法生成的解決方案。實(shí)驗(yàn)證明,基于動態(tài)蒙特卡羅樹搜索和變鄰域局部搜索算法能顯著提升AGV的運(yùn)輸效率,減少運(yùn)輸成本,從而提高企業(yè)的經(jīng)濟(jì)效益。(3)為了解決多AGV路徑規(guī)劃問題,本文提出了兩階段路徑規(guī)劃方法。首先,采用改進(jìn)的A*算法為各個AGV規(guī)劃一條從任務(wù)起點(diǎn)到任務(wù)終點(diǎn)且不與靜態(tài)障礙物碰撞的路徑。其次,若AGV沿著規(guī)劃路徑行駛時發(fā)生沖突,AGV通過攜帶的傳感器提前感知其周圍兩個單位內(nèi)的其它AGV的運(yùn)行狀態(tài),然后采用基于博弈論的方法消解沖突,避免AGV之間的相互碰撞,更快速的完成任務(wù)。
【圖文】：

京郵電大學(xué)專業(yè)學(xué)位碩士研究生學(xué)位論文 第一章 緒高運(yùn)輸效率。在運(yùn)輸一些特殊的物質(zhì)（如有毒物質(zhì)，放射性物質(zhì)）時，使用 AGV 運(yùn)輸減少人與這些物質(zhì)接觸的機(jī)會，在保護(hù)工人安全方面具有傳統(tǒng)運(yùn)輸無法比擬的優(yōu)勢。不將來，隨著 AGV 技術(shù)的日益成熟，倉儲 AGV 的應(yīng)用將更加廣泛，，市場上常見的倉儲 A圖 1.2 所示。

應(yīng)用簡單的 2-opt 局部搜索后的解決方案解決方案 S 的總距離，用 f(s)表示 Positive_Distance 和 Reversed_DistanceS 中任意兩條能應(yīng)用 2-opt 移動的弧 do使用 Efficient 方法估算對應(yīng)于這兩個弧的 2-opt 移動if 2-opt 移動后的距離小于 f(s) then％ 將相應(yīng)的 2-opt 移動應(yīng)用于 SS 2opt ( S)回到 line 1 繼續(xù)迭代end ifd forurn S
【學(xué)位授予單位】：南京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：TP242;O221

【相似文獻(xiàn)】

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

1 李剛剛;魯習(xí)文;;目標(biāo)為最小化工件運(yùn)輸時間和的單臺機(jī)器帶一個維修時間段的排序問題的一個改進(jìn)算法[J];運(yùn)籌學(xué)學(xué)報;2019年04期

2 茍燕;戴秦;張新功;;具有時間與位置相關(guān)的兩類平行機(jī)排序問題[J];運(yùn)籌學(xué)學(xué)報;2019年04期

3 冉金玉;張新功;;總加權(quán)誤工損失的兩個代理單機(jī)排序問題[J];湖北民族學(xué)院學(xué)報(自然科學(xué)版);2019年01期

4 韓飛;;高中數(shù)學(xué)一道數(shù)列典型題解法的探究[J];數(shù)學(xué)學(xué)習(xí)與研究;2016年23期

5 豆俊梅;孫彩賢;;單機(jī)排序問題的研究[J];數(shù)學(xué)學(xué)習(xí)與研究;2017年24期

6 胡覺亮;楊佳雯;蘇曉彤;董建明;;機(jī)器帶周期性維護(hù)時段的加工與運(yùn)輸協(xié)同排序問題[J];浙江理工大學(xué)學(xué)報(自然科學(xué)版);2016年06期

7 仲維亞;馬曉茹;;帶有運(yùn)輸且加工具有靈活性的無等待流水作業(yè)排序問題[J];運(yùn)籌學(xué)學(xué)報;2016年04期

8 隋楠;羅成新;;具有維護(hù)活動及公共工期的加工時間依賴資源的單機(jī)排序問題[J];沈陽航空航天大學(xué)學(xué)報;2016年06期

9 林浩;何程;;關(guān)于工期分配與加權(quán)誤工數(shù)的雙指標(biāo)排序問題（英文）[J];工程數(shù)學(xué)學(xué)報;2017年01期

10 趙傳立;張蕾;;帶有交貨期窗口和加工時間可控的排序問題[J];沈陽師范大學(xué)學(xué)報(自然科學(xué)版);2016年04期

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

1 張蓮珠;;關(guān)于六角鏈的極值和排序問題的一些結(jié)果[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（上卷）[C];2000年

2 呂緒華;楊漢興;;求解裝配式排序問題的歸并算法及其性能比研究[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（下卷）[C];2000年

3 周支立;李懷祖;;有重疊區(qū)域的兩抓鉤周期性排序問題的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孫世杰;陳躍;;參數(shù)可控的排序問題[A];2001年全國數(shù)學(xué)規(guī)劃及運(yùn)籌研討會論文集[C];2001年

5 張玉忠;;分批排序問題研究[A];中國運(yùn)籌學(xué)會第七屆學(xué)術(shù)交流會論文集（上卷）[C];2004年

6 張玉忠;;分批排序問題研究[A];中國運(yùn)籌學(xué)會第七屆學(xué)術(shù)交流會論文集（中卷）[C];2004年

7 胡榮;呂緒華;;3TMF排序問題的計算復(fù)雜性及分支定界法[A];中國運(yùn)籌學(xué)會第八屆學(xué)術(shù)交流會論文集[C];2006年

8 柏孟卓;唐國春;;加工時間可控的同時加工排序問題[A];2006年中國運(yùn)籌學(xué)會數(shù)學(xué)規(guī)劃分會代表會議暨第六屆學(xué)術(shù)會議論文集[C];2006年

9 樊保強(qiáng);;帶倉儲約束的準(zhǔn)時排序問題[A];中國運(yùn)籌學(xué)會第九屆學(xué)術(shù)交流會論文集[C];2008年

10 吳翠連;;有尺寸的單機(jī)分批排序問題的近似算法[A];中國企業(yè)運(yùn)籌學(xué)[2011（1）][C];2011年

相關(guān)重要報紙文章 前3條

1 楊文波;淺談方位詞“東、西、南、北”的詞語排序問題[N];語言文字周報;2018年

2 山東 趙玉勇;小博士編程[N];電腦報;2004年

3 何靖;全國計算機(jī)應(yīng)用技術(shù)證書考試（NIT）[N];中國電腦教育報;2003年

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

1 李融奇;在線排序和批排序問題研究[D];浙江大學(xué);2018年

2 沈佳煜;不確定情形下若干排序問題的研究[D];南京理工大學(xué);2017年

3 高園;新型排序問題的計算復(fù)雜性研究[D];鄭州大學(xué);2018年

4 殷娜;依賴于資源分配的排序問題研究[D];上海大學(xué);2015年

5 李好好;若干排序問題研究[D];浙江大學(xué);2014年

6 王吉波;工件加工時間可變的現(xiàn)代排序問題[D];大連理工大學(xué);2005年

7 羅潤梓;平行機(jī)半在線排序問題[D];上海大學(xué);2005年

8 季敏;當(dāng)代工業(yè)中的若干排序問題研究[D];浙江大學(xué);2006年

9 葉德仕;通訊網(wǎng)絡(luò)中排序問題的若干在線和高性能算法[D];浙江大學(xué);2005年

10 李文華;關(guān)于分批排序問題的研究[D];鄭州大學(xué);2006年

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

1 李紅;多AGV的多任務(wù)分配與路徑規(guī)劃研究[D];南京郵電大學(xué);2019年

2 陳秋宏;與誤工相關(guān)的雙代理單機(jī)排序問題研究[D];重慶師范大學(xué);2019年

3 馬亞杰;工件具有相似加工時長的排序問題[D];湖南師范大學(xué);2019年

4 叢穩(wěn);工件可拒絕的單機(jī)重新排序問題[D];鄭州大學(xué);2019年

5 曹移林;平行多階段作業(yè)排序問題的研究[D];華東理工大學(xué);2019年

6 康宇紅;具有錯位限制的重新排序問題研究[D];重慶師范大學(xué);2019年

7 姜曉燕;MapReduce排序問題的若干算法研究[D];北京郵電大學(xué);2019年

8 王亞男;具有退化維護(hù)和資源分配的單機(jī)排序問題[D];沈陽師范大學(xué);2019年

9 李石;與資源相關(guān)加工時間可變的單機(jī)排序問題[D];沈陽師范大學(xué);2019年

10 高焰紅;平行批處理機(jī)上不相容族工件的在線排序問題[D];鄭州大學(xué);2019年

本文編號：2693437