基于Ｍｕｌｔｉ－Ａｇｅｎｔ的集裝箱碼頭物流作業(yè)重構(gòu)

［摘 要］ 在介紹集裝箱碼頭物流作業(yè)流程的基礎(chǔ)上，通過引入計算Agent和作業(yè)角色Agent構(gòu)建了基于Multi_Agent的集裝箱碼頭物流作業(yè)重構(gòu)系統(tǒng)結(jié)構(gòu)，并說明了重構(gòu)中作業(yè)角色Agent的工作過程，用強化學(xué)習(xí)算法設(shè)計了作業(yè)角色Agent。接著闡述了在基于Multi_Agent的集裝箱碼頭物流作業(yè)重構(gòu)中計算Agent重構(gòu)模型，以及用對策論和社會規(guī)則相結(jié)合實現(xiàn)相鄰作業(yè)角色Agent的協(xié)調(diào)。最后，以某集裝箱碼頭泊位作業(yè)和岸橋作業(yè)兩相鄰作業(yè)重構(gòu)進(jìn)行了數(shù)據(jù)分析，證明了重構(gòu)的有效性。

［關(guān)鍵詞］ Multi-Agent；重構(gòu)；協(xié)調(diào)；集裝箱碼頭；物流

doi:10.3969/j.issn.1673-0194.2009.10.031

［中圖分類號］F270.7［文獻(xiàn)標(biāo)識碼］A［文章編號］1673-0194（2009）10-0092-04

集裝箱碼頭物流作業(yè)是指集裝箱從到達(dá)港口碼頭至離開港口碼頭中形成的作業(yè)過程。集裝箱碼頭的物流搬運設(shè)備主要有:岸邊集裝箱起重機(簡稱岸橋)、堆場物流橋(簡稱場橋)、集裝箱拖掛車(簡稱集卡)等。岸橋承擔(dān)船舶的物流作業(yè)，場橋承擔(dān)堆場的物流和堆碼作業(yè)，而從碼頭前沿至堆場、堆場內(nèi)箱區(qū)間的水平運輸由集裝箱拖掛車來完成。裝箱船到港后，集裝箱經(jīng)過“進(jìn)入泊位—橋吊卸貨—水平運輸—跨車/龍門吊卸下—堆場堆存—碼頭內(nèi)部運輸—其他運輸方式轉(zhuǎn)運”的流動過程，出口反之。港口集裝箱碼頭作業(yè)主要包括:泊位分配、橋吊作業(yè)、水平運輸（內(nèi)）、堆場堆存、水平運輸（外)、閘口等作業(yè)環(huán)節(jié)。在集裝箱碼頭物流作業(yè)過程中，被調(diào)度的資源包括物流搬運設(shè)備以及泊位、堆場及港區(qū)道路。

在集裝箱碼頭物流作業(yè)沖突有3種沖突類型:{1}資源沖突，如泊位調(diào)度中，多條船在同一時刻爭奪有限的泊位資源，而此時系統(tǒng)并不能同時滿足它們的要求；{2}目標(biāo)沖突，如岸橋調(diào)度作業(yè)目標(biāo)除了合理分配岸橋給各個泊位，還有就是在岸橋作業(yè)不中斷，這必然導(dǎo)致與之相配合的集卡出現(xiàn)排隊等待現(xiàn)象，與集卡調(diào)度作業(yè)的目標(biāo)相悖；{3}結(jié)果沖突，即不同的作業(yè)對同一問題求得的結(jié)果彼此相悖。從總體上來看，所有作業(yè)區(qū)（如碼頭前沿、堆場）總的物流能力是一定的，但分配到各個作業(yè)區(qū)上的資源是有限的，又由于原來物流作業(yè)系統(tǒng)各項作業(yè)是簡單疊加，缺乏有效溝通和協(xié)調(diào)，各項作業(yè)存在沖突。為了有效利用碼頭資源，同時使港口整個的物流作業(yè)時間最小化效率最大化，盡可能避免物流作業(yè)故障、堵塞和排隊等待的現(xiàn)象出現(xiàn)，針對集裝箱碼頭物流作業(yè)系統(tǒng)具有開放性、復(fù)雜性、隨機性的特點，需要對集裝箱碼頭物流作業(yè)進(jìn)行重構(gòu)，提出了基于Multi-Agent的集裝箱碼頭物流作業(yè)重構(gòu)思路。

1 基于Multi-Agent的集裝箱碼頭物流作業(yè)重構(gòu)系統(tǒng)結(jié)構(gòu)［１］

在這里，為每個作業(yè)環(huán)節(jié)設(shè)立一個Agent，稱為作業(yè)角色Agent。將這些作業(yè)角色Agent就港口資源的使用以及由此帶來的資源分配調(diào)度問題結(jié)成的聯(lián)盟稱作計算Agent。角色Agent之間是平等自治的關(guān)系，每個自治的角色Agent代表一個作業(yè)的利益，計算Agent的最終重構(gòu)目標(biāo)并不是使單個作業(yè)的利益最大，而是使整個物流作業(yè)系統(tǒng)利益最大。

對計算Agent a，其結(jié)構(gòu)模型如下：

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當(dāng)前的狀態(tài)，計算Agent的狀態(tài)是各個角色Agent狀態(tài)與公共的資源狀態(tài)和任務(wù)狀態(tài)的聯(lián)合；RMAa是對應(yīng)于a的一個特殊的角色Agent，負(fù)責(zé)管理a的資源，a中的每一個角色Agent更新公共的任務(wù)狀態(tài)，而RMAa通過任務(wù)狀態(tài)，了解資源使用，調(diào)度角色Agent，無須具備角色Agent領(lǐng)域的相關(guān)知識。

對每個作業(yè)角色Agent ra∈RA，

ra=〈era，Sra，csra，Mra，Kra〉。

其中，era是與ra對應(yīng)的計算實體；

Sra是ra的作業(yè)狀態(tài)集csra；是ra的當(dāng)前作業(yè)狀態(tài)集，包括ra當(dāng)前的任務(wù)狀態(tài)、資源狀態(tài)以及與其他角色Agent的關(guān)系等；Mra是ra具有的方法集；Kra是ra的控制與推理核心，與所屬的計算Agent的RME直接交互。

2作業(yè)角色Agent的實現(xiàn)

2.1作業(yè)角色Agent ra的工作過程［２-３］

作業(yè)角色Ａgent在工作過程中一般包含學(xué)習(xí)器、協(xié)調(diào)模塊、通訊模塊、行為決策器和作業(yè)方案模型庫、知識庫等。其工作過程可描述為：作業(yè)狀態(tài)檢測器將檢測到的狀態(tài)信息發(fā)送給角色Ａgent的學(xué)習(xí)器，同時相鄰的角色Ａgent也為學(xué)習(xí)器提供自身的狀態(tài)信息；學(xué)習(xí)器根據(jù)接收到的信息以及有關(guān)經(jīng)驗知識或者學(xué)習(xí)得到的定量信息，為行為決策器提供決策依據(jù)，行為決策器根據(jù)學(xué)習(xí)提供的依據(jù)，選擇行為，并由執(zhí)行裝置執(zhí)行行為。當(dāng)行為作用于作業(yè)后，將改變作業(yè)的作業(yè)狀態(tài)，經(jīng)過一定的時間間隔，作業(yè)狀態(tài)檢測到的作業(yè)狀態(tài)信息傳送給角色Ａgent，并計算得到一個加強信號反饋給學(xué)習(xí)器，學(xué)習(xí)器根據(jù)提供的加強信號修正Ｑ值，并再次根據(jù)作業(yè)態(tài)進(jìn)行決策。以上過程重復(fù)進(jìn)行。如泊位角色Agent工作示意圖如圖1所示。

2.2作業(yè)角色Agent的設(shè)計［４］

這里用強化學(xué)習(xí)方法來設(shè)計作業(yè)角色Agent，采用下面的量作為加強信號：

Ｒ＝?jīng)Q策間隔內(nèi)通過作業(yè)量/作業(yè)排隊的增加量。

Ｑ函數(shù)的定義如下：

Ｑ（s，a）=R(s，a)+γmaxQ(δ(s，a)，a′)。

這里設(shè)計的Q值學(xué)習(xí)算法如下：

（1） 在決策時間點，s為當(dāng)前作業(yè)狀態(tài)，選擇控制目標(biāo)；

（2） 針對控制目標(biāo)，分別對Ｋ，Ｃ行為計算Ｑ值；

（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ù)；α為學(xué)習(xí)系數(shù)；Ｋ，Ｃ行為分別表示保持作業(yè)狀態(tài)和改變作業(yè)狀態(tài)；γ＝e-β(ty-tx)，β為系數(shù)，ty-tx表示兩次決策的時間間隔。

3基于Multi-Agent的集裝箱碼頭物流作業(yè)重構(gòu)設(shè)計

3.1計算Agent的重構(gòu)模型

對包含n個角色Agent的計算Agent i的資源配置可以表示為:

cfgi=〈Ri，αi1，…，αin，βi1，…，βin，γi〉。

其中，Ri為資源描述，包括資源代價；αi1，…，αin，為n個角色Agent所需要的資源份額；βi1，…，βin為n個角色Agent所承擔(dān)的空閑資源份額；γi為空閑資源占總資源的份額。

當(dāng)對計算資源的需求發(fā)生變化時，設(shè)一次重構(gòu)只能有一個角色Agent需要的資源份額發(fā)生變化。不失一般性，設(shè)角色Agent raia需要的資源發(fā)生變化，ain≠α′in，則空閑資源的變化為：

γ′i=αin-α′in+γi。

raia對空閑資源的承擔(dān)，要么β′in=βin，保持不變；要么隨需求變化采用下面公式計算:

3.2重構(gòu)中相鄰作業(yè)角色Agent間協(xié)調(diào)［５-６］

集裝箱碼頭各角色Agent在動態(tài)環(huán)境下執(zhí)行管理者定義的任務(wù)，不斷響應(yīng)碼頭環(huán)境和生產(chǎn)任務(wù)的變化，互相協(xié)調(diào)完成集裝箱物流作業(yè)的任務(wù)，實現(xiàn)集裝箱碼頭物流作業(yè)的重構(gòu)優(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的行為集是相同的，都具有兩種決策行為：Ｃ為改變作業(yè)狀態(tài)；Ｋ為維持作業(yè)狀態(tài)。不同策略的贏得值為角色Agent在學(xué)習(xí)過程中Ｑ值。

3.2.2基于社會規(guī)則的協(xié)調(diào)

假定提出協(xié)調(diào)請求的一方為Ａ，接受協(xié)調(diào)請求的為Ｂ，主要的社會規(guī)則有：

規(guī)則1：若Ｂ的實際作業(yè)量低于某一閾值，則Ｂ應(yīng)執(zhí)行使Ａ獲得最大贏得值的行為；

規(guī)則2：若Ａ與Ｂ進(jìn)行了協(xié)調(diào)，在兩個決策間隔內(nèi)不再接受其他請求；

規(guī)則3：當(dāng)所控作業(yè)均處于作業(yè)高峰時，角色Agent間停止基于對策論的協(xié)調(diào)，而由ＲＭＡa根據(jù)經(jīng)驗知識進(jìn)行協(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)方式有機地結(jié)合起來，充分利用各自的優(yōu)勢，協(xié)調(diào)算法如圖3所示。

4實例分析

這里對相鄰兩作業(yè)重構(gòu)進(jìn)行探討［７-８］。由兩個作業(yè)組成的結(jié)構(gòu)如圖4所示。集裝箱碼頭有泊位資源數(shù)量為6，岸橋資源數(shù)量為10，泊位在一條連續(xù)的岸線上，船舶中的80%為歐美、日韓的大型集裝箱班輪，箱量平均為1 500 TEU；其余20%為支線船舶，箱量平均為700 TEU。船舶到達(dá)時間呈指數(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)，船舶服務(wù)的最大岸橋數(shù)量限制為4~6。

Ｒ＝船舶到達(dá)時間間隔內(nèi)裝卸增加量／船舶排隊增加量，選β＝1.2，重構(gòu)效果如表1所示。

通過分析可以看出，相同條件下，重構(gòu)可以使船舶在港時間減少，岸橋平均物流效率提高。將Ｍulti-Ａgent應(yīng)用在集裝箱碼頭物流作業(yè)重構(gòu)中符合集裝箱碼頭實際作業(yè)的需求， Ｍulti-Ａgent系統(tǒng)的自主性、適應(yīng)性和社會性等特點，使其在解決復(fù)雜問題時具有一定的技術(shù)優(yōu)勢．

主要參考文獻(xiàn)

［1］ 石純一. 基于Agent 的計算［M］.北京：清華大學(xué)出版社，2007.

［2］ 于蒙，王少梅．基于多Agent的集裝箱碼頭生產(chǎn)調(diào)度系統(tǒng)建摸研究［J］.武漢理工大學(xué)學(xué)報:交通科學(xué)與工程版，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)及其在預(yù)測與智能交通系統(tǒng)中的應(yīng)用［M］．上海：華東理工大學(xué)出版社，2004：154-158．

［5］ 運籌學(xué)教材編寫組．運籌學(xué)［M］．北京：清華大學(xué)出版社，1990：389-404．

［6］ 夏新海.集裝箱碼頭裝卸作業(yè)的協(xié)同與優(yōu)化［J］.廣州航海高等專科學(xué)報，2008，16（2）：16-19.

［7］ Gambardella L M， Mastrolilli M， Rizzoli A E， et al. An Ｏptimization Ｍethodology for Ｉntermodal Ｔterminal Ｍanagement［Ｊ］.Journal of Intelligent Manufacturing， 2001，12(5-6) :521-534.

［8］ 韓駿，孫曉娜，靳志宏.集裝箱碼頭泊位與岸橋協(xié)調(diào)調(diào)度優(yōu)化［J］.大連海事大學(xué)學(xué)報， 2008，34(2):117-121.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文