集裝箱堆場收發箱管理Multi－Agent系統研究

周鵬飛，方金燦

（大連理工大學 水利工程學院，遼寧 大連 116024）

0 引 言

隨著經濟全球化以及世界貿易的發展，集裝箱運輸持續快速增長.集裝箱吞吐量的增加以及船舶的大型化、高速化給集裝箱碼頭生產管理提出了更高的要求.集裝箱堆場是碼頭生產運作組織的關鍵環節，其運作管理需著眼于碼頭整體生產協調與效率提高.傳統的集中式管理系統缺乏適應性，很難適應資源和決策分散的堆場優化管理.Multi－Agent system（MAS）可通過一系列分布式Agent協商解決復雜問題，具有分布性、協同性、并行求解等優點，符合堆場管理要求.

目前集裝箱碼頭MAS的相關研究報道主要有：Botti［1］提出了集裝箱碼頭的Multi－Agent應用模型；Degano等［2］將Multi－Agent技術應用于多功能集裝箱碼頭進出口裝卸優化，利用Agent對作業干擾事件進行檢測；Yin等［3］針對動態泊位計劃問題設計了基于遺傳算法的泊位優化Agent，建立了分布式Multi－Agent系統；于蒙等［4］建立了基于MAS的集裝箱碼頭智能生產調度系統框架，該系統考慮了泊位、岸橋、集卡等設施和設備的資源利用；徐健等［5］提出了基于MAS的自動碼頭調度算法，通過搜索資源Agent形成時間代價矩陣來指導Agent間的協作.

堆場收箱時箱位優化研究主要有Kim 等［6］考慮箱重等級，運用動態規劃模型求解最少翻箱的堆存方案，Zhang等［7］修正了其翻箱量求解公式；Kang等［8］運用模擬退火算法和仿真研究了箱重分布確定條件下的出口箱箱位分配問題.王斌［9］和周鵬飛［10］假設進出口箱統計規律，分別基于不確定規劃探討了不確定條件下的堆場箱位優選問題.堆場發箱時翻箱優化研究主要有Kim等［11］提出的基于分支定界和啟發式的提箱翻倒箱位優選方法，在此基礎上徐亞等［12］提出了改進的啟發式方法.

從以上分析可以看出，針對集裝箱碼頭的Multi－Agent系統研究大多集中在泊位、場橋等碼頭資源管理方面.堆場收發箱作業作為集裝箱碼頭重要的生產活動，涉及閘口、堆場、龍門吊等多個生產環節，其效率關系到碼頭生產成本和服務水平.本文針對碼頭堆場管理問題，探討堆場收發箱管理Multi－Agent系統，以實現堆場收發箱分布式動態優化管理.

1 堆場收發箱管理Multi－Agent系統架構

1.1 堆場收發箱業務流程

堆場收發箱作業主要在閘口和堆場作業區進行，涉及箱位和堆場龍門吊等管理問題.閘口相關業務有：（1）在收箱過程中，閘口首先收到客戶交箱請求；然后根據箱、車信息和堆場狀態，優化分配箱位；制定并下發外卡的港內行車路線指令.（2）在發箱過程中，閘口首先收到客戶提箱請求，核對箱信息無誤后根據箱位置制定并下發外卡的港內行車路線指令.堆場相關業務有：（1）在收箱過程中，堆場首先根據收箱請求結合堆場狀態優化分配箱位，然后調派龍門吊進行堆箱操作.（2）在發箱過程中，堆場首先根據提箱請求，查詢目標箱位；若需翻箱則優選翻箱落位，然后調派龍門吊進行翻、取箱操作.在堆場收發箱過程中箱位分配不僅決定著堆場翻箱率，而且影響龍門吊、集卡的調配效果，進而影響碼頭整體作業效率，是其重要管理瓶頸.

1.2 系統架構

在對堆場收發箱業務流程分析的基礎上，提出了集裝箱堆場收發箱管理Multi－Agent系統基本架構，如圖1所示.其中：（1）信息Agent，主要功能是提交箱預約和計劃信息的標準化處理，包括根據箱抵港時間、箱重、目的港等信息分配箱屬性值，根據到港時間計劃建立提交箱序列等.（2）閘口Agent，主要功能是接收客戶收發箱請求，轉發客戶收發箱請求，實時查詢堆場狀態.（3）堆場Agent，負責監控堆場狀態，包括進、出口箱區.收箱時負責優化請求及數據集成發送；收箱完成后負責更新箱區數據.提箱時負責獲取并轉發目標箱位、翻箱落位優化請求及數據集成發送；發箱完成后負責更新箱區數據.（4）優化Agent，主要功能是優化求解，包括收箱時根據交箱序列及箱屬性優化分配箱位及發箱時根據貝狀態和提箱序列優化翻箱落位.（5）用戶Agent，主要功能是堆場收發箱過程監控和查詢.（6）數據庫，包括堆場狀態、提交箱序列、調度方案等信息數據.（7）知識庫，主要包括箱操作、數據更新以及消息處理方面的知識規則，以C＃類庫體現，供Agent群使用.

圖1 集裝箱堆場收發箱管理Multi－Agent系統架構Fig.1 Multi－Agent system architecture of container reception and distribution management of container yard

2 Agent模型設計

2.1 Agent基本結構設計

根據系統特點，單Agent按混合型設計，其基本結構如圖2所示.用戶界面初始化模塊負責用戶操作界面的布局和功能初始化，用戶操作界面提供Agent交互接口和計算參數設置或重置功能.對象定義模塊負責對單Agent資源對象或計算參數變量進行定義，如消息隊列對象、消息監聽線程對象等.Agent交互接口及計算參數設置模塊負責設置MAS中Agent交互接口信息，如計算機IP、端口等，并負責設置堆場收發箱優化涉及的優化參數，如箱區和貝規模參數等.消息監聽模塊、消息判斷處理模塊以及消息發送模塊實現Agent交互通信管理功能.其中，消息監聽模塊負責監聽Agent消息并接收；消息判斷處理模塊通過與數據庫和知識庫內的消息隊列匹配逐條分析并處理；消息發送模塊負責發送Agent響應消息.限于篇幅下文主要探討系統關鍵技術實現：堆場Agent消息處理與優化Agent的箱位分配.

圖2 單Agent結構示意圖Fig.2 Structure of single Agent

2.2 堆場Agent的消息處理

堆場Agent是集裝箱堆場收發箱管理系統的核心，其工作流程如圖3所示.當接收到消息后，堆場Agent首先對消息來源進行判斷.若消息來自信息Agent，可判定系統在根據交箱預約信息進行收箱箱位分配，堆場Agent將該消息集成轉發給優化Agent進行滾動調度，形成收箱箱位分配初始方案；若消息來自閘口Agent，需判斷消息請求類型，然后集成轉發箱位優化請求給優化Agent 或指派提箱作業；若消息來自優化Agent，需判斷優化結果消息類型，輸出優化結果并將消息集成轉發給用戶Agent，若需進一步優化求解，堆場Agent將生成并發送優化請求給優化Agent.堆場Agent消息處理偽代碼略.

2.3 優化Agent的箱位分配

2.3.1 收箱箱位分配 碼頭出口箱收箱基本過程是：（1）客戶交箱預約；（2）根據預約交箱及相關信息制定箱位分配計劃，交箱序列動態更新；（3）集裝箱進場時，指定箱位，完成交箱.考慮碼頭出口箱收箱特點，將收箱箱位分配分為兩階段，形成兩級調度：a.根據預約交箱預分配箱位；b.交箱時根據動態交箱序列調整預分配.兩級調度流程如圖4所示.基本流程是：在滾動調度的基礎上，首先根據預約交箱信息，運用禁忌搜索算法得到初始箱位分配方案.當箱進場時，若當前進場箱序列和初始方案箱序列一致，則保持原調度方案不變；若不一致時，則進行實時調度，調整原調度方案，形成再調度方案，并作為下一進場箱的初始調度方案.滾動周期結束時進行下一階段滾動調度.

圖3 堆場Agent工作流程圖Fig.3 Work flow chart of storage yard Agent

圖4 兩級調度流程圖Fig.4 Flow chart of two－levels scheduling

2.3.2 發箱翻箱落位優化 考慮到集裝箱堆場管理實際，本文假設：①翻箱在同貝內進行；②提箱時提箱序列和貝內箱分布已知；③提箱過程中貝內無新箱進場.首先按提箱序列，分別給箱編號為1，2，…，N（N為貝內箱數），提箱越早，編號越小.為表述方便，稱當前翻倒箱所在棧為當前棧，稱貝內其他棧為候選考察棧.本文考慮實際集裝箱翻倒概率不同，改進了文獻［12］的翻箱期望估計公式，在此基礎上提出了基于翻箱期望最小的翻箱落位優化方法.改進后的考察棧翻箱期望E（e，n）估計可用式（1）遞歸求解：

式中：e為考察棧剩余空箱數，n為棧內箱最小編號，p（e，n，P）為箱P翻倒到考察棧可能性代表值，用近似式（2）求解，E（0，n）＝0.

其中a為候選棧最小箱序總和，b為考察棧箱序總和，其他符號解釋同前.

翻箱前后只有當前棧和考察棧的預期翻箱量改變，因此可根據E（e，n）求解當前棧和考察棧在翻箱前后總翻箱增量，選取增加量最小的考察棧為翻倒最佳落箱位.求解過程偽代碼略.

3 Agent的通信機制與協作機制

3.1 Agent的通信機制

該系統采用點對點方式進行通信，為確保Agent群間通信的完整性與實時性，選擇基于TCP／IP協議的Socket進行通信，通信機制如圖5所示.Socket監聽模塊負責監聽并接收字節流消息，經消息轉換模塊將其轉換為消息對象，并將其加入消息對象隊列，基于FIFO 原則處理消息對象隊列.消息識別－處理模塊用于識別消息來源，并根據消息內容執行響應操作；根據響應操作執行結果，消息生成模塊生成響應消息并轉發；知識庫包含消息轉換、識別與處理、生成等的規則和知識.

圖5 Agent通信機制Fig.5 Communication mechanism between agents

模型中，Agent群間通信的消息形式采用C＃自定義消息類AgentMessage，其部分字段及其意義見表1.該消息類包含兩類字段：（1）標志消息發送者、箱型等功能字段；（2）承載求解所需的數據字段，如標記進口箱目標箱號、堆場區段號的字段等.Agent群通信時，發送端生成消息對象并賦值，經XML 序列化后發出；接收端接收到消息后，反序列化數據得到消息對象，根據消息類型和字段值執行響應操作.為解決Tcp消息無邊界問題，采取消息內容與長度同步發送機制.

表1 AgentMessage字段表Tab.1 Field chart of AgentMessage

3.2 Agent的協作機制

Agent間的協作是指Agent相互合作，協調工作，共同完成系統的目標和任務.系統中信息Agent、閘口Agent、堆場Agent、用戶Agent、優化Agent須相互協作，完成各自預定的功能，才能實現堆場收發箱作業優化與管理，其協作過程如圖6所示.

圖6 Agent群協作過程Fig.6 Collaboration process of Agent group

4 系統實現與仿真算例分析

4.1 系統實現

本系統采用Visual C＃進行開發.以棧數×棧高為7×5時發箱為例，假設客戶要求提取1號箱，則該系統各Agent協作完成該任務的過程為（為敘述簡便起見，以下省略了各Agent與用戶Agent交互過程）閘口Agent接收1號箱提箱請求，轉發給堆場Agent；堆場Agent查詢得到1號箱位置，轉發給閘口Agent（制定行車指南），并判定是否需翻箱及優化，若需要，發送優化請求給優化Agent進行箱位優化（可有多個優化Agent實現并行），交互實現1號箱管理作業.閘口Agent與堆場Agent運行效果如圖7所示.堆場收發箱管理MAS通過將收發箱管理任務分解并分配給閘口Agent、堆場Agent、優化Agent 等多個Agent，實現了堆場收發箱的分布式并行管理，并可分擔計算時間成本；同時Agent間的實時動態交互實現了收發箱動態管理.

4.2 收箱管理算例仿真與分析

這里選取10和30個貝的堆場區段作為算例進行分析，區段內設1臺龍門吊，最大堆存系數取90%.滾動調度長度和周期分別取3d和1d.仿真不同r×T（即棧數×額定堆存高度）和交箱動態變化度組合（交箱時間動態變化程度）的M＝50個算例，選取實際中常用的基于壓箱最小與最近規則的啟發式分配方法進行對比分析.

圖7 閘口Agent、堆場Agent運行效果圖Fig.7 Operation effect chart of gate Agent and storage yard Agent

表2給出了50組算例兩種方法的平均對比結果，可以看出，10 和30 貝堆場區段不同條件下，兩級調度算法效果均優于啟發式分配算法，分別在10%和67%以上.這主要得益于兩級調度算法綜合利用了交箱預約信息和實時動態信息，所得解更趨近于全局最優.區段規模越大，兩級調度算法優勢越明顯.通過對比不同交箱時間動態變化度的總成本變化趨勢可看出，動態交箱時間變化度越小，即實時序列與預約序列相差越小，兩級調度算法效果越好.表3給出了不同成本比例下2種算法調度效果對比，可以看出不同成本比例下兩級調度算法調度效果均更好.

表2 不同區段規模4×3、6×4、7×5分布時兩級調度算法與啟發式分配算法調度效果對比Tab.2 Scheduling effect contrast between two－levels scheduling algorithm and heuristic allocation algorithm of 4×3，6×4and 7×5distribution of different yard section scales

表3 不同區段規模4×3分布時不同成本比例下兩級調度算法與啟發式分配算法調度效果對比Tab.3 Scheduling effect contrast between two－levels scheduling algorithm and heuristic allocation algorithm under different cost ratios of 4×3distribution of different yard section scales

在計算時間方面，兩級調度算法中實時調度求解耗費時間不超過0.01s，滿足實時性要求，這里主要分析滾動調度時耗.表4給出了兩種區段規模的滾動調度求解耗時統計結果，可以看出，一般較大規模問題算法求解時間小于2 min，當問題規模非常大（區段規模為30貝，貝規模為7×5，集裝箱約為900 個）時滾動調度耗時平均為249s.由于滾動調度針對預約交箱過程不要求實時求解，并且多個優化Agent求解是分布并行的，可滿足實際應用要求.

表4 不同區段規模下滾動調度耗費時間Tab.4 Rolling scheduling time－consuming under different yard section scales

4.3 發箱管理算例仿真與分析

本文對不同r×T組合的M＝50個算例分別利用IH 算法［12］及提出的MAS 進行求解，結果見表5，其中N＝（r－1）×T＋1，為集裝箱數.可以看出，MAS求解的平均翻箱量小，統計不同規模的貝分布，較IH 算法平均改進均在11%以上，最大相對改進在42%以上，且隨著貝規模的增大，啟發式分配算法較IH 算法改進有增大的趨勢.

表5 翻箱優化算法的平均翻箱量、平均相對改進及最大相對改進Tab.5 Average number of relocation，average relative improvement and maximum relative improvement of container relocation optimization algorithm

5 結 論

堆場收發箱管理是集裝箱碼頭的動態分布式問題.本文在對集裝箱堆場收發箱作業流程分析的基礎上，建立了堆場收發箱管理Multi－Agent系統模型，分析了Agent的基本結構和功能，提出了堆場收發箱作業優化Agent模型和算法，探討了系統的通信和協作機制.系統算例仿真分析表明系統能夠有效發揮Multi－Agent的分布并行動態性優勢，提高收發箱管理效果，驗證了系統的有效性和可行性.

［1］ Botti V J.Multi－Agent system technology in a port container terminal automation［J］.ERCIM News，2004（56）：37－39.

［2］ Degano C F，Pellegrinno A.Multi－Agent coordination and collaboration for control and optimization strategies in an intermodal container terminal ［C］／／IEEE International Engineering Management Conference.Cambridge：IEEE，2002：590－595.

［3］ Yin X F，Khoo L P，Chen C H.A distributed agent system for port planning and scheduling ［J］.Advanced Engineering Informatics，2011，25：403－412.

［4］ 于 蒙，王少梅.基于多Agent的集裝箱碼頭生產調度系統建模研究［J］.武漢理工大學學報，2007，31（3）：494－497.YU Meng，WANG Shao－mei.Research on modeling of Multi－Agent－based scheduling system for container terminal ［J］.Journal of Wuhan University of Technology，2007，31（3）：494－497.（in Chinese）

［5］ 徐 健，陳啟軍.基于MAS的集裝箱自動化碼頭調度算法［J］.系統仿真學報，2009，21（15）：4888－4991.XU Jian，CHEN Qi－jun.Multi－Agent system for scheduling of automated container terminal ［J］.Journal of System Simulation，2009，21（15）：4888－4991.（in Chinese）

［6］ Kim K H，Park Y M，Ryu K R.Deriving decision rules to locate export containers in container yards［J］.European Journal of Operational Research，2000，124：89－101.

［7］ ZHANG Can－rong，CHEN Wei－wei，SHI Le－yuan，et al.A note on deriving decision rules to locate export containers in container yards［J］.European Journal of Operational Research，2010，205（2）：483－485.

［8］ Kang J，Ryu K R，Kim K H.Deriving stacking strategies for export containers with uncertain weight information ［J］.Journal of Intelligent Manufacturing，2006，17（4）：399－410.

［9］ 王 斌.集裝箱碼頭堆場的一種動態隨機堆存方法［J］.系統工程理論與實踐，2007（4）：147－154.WANG Bin.Dynamic and stochastic storage model in a container yard［J］.Systems Engineering－Theory＆Practice，2007（4）：147－154.（in Chinese）.

［10］ 周鵬飛.面向不確定環境的集裝箱碼頭優化調度研究［D］.大連：大連理工大學，2005.ZHOU Peng－fei.Study on resource allocation under uncertainty environments in container terminal［D］.Dalian：Dalian University of Technology，2005.（in Chinese）.

［11］ Kim K H，Hong G P.A heuristic rule for relocating blocks ［J］.Computers and Operations Research，2006，33（4）：940－954.

［12］ 徐 亞，陳秋雙，龍 磊，等.集裝箱倒箱問題的啟發式算法研究［J］.系統仿真學報，2008，20（14）：3666－3669，3674 XU Ya，CHEN Qiu－shuang，LONG Lei，et al.Heuristics for container relocation problem ［J］.Journal of System Simulation，2008，20（14）：3666－3669，3674.（in Chinese）.