周鵬飛，方金燦

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

0 引 言

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

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

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

從以上分析可以看出，針對集裝箱碼頭的Multi－Agent系統(tǒng)研究大多集中在泊位、場橋等碼頭資源管理方面.堆場收發(fā)箱作業(yè)作為集裝箱碼頭重要的生產(chǎn)活動，涉及閘口、堆場、龍門吊等多個生產(chǎn)環(huán)節(jié)，其效率關(guān)系到碼頭生產(chǎn)成本和服務(wù)水平.本文針對碼頭堆場管理問題，探討堆場收發(fā)箱管理Multi－Agent系統(tǒng)，以實現(xiàn)堆場收發(fā)箱分布式動態(tài)優(yōu)化管理.

1 堆場收發(fā)箱管理Multi－Agent系統(tǒng)架構(gòu)

1.1 堆場收發(fā)箱業(yè)務(wù)流程

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

1.2 系統(tǒng)架構(gòu)

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

圖1 集裝箱堆場收發(fā)箱管理Multi－Agent系統(tǒng)架構(gòu)Fig.1 Multi－Agent system architecture of container reception and distribution management of container yard

2 Agent模型設(shè)計

2.1 Agent基本結(jié)構(gòu)設(shè)計

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

圖2 單Agent結(jié)構(gòu)示意圖Fig.2 Structure of single Agent

2.2 堆場Agent的消息處理

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

2.3 優(yōu)化Agent的箱位分配

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

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

圖4 兩級調(diào)度流程圖Fig.4 Flow chart of two－levels scheduling

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

式中：e為考察棧剩余空箱數(shù)，n為棧內(nèi)箱最小編號，p（e，n，P）為箱P翻倒到考察?？赡苄源碇担媒剖剑?）求解，E（0，n）＝0.

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

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

3 Agent的通信機制與協(xié)作機制

3.1 Agent的通信機制

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

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

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

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

3.2 Agent的協(xié)作機制

Agent間的協(xié)作是指Agent相互合作，協(xié)調(diào)工作，共同完成系統(tǒng)的目標和任務(wù).系統(tǒng)中信息Agent、閘口Agent、堆場Agent、用戶Agent、優(yōu)化Agent須相互協(xié)作，完成各自預(yù)定的功能，才能實現(xiàn)堆場收發(fā)箱作業(yè)優(yōu)化與管理，其協(xié)作過程如圖6所示.

圖6 Agent群協(xié)作過程Fig.6 Collaboration process of Agent group

4 系統(tǒng)實現(xiàn)與仿真算例分析

4.1 系統(tǒng)實現(xiàn)

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

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

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

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

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

表2 不同區(qū)段規(guī)模4×3、6×4、7×5分布時兩級調(diào)度算法與啟發(fā)式分配算法調(diào)度效果對比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 不同區(qū)段規(guī)模4×3分布時不同成本比例下兩級調(diào)度算法與啟發(fā)式分配算法調(diào)度效果對比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

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

表4 不同區(qū)段規(guī)模下滾動調(diào)度耗費時間Tab.4 Rolling scheduling time－consuming under different yard section scales

4.3 發(fā)箱管理算例仿真與分析

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

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

5 結(jié) 論

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

［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的集裝箱碼頭生產(chǎn)調(diào)度系統(tǒng)建模研究［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的集裝箱自動化碼頭調(diào)度算法［J］.系統(tǒng)仿真學報，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］ 王 斌.集裝箱碼頭堆場的一種動態(tài)隨機堆存方法［J］.系統(tǒng)工程理論與實踐，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］ 周鵬飛.面向不確定環(huán)境的集裝箱碼頭優(yōu)化調(diào)度研究［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］ 徐 亞，陳秋雙，龍 磊，等.集裝箱倒箱問題的啟發(fā)式算法研究［J］.系統(tǒng)仿真學報，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）.