基于螢火蟲算法的集裝箱碼頭集卡路徑多目標優(yōu)化研究

卓宏明

(浙江國際海運職業(yè)技術學院，浙江　舟山　316021)

基于螢火蟲算法的集裝箱碼頭集卡路徑多目標優(yōu)化研究

卓宏明

(浙江國際海運職業(yè)技術學院，浙江舟山316021)

摘要:在兩艘船同時作業(yè)情況下，建立以集卡總行駛距離最短及完成兩船所有裝卸任務的時段內各箱區(qū)間作業(yè)量不平衡性最小的多目標優(yōu)化模型。在模型求解時，采用新穎的螢火蟲算法求解，編碼方式采用離散整數(shù)編碼，每個整數(shù)編碼表示對應的集卡作業(yè)回路運行次數(shù)。最后通過舟山甬舟集裝箱碼頭案例分析，較好的解決了集卡路徑優(yōu)化問題，為碼頭運營者提供了一定的決策支持，也驗證了模型與算法的有效性與實用性。

關鍵詞:集裝箱碼頭；集卡調度；螢火蟲算法

0引言

隨著集裝箱碼頭業(yè)務競爭的日益激烈，如何在現(xiàn)有規(guī)模下提高碼頭資源利用率,提高集裝箱碼頭運作效率，就必須合理解決集卡調度問題。NISHIMURA (2005)[1]建立了集卡動態(tài)路徑優(yōu)化模型，并比較分析集卡靜態(tài)調度與動態(tài)調度，最后用遺傳算法求解模型。Lai Ming yong、Cao Erbao(2010)[2]建立了以車輛行走距離總和最小的混合整數(shù)規(guī)劃模型，并采用自適應遺傳算法對該模型進行求解；楊靜蕾(2006)[3]建立了以集卡總行程最短為目標的集卡調度模型；計明軍、劉豐碩等(2010)[4]建立了基于作業(yè)面的兩船裝卸協(xié)同作業(yè)的集裝箱碼頭集卡調度；趙斐(2011)[5]建立了面向“作業(yè)面”的集裝箱碼頭集卡路徑成本優(yōu)化模型，并用遺傳算法混合蟻群算法求解模型；陸永祥(2013)[6]研究了在“作業(yè)面”調度模式下的集裝箱碼頭集卡調度以及集卡合理配置。但多數(shù)文獻只考慮了單目標沒有考慮箱區(qū)間的作業(yè)量平衡問題。

本文在碼頭現(xiàn)行的“作業(yè)面”集卡調度作業(yè)基礎上，研究兩船同步裝卸作業(yè)，提出完成兩船所有裝卸的集卡總行駛距離最短和該作業(yè)時段內各箱區(qū)的作業(yè)量不平衡性最小的多目標集卡調度優(yōu)化模型。

1多目標集卡路徑優(yōu)化模型

1.1問題描述

當集裝箱船舶靠泊后，兩艘船舶進行同步裝卸，如何確定集卡的作業(yè)回路，使得完成所有裝卸作業(yè)的集卡總行駛路程最短，并且該作業(yè)時段內各箱區(qū)的作業(yè)量不平衡性最小。進口箱區(qū)的作業(yè)量包括進口箱量和外部集卡的提箱箱量，而出口箱區(qū)的作業(yè)量包括出口箱量和外部集卡的集港箱量，從而降低堆場交通阻塞，提高集裝箱碼頭的作業(yè)效率，降低生產(chǎn)作業(yè)成本。

1.2模型的假設

模型基于以下幾點假設：本論文的主要研究對象是單掛集卡每次僅運輸一個集裝箱；碼頭各節(jié)點之間的集卡行駛距離已知；集裝箱碼頭堆場采用進出口箱分開堆存策略；船舶在集裝箱碼頭進、出口箱量已知；實際碼頭裝船前，A1/A2/A3/B1/B2/B3等出口箱區(qū)的出口箱量已確定；開始作業(yè)前箱區(qū)中所在的箱量及箱區(qū)的容量已知；作業(yè)時段內外卡在各箱區(qū)的提箱量、集箱量已知。A4/A5為a船舶的進口箱區(qū)，B4/B5為b船舶的進口箱區(qū)。

1.3集卡模型的建立

模型符號說明:YIa表示a船所在泊位分配的進口箱區(qū)總數(shù)；YIb表示b船所在泊位分配的進口箱區(qū)總數(shù)；YQa表示a船所在泊位分配的出口箱區(qū)總數(shù)；YOb表示b船所在泊位分配的出口箱區(qū)總數(shù)；ai表示a船所在泊位分配的第j個進口箱區(qū)，ai=1，2，3，…，YIa；bi表示b船所在泊位分配的第i個進口箱區(qū)，bi=1，2，3，…，YIb；aj表示a船所在泊位分配的第i個出口箱區(qū)，aj=1，2，3，…，YQa；bj表示b船所在泊位分配的第j個出口箱區(qū)，bj=1，2，3，…，YQb；Lai表示集卡在卸箱船舶a進口作業(yè)回路，卸箱船舶a→進口箱區(qū)ai→卸箱船舶a行走一圈的距離；Lbi表示集卡在卸箱船舶b進口作業(yè)回路，卸箱船舶b→進口箱區(qū)bi→卸箱船舶b行走一圈的距離；Laibj表示集卡在卸箱a船舶、裝箱船舶b，兩船同步裝卸作業(yè)回路，卸箱船舶a→進口箱區(qū)ai→出口箱區(qū)bj→裝箱船舶b→卸箱船舶a行走一圈的距離，且a≠b；Lbiaj表示集卡在卸箱船舶b、裝箱船舶a，兩船同步裝卸作業(yè)回路，卸箱船舶b→進口箱區(qū)bi→出口箱區(qū)aj→裝箱船舶a→卸箱船舶b行走一圈的距離，且a≠b；Laj表示集卡在裝箱船舶a出口作業(yè)回路，裝箱船舶a→出口箱區(qū)aj→裝箱船舶a行走一圈的距離；Lbj：表示集卡在裝箱船舶b出口作業(yè)回路，裝箱船舶b→出口箱區(qū)bi→裝箱船舶b行走一圈的距離；Iai：表示作業(yè)時段內a船所在泊位分配的第ai個進口箱區(qū)的總作業(yè)量；Ibi：表示作業(yè)時段內b船所在泊位分配的第bi個進口箱區(qū)的總作業(yè)量；Qaj表示作業(yè)時段內a船所在泊位分配的第aj個出口箱區(qū)的總作業(yè)量；Obj表示作業(yè)時段內b船所在泊位分配的第bj個出口箱區(qū)的總作業(yè)量；Qai表示a船所在泊位分配的第ai個進口箱區(qū)的總容量；Qbi表示b船所在泊位分配的第bi個進口箱區(qū)的總容量；Qaj表示a船所在泊位分配的第aj個出口箱區(qū)的總容量；Qbj表示b船所在泊位分配的第bj個出口箱區(qū)的總容量；Nai表示船舶a的進口總箱量；Nbj表示船舶b的進口總箱量；Naj表示船舶a的出口總箱量；Nbj表示船舶b的出口總箱量；yai表示作業(yè)時段內a船所在泊位分配的第ai個進口箱區(qū)的外卡總提箱量；ybi表示作業(yè)時段內b船所在泊位分配的第bi個進口箱區(qū)的外卡總提箱量；yaj表示作業(yè)時段內a船所在泊位分配的第aj個出口箱區(qū)的外卡總集箱量；ybj表示作業(yè)時段內b船所在泊位分配的第bj個出口箱區(qū)的外卡總集箱量；

決策變量:xai決策變量,表示集卡在卸箱船舶a進口作業(yè)回路，卸箱船舶a→進口箱區(qū)→ai卸箱船舶a的行走次數(shù)；xbi決策變量,表示集卡在卸箱船舶b進口作業(yè)回路，卸箱船舶b→進口箱區(qū)bi→卸箱船舶b的行走次數(shù)；xaibj決策變量,表示集卡在卸箱船舶a、裝箱船舶b，兩船同步裝卸作業(yè)回路，卸箱船舶a→進口箱區(qū)ai→出口箱區(qū)bj→裝箱船舶b→卸箱船舶a的行走次數(shù)，且a≠b；xbiaj決策變量,表示集卡在卸箱船舶b、裝箱船舶a，兩船同步裝卸作業(yè)回路，卸箱船舶b→進口箱區(qū)bi→出口箱區(qū)aj→裝箱船舶a→卸箱船舶b的行走次數(shù)，且a≠b；xaj決策變量,表示集卡在裝箱船舶a出口作業(yè)回路，裝箱船舶a→出口箱區(qū)aj→裝箱船舶a的行走次數(shù)；xbj決策變量,表示集卡在裝箱船舶b出口作業(yè)回路，裝箱船舶b→出口箱區(qū)bj→裝箱船舶b的行走次數(shù)；

路徑優(yōu)化模型以集卡總行程最短及完成兩船所有裝卸任務的時段內各箱區(qū)間作業(yè)量不平衡性最小的多優(yōu)化目標函數(shù)。

總目標函數(shù):

f=f1×f2

(1)

目標函數(shù)1:

(2)

目標函數(shù)2:

f2=min(max(max(Iai+yai)，max(Ibi)，max(Oaj)，max(Obj))-min(min(Iai)，min(Ibi),min(Oaj)，min(Obi)

(3)

約束條件：

Iai=χai+χaibj+yai,Ibi=χbi+biaj+ybi

(4)

Oaj=χai+xbiaj+yai，Obi=χbj+χaibj+ybj

(5)

0≤χai+xaibj-yai≤Qai，0≤χbi+χbiaj-ybi≤Qbi

(6)

0≤-(χaj+χbiaj)+yaj≤Qaj,0≤-(χbj+χaibj)+ybj≤Qbj

(7)

(8)

(9)

0≤χai≤Nai,0≤χbi≤Nbi,0≤χaj≤Naj,0≤χbj≤Nbj

(10)

0≤χaibj≤min(Nai,Nbj),0≤χbiaj≤min(Nbi,Naj)

(11)

χai,χbi,χaibj,χbiaj,χaj,χbj=0,1,2,3…

(12)

其中：

式(1)是以集卡總行程最短及完成兩船所有裝卸任務的時段內各箱區(qū)間作業(yè)量不平衡性最小的多優(yōu)化目標函數(shù)；式(2)是目標函數(shù)1以集卡總行程最短為優(yōu)化目標；式(3)是目標函數(shù)2以完成兩船所有裝卸的時段內各箱區(qū)間作業(yè)量不平衡性最小為優(yōu)化目標；式(4)和式(5)表示各箱區(qū)的總作業(yè)量為完成兩船所有裝卸任務的時段內進口箱量(出口箱量)與外卡提箱量(外卡集箱量)之和；式(6)和式(7)表示各箱區(qū)的箱量需要滿足的容量約束；式(8)和式(9)保證船舶所有裝卸任務的完成；式(10)和式(11)表示決策變量需要滿足的進出口箱量約束；式(12)表示決策變量集卡作業(yè)回路行走次數(shù)為非負整數(shù)。

2模型求解

2.1螢火蟲算法(FA)

螢火蟲算法(FA)由劍橋學者Yang xin-she在2008年提出[7]，自然界中的螢火蟲個體用搜索空間中的點模擬，個體吸引和移動過程用搜索和優(yōu)化過程模擬，螢火蟲個體所處位置的好壞，轉化為求解問題的目標函數(shù)度量，搜索和優(yōu)化過程中用好的可行解取代較差可行解的迭代過程類比螢火蟲個體的優(yōu)勝劣汰過程。

2.2編碼方式

本模型將整靠泊的兩艘船舶同步裝卸的集卡所有作業(yè)回路運行次數(shù)作為決策變量。船a與船b集卡調度時，把集卡所有的作業(yè)回路運行次數(shù)作為一個螢火蟲，假設船舶所在泊位分配的進口箱區(qū)總數(shù)為YIa、出口箱區(qū)總數(shù)為YOa；船舶a所在泊位分配的進口箱區(qū)總數(shù)為YIb、出口箱區(qū)總數(shù)為YOb，則螢火蟲求解空間維數(shù)為N=YIa+YIb+YIa×YOb+YIb×YOa+YOa+YOb維，矩陣中每個元素就是集卡對應的作業(yè)回路運行次數(shù)。由于作業(yè)回路運行次數(shù)為整數(shù)，所以采用離散整數(shù)編碼，每個整數(shù)編碼表示對應的集卡作業(yè)回路運行次數(shù)。

2.3算法流程

[編者按] 為深入貫徹落實《中共中央 國務院關于實施鄉(xiāng)村振興戰(zhàn)略的意見》(中發(fā)〔2018〕1號)和《鄉(xiāng)村振興戰(zhàn)略規(guī)劃(2018-2022年)》，推動鄉(xiāng)村旅游提質增效，促進鄉(xiāng)村旅游可持續(xù)發(fā)展，加快形成農(nóng)業(yè)農(nóng)村發(fā)展新動能，文化和旅游部等17部門聯(lián)合印發(fā)了《關于促進鄉(xiāng)村旅游可持續(xù)發(fā)展的指導意見》?，F(xiàn)轉載如下。

步驟1：初始化算法基本參數(shù)。FA算法基本參數(shù)的初始化。螢火蟲數(shù)目n；光吸收強度系數(shù)γ；步長因子α；最大吸引度β0；最大迭代次數(shù)maxt。

步驟2：在可行區(qū)域的范圍內隨機初始化n個螢火蟲位置。

步驟3：計算螢火蟲的適應度值，也就是計算目標函數(shù)值。

步驟4：用螢火蟲的相對螢光亮度公式：

I=I0×e-γrij

(13)

及螢火蟲的吸引度公式：

β=β0×e-γr2ij

(14)

其中，I0為螢火蟲自身(r=0處)的螢光亮度，稱為最大螢光亮度，它與目標函數(shù)正相關，目標函數(shù)值越優(yōu)螢火蟲亮度就越高。γ為光強吸收系數(shù)，通常設為常數(shù)，設置光強吸收系數(shù)用以體現(xiàn)螢光會隨著距離的增加和傳播媒介的吸收逐漸減弱。rij為螢火蟲i和j之間的空間距離。β0為光源處(r=0處)的吸引度，稱為最大吸引度。

步驟5：用螢火蟲i被螢火蟲j吸引而向其移動的位置更新公式：

χi=χi+β×(χj-χi)+α×(rand-1/2)

(15)

其中，χi、χj為螢火蟲i和j所處的空間位置；α為步長因子，是[0，1]區(qū)間上的常數(shù)；rand為[0，1]區(qū)間上服從均勻分布的隨機因子。

隨機擾動最佳位置的螢火蟲，再更新螢火蟲的位置并滿足約束條件。由于決策變量為非負整數(shù)，所以對其移動距離做了放大取整處理。

步驟6：迭代次數(shù)加1。判斷是否滿足最大迭代次數(shù)，滿足則輸出最優(yōu)值，否則，返回步驟3。

3舟山甬舟集裝箱碼頭案例分析

以舟山甬舟集裝箱碼頭為例進行案例分析。該碼頭位于浙江省舟山市金塘大浦口，前沿水深-18 m，規(guī)劃建成5個總長為1 774 m、年吞吐通過能力達250萬標箱的現(xiàn)代化大型集裝箱泊位?，F(xiàn)在已經(jīng)建成2個泊位及17.5萬平方的堆場，2013年吞吐量已經(jīng)突破50萬TEU。查詢碼頭船舶作業(yè)計劃可知2014年5月12日當天靠泊的聯(lián)合22船，(為簡化船名這里用船a來代替)進口箱量為20 TEU，分配的進口箱區(qū)為A4、A5，出口箱量為70 TEU，分配的出口箱區(qū)為A1、A2、A3；靠泊的柏安9號船(為簡化船名這里用船b來代替)進口箱量為180 TEU分配的進口箱區(qū)為B4、B5，出口箱量為121 TEU分配的出口箱區(qū)為B1、B2、B3。各箱區(qū)的容量及完成兩船所有裝卸作業(yè)時段內的外卡提箱量、集港箱量如表1所示。碼頭各節(jié)點之間的集卡行駛距離如表2所示。該案例的螢火蟲求解空間為2+2+2×3+2×3+3+3=22維。

表1　各箱區(qū)的容量、原堆存量、提箱集港箱量(TEU)

表2　碼頭各節(jié)點間集卡行駛的距離(m)

FA算法中螢火蟲數(shù)目取50，光吸收強度系數(shù)為1；步長因子為0.2；最大吸引度為1；最大迭代次數(shù)為300。模型求解收斂圖如圖1所示，總目標最優(yōu)值為3 672 000。目標1集卡總運行距離為459 000m，目標2各箱區(qū)作業(yè)量極差為80TEU。

圖1　模型最優(yōu)結果收斂曲線

所求得的最優(yōu)集卡運輸線路和運輸箱量如表3所示。

表3　集卡運輸線路和運輸箱量(TEU)

通過FA螢火蟲算法求得模型的解，所得的集卡最優(yōu)運輸線路可以實現(xiàn)集卡的總運輸距離及各箱區(qū)的作業(yè)量不平衡性最小的多優(yōu)化目標。

4結語

本文提出了面向“作業(yè)面”的兩船同步裝卸的集卡路徑優(yōu)化多目標模型，運用螢火蟲算法求解模型，最后通過甬舟碼頭案例分析，結果表明該方法較好的解決了集卡路徑優(yōu)化問題，為碼頭運營者提供了一定的決策支持。

參考文獻：

[1]NishimuraEtsuko.Yardtrailerroutingatamaritimecontainerterminal[J].TransportationResearchPartE,2005,41(1):53-76.

[2]LaiMingyong,CaoErbao.Animproveddifferentialevolutionalgorithmforvehicleroutingproblemwithsimultaneouspickupsanddeliveriesandtimewindows[J].EngineeringApplicationsofArtificialIntelligence,2010，23(2):188-195．

[3]楊靜蕾.集裝箱碼頭物流路徑優(yōu)化研究[J].水運工程,2006，(1):32-35.

[4]計明軍,劉豐碩,李郭記,等.基于裝卸協(xié)同作業(yè)的集裝箱碼頭集卡調度及配置優(yōu)化[J].大連海事大學學報:自然科學版,2010,36(1):47-50.

[5]趙斐.基于GA-ACO的港口集卡路徑優(yōu)化研究[D].邯鄲:河北工程大學,2011.

[6]陸永祥.實時作業(yè)調度下集卡優(yōu)化配置數(shù)量的確定[D].大連:大連海事大學,2013.

[7]劉長平,葉春明.一種新穎的仿生群智能優(yōu)化算法:螢火蟲算法[J].計算機應用研究,2011，28(9):3295-3297．

Multi-objective Truck Routing Optimization of Container

Terminals Based on Firefly Algorithm

ZHUO Hong-ming

(Zhejiang International Maritime College, Zhoushan 316021, China)

Abstract:In order to improve the efficiency of container stevedoring, in two boats at the same time operating conditions, the establishment of a set of cards in each box within the shortest total distance traveled and the completion of the task of handling two ships of all time intervals the least amount of work unbalanced multi-objective optimization model. When solving the model, using a novel fireflies algorithm, encoding discrete integer encoding, each integer corresponding to the coded representation of the working circuit card assembly operation times. Finally, Ningbo Zhoushan Container Terminal by case analysis, the results show that the method to solve a set of cards better path optimization problems for terminal operators to provide a certain amount of decision support, meanwhile demonstrate the effectiveness and practicality of the model and algorithms.

Key words:container terminals; truck scheduling; firefly algorithm

浙江交通職業(yè)技術學院學報，第16卷第1期，2015年3月

Journal of Zhejiang Institute of Communications

Vol.16 No.1,Mar.2015

作者簡介：于文波(1979-)，女，遼寧凌源人,高級實驗師,碩士,E-mail:yuwenbobo@126.com。

基金項目：2014年沈陽工程學院學生創(chuàng)新科研項目(LGXS-1404)

收稿日期：2014-11-03

文章編號：1671-234X(2015)01-0033-05

中圖分類號:U691.72?

文獻標識碼：A doi：10.3969/j.issn.1671-234X.2015.01.008