《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 其他 > 設(shè)計(jì)應(yīng)用 > 基于多智能體的集裝箱碼頭裝卸設(shè)備協(xié)同調(diào)度
基于多智能體的集裝箱碼頭裝卸設(shè)備協(xié)同調(diào)度
來源:微型機(jī)與應(yīng)用2012年第17期
楊 鵬1,,2,,孫俊清1,,2,,于 青1,,2
(1.天津理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,,天津 300191,; 2.天津市智能計(jì)算及軟件新技術(shù)重點(diǎn)實(shí)
摘要: 針對集裝箱裝卸設(shè)備作業(yè)相互耦合的特點(diǎn),,設(shè)計(jì)了基于多智能體的協(xié)同調(diào)度優(yōu)化模型,。首先應(yīng)用帶有阻塞限制的混合流水車間模型構(gòu)建了調(diào)度模型,,隨后應(yīng)用蟻群算法得到初始方案,最后應(yīng)用多智能體的合同網(wǎng)機(jī)制對方案進(jìn)行調(diào)整,。仿真結(jié)果顯示,,該調(diào)度方法具有較好的可行性。
Abstract:
Key words :

摘  要: 針對集裝箱裝卸設(shè)備作業(yè)相互耦合的特點(diǎn),,設(shè)計(jì)了基于多智能體的協(xié)同調(diào)度優(yōu)化模型,。首先應(yīng)用帶有阻塞限制的混合流水車間模型構(gòu)建了調(diào)度模型,隨后應(yīng)用蟻群算法得到初始方案,,最后應(yīng)用多智能體的合同網(wǎng)機(jī)制對方案進(jìn)行調(diào)整,。仿真結(jié)果顯示,該調(diào)度方法具有較好的可行性,。
關(guān)鍵詞: 集裝箱碼頭,;裝卸設(shè)備;集成調(diào)度,;智能體


 集裝箱碼頭在有限的作業(yè)空間上布置了多種裝卸設(shè)備,,如岸橋、場橋,、集卡和自動導(dǎo)引運(yùn)輸車(AGV)等,,通過這些設(shè)備間的協(xié)調(diào)作業(yè)完成碼頭的物流任務(wù)。在日常運(yùn)作中管理者需要對裝卸設(shè)備進(jìn)行調(diào)度以提高作業(yè)效率,,而這些決策又常常相互影響,、相互制約,因此針對集裝箱碼頭裝卸設(shè)備的調(diào)度和協(xié)調(diào)是一個比較復(fù)雜,、困難的問題,。
1 研究現(xiàn)狀
 近年來,國內(nèi)外很多學(xué)者針對集裝箱碼頭裝卸設(shè)備調(diào)度及優(yōu)化問題展開了研究,。Lee[1]研究了集裝箱港口中岸橋的作業(yè)順序分配問題,建立了考慮橋吊互不干涉約束的混合整數(shù)規(guī)劃模型,,并提出了模型的啟發(fā)式遺傳算法,。計(jì)明軍和靳志宏[2]研究了基于時間最短的集卡線路優(yōu)化模型,并應(yīng)用進(jìn)化算法求解模型,,但未討論集卡配置問題,。這些研究取得了豐碩的成果,但也存在有待改進(jìn)和提高的方面?,F(xiàn)有研究中構(gòu)建的模型大多針對碼頭單個設(shè)備(或單類設(shè)備)的模型,,而忽略了作業(yè)設(shè)備的關(guān)聯(lián)性,因此調(diào)度結(jié)果的可行性相對較差,。
近年來,,基于多Agent的復(fù)雜系統(tǒng)建模的最新發(fā)展,使得開展基于多Agent的碼頭裝卸設(shè)備集成優(yōu)化成為可能,如李斌和李文鋒[3]應(yīng)用多Agent方法對集裝箱碼頭的協(xié)同生產(chǎn)調(diào)度問題進(jìn)行了探討,,提出了集裝箱碼頭集成服務(wù)系統(tǒng)的思想,。楊鵬等[4]將Agent方法應(yīng)用于場橋間的作業(yè)協(xié)調(diào),但研究對象僅限于堆場的場橋作業(yè)環(huán)節(jié),。Agent系統(tǒng)屬于分布式自治系統(tǒng),,具有高度的靈活性,但在決策實(shí)時性方面則往往難以滿足系統(tǒng)要求,。本文應(yīng)用集中式?jīng)Q策和多Agent融合的方法,,對碼頭裝卸設(shè)備的協(xié)同調(diào)度問題開展研究。
2 裝卸設(shè)備調(diào)度集成建模
 本文將裝卸設(shè)備集成調(diào)度問題分解為存在關(guān)聯(lián)性的三個問題:(1)裝卸設(shè)備的集成調(diào)度建模問題,;(2)集成調(diào)度模型的求解問題,;(3)基于多智能體的調(diào)度方案柔性調(diào)整問題。其中問題(1)的建模過程中可以忽略裝卸設(shè)備初始位置及其作業(yè)過程中的相互影響等因素,;而問題(2)得到的調(diào)度結(jié)果只是初始方案(或稱為粗方案),;在問題(3)中需要設(shè)計(jì)設(shè)備Agent的避讓規(guī)則以及作業(yè)任務(wù)調(diào)整規(guī)則,經(jīng)過仿真,、調(diào)整得到最終的細(xì)化調(diào)度方案,。
2.1 問題描述
 集裝箱碼頭存在岸橋作業(yè)、水平運(yùn)輸和場橋作業(yè)三類操作,,對應(yīng)設(shè)備分別為岸橋,、集卡、場橋,。集裝箱作業(yè)需要在三類設(shè)備中依次選擇完成任務(wù),,但不存在環(huán)節(jié)間的緩沖區(qū)?;诖a頭作業(yè)流程的特點(diǎn),,應(yīng)用帶有阻塞限制的混合流水車間模型(NWHFS)對其描述。
 本文基于以下假設(shè)構(gòu)建了集成調(diào)度模型:(1)由于自動導(dǎo)引車(AGV)在國內(nèi)使用較少,,因此假設(shè)裝卸設(shè)備僅包括岸橋,、場橋和內(nèi)部集卡(如無特殊注明,以下集卡均表示內(nèi)部集卡),;(2)模型中僅考慮船舶的卸載作業(yè)(裝船作業(yè)與此類似,,僅順序相反);(3)忽略裝卸設(shè)備作業(yè)細(xì)節(jié),,同類設(shè)備能力相同,,完成相同任務(wù)的耗時與設(shè)備所處位置無關(guān)。



2.2 基于MAS的柔性調(diào)度方案
 考慮將裝卸設(shè)備映射為Agent,,根據(jù)設(shè)備的特點(diǎn)和作業(yè)規(guī)則為Agent設(shè)置沖突避讓規(guī)則,,應(yīng)用合同網(wǎng)機(jī)制為設(shè)備設(shè)計(jì)作業(yè)任務(wù)調(diào)整規(guī)則,。模型中共設(shè)置岸橋、場橋和集卡三類Agent,,下面將對各類Agent的沖突消解機(jī)制和任務(wù)調(diào)整機(jī)制進(jìn)行介紹,。
2.2.1 沖突消解機(jī)制
 場橋Agent的沖突消解機(jī)制:在仿真模型中,為場橋Agent設(shè)置圓形沖突探測區(qū),,一旦出現(xiàn)探測區(qū)的重疊,,則重疊的場橋Agent各自提出修改路徑的代價函數(shù)——修改路徑的移動成本。最終成本最小的Agent調(diào)整路徑,,若成本相同,,則隨機(jī)選擇Agent調(diào)整路徑。
 岸橋Agent的沖突消解機(jī)制:岸橋僅能夠在岸邊做一維移動,,岸橋Agent也具備沖突探測區(qū),,當(dāng)岸橋Agent發(fā)生移動沖突,則選擇外側(cè)岸橋Agent向外側(cè)移動等待,。
 在天津地區(qū)集裝箱碼頭的調(diào)研過程中了解到,,由于驗(yàn)放閘口的入場集卡數(shù)量控制功能,國內(nèi)碼頭集卡作業(yè)中極少出現(xiàn)沖突或死鎖,,因此模型中假設(shè)集卡Agent不存在沖突問題,。
2.2.2 裝卸任務(wù)調(diào)整機(jī)制
 在模型中為裝卸設(shè)備Agent設(shè)置:忙碌、空閑和沖突等待狀態(tài),。當(dāng)Agent正在固定位置執(zhí)行裝卸任務(wù)或向目標(biāo)工位移動,,其狀態(tài)為忙碌;當(dāng)Agent完成其全部裝卸任務(wù)序列,,其狀態(tài)為空閑,;當(dāng)Agent被其他Agent阻擋,其狀態(tài)為沖突等待,。
 當(dāng)系統(tǒng)中出現(xiàn)處于空閑或沖突等待狀態(tài)的Agent,,則忙碌狀態(tài)的設(shè)備Agent將對尚未完成的任務(wù)進(jìn)行招標(biāo)。由空閑和沖突等待狀態(tài)Agent及其自身競標(biāo),,競標(biāo)的報價函數(shù)為完成該裝卸任務(wù)的移動時間,。最終任務(wù)分配給報價最低的Agent,該Agent將其狀態(tài)置為忙碌,,原有Agent從其任務(wù)序列中刪除該任務(wù)。
3 仿真結(jié)果
 為了檢驗(yàn)本文的調(diào)度方法,,本文參考天津某碼頭布局方式,、管制習(xí)慣和參考文獻(xiàn)[5]提供的裝卸設(shè)備參數(shù)進(jìn)行仿真實(shí)驗(yàn),仿真采用的軟件為NetLogo,。應(yīng)用Agent方法進(jìn)行調(diào)度方案修正的記為A試驗(yàn),;未采用MAS方法修正調(diào)度方案的記為B試驗(yàn),。為了確保B試驗(yàn)?zāi)軌蛲瓿扇垦b卸任務(wù),為其設(shè)置了簡單的沖突處理機(jī)制,。仿真結(jié)果如圖1,、圖2所示。

 

 

 圖1中由于裝卸設(shè)備之間缺乏有效的協(xié)調(diào)機(jī)制,,B的總?cè)蝿?wù)完成時間隨任務(wù)量的增長而顯著增加,;由于A中采用了協(xié)商機(jī)制,具備沖突消解措施,,任務(wù)完成時間并未顯著增長,。圖2中卸載的集裝箱數(shù)量為60。在A實(shí)驗(yàn)中,,采用了基于Agent的沖突條件和任務(wù)再分配機(jī)制,,因此,裝卸設(shè)備間存在協(xié)作和協(xié)調(diào)關(guān)系,,能夠有效發(fā)揮裝卸設(shè)備的潛力,;而由于設(shè)備移動路徑?jīng)_突的存在,并且缺乏任務(wù)分配平衡機(jī)制,,因此B實(shí)驗(yàn)中,,總完工時間并未隨裝卸設(shè)備數(shù)量的增加而顯著降低。
 在本文的研究中,,MAS模型僅用于最初調(diào)度方案的調(diào)整和優(yōu)化,,如果初始方案不可行度較高,則最終調(diào)整方案的結(jié)果也較差,。今后將考慮根據(jù)Agent仿真結(jié)果構(gòu)建禁忌表,,在Agent仿真結(jié)果的基礎(chǔ)上應(yīng)用算法再優(yōu)化,并且還要考慮裝卸設(shè)備作業(yè)時間不確定性等方面的因素,,使得模型更加真實(shí)地反映集裝箱碼頭的操作進(jìn)程,。
參考文獻(xiàn)
[1] LEE D H, Wang Huiqiu,, Miao Lixin. Quay crane scheduling with non-interference constraints in port container terminals[J]. Transportation Research part E,, 2008, 44:124- 135
[2] 計(jì)明軍,,靳志宏.集裝箱碼頭集卡與岸橋協(xié)調(diào)調(diào)度優(yōu)化[J].復(fù)旦學(xué)報,,2007(8):476-480.
[3] 李斌,李文鋒.基于MAS的集裝箱碼頭物流系統(tǒng)協(xié)同生產(chǎn)調(diào)度體系[J].計(jì)算機(jī)集成制造系統(tǒng),,2011,,11(17):2502-2513.
[4] 楊鵬,柴小燕,,孫俊清.集裝箱碼頭場橋協(xié)同調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用,,2011,,47(1):231-234
[5] 張煌,王少梅.基于遺傳算法的泊位連續(xù)化動態(tài)調(diào)度研究[J].系統(tǒng)仿真學(xué)報,,2007,,19(10):2161-2164.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。