[摘 要] 在介紹集裝箱碼頭物流作業(yè)流程的基礎上,通過引入計算Agent和作業(yè)角色Agent構建了基于Multi_Agent的集裝箱碼頭物流作業(yè)重構系統(tǒng)結構,并說明了重構中作業(yè)角色Agent的工作過程,用強化學習算法設計了作業(yè)角色Agent。接著闡述了在基于Multi_Agent的集裝箱碼頭物流作業(yè)重構中計算Agent重構模型,以及用對策論和社會規(guī)則相結合實現(xiàn)相鄰作業(yè)角色Agent的協(xié)調(diào)。最后,以某集裝箱碼頭泊位作業(yè)和岸橋作業(yè)兩相鄰作業(yè)重構進行了數(shù)據(jù)分析,證明了重構的有效性。
[關鍵詞] Multi-Agent;重構;協(xié)調(diào);集裝箱碼頭;物流
doi:10.3969/j.issn.1673-0194.2009.10.031
[中圖分類號]F270.7[文獻標識碼]A[文章編號]1673-0194(2009)10-0092-04
集裝箱碼頭物流作業(yè)是指集裝箱從到達港口碼頭至離開港口碼頭中形成的作業(yè)過程。集裝箱碼頭的物流搬運設備主要有:岸邊集裝箱起重機(簡稱岸橋)、堆場物流橋(簡稱場橋)、集裝箱拖掛車(簡稱集卡)等。岸橋承擔船舶的物流作業(yè),場橋承擔堆場的物流和堆碼作業(yè),而從碼頭前沿至堆場、堆場內(nèi)箱區(qū)間的水平運輸由集裝箱拖掛車來完成。裝箱船到港后,集裝箱經(jīng)過“進入泊位—橋吊卸貨—水平運輸—跨車/龍門吊卸下—堆場堆存—碼頭內(nèi)部運輸—其他運輸方式轉(zhuǎn)運”的流動過程,出口反之。港口集裝箱碼頭作業(yè)主要包括:泊位分配、橋吊作業(yè)、水平運輸(內(nèi))、堆場堆存、水平運輸(外)、閘口等作業(yè)環(huán)節(jié)。在集裝箱碼頭物流作業(yè)過程中,被調(diào)度的資源包括物流搬運設備以及泊位、堆場及港區(qū)道路。
在集裝箱碼頭物流作業(yè)沖突有3種沖突類型:{1}資源沖突,如泊位調(diào)度中,多條船在同一時刻爭奪有限的泊位資源,而此時系統(tǒng)并不能同時滿足它們的要求;{2}目標沖突,如岸橋調(diào)度作業(yè)目標除了合理分配岸橋給各個泊位,還有就是在岸橋作業(yè)不中斷,這必然導致與之相配合的集卡出現(xiàn)排隊等待現(xiàn)象,與集卡調(diào)度作業(yè)的目標相悖;{3}結果沖突,即不同的作業(yè)對同一問題求得的結果彼此相悖。從總體上來看,所有作業(yè)區(qū)(如碼頭前沿、堆場)總的物流能力是一定的,但分配到各個作業(yè)區(qū)上的資源是有限的,又由于原來物流作業(yè)系統(tǒng)各項作業(yè)是簡單疊加,缺乏有效溝通和協(xié)調(diào),各項作業(yè)存在沖突。為了有效利用碼頭資源,同時使港口整個的物流作業(yè)時間最小化效率最大化,盡可能避免物流作業(yè)故障、堵塞和排隊等待的現(xiàn)象出現(xiàn),針對集裝箱碼頭物流作業(yè)系統(tǒng)具有開放性、復雜性、隨機性的特點,需要對集裝箱碼頭物流作業(yè)進行重構,提出了基于Multi-Agent的集裝箱碼頭物流作業(yè)重構思路。
1 基于Multi-Agent的集裝箱碼頭物流作業(yè)重構系統(tǒng)結構[1]
在這里,為每個作業(yè)環(huán)節(jié)設立一個Agent,稱為作業(yè)角色Agent。將這些作業(yè)角色Agent就港口資源的使用以及由此帶來的資源分配調(diào)度問題結成的聯(lián)盟稱作計算Agent。角色Agent之間是平等自治的關系,每個自治的角色Agent代表一個作業(yè)的利益,計算Agent的最終重構目標并不是使單個作業(yè)的利益最大,而是使整個物流作業(yè)系統(tǒng)利益最大。
對計算Agent a,其結構模型如下:
a=〈Ea,RAa,Sa,caa,RMAa〉。
其中,Ea是a包含的計算實體集;RAa是a包含的角色Agent集;
RAa={泊位作業(yè)Agent,橋吊作業(yè)Agent,水平運輸Ⅰ-Agent,堆場作業(yè)Agent,水平運輸Ⅱ-Agent,閘口作業(yè)Agent}
Sa是a的可能狀態(tài)集;caa是a當前的狀態(tài),計算Agent的狀態(tài)是各個角色Agent狀態(tài)與公共的資源狀態(tài)和任務狀態(tài)的聯(lián)合;RMAa是對應于a的一個特殊的角色Agent,負責管理a的資源,a中的每一個角色Agent更新公共的任務狀態(tài),而RMAa通過任務狀態(tài),了解資源使用,調(diào)度角色Agent,無須具備角色Agent領域的相關知識。
對每個作業(yè)角色Agent ra∈RA,
ra=〈era,Sra,csra,Mra,Kra〉。
其中,era是與ra對應的計算實體;
Sra是ra的作業(yè)狀態(tài)集csra;是ra的當前作業(yè)狀態(tài)集,包括ra當前的任務狀態(tài)、資源狀態(tài)以及與其他角色Agent的關系等;Mra是ra具有的方法集;Kra是ra的控制與推理核心,與所屬的計算Agent的RME直接交互。
2作業(yè)角色Agent的實現(xiàn)
2.1作業(yè)角色Agent ra的工作過程[2-3]
作業(yè)角色Agent在工作過程中一般包含學習器、協(xié)調(diào)模塊、通訊模塊、行為決策器和作業(yè)方案模型庫、知識庫等。其工作過程可描述為:作業(yè)狀態(tài)檢測器將檢測到的狀態(tài)信息發(fā)送給角色Agent的學習器,同時相鄰的角色Agent也為學習器提供自身的狀態(tài)信息;學習器根據(jù)接收到的信息以及有關經(jīng)驗知識或者學習得到的定量信息,為行為決策器提供決策依據(jù),行為決策器根據(jù)學習提供的依據(jù),選擇行為,并由執(zhí)行裝置執(zhí)行行為。當行為作用于作業(yè)后,將改變作業(yè)的作業(yè)狀態(tài),經(jīng)過一定的時間間隔,作業(yè)狀態(tài)檢測到的作業(yè)狀態(tài)信息傳送給角色Agent,并計算得到一個加強信號反饋給學習器,學習器根據(jù)提供的加強信號修正Q值,并再次根據(jù)作業(yè)態(tài)進行決策。以上過程重復進行。如泊位角色Agent工作示意圖如圖1所示。
2.2作業(yè)角色Agent的設計[4]
這里用強化學習方法來設計作業(yè)角色Agent,采用下面的量作為加強信號:
R=?jīng)Q策間隔內(nèi)通過作業(yè)量/作業(yè)排隊的增加量。
Q函數(shù)的定義如下:
Q(s,a)=R(s,a)+γmaxQ(δ(s,a),a′)。
這里設計的Q值學習算法如下:
(1) 在決策時間點,s為當前作業(yè)狀態(tài),選擇控制目標;
(2) 針對控制目標,分別對K,C行為計算Q值;
(3) 根據(jù)一定的原則,選擇行為 a(K或C);
(4) 執(zhí)行行為a, 觀察新的作業(yè)狀態(tài)s′和R值;
(5) 調(diào)整輸入為狀態(tài)S的Q值,調(diào)整規(guī)則為:
(6)轉(zhuǎn)向步驟(1)。其中,γ為折扣系數(shù);α為學習系數(shù);K,C行為分別表示保持作業(yè)狀態(tài)和改變作業(yè)狀態(tài);γ=e-β(ty-tx),β為系數(shù),ty-tx表示兩次決策的時間間隔。
3基于Multi-Agent的集裝箱碼頭物流作業(yè)重構設計
3.1計算Agent的重構模型
對包含n個角色Agent的計算Agent i的資源配置可以表示為:
cfgi=〈Ri,αi1,…,αin,βi1,…,βin,γi〉。
其中,Ri為資源描述,包括資源代價;αi1,…,αin,為n個角色Agent所需要的資源份額;βi1,…,βin為n個角色Agent所承擔的空閑資源份額;γi為空閑資源占總資源的份額。
當對計算資源的需求發(fā)生變化時,設一次重構只能有一個角色Agent需要的資源份額發(fā)生變化。不失一般性,設角色Agent raia需要的資源發(fā)生變化,ain≠α′in,則空閑資源的變化為:
γ′i=αin-α′in+γi。
raia對空閑資源的承擔,要么β′in=βin,保持不變;要么隨需求變化采用下面公式計算:
3.2重構中相鄰作業(yè)角色Agent間協(xié)調(diào)[5-6]
集裝箱碼頭各角色Agent在動態(tài)環(huán)境下執(zhí)行管理者定義的任務,不斷響應碼頭環(huán)境和生產(chǎn)任務的變化,互相協(xié)調(diào)完成集裝箱物流作業(yè)的任務,實現(xiàn)集裝箱碼頭物流作業(yè)的重構優(yōu)化。作業(yè)角色Agent間的協(xié)調(diào)框架如圖2所示。
對于角色Agent間的協(xié)調(diào),利用對策論中合作型談判解的理論。
3.2.1基于對策論的協(xié)調(diào)
在集裝箱碼頭物流作業(yè)系統(tǒng)中,對策的類型是二人非零和合作型對策。對策采用雙矩陣形式來表示:Γ=(Agent A,AgentB;A,B),分別表示Agent A,AgentB的贏得矩陣。每個角色Agent的行為集是相同的,都具有兩種決策行為:C為改變作業(yè)狀態(tài);K為維持作業(yè)狀態(tài)。不同策略的贏得值為角色Agent在學習過程中Q值。
3.2.2基于社會規(guī)則的協(xié)調(diào)
假定提出協(xié)調(diào)請求的一方為A,接受協(xié)調(diào)請求的為B,主要的社會規(guī)則有:
規(guī)則1:若B的實際作業(yè)量低于某一閾值,則B應執(zhí)行使A獲得最大贏得值的行為;
規(guī)則2:若A與B進行了協(xié)調(diào),在兩個決策間隔內(nèi)不再接受其他請求;
規(guī)則3:當所控作業(yè)均處于作業(yè)高峰時,角色Agent間停止基于對策論的協(xié)調(diào),而由RMAa根據(jù)經(jīng)驗知識進行協(xié)調(diào)。
3.2.3 協(xié)調(diào)的實現(xiàn)
角色Agent之間的協(xié)調(diào)涉及基于對策論的顯式協(xié)調(diào)和基于社會規(guī)則的隱式協(xié)調(diào)兩種方式,在實現(xiàn)的過程中,將這兩種協(xié)調(diào)方式有機地結合起來,充分利用各自的優(yōu)勢,協(xié)調(diào)算法如圖3所示。
4實例分析
這里對相鄰兩作業(yè)重構進行探討[7-8]。由兩個作業(yè)組成的結構如圖4所示。集裝箱碼頭有泊位資源數(shù)量為6,岸橋資源數(shù)量為10,泊位在一條連續(xù)的岸線上,船舶中的80%為歐美、日韓的大型集裝箱班輪,箱量平均為1 500 TEU;其余20%為支線船舶,箱量平均為700 TEU。船舶到達時間呈指數(shù)分布,平均到港時間間隔為3、3.9、4.8,到港船舶數(shù)量90、80、55。船型分為4類,服從正態(tài)分布,箱量根據(jù)船型隨機選取,選取范圍為:{1}300~800;{2}800~1 200;{3}1 200~ 2 000;{4}2 000~4 000,生成的平均箱量為1 190。船舶要求的裝卸時限根據(jù)裝卸量生成,范圍為4~18h,也呈正態(tài)分布。岸橋的理想裝卸效率為40 TEU/(臺·h),船舶服務的最大岸橋數(shù)量限制為4~6。
R=船舶到達時間間隔內(nèi)裝卸增加量/船舶排隊增加量,選β=1.2,重構效果如表1所示。
通過分析可以看出,相同條件下,重構可以使船舶在港時間減少,岸橋平均物流效率提高。將Multi-Agent應用在集裝箱碼頭物流作業(yè)重構中符合集裝箱碼頭實際作業(yè)的需求, Multi-Agent系統(tǒng)的自主性、適應性和社會性等特點,使其在解決復雜問題時具有一定的技術優(yōu)勢.
主要參考文獻
[1] 石純一. 基于Agent 的計算[M].北京:清華大學出版社,2007.
[2] 于蒙,王少梅.基于多Agent的集裝箱碼頭生產(chǎn)調(diào)度系統(tǒng)建摸研究[J].武漢理工大學學報:交通科學與工程版,2007(6) :495-497.
[3] Legato P,Mazza R M.Berth Planning and Resources Optimization at a Container Terminal via Discrete Event Simulation[J].European Journal of Operation Research,2001,133(3):537-547.
[4] 李英.多Agent系統(tǒng)及其在預測與智能交通系統(tǒng)中的應用[M].上海:華東理工大學出版社,2004:154-158.
[5] 運籌學教材編寫組.運籌學[M].北京:清華大學出版社,1990:389-404.
[6] 夏新海.集裝箱碼頭裝卸作業(yè)的協(xié)同與優(yōu)化[J].廣州航海高等專科學報,2008,16(2):16-19.
[7] Gambardella L M, Mastrolilli M, Rizzoli A E, et al. An Optimization Methodology for Intermodal Tterminal Management[J].Journal of Intelligent Manufacturing, 2001,12(5-6) :521-534.
[8] 韓駿,孫曉娜,靳志宏.集裝箱碼頭泊位與岸橋協(xié)調(diào)調(diào)度優(yōu)化[J].大連海事大學學報, 2008,34(2):117-121.
注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文