韓曉龍，牟少莉

(上海海事大學物流研究中心，上海201306)

1 文獻綜述

集裝箱碼頭運輸已經(jīng)發(fā)展成為全球國際貿易中最重要的運輸方式之一。近年來，隨著集裝箱碼頭的擴建、集裝箱數(shù)量的增加、作業(yè)設備調度規(guī)則的不斷更新，以及碼頭設備資源管理的復雜性，使得碼頭集裝箱調度逐漸成為一項非常復雜的工程。研究者對集裝箱碼頭作業(yè)設備的調度優(yōu)化研究層出不窮。BISH等［1－2］提出了一個車輛位置分配問題，堆場龍門吊的位置已知，因此，在卸載集裝箱時，有優(yōu)先約束以及在多臺龍門吊和多輛集卡的情況下，對裝、卸集裝箱同時作業(yè)問題進行了優(yōu)化。文獻［3］基于碼頭堆場堆存能力，建立了集卡分派優(yōu)化兩階段模型，分別用Lingo和Gurobi進行求解，得到最優(yōu)方案。NISHIMURA等［4］將一定數(shù)量的集卡分配給岸橋進行作業(yè)，在岸橋位置已知時，建立單車和多車兩種情況下的模型，并用遺傳算法對相應問題進行求解。張莉等［5］分析了集卡的數(shù)量配置對集裝箱碼頭裝卸作業(yè)的影響，并使用Witness仿真軟件，得出在裝卸不同時段進行動態(tài)調配，集卡車速提高并不一定能加快整船的裝卸效率。曾慶成等［6］研究了集卡調度問題，建立集卡調度動態(tài)模型，使岸橋裝卸作業(yè)時等待時間最小。隨著集卡數(shù)量的增加，通過Q學習算法求解結果優(yōu)于最長等待時間、最遠距離等調度策略，以及動態(tài)分配集卡要優(yōu)于靜態(tài)分配集卡的策略。KOO等［7］提出了一種基于啟發(fā)式禁忌搜索算法的新型車隊管理程序，運用網(wǎng)絡流的方法建立以車輛的空載時間最小為目標的模型，使用禁忌搜索算法優(yōu)化車隊大小并求出運輸路徑。張波等［8］將模擬退火算法應用于路徑優(yōu)化問題中，對類似貨郎擔的車輛路徑問題進行求解，并用該算法得到最優(yōu)計算結果與樹形算法進行比較，克服傳統(tǒng)優(yōu)化算法局部求解的缺點，在解決城市道路交通方面的問題中具有一定的實用價值。CAO等［9］研究的是岸橋與集卡的綜合調度，在進行卸箱作業(yè)中，建立以總完工時間最小為目標的MIP模型，運用遺傳算法以及基于Johnson規(guī)則的改進啟發(fā)式算法求解模型，得到協(xié)調調度方案的最優(yōu)解。CAO等［10］研究集卡與龍門吊的協(xié)調調度(i－YTYCSP)，建立了一個整數(shù)規(guī)劃模型，用通用 Benders分解方法和組合Benders分解方法來求解模型。WOOYEON等［11］研究交叉對接系統(tǒng)，可以預測集卡在碼頭的卸箱作業(yè)以及如何分配集卡，從而找到較好的集卡調度序列，以減少總作業(yè)時間，提高碼頭作業(yè)效率，其采用啟發(fā)式算法對臨時存儲交叉對接問題進行求解。EBRU等［12］研究集裝箱碼頭同時進行裝卸作業(yè)，對作業(yè)集卡進行合理調度，減少作業(yè)總時間，并考慮到絕對和漸近情況，運用啟發(fā)式算法進行求解，通過數(shù)值實驗，取得該調度問題的最優(yōu)結果。

然而，在文獻中，對碼頭作業(yè)設備協(xié)同調度問題研究較少，未考慮實際操作的約束及模型求解的復雜性，故筆者考慮岸橋與集卡在實際作業(yè)中的絕對重要性以及約束，建立岸橋與集卡的協(xié)同調度優(yōu)化模型，用改進的遺傳算法(CHC算法)進行求解，提高求解準確性，實現(xiàn)集卡的最優(yōu)調度。

2 問題描述及數(shù)學模型構建

2.1 問題描述

在港口實際操作中，為船舶配置一定數(shù)量的岸橋和集卡，集裝箱作業(yè)可以看成碼頭內部的水平運輸物流系統(tǒng)，主要包括裝、卸兩個流程，集卡則是該流程中的主要運輸設備，是連接岸橋與堆場的中間設備，筆者基于一定的實際作業(yè)條件約束，研究岸橋與集卡的協(xié)同調度問題，在集裝箱進口作業(yè)中，集卡完成一次作業(yè)后，空載返回岸橋，等待進行下一次作業(yè)，如此反復，最小化集卡的最大完工時間。集卡的一個簡單作業(yè)循環(huán)流程如圖1所示。

圖1 集卡作業(yè)循環(huán)流程

2.2 模型基本假設

為了便于求解，對問題進行一定的簡化。根據(jù)港口集卡的卸船作業(yè)實際情況提出如下假設:

(1)只考慮碼頭船舶卸箱作業(yè);

(2)不同的岸橋提取集裝箱時間點不同，但每次作業(yè)時間均相等;

(3)集卡一次只能運輸一個集裝箱;

(4)岸橋間互不存在約束，不能對同一集裝箱重復操作，不存在等待集卡的情況;

(5)龍門吊互不存在約束，數(shù)量足夠對集卡的作業(yè)，無需等待。

2.3 模型參數(shù)設置

筆者將每個待作業(yè)的集裝箱視為一項作業(yè)，序號為 i，j，共有 Q 項作業(yè)，k 輛集卡，k，l分別為集卡的作業(yè)序號，N臺岸橋，m，n分別為岸橋的作業(yè)序號。此外，定義兩個虛擬工作0和n+1，分別表示集裝箱的初始和最終作業(yè)狀態(tài)。該模型采用的參數(shù)如下:

N為岸橋的作業(yè)數(shù)量;K為集卡的作業(yè)數(shù)量;Q為集裝箱的作業(yè)數(shù)量;ukilj為岸橋在集卡k作業(yè)i后立即對集卡l作業(yè)j的準備時間;p為岸橋m對集卡k上作業(yè)i的作業(yè)時間;ukij為集卡k作業(yè)i后立即作業(yè)j的準備時間;t為集卡進行作業(yè)的運輸時間;r為龍門吊從集卡卸箱的作業(yè)時間;M為一個很大的數(shù);Smi為岸橋m進行作業(yè)的開始時間;cmi為岸橋m進行作業(yè)的完成時間;Ski為集卡k進行作業(yè)的開始時間;cki為集卡k進行作業(yè)的完成時間。

模型中決策變量如下:

2.4 構建數(shù)學模型

目標函數(shù)即最小化作業(yè)總完工時間為:

式(1)為目標函數(shù)，求總完工時間最小;式(2)為最后總完工時間，由最后一輛集卡作業(yè)完成時間決定;式(3)和式(4)為對岸橋作業(yè)先后順序的約束;式(5)為岸橋m對集卡l作業(yè)j開始時間的約束;式(6)為岸橋m對集卡l作業(yè)j的完成時間約束;式(7)為岸橋作業(yè)結束后集卡再開始作業(yè);式(8)和式(9)為同一輛集卡作業(yè)的先后順序約束;式(10)為對集卡 i后序作業(yè)j的順序約束;式(11)為集卡一次作業(yè)的時間約束;式(12)為不同集卡作業(yè)先后順序;式(13)為集卡一次只能進行一次作業(yè);式(14)為作業(yè)先后順序約束。

3 模型求解

3.1 CHC算法應用

遺傳算法計算簡易流程如圖2所示。

圖2 遺傳算法計算簡易流程圖

筆者以2臺岸橋，4輛集卡和12只集裝箱作業(yè)為例，根據(jù)集卡調度的規(guī)則，結合CHC算法，進行求解。

3.1.1 編碼

CHC采用整數(shù)編碼，隨機生成12個1和N(N為岸橋的數(shù)量)的隨機數(shù)作為岸橋對集裝箱的作業(yè)序號，如圖3所示。

圖3 岸橋作業(yè)集裝箱作業(yè)序號

同時可得岸橋與集卡作業(yè)的初始種群，如表1和表2所示。

表1 岸橋(QC)初始分配任務

表2 集卡(YT)初始作業(yè)分配任務

3.1.2 適應度計算

遺傳算法中適應度函數(shù)與目標函數(shù)有較大的關聯(lián)，筆者采用界限構造法，若優(yōu)化問題為求最小值問題，則 fit(f(x))={cmax－f(x)，f(x) ＜cmax};若優(yōu)化問題為求最大值問題，則 fit(f(x))={f(x)－cmin，f(x) ＞cmin};其中，f(x)為求解問題的目標函數(shù)，cmax為f(x)最大值估計，cmin為 f(x)最小值估計。

筆者求解的目標函數(shù)為集卡總完工時間最小值問題，定義f(x)為目標函數(shù)，即f(x)=min T，那么，適應度函數(shù)可表示為:fit(f(x))=c－f(x);c取值為200，即 fit(f(x))=200－T。

3.1.3 選擇

筆者使用跨世紀精英的最佳保留選擇法，使用輪盤賭選擇后，將當前種群中適應度最高的個體結構完整地復制到子代，保留適應度較高的個體，不會因為選擇操作的誤差而被淘汰掉，提高精確度，選取11個個體的適應度，選擇概率，累計概率，如表3所示。

表3 CHC算法的跨世紀精英選擇法

假設抽取隨機數(shù)0.79，介于第5和第6個個體之間，那么第6個個體被選中，以此類推，選取最佳個體。

3.1.4 交叉

改進的CHC算法使用兩點交叉，隨機地產(chǎn)生兩個實數(shù) k，h(1≤k≤h≤N) ，取 k=2，h=10，從而確定交叉點位置，N為染色體長度，取N=12，選取交叉點之間的部分染色體交叉，圖示如圖4。

圖4 兩點交叉

3.1.5 變異

筆者采用基本位變異法，對某一個體，通過已確定或動態(tài)確定的變異概率確定是否對其進行變異;再隨機產(chǎn)生一個變異點k(1≤k≤W－1)，取k=1，W為個體中變異點的數(shù)量，取W=1，最終確定一個變異點，用等位基因替代產(chǎn)生新子代。

3.2 參數(shù)設定

遺傳算法自身參數(shù)有種群大小n、迭代代數(shù)gen、交叉概率pc和變異概率pm。種群大小n的取值范圍一般取為20～100，本著種群規(guī)模不宜太大，取n=50。進化代數(shù)應結合染色體長度和種群規(guī)模等因素進行綜合考慮，取進化代數(shù)gen=100。研究問題染色體長度取為N=12，在實際操作中，作業(yè)規(guī)模會變得很大，染色體長度也會相應增加。

進化終止的條件規(guī)定:在種群中最大適應度值已趨于穩(wěn)定、增加不超過0.5%，或平均適應度值相對穩(wěn)定、增加不超過3% 的時候，可以終止遺傳算法，取進化代數(shù)到達規(guī)定值終止運行。

交叉采用兩點交叉方式，交叉概率pc=0.8，變異采用基本位變異方法，如圖5所示，已進行交叉的個體不再參與變異，這里變異概率 pm=0.05，變異概率為 pm/(1－pc) 。

圖5 基本位變異

3.3 算例結果及分析

將遺傳算法在Matlab 7.12(R2011a)軟件，MicrosoftWindows 7系統(tǒng)環(huán)境下實現(xiàn)，得到基于集卡總完工時間最小，橋吊最優(yōu)任務序列及作業(yè)時間、集卡最優(yōu)任務序列以及等待時間。

由種群的平均適應度值變化趨勢可以得出，集卡動態(tài)調度模型用遺傳算法求解具有收斂性，并且種群中的每個子代中最大適應度值也趨于穩(wěn)定，即隨著代數(shù)的增加時間趨于平穩(wěn)狀態(tài)，顯示了CHC算法在求解作業(yè)時間的優(yōu)越性，此時的最大適應度值為fitmax=183，最小適應度為fitmin=168，平均適應度fitmean=172.78，對應的橋吊與集卡的染色體，即最優(yōu)調度方案分別如表4和表5所示。

表4 岸橋(QC)的最優(yōu)作業(yè)序列

表5 集卡(YT)的最優(yōu)作業(yè)序列

從表4和表5可以得出，1號岸橋的作業(yè)序列為1→2→5→9→10→11，2號岸橋作業(yè)的序列為3→4→6→7→8→12;同時1號集卡作業(yè)序列為4→7→8→9→10→12，2號集卡的作業(yè)序列為11，3號集卡作業(yè)序列為3，4號集卡的作業(yè)序列為1→2→5→6。

最大完成時間由4輛集卡中最后一輛集卡的最大完成時間來決定，即max T=32，如表6所示。

表6 作業(yè)的開始、作業(yè)、結束時間

4 結論

筆者研究了考慮多種約束條件下的集卡與岸橋的協(xié)同調度問題，主要對卸箱作業(yè)過程，在考慮集卡作業(yè)的情況下做出岸橋的工作計劃，并考慮了岸橋與集卡工作之間的優(yōu)先約束，例如，不存在岸橋等待集卡的情況。由于NP－h(huán)ard問題模型的復雜性，一般的優(yōu)化算法不能求解。為此，引進了一個CHC算法來求解問題。通過算例測試，該算法能得到最優(yōu)方案。

［1］B ISH E K，LEONG T.Analysis of a new vehicle scheduling and location problem［J］.Naval Research Logistics，2001(48):363 －385.

［2］B ISH E K.A multiple－crane－constrained scheduling problem in a container terminal［J］.European Journal of Operational Research，2003(144):83－107.

［3］徐 遠琴，韓曉龍.集裝箱碼頭集卡動態(tài)調度模型優(yōu)化［J］.武漢理工大學學報:信息與管理工程版，2013，36(3):357 －360.

［4］N ISHIMURA E，IMAIA.Yard trailer routing at a maritime container terminal［J］.Transportation Research Part E，2005，41(1):53－76.

［5］張莉，霍佳震.基于單船裝卸運輸模型的集卡配置仿真研究［J］.系統(tǒng)仿真學報，2006(12):3532－3538.

［6］曾慶成，楊忠振.集裝箱碼頭集卡調度模型與Q學習算法［J］.哈爾濱工程大學學報，2008，29(1):1 －6.

［7］KOO PH，LEEW S，JANG D.Fleet sizing and vehicle routing for container transportation in a static environment［J］.OR Spectrum，2004，26(2):193 － 209.

［8］張波，葉家瑋，胡郁蔥.模擬退火算法在路徑優(yōu)化問題中的應用［J］.中國公路學報，2004(1):79－83.

［9］CAO JX，SHIQ X，LEE D H.Integrated quay crane and yard truck schedule problem in container terminals［J］.Tsinghua Science and Technology，2010，15(4):467－474.

［10］CAO JX，LEE D H.The integrated yard truck and yard crane scheduling problem:Benders＇decomposition － based methods［J］.Transportation Research Part E，2010，46(3):344 －353.

［11］WOOYEON Y，EGBELU P J.Scheduling of inbound and outbound trucks in cross docking systems with temporary storage［J］.European Journalof Operational Research，2008(184):377 －396.

［12］EBRU K B，F(xiàn)RANK Y C.Dispatching vehicles in a mega container terminal［J］.OR Spectrum ，2005，27(3):491－506.