韓曉龍，牟少莉

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

1 文獻(xiàn)綜述

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

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

2 問題描述及數(shù)學(xué)模型構(gòu)建

2.1 問題描述

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

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

2.2 模型基本假設(shè)

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

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

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

(3)集卡一次只能運(yùn)輸一個(gè)集裝箱;

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

(5)龍門吊互不存在約束，數(shù)量足夠?qū)ǖ淖鳂I(yè)，無需等待。

2.3 模型參數(shù)設(shè)置

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

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

模型中決策變量如下:

2.4 構(gòu)建數(shù)學(xué)模型

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

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

3 模型求解

3.1 CHC算法應(yīng)用

遺傳算法計(jì)算簡(jiǎn)易流程如圖2所示。

圖2 遺傳算法計(jì)算簡(jiǎn)易流程圖

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

3.1.1 編碼

CHC采用整數(shù)編碼，隨機(jī)生成12個(gè)1和N(N為岸橋的數(shù)量)的隨機(jī)數(shù)作為岸橋?qū)b箱的作業(yè)序號(hào)，如圖3所示。

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

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

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

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

3.1.2 適應(yīng)度計(jì)算

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

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

3.1.3 選擇

筆者使用跨世紀(jì)精英的最佳保留選擇法，使用輪盤賭選擇后，將當(dāng)前種群中適應(yīng)度最高的個(gè)體結(jié)構(gòu)完整地復(fù)制到子代，保留適應(yīng)度較高的個(gè)體，不會(huì)因?yàn)檫x擇操作的誤差而被淘汰掉，提高精確度，選取11個(gè)個(gè)體的適應(yīng)度，選擇概率，累計(jì)概率，如表3所示。

表3 CHC算法的跨世紀(jì)精英選擇法

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

3.1.4 交叉

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

圖4 兩點(diǎn)交叉

3.1.5 變異

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

3.2 參數(shù)設(shè)定

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

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

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

圖5 基本位變異

3.3 算例結(jié)果及分析

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

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

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

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

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

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

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

4 結(jié)論

筆者研究了考慮多種約束條件下的集卡與岸橋的協(xié)同調(diào)度問題，主要對(duì)卸箱作業(yè)過程，在考慮集卡作業(yè)的情況下做出岸橋的工作計(jì)劃，并考慮了岸橋與集卡工作之間的優(yōu)先約束，例如，不存在岸橋等待集卡的情況。由于NP－h(huán)ard問題模型的復(fù)雜性，一般的優(yōu)化算法不能求解。為此，引進(jìn)了一個(gè)CHC算法來求解問題。通過算例測(cè)試，該算法能得到最優(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］徐 遠(yuǎn)琴，韓曉龍.集裝箱碼頭集卡動(dòng)態(tài)調(diào)度模型優(yōu)化［J］.武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，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］張莉，霍佳震.基于單船裝卸運(yùn)輸模型的集卡配置仿真研究［J］.系統(tǒng)仿真學(xué)報(bào)，2006(12):3532－3538.

［6］曾慶成，楊忠振.集裝箱碼頭集卡調(diào)度模型與Q學(xué)習(xí)算法［J］.哈爾濱工程大學(xué)學(xué)報(bào)，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)化問題中的應(yīng)用［J］.中國公路學(xué)報(bào)，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.