基于多Agent的偏好泊位約束下泊位-岸橋分配

朱碩博，金永賀（上海海事大學信息工程學院，上海　201306）

基于多Agent的偏好泊位約束下泊位-岸橋分配

朱碩博，金永賀
（上海海事大學信息工程學院，上海201306）

泊位和岸橋是碼頭前沿最寶貴的資源，為其設計合理調度機制能夠獲得更高的效能。考慮連續泊位的岸線，加入偏好泊位約束條件，以最小化偏離偏好泊位成本為目標函數，結合多Agent的智能化特點，提出基于多Agent的聯合調度模型，在模型基礎上設計分步的遺傳算法，實現高效的泊位岸橋聯合調度。并用實驗證明模型和算法的有效性，實驗結果驗證引入偏好泊位約束條件確實能提高碼頭作業效率，降低因偏離偏好泊位帶來的成本。

連續泊位；偏好泊位；多Agent；遺傳算法；智能化

0　引言

隨著經濟全球化以及世界貿易的高速發展，集裝箱水路運輸逐漸呈現船舶的大型化、高速化態勢，這也對碼頭裝卸設備的合理配置提出了更高的要求。泊位和岸橋的分配是碼頭前沿作業的首要環節，因而設計合理的靠泊計劃和岸橋分配策略是提高集裝箱碼頭作業效率的關鍵。

Imai等［1］針對離散的泊位-岸橋調度建立了優化模型，根據船舶總在港時間最小化為原則安排服務順序。Liang等［2］以船舶總在港時間最小化為目標建立模型，采用遺傳算法與啟發式算法相結合求解。高超鋒［3］針對多個岸橋并行作業時相互干擾的問題，研究了岸橋并行作業效率約束下泊位分配與岸橋調度問題。杜衛華等［4］在泊位岸橋集成調度中加入岸橋移動約束條件，設計算法模型，解決了岸橋頻繁移動導致的岸橋作業相互干擾及資源利用率低的問題。

在以上的文獻中都沒有提及偏好泊位的概念，實際船舶在靠泊作業時是存在偏好泊位約束的，因為船舶在靠泊作業過程所需要的岸橋、集卡、堆場及工作人員已經做好準備，這個泊位就是該船舶的偏好泊位。P. Legato等［5］考慮船舶偏好泊位和時間，以船舶作業時間和岸橋使用數量最少為目標建立泊位分配和岸橋調度模型。樂美龍等［6］針對泊位和岸橋聯合分配問題，考慮偏好泊位等7個影響因素的泊位-岸橋集成分配問題。但也只是簡單地介紹了偏好泊位作為約束條件之一的分配問題，沒有給出具體的偏好泊位對調度的模型優化。鄭子龍等［7］針對離散泊位提出了偏好泊位約束下的泊位分配問題，對離散泊位分配建模優化，但是現在泊位發展的趨勢是連續泊位，連續泊位越來越符合實際船舶靠泊與碼頭作業需要。

隨著多Agent的智能系統建模的發展，基于多Agent的泊位岸橋調度集成優化成為可能。周鵬飛［8］針對碼頭堆場管理問題，設計了堆場收發箱多Agent管理系統，實現堆場收發箱分布式動態優化管理。李尤豐［9］通過對集裝箱碼頭裝卸作業環節的設備設施的分配調度特點及各子系統間的關系，建立基于多Agent系統的生產調度模型。王祥雪等［10］提出的基于多Agent系統的協同作業模型，設計了系統的Agent層次模型和實線層類圖，優化集裝箱裝卸最短路徑搜索方案。李斌［11］針對集裝箱碼頭物流系統的協同生產問題，建立基于Agent的計算的集裝箱碼頭物流系統優化，得出一種高魯棒的協同生產體系。鄒金松［12］通過分析集裝箱碼頭智能操作系統框架，對系統的功能進行設計，實現集裝箱碼頭智能操作系統。

當前已有一些文獻是針對動態連續型泊位和岸橋聯合調度進行優化的研究，但是考慮偏好泊位這一約束，并結合多Agent智能特點進行研究的文獻很少。本文提出的基于多Agent的偏好泊位約束下連續泊位分配和岸橋聯合調度問題，建立了聯合調度的多Agent模型，并通過算法設計以及仿真模擬實驗，分析加入偏好泊位約束條件對船舶的靠泊影響，以及對泊位和岸橋的分配的影響，這對于進一步優化泊位-岸橋調度具有實際意義。

1　問題描述

1.1泊位-岸橋聯合調度問題

泊位-岸橋聯合調度是指在某段時間內，碼頭調度人員根據各類資源的狀態和調度策略，為每艘即將到港作業的船舶分配最佳靠泊位置和靠泊順序，并根據船舶作業要求調配相應數量的岸橋，以期望得到最優的服務和最高的作業效率。在實際的操作中，泊位分配和岸橋調度是兩個緊密相關的過程，岸橋不是固定在一個位置不動的，而是根據任務需要沿著作業線移動，本文是將泊位和岸橋兩者的調度聯合起來考慮的。

在碼頭實際靠泊作業中，每艘船舶都有其偏好的泊位，船舶在靠泊后，參與作業的岸橋數以及堆場運輸的協調性等都是碼頭作業效率的影響因素，船舶停靠在其偏好泊位上能夠大幅提高作業效率。對于偏好泊位的描述，可以用圖1-1來表示，其中橫軸代表泊位岸線，縱軸代表時間；Δbi表示船舶i偏離偏好泊位的距離；Tpr表示船舶i延遲到港時間；Tqs表示船舶i延遲離港時間。

圖1　船舶靠泊時空圖

1.2Agent的結構設計

根據調度框架結構的需要，設計了混合型的Agent結構，其中，動態管理Agent、岸橋調度Agent和泊位分配Agent作為管理者，側重的是思考型；船舶Agent、岸橋Agent和泊位Agent作為任務的執行者，側重的是反應型。Agent內部是由感知器、緩沖區、推理機、知識庫、響應器和注冊機組成，即Agent=＜P，B，D，K，R，I＞。圖2給出了岸橋調度Agent作為管理者的內部結構，其他Agent內部結構與其類似，區別在于推理機的不同。

P：感知器。實時監聽發送給Agent的信息，實現對外部環境的主動感知。

B：緩沖區。存放發送給Agent的消息隊列。

D：推理機。是Agent的核心組成，包括推理、決策分析、優化及評估等功能，不同類型的Agent的推理機功能不同。

K：知識庫。存放Agent相關知識、規則的數據庫。

R：響應器。負責向其他Agent發送消息。

I：注冊機。Agent中變量的聲明、定義和初始化。

圖2　岸橋調度Agent的內部結構

1.3泊位岸橋調度多Agent系統框架模型

碼頭泊位岸橋聯合調度是一個復雜、動態的過程，本文在對泊位、岸橋業務流程深入分析的基礎上，提出了基于多Agent的泊位-岸橋聯合調度系統框架。系統由以下幾類Agent組成：船舶Agent、動態管理Agent、泊位Agent、岸橋Agent、泊位分配Agent、岸橋調度A-gent。圖3給出了集裝箱碼頭多Agent系統結構框架模型。

圖3　集裝箱碼頭多Agent系統結構框架模型

該模型中，動態管理Agent的功能是負責控制和監督整個任務的具體執行；岸線上每個泊位對應一個泊位Agent，實時更新泊位的狀態信息，將結果及時反饋給泊位分配Agent，并接受泊位分配Agent的靠泊分配任務；岸線上每個岸橋對應一個岸橋Agent，實時將岸橋狀態信息反饋給岸橋調度Agent，接受岸橋調度A-gent的調度；泊位分配Agent負責給各個泊位Agent發送指令，查詢泊位Agent的實時信息，接收動態管理A-gent的實時調度請求，根據泊位Agent的實時狀態做出回應；岸橋調度Agent接收動態管理Agent的實時調度請求，根據岸橋Agent的狀態信息對岸橋進行調度，并進行實時反饋。

2　數學模型

船舶在靠泊過程中偏離偏好泊位，將會降低碼頭裝卸作業效率，導致延遲離港以及延遲到港的問題，從而增加碼頭作業成本。這些問題是不可避免的，如何將偏離帶來的損失控制在最小范圍，這是一個復雜的調度問題。本文在連續泊位條件下，加入偏離偏好泊位因素與因偏離偏好泊位對岸橋調度造成的影響的混合整數規劃模型。

模型基于以下的假設條件：

（1）岸線有滿足船舶靠泊的一切條件；

（2）每艘船舶都有一個偏好的停泊位置；

（3）每艘船舶都有最小岸橋需求數和最大岸橋需求數，本文忽略岸橋移動時間；

船舶作業時間連續，不會中斷，相鄰岸橋之間存在干擾。為了便于模型的建立，引入以下符號：

2.1參數

A：到港船舶集合，A=｛1，2，…，K｝；

B：港口的可用岸橋總數量；

L：港口岸線的總長度；

li：船舶i的長度；

Ci：能夠同時分配給船舶i的岸橋數變化范圍，Ci=

pi：船舶i的預期到港時間；

qi：船舶i的預期離港時間；

wi：船舶i的最遲離港時間；

α：偏離偏好泊位系數；

2.2決策變量

bi：船舶i實際靠泊位置；

Δbi：船舶i實際靠泊位置偏離偏好位置的距離，Δbi=|Δbi-bi|；

ri：船舶i實際到港作業時間；

si：船舶i完成作業實際離港時間；

2.3目標函數與約束條件

該模型主要考慮的是船舶在靠泊過程中偏離偏好泊位靠泊，系統重新分配岸橋產生的成本，船舶Δbi'個泊位偏差距離共需要（1+·Δbi）·mi個岸橋服務時間；同時，在目標函數中還應該體現出兩個時間差的成本，一是延遲離港時間成本，二是延遲到港的時間成本。該模型的目標函數為：

此模型給出了船舶的靠泊位置、靠泊時間和在每個時間點服務于該船舶的岸橋數量。目標函數式（1）表示船舶在港停泊的最小總成本；式（2）-（4）分別給出目標函數式中三個成本的表達式，（2）式表示因偏離偏好泊位所引起的岸橋變動成本，（3）式表示遲于預期離港時間產生的成本，（4）式表示遲于到港時間產生的成本；（5）式限制了船舶的停泊位置；（6）式表示船舶離港時間與靠泊時間關系；（7）式限制了同一時刻作業的岸橋總數小于總可用岸橋數；（8）式是各船舶的實際作業時間；（9）、（10）式限制了該模型必須保證船舶離港時間不遲于最遲離港時間，到港時間不早于預期到港時間；（11）、（12）式限制了兩艘船舶在空間和時間二維圖中不會重疊。

3　分步的遺傳算法

本文提出的基于多Agent的泊位岸橋聯合調度的算法主要思想即：首先根據遺傳算法確定船舶的靠泊位置和靠泊順序；在泊位確定的基礎上，再確定每個泊位上的岸橋數量。

算法步驟如下：

①染色體編碼：編碼方式如表1所示。子染色體1是服務優先級順序，與泊位偏好成正比；子染色體2是停靠泊位位置。為了保證實驗結果的多樣性，初始種群隨機生成。

表1　染色體編碼示例

②適應度值函數：本文模型考慮的是最小化目標函數，故采用目標函數值倒數來表示適應度值函數，即f=1/z。進化過程中適應度值函數越大的染色體，越有可能被保留繼續進行遺傳操作以生成子代染色體；

③選擇策略：采用比例算子，根據上一步個體的適應度函數采用輪盤賭法確定個體被選擇出來的概率；

④交叉映射：包括雙切點交叉和修復程序，用這種修復程序修復因簡單雙切點交叉而引起的不合法性。包含四個步驟：（1）確定染色體矩陣切點列X，Y；（2）交換中間部分；（3）選取合理的映射關系（1-2，6-7，5-3；10-30，110-90，125-105）；（4）按映射關系恢復未交換部分的合法性。過程如圖4所示。

⑤換位變異：隨機在染色體矩陣上選取兩列位置，將相應基因的位置交換，過程如圖5所示。

⑥終止條件：達到迭代次數或達到最優解情況。

4　算例求解

假設某集裝箱碼頭的連續岸線長度為1200m，岸橋總數為10個，隨機選取一段時間內的船舶到港信息如表2。

表2　船舶到港信息

圖4　染色體交叉映射過程

圖5　染色體換位變異過程

已知設置不同的偏好泊位懲罰成本會對泊位分配結果產生影響，船舶在靠泊泊位時，都希望能夠靠泊在偏好泊位，但是泊位分配過程中總存在各種意外。本文通過實驗，借助C++軟件求解，假設α=0，遺傳參數：種群規模為10，遺傳迭代次數為200，交叉概率為0.5，變異概率為0.4。通過改變的值，得到不同額外成本下的泊位分配結果如表3所示。

通過表3的結果可以發現，隨著偏離偏好泊位懲罰成本的不斷上升，對該模型結果的約束效果越明顯。當=10時，此時相當于不考慮偏離成本的因素，總的偏離量達到了13，當實驗的數值不斷增大，總的偏離量也在隨之減少。通過實驗結果的對比，發現引入懲罰成本概念，可以大大降低船舶偏離偏好泊位的現象，從而提高碼頭作業效率，降低作業成本。

表3　不同偏好泊位懲罰成本下的泊位分配

為了更直觀地觀察加入偏好泊位懲罰成本對泊位岸橋聯合分配的影響，在其他條件不變的情況下，對比不同偏離系數α下的分配狀態，圖6、圖7分別給出了α=0和α=8泊位岸橋聯合調度的結果圖。從圖中可以看到，當α增大時，船舶靠泊在偏好泊位上的概率更大，進而岸橋的調度也得到了優化。

5　結語

本文在對連續岸線上泊位岸橋聯合調度研究基礎上，引入偏好泊位約束條件，以偏離偏好泊位成本為約束條件，并結合多Agent智能化的特點，建立基于多A-gent的泊位岸橋聯合分配模型。設計了分步的遺傳算法，結合數學模型進行泊位分配，降低船舶偏離偏好泊位的概率，再根據泊位狀態安排相應數量的岸橋。最后通過對比實驗的結果證明了模型和算法是有效的，設置較高的偏離懲罰成本能夠使船舶優先考慮偏好泊位。但在文中只是說明了根據泊位分配岸橋數量，而沒有具體的分配策略，缺少對Agent間通信的研究，這是接下來需要繼續深入研究的。

［1］Imai A，Chen H C，Nishimura E，et al.The Simultaneous Berth and Quay Crane Allocation Problem［J］.Transportation Research Part E Logistics&Transportation Review，2008，44（5）：900–920.

［2］Liang C，Huang Y，Yang Y.A Quay Crane Dynamic Scheduling Problem by Hybrid Evolutionary Algorithm for Berth Allocation Planning［J］.Computers&Industrial Engineering，2009，56（3）：1021-1028.

［3］高超鋒，胡志華.岸橋并行作業效率約束下泊位與岸橋集成分派［J］.重慶交通大學學報：自然科學版，2014（3）.

［4］杜衛華，黃有方，楊斌.岸橋移動約束的連續泊位和岸橋集成調度［J］.上海海事大學學報，2013，34（4）：43-48.

［5］Legato P，Gulli R，Trunfio R.The Quay Crane Deployment Problem at a Maritime Container Terminal［C］.Proceedings of the 22nd Eu-ropean Conference on Modeling and Simulation.Campora San Giovanni，Amantea Italy，2008：53-59.

圖6　α=0時泊位岸橋聯合調度

圖7　α=8時泊位岸橋聯合調度

［6］樂美龍，劉秀玲.基于泊位偏好與服務優先級的泊位和岸橋分配［J］.遼寧工程技術大學學報（自然科學版），2013（5）：709-712.

［7］鄭子龍，楊斌，胡志華.偏好泊位約束下的集裝箱港口離散泊位分配問題［J］.水運工程，2013（12）：64-68.

［8］周鵬飛，方金燦.集裝箱堆場收發箱管理Multi-Agent系統研究［J］.大連理工大學學報，2013（3）：382-389.

［9］李尤豐.基于MAS的碼頭物流系統的調度體系研究［J］.計算機技術與發展，2013（5）：246-249.

［10］王祥雪，朱瑾.基于MAS的集裝箱自動化碼頭協同作業系統模型［J］.計算機應用研究，2013，30（04）：1072-1075.

［11］李斌，李文鋒.基于MAS的集裝箱碼頭物流系統協同生產調度體系［J］.計算機集成制造系統，2011，17（11）：2502-2513.

［12］鄒金松.集裝箱碼頭智能操作系統設計與實現［J］.工程建設與設計，2015（9）：117-120.

Continuous Berth；Preference Berth；Multi-Agent；Genetic Algorithm；Intelligent

Berth-Crane Allocation Problem Based on Multi-Agent with the Preferences of Berthing Position

ZHU Shuo-bo，JIN Yong-he
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

Berth and crane are the most precious resources，making reasonable design for the scheduling mechanism can make full use of resources. Considers the continuous berth with preference berthing constraints，to minimize the deviation from the berth preference cost as objective function，combined with the Multi-Agent's intelligent characteristics，proposes a scheduling model based on Multi-Agent.Designs a new genetic algorithm bases on the model to achieve efficient berth crane scheduling.And makes example to prove the validity of the model and algorithm.The experimental results verify the introduction of preference constraints can efficiency improve the berth handling，and also can reduce the cost caused by the deviation from the berth preference.

1007-1423（2016）20-0039-06

10.3969/j.issn.1007-1423.2016.20.008

朱碩博（1990-），男，江蘇徐州人，碩士研究生，研究方向為港口物流優化

金永賀（1988-），男，山東菏澤人，碩士研究生，研究方向為港口物流信息化

2016-04-19

2016-06-10