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

朱碩博，金永賀（上海海事大學(xué)信息工程學(xué)院，上?！?01306）

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

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

泊位和岸橋是碼頭前沿最寶貴的資源，為其設(shè)計合理調(diào)度機制能夠獲得更高的效能?？紤]連續(xù)泊位的岸線，加入偏好泊位約束條件，以最小化偏離偏好泊位成本為目標(biāo)函數(shù)，結(jié)合多Agent的智能化特點，提出基于多Agent的聯(lián)合調(diào)度模型，在模型基礎(chǔ)上設(shè)計分步的遺傳算法，實現(xiàn)高效的泊位岸橋聯(lián)合調(diào)度。并用實驗證明模型和算法的有效性，實驗結(jié)果驗證引入偏好泊位約束條件確實能提高碼頭作業(yè)效率，降低因偏離偏好泊位帶來的成本。

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

0　引言

隨著經(jīng)濟全球化以及世界貿(mào)易的高速發(fā)展，集裝箱水路運輸逐漸呈現(xiàn)船舶的大型化、高速化態(tài)勢，這也對碼頭裝卸設(shè)備的合理配置提出了更高的要求。泊位和岸橋的分配是碼頭前沿作業(yè)的首要環(huán)節(jié)，因而設(shè)計合理的靠泊計劃和岸橋分配策略是提高集裝箱碼頭作業(yè)效率的關(guān)鍵。

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

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

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

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

1　問題描述

1.1泊位-岸橋聯(lián)合調(diào)度問題

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

在碼頭實際靠泊作業(yè)中，每艘船舶都有其偏好的泊位，船舶在靠泊后，參與作業(yè)的岸橋數(shù)以及堆場運輸?shù)膮f(xié)調(diào)性等都是碼頭作業(yè)效率的影響因素，船舶?？吭谄淦貌次簧夏軌虼蠓岣咦鳂I(yè)效率。對于偏好泊位的描述，可以用圖1-1來表示，其中橫軸代表泊位岸線，縱軸代表時間；Δbi表示船舶i偏離偏好泊位的距離；Tpr表示船舶i延遲到港時間；Tqs表示船舶i延遲離港時間。

圖1　船舶靠泊時空圖

1.2Agent的結(jié)構(gòu)設(shè)計

根據(jù)調(diào)度框架結(jié)構(gòu)的需要，設(shè)計了混合型的Agent結(jié)構(gòu)，其中，動態(tài)管理Agent、岸橋調(diào)度Agent和泊位分配Agent作為管理者，側(cè)重的是思考型；船舶Agent、岸橋Agent和泊位Agent作為任務(wù)的執(zhí)行者，側(cè)重的是反應(yīng)型。Agent內(nèi)部是由感知器、緩沖區(qū)、推理機、知識庫、響應(yīng)器和注冊機組成，即Agent=＜P，B，D，K，R，I＞。圖2給出了岸橋調(diào)度Agent作為管理者的內(nèi)部結(jié)構(gòu)，其他Agent內(nèi)部結(jié)構(gòu)與其類似，區(qū)別在于推理機的不同。

P：感知器。實時監(jiān)聽發(fā)送給Agent的信息，實現(xiàn)對外部環(huán)境的主動感知。

B：緩沖區(qū)。存放發(fā)送給Agent的消息隊列。

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

K：知識庫。存放Agent相關(guān)知識、規(guī)則的數(shù)據(jù)庫。

R：響應(yīng)器。負(fù)責(zé)向其他Agent發(fā)送消息。

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

圖2　岸橋調(diào)度Agent的內(nèi)部結(jié)構(gòu)

1.3泊位岸橋調(diào)度多Agent系統(tǒng)框架模型

碼頭泊位岸橋聯(lián)合調(diào)度是一個復(fù)雜、動態(tài)的過程，本文在對泊位、岸橋業(yè)務(wù)流程深入分析的基礎(chǔ)上，提出了基于多Agent的泊位-岸橋聯(lián)合調(diào)度系統(tǒng)框架。系統(tǒng)由以下幾類Agent組成：船舶Agent、動態(tài)管理Agent、泊位Agent、岸橋Agent、泊位分配Agent、岸橋調(diào)度A-gent。圖3給出了集裝箱碼頭多Agent系統(tǒng)結(jié)構(gòu)框架模型。

圖3　集裝箱碼頭多Agent系統(tǒng)結(jié)構(gòu)框架模型

該模型中，動態(tài)管理Agent的功能是負(fù)責(zé)控制和監(jiān)督整個任務(wù)的具體執(zhí)行；岸線上每個泊位對應(yīng)一個泊位Agent，實時更新泊位的狀態(tài)信息，將結(jié)果及時反饋給泊位分配Agent，并接受泊位分配Agent的靠泊分配任務(wù)；岸線上每個岸橋?qū)?yīng)一個岸橋Agent，實時將岸橋狀態(tài)信息反饋給岸橋調(diào)度Agent，接受岸橋調(diào)度A-gent的調(diào)度；泊位分配Agent負(fù)責(zé)給各個泊位Agent發(fā)送指令，查詢泊位Agent的實時信息，接收動態(tài)管理A-gent的實時調(diào)度請求，根據(jù)泊位Agent的實時狀態(tài)做出回應(yīng)；岸橋調(diào)度Agent接收動態(tài)管理Agent的實時調(diào)度請求，根據(jù)岸橋Agent的狀態(tài)信息對岸橋進行調(diào)度，并進行實時反饋。

2　數(shù)學(xué)模型

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

模型基于以下的假設(shè)條件：

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

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

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

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

2.1參數(shù)

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

B：港口的可用岸橋總數(shù)量；

L：港口岸線的總長度；

li：船舶i的長度；

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

pi：船舶i的預(yù)期到港時間；

qi：船舶i的預(yù)期離港時間；

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

α：偏離偏好泊位系數(shù)；

2.2決策變量

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

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

ri：船舶i實際到港作業(yè)時間；

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

2.3目標(biāo)函數(shù)與約束條件

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

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

3　分步的遺傳算法

本文提出的基于多Agent的泊位岸橋聯(lián)合調(diào)度的算法主要思想即：首先根據(jù)遺傳算法確定船舶的靠泊位置和靠泊順序；在泊位確定的基礎(chǔ)上，再確定每個泊位上的岸橋數(shù)量。

算法步驟如下：

①染色體編碼：編碼方式如表1所示。子染色體1是服務(wù)優(yōu)先級順序，與泊位偏好成正比；子染色體2是?？坎次晃恢谩榱吮ＷC實驗結(jié)果的多樣性，初始種群隨機生成。

表1　染色體編碼示例

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

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

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

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

⑥終止條件：達(dá)到迭代次數(shù)或達(dá)到最優(yōu)解情況。

4　算例求解

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

表2　船舶到港信息

圖4　染色體交叉映射過程

圖5　染色體換位變異過程

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

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

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

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

5　結(jié)語

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

［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］高超鋒，胡志華.岸橋并行作業(yè)效率約束下泊位與岸橋集成分派［J］.重慶交通大學(xué)學(xué)報：自然科學(xué)版，2014（3）.

［4］杜衛(wèi)華，黃有方，楊斌.岸橋移動約束的連續(xù)泊位和岸橋集成調(diào)度［J］.上海海事大學(xué)學(xué)報，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時泊位岸橋聯(lián)合調(diào)度

圖7　α=8時泊位岸橋聯(lián)合調(diào)度

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

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

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

［9］李尤豐.基于MAS的碼頭物流系統(tǒng)的調(diào)度體系研究［J］.計算機技術(shù)與發(fā)展，2013（5）：246-249.

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

［11］李斌，李文鋒.基于MAS的集裝箱碼頭物流系統(tǒng)協(xié)同生產(chǎn)調(diào)度體系［J］.計算機集成制造系統(tǒng)，2011，17（11）：2502-2513.

［12］鄒金松.集裝箱碼頭智能操作系統(tǒng)設(shè)計與實現(xiàn)［J］.工程建設(shè)與設(shè)計，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-），男，江蘇徐州人，碩士研究生，研究方向為港口物流優(yōu)化

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

2016-04-19

2016-06-10