鄭紅星，于 凱，李芳芳，王 穎

（大連海事大學(xué) 交通運(yùn)輸管理學(xué)院，遼寧 大連 116026）

0 引言

近年來，隨著經(jīng)濟(jì)和航運(yùn)業(yè)的發(fā)展，集裝箱運(yùn)輸業(yè)在全球運(yùn)輸行業(yè)中的地位不斷升高，港口間的競(jìng)爭(zhēng)越來越激烈。我國(guó)集裝箱運(yùn)輸?shù)钠占盎皆絹碓礁?，集裝箱港口的吞吐量越來越大，堆場(chǎng)堆存的集裝箱總量也越來越多，堆場(chǎng)空間不足的問題日益突出，因此混堆模式在集裝箱港口的應(yīng)用越來越受到重視，混堆模式下集裝箱港口面臨的相關(guān)問題成為當(dāng)前我國(guó)港口研究的熱點(diǎn)之一。

很多學(xué)者對(duì)上述問題進(jìn)行了研究。文獻(xiàn)［1］為提高箱位分配的有效性和堆場(chǎng)空間利用率，在滾動(dòng)式計(jì)劃的基礎(chǔ)上，研究了進(jìn)、出口箱混堆箱位分配問題，并給出了兩階段算法。文獻(xiàn)［2］建立了混堆模式下進(jìn)出口集裝箱堆存均衡優(yōu)化的兩階段數(shù)學(xué)模型，并用啟發(fā)式算法對(duì)模型進(jìn)行了求解，最后利用深圳蛇口集裝箱碼頭的實(shí)際數(shù)據(jù)，采用仿真方法對(duì)模型和算法進(jìn)行了驗(yàn)證。文獻(xiàn)［3］對(duì)混堆模式下的集裝箱箱區(qū)指派問題進(jìn)行了研究，建立了箱區(qū)間作業(yè)量均衡的多目標(biāo)整數(shù)規(guī)劃模型，并采用模擬退火算法進(jìn)行了求解。文獻(xiàn)［4］研究了集裝箱堆場(chǎng)箱位指派問題，依據(jù)堆場(chǎng)混堆的作業(yè)規(guī)則定義了作業(yè)箱優(yōu)先等級(jí)，以新增集裝箱壓箱數(shù)最小為目標(biāo)為該問題構(gòu)建了箱位指派優(yōu)化模型，并設(shè)計(jì)了相應(yīng)的啟發(fā)式算法進(jìn)行求解。文獻(xiàn)［5］提出將貝位作業(yè)平衡率及集卡運(yùn)輸距離兩指標(biāo)集成為一個(gè)目標(biāo)的非線性整數(shù)規(guī)劃模型，給出了Lingo的求解過程和分析。從以上文獻(xiàn)可以看出，目前研究混堆模式的相關(guān)文獻(xiàn)大都側(cè)重于堆場(chǎng)空間資源的合理利用，但場(chǎng)橋調(diào)度對(duì)堆場(chǎng)空間資源的利用率影響很大，也很有必要進(jìn)行深入研究。

近年來國(guó)內(nèi)外很多學(xué)者針對(duì)場(chǎng)橋調(diào)度的相關(guān)問題進(jìn)行了深入研究。文獻(xiàn)［6］為了充分利用集裝箱碼頭設(shè)備資源，提出了啟發(fā)式規(guī)則用于動(dòng)態(tài)調(diào)度岸橋、場(chǎng)橋及集卡；同時(shí)基于上海港建立了仿真模型來驗(yàn)證所提調(diào)度方法的效率。文獻(xiàn)［7-8］為了減少集卡的平均等待時(shí)間，建立了多場(chǎng)橋動(dòng)態(tài)調(diào)度模型，并給出了相應(yīng)的解法，該研究十分有效地解決了場(chǎng)橋?yàn)榧ǚ?wù)的最佳序列問題。文獻(xiàn)［9］研究了帶有緩存區(qū)的集裝箱碼頭場(chǎng)橋調(diào)度問題，以最小化裝船時(shí)間為目標(biāo)建立了整數(shù)規(guī)劃模型，并設(shè)計(jì)了啟發(fā)式算法來求解模型，很好地解決了多場(chǎng)橋?yàn)閱闻_(tái)岸橋服務(wù)的問題。文獻(xiàn)［10］在考慮相鄰場(chǎng)橋間干擾問題的基礎(chǔ)上，建立了決策變量均為0-1變量的離散時(shí)間場(chǎng)橋調(diào)度模型，并設(shè)計(jì)了啟發(fā)式算法用于縮小搜索空間，將滾動(dòng)周期算法用于尋求模型的最優(yōu)解；文獻(xiàn)［11］在文獻(xiàn)［10］研究的基礎(chǔ)上考慮了更多的現(xiàn)實(shí)約束，建立了一個(gè)以任務(wù)延遲時(shí)間最小為目標(biāo)的混合整數(shù)規(guī)劃場(chǎng)橋調(diào)度模型。文獻(xiàn)［12］研究了各種堆場(chǎng)起重機(jī)的一次操作循環(huán)時(shí)間（接箱、裝箱、卸箱和交箱），給出了每個(gè)基本運(yùn)動(dòng)的時(shí)間及方差的推導(dǎo)公式，最后通過仿真評(píng)估了公式的準(zhǔn)確性。文獻(xiàn)［13］針對(duì)場(chǎng)橋調(diào)度問題建立了約束寬松的模型，并采用商業(yè)軟件包快速求解，但未能提出更有效且靈活的算法。文獻(xiàn)［14-15］基于滾動(dòng)周期采用目標(biāo)規(guī)劃法建立了動(dòng)態(tài)場(chǎng)橋調(diào)度模型，設(shè)計(jì)了混合算法進(jìn)行求解，其研究為各場(chǎng)橋如何在各箱區(qū)間轉(zhuǎn)場(chǎng)作業(yè)提供決策支持。文獻(xiàn)［16］提出了集卡與場(chǎng)橋的集成調(diào)度模型，設(shè)計(jì)了Benders分解算法。文獻(xiàn)［17］為避免大規(guī)模場(chǎng)橋調(diào)度問題的計(jì)算時(shí)間過長(zhǎng)，研究并構(gòu)建了場(chǎng)橋調(diào)度知識(shí)庫(kù)系統(tǒng)來指導(dǎo)碼頭對(duì)場(chǎng)橋的調(diào)度。文獻(xiàn)［18］為克服場(chǎng)橋資源不足的問題，引入場(chǎng)橋資源共享機(jī)制，構(gòu)建了一個(gè)帶時(shí)間窗且以運(yùn)行成本最小為目標(biāo)的兩階段數(shù)學(xué)模型，并用量子遺傳算法求解。文獻(xiàn)［19］構(gòu)建了混堆模式下的場(chǎng)橋調(diào)度模型，并給出了相應(yīng)的算法，但只考慮每個(gè)箱區(qū)單臺(tái)場(chǎng)橋的調(diào)度問題，不涉及多臺(tái)場(chǎng)橋間的干擾問題，與現(xiàn)場(chǎng)實(shí)際情況相差較大。綜合以上文獻(xiàn)，針對(duì)場(chǎng)橋調(diào)度的研究大多限定在分堆模式下，而且大部分研究都忽略集卡在場(chǎng)內(nèi)的等待時(shí)間上限，回避了討論外集卡對(duì)調(diào)度的影響。

綜上所述，針對(duì)混堆模式下的集裝箱港口多場(chǎng)橋調(diào)度問題的研究較少，本文對(duì)混堆模式集裝箱港口的某個(gè)箱區(qū)內(nèi)多個(gè)場(chǎng)橋協(xié)同調(diào)度問題進(jìn)行深入了研究，提出了混堆箱區(qū)內(nèi)多場(chǎng)橋調(diào)度模型，使固定時(shí)段內(nèi)集卡等待的港方附加成本和場(chǎng)橋移動(dòng)成本總和最小。

1 問題描述

目前我國(guó)集裝箱碼頭大都采用分堆模式堆存，但也有少部分碼頭為提高空間利用率選用了混堆模式。在分堆模式下，為內(nèi)卡服務(wù)的場(chǎng)橋只在海運(yùn)堆場(chǎng)作業(yè)，為外卡服務(wù)的場(chǎng)橋只在陸運(yùn)堆場(chǎng)作業(yè)；而在混堆箱區(qū)內(nèi)，某個(gè)箱位對(duì)應(yīng)的箱子類型可能是進(jìn)口箱、出口箱、進(jìn)箱、待提箱中的一個(gè)（均設(shè)為20 尺箱），故場(chǎng)橋要服務(wù)的集卡包括重載內(nèi)卡、重載外卡、空載內(nèi)卡和空載外卡，而且集卡作業(yè)時(shí)間和要求也不同，如圖1所示（場(chǎng)橋與貝位均按從左往右的方向編號(hào)）?？紤]到內(nèi)集卡的服務(wù)時(shí)間直接影響船期，而外集卡的服務(wù)時(shí)間影響場(chǎng)外的客戶滿意度。就碼頭而言，保證船舶準(zhǔn)時(shí)離港永遠(yuǎn)是第一位的，因此如何合理地安排內(nèi)外集卡接受服務(wù)的次序，既不影響船期又使場(chǎng)外客戶相對(duì)滿意，是混堆模式下的多場(chǎng)橋調(diào)度難于分堆模式之處，也是提高該模式下堆場(chǎng)作業(yè)效率的關(guān)鍵，具有很高的研究?jī)r(jià)值。

箱區(qū)內(nèi)多場(chǎng)橋調(diào)度問題可視為如何將箱區(qū)內(nèi)的所有裝卸任務(wù)在各場(chǎng)橋間分配，并確定各場(chǎng)橋裝卸任務(wù)的序列問題。文中研究的問題是在一段時(shí)間內(nèi)某混堆箱區(qū)內(nèi)的任務(wù)量已知且每個(gè)任務(wù)的箱位確定，但對(duì)應(yīng)的集卡（包括內(nèi)外集卡）到達(dá)作業(yè)位置的時(shí)間不同的前提下，如何確定各場(chǎng)橋執(zhí)行裝卸任務(wù)的最優(yōu)次序，使得集卡等待的碼頭附加成本（由于待作業(yè)集卡等待給碼頭帶來的額外成本）與場(chǎng)橋大車移動(dòng)成本之和最小的同時(shí)保證超過等待上限的集卡盡量少。

2 調(diào)度模型

考慮混堆模式下的集裝箱港口中，堆場(chǎng)內(nèi)作業(yè)頻率比分堆模式更高，集卡等待時(shí)長(zhǎng)過大更容易增加港口作業(yè)安全風(fēng)險(xiǎn)并降低客戶滿意度（外卡貨主和船東），因此很有必要控制內(nèi)外集卡的等待時(shí)長(zhǎng)。區(qū)別于其他文獻(xiàn)，本文提出的多場(chǎng)橋調(diào)度模型目標(biāo)函數(shù)中新引入了內(nèi)外集卡等待給港口帶來的費(fèi)用，并將各任務(wù)純裝卸所需時(shí)間（各個(gè)move）視為變量（以往視為一固定常量）；約束部分主要增加了內(nèi)外集卡在堆場(chǎng)內(nèi)的等待時(shí)間約束，包括等待費(fèi)率值和等待時(shí)長(zhǎng)之間的映射關(guān)系，以及內(nèi)外集卡各自的上限約束。

2.1 模型假設(shè)

模型假設(shè)如下：①箱區(qū)內(nèi)各任務(wù)的箱位及裝卸所需時(shí)長(zhǎng)已知；②計(jì)劃期（120min）內(nèi)各任務(wù)對(duì)應(yīng)集卡的到達(dá)時(shí)刻均可預(yù)知（外卡可提前預(yù)約，內(nèi)卡根據(jù)往返規(guī)律預(yù)約）；③只有當(dāng)任務(wù)對(duì)應(yīng)集卡到達(dá)作業(yè)位置才能裝卸；④場(chǎng)橋間不可互相跨越且須有安全作業(yè)距離；⑤外卡等待時(shí)間超過上限后優(yōu)先級(jí)高于未超等待上限的內(nèi)卡，內(nèi)卡等待時(shí)間超過上限優(yōu)先級(jí)最高，且必須被服務(wù)。

2.2 模型建立

區(qū)別于分堆模式，在混堆模式的港口中外卡和內(nèi)卡可能同時(shí)在堆場(chǎng)等待作業(yè)；但由于港口作業(yè)過程中以船舶為中心，待作業(yè)內(nèi)卡的優(yōu)先級(jí)別較高，故內(nèi)卡比外卡的等待上限低。當(dāng)外卡等待超過一定時(shí)限（據(jù)煙臺(tái)港東龍國(guó)際碼頭調(diào)查可知，一般情況下外卡等待時(shí)間在30min內(nèi)，不會(huì)影響場(chǎng)橋作業(yè)調(diào)度）時(shí)，可能會(huì)造成場(chǎng)內(nèi)交通堵塞和各種不確定的安全隱患，進(jìn)而給碼頭帶來潛在成本，故對(duì)超過該時(shí)限的外卡進(jìn)行計(jì)時(shí)計(jì)費(fèi)（記為港方的額外成本）；禁止外卡等待時(shí)長(zhǎng)超過外卡等待上限（一般情況下為1h，該情況下超過了外卡的等待容忍度，并造成了堆場(chǎng)內(nèi)的交通中斷，增大了各種安全隱患的出現(xiàn)概率）這種情況在堆場(chǎng)出現(xiàn)。與外卡類似，禁止內(nèi)卡等待時(shí)長(zhǎng)超過等待上限的情況出現(xiàn)，而不同之處在于當(dāng)內(nèi)卡的等待時(shí)長(zhǎng)少于等待上限時(shí)也計(jì)時(shí)計(jì)費(fèi)。因此，本文模型中采用下述變量。

（1）常量說明N為計(jì)劃期內(nèi)某混堆箱區(qū)內(nèi)的任務(wù)編號(hào)集合；n為N中包含的任務(wù)數(shù)；Y表示計(jì)劃期內(nèi)某箱區(qū)配置的場(chǎng)橋數(shù)，且Y＞1；m為場(chǎng)橋編號(hào)；C0為場(chǎng)橋大車移動(dòng)單位時(shí)間需要的成本；V0為場(chǎng)橋大車的移走速度；l0為單個(gè)貝位的長(zhǎng)度；bsafe為相鄰場(chǎng)橋間留有的安全作業(yè)貝位數(shù)；B（X0m）為計(jì)劃期初m號(hào)場(chǎng)橋的初始狀態(tài)所在貝位號(hào)。

（2）決策變量說明Xim表示場(chǎng)橋m第i次裝卸的任務(wù)。

（3）狀態(tài)變量說明r（Xim）為任務(wù)Xim對(duì)應(yīng)集卡到達(dá)作業(yè)位置的時(shí)刻；h（Xim）為場(chǎng)橋m完成第i次任務(wù)所需的時(shí)間；t（Xim）為場(chǎng)橋m完成第i次裝卸任務(wù)的時(shí)刻；WT（Xim）為場(chǎng)橋m第i次作業(yè)任務(wù)對(duì)應(yīng)集卡的等待時(shí)間；d（X（i-1）m，Xim）為場(chǎng)橋m從一個(gè)任務(wù)移到其緊后任務(wù)處需要的時(shí)間；B（Xim）為場(chǎng)橋m第i次作業(yè)任務(wù)所在的貝位號(hào)（由假設(shè)1知箱區(qū)內(nèi)各任務(wù)的箱位是確定的，故當(dāng)Xim確定后B（Xim）是個(gè)確定常量）；為在某時(shí)刻t場(chǎng)橋m所處的貝位，用于定義系統(tǒng)的初始時(shí)刻，視為0；d（X0m，X1m）為場(chǎng)橋m從初始位置移走到第1個(gè)裝卸任務(wù)處需要的時(shí)間；Km為場(chǎng)橋m裝卸的總?cè)蝿?wù)數(shù)。

（4）混堆模式多場(chǎng)橋調(diào)度模型特有參量W（Xim）為0-1變量且當(dāng)Xim對(duì)應(yīng)的集卡是內(nèi)卡時(shí)W（Xim）=0，否則W（Xim）=1；T1為內(nèi)集卡等待時(shí)間的上限值；T2為外集卡等待時(shí)間的上限值；T3為外集卡等待時(shí)間的開始計(jì)費(fèi)時(shí)限（一般為30 min）；C（Xim）為任務(wù)Xim對(duì)應(yīng)集卡等待單位時(shí)間的成本，

上述模型中，目標(biāo)函數(shù)中的C1為場(chǎng)橋大車移動(dòng)成本，C2為集卡等待給碼頭帶來的附加成本（包括兩部分：內(nèi)卡等待給碼頭增加的成本和外卡等待給碼頭增加的成本）。約束條件式（1）保證任一個(gè)任務(wù)的完成時(shí)刻不早于該任務(wù)的集卡到達(dá)時(shí)刻與裝卸時(shí)間之和；式（2）為某任務(wù)完成時(shí)刻、集卡到達(dá)時(shí)刻、裝卸時(shí)長(zhǎng)等之間的等式約束；式（3）為堆場(chǎng)內(nèi)某個(gè)任務(wù)對(duì)應(yīng)集卡等待時(shí)長(zhǎng)同集卡的到達(dá)時(shí)刻、作業(yè)完成時(shí)刻和裝卸作業(yè)時(shí)間的等式約束；式（4）為場(chǎng)橋從某任務(wù)行走到下一任務(wù)所需時(shí)間的等式約束；式（5）～式（7）共同保證了各任務(wù)只能由一臺(tái)場(chǎng)橋裝卸且只能被裝卸一次；式（8）保證場(chǎng)橋間不會(huì)穿越且留有安全作業(yè)距離；式（9）保證混堆模式下各任務(wù)對(duì)應(yīng)集卡的等待時(shí)間不能超過其上限（分堆模式一般無此約束）；式（10）為三個(gè)常量參數(shù)間的大小關(guān)系約束；式（11）為決策變量的取值約束。

3 模型求解

本文建立的數(shù)學(xué)模型顯然存在滿足各約束的可行解（例如采用先到先服務(wù)規(guī)則得到的一些方案即為可行解），而且由于｛Xim｝都取正整數(shù)，則可行解集為有限集合，必然存在使目標(biāo)最小的解，即模型必有最優(yōu)解。雖然模型存在最優(yōu)解，但是該模型屬于整數(shù)規(guī)劃模型，又是NP 難問題，精確求解算法（如枚舉、分支定界、割平面等）只能解決很小任務(wù)規(guī)模的問題，一旦任務(wù)規(guī)模較大，需自行設(shè)計(jì)啟發(fā)式算法快速搜索出近似最優(yōu)解，因此本文設(shè)計(jì)了改進(jìn)遺傳算法（Improved Genetic Algorithm，IGA）對(duì)模型求解，具體算法如下。

3.1 染色體編碼方式

采用實(shí)數(shù)編碼，染色體的長(zhǎng)度為（任務(wù)數(shù)＋場(chǎng)橋數(shù)-1），基因位為0表示不同場(chǎng)橋間的間隔符號(hào)，染色體的基本結(jié)構(gòu)如圖2所示，為10個(gè)集裝箱由兩場(chǎng)橋裝卸的一個(gè)方案的染色體表示。各個(gè)基因位值表示任務(wù)編號(hào)，染色體從左往右表示場(chǎng)橋的裝卸順序。

3.2 初始種群的生成

本文研究的問題要求每個(gè)任務(wù)只能由一臺(tái)場(chǎng)橋裝卸一次，因此提出一個(gè)初始種群生成方法，具體步驟如下：

步驟1 確定基因值的取值范圍為1～n（任務(wù)數(shù)）的自然數(shù)，記為集合G。

步驟2 從G內(nèi)隨機(jī)地選出n個(gè)不重復(fù)的數(shù)，按照選取順序?qū)⑦x出的數(shù)排成一個(gè)行向量。

步驟3 將“0”隨機(jī)插入步驟2生成的行向量中任意兩個(gè)相鄰的元素間，記錄插入“0”后的新行向量（獲得一個(gè)染色體）。

步驟4 返回步驟2，直至循環(huán)次數(shù)達(dá)到初始種群容量（NIND）才停止。

3.3 解空間切割

調(diào)度模型中要求相鄰兩個(gè)場(chǎng)橋不能互相干擾或跨越，初始種群中的一些個(gè)體（解）可能不滿足上述情況，故需要剔除此類不可行解。本文提出一個(gè)解空間切割法，具體為：采用相鄰場(chǎng)橋間不需跨越或干擾的約束，對(duì)當(dāng)前種群（解空間）進(jìn)行一次切割，即直接刪除不滿足條件的個(gè)體（解）；然后采用隨機(jī)復(fù)制剩余個(gè)體的方式恢復(fù)種群至原始規(guī)模。

3.4 適值函數(shù)與選擇機(jī)制

本文問題中所有任務(wù)對(duì)應(yīng)的集卡等待時(shí)間必須低于各自的上限，而且當(dāng)任務(wù)規(guī)模較大時(shí)，算法在尋優(yōu)過程中會(huì)出現(xiàn)較多的個(gè)體（解）不滿足上述約束。若仍采用解空間切割法則會(huì)造成剩余的可行解很少，甚至為零，因此，引入一個(gè)帶有懲罰規(guī)則的適值函數(shù)，以便保證求得的調(diào)度問題解對(duì)應(yīng)的方案中所有集卡的等待時(shí)間低于各自上限。

具體的適值函數(shù)式為：

式中：Xi表示種群中的某個(gè)個(gè)體（解）；f（Xi）表示解Xi所對(duì)應(yīng)的目標(biāo)函數(shù)值；Freq為方案中等待超過上限的集卡數(shù)；M為一極大的正數(shù)。

本文采用輪盤賭選擇機(jī)制（允許相同個(gè)體）進(jìn)行個(gè)體的選擇。

3.5 交叉操作

針對(duì)染色體編碼特點(diǎn)，采用順序交叉法重組染色體，具體步驟如下：

步驟1 隨機(jī)選擇兩個(gè)交叉點(diǎn)X和Y，確定兩父體（P1，P2）中將被復(fù)制到子代的基因片段，并初步得到兩個(gè)不完整的子代a，b。

步驟2 對(duì)P1和P2從第二個(gè)交叉點(diǎn)Y開始列出原基因碼順序，得到P1和P2的基因碼排列。

步驟3 從P1和P2的基因碼排列中分別刪掉P2和P1已復(fù)制到子代的基因碼，得到排列a′和b′。

步驟4 對(duì)a，從第二個(gè)交叉點(diǎn)開始按順序?qū)⑴帕衎′的基因碼從左往右填入對(duì)應(yīng)的基因位并替換“×”。對(duì)b做同樣操作，完成后得到兩個(gè)新生的子代個(gè)體O1和O2。圖3所示為兩個(gè)個(gè)體的交叉實(shí)例展示。

在隨機(jī)交叉過程中可能會(huì)出現(xiàn)一些“錯(cuò)誤個(gè)體”（“0”處于基因鏈的首位和末位的個(gè)體），例如任意P1和P2順序交叉后可能有“0”基因位于整個(gè)染色體的首位或尾位。因此，在算法的每一代完成所有交叉操作后，立刻調(diào)用基因修復(fù)程序，將生成的新種群中的錯(cuò)誤個(gè)體修復(fù)為可行個(gè)體。

3.6 改進(jìn)變異操作與終止規(guī)則

提出改進(jìn)的變異操作，具體如下：初次變異，為了實(shí)現(xiàn)場(chǎng)橋間任務(wù)分配的改變，采用“倒位變異”，即在“0”兩側(cè)分別選兩個(gè)基因倒換位置；緊接著二次變異，采用“換序變異”改變某場(chǎng)橋裝卸任務(wù)的順序，即在“0”同一側(cè)選兩個(gè)基因換位，如圖4所示。

相比傳統(tǒng)遺傳算法的變異操作只有一次，且各個(gè)基因位的值均可在一個(gè)給定的取值范圍內(nèi)變異或者選擇兩基因互換，改進(jìn)的變異操作提高了變異后解的準(zhǔn)確性和多樣性。

當(dāng)算法的迭代次數(shù)達(dá)到預(yù)先設(shè)置的進(jìn)化代數(shù)時(shí)，算法終止。

3.7 基因修復(fù)技術(shù)

在算法的迭代過程中，交叉操作可能導(dǎo)致錯(cuò)誤個(gè)體出現(xiàn)于群體中。為了消除這些錯(cuò)誤個(gè)體對(duì)整個(gè)程序的影響（出現(xiàn)中斷或死循環(huán)），傳統(tǒng)的遺傳算法中采用直接跳過個(gè)體、替換個(gè)體或直接刪除個(gè)體等方法。但是該類方法會(huì)使得錯(cuò)誤的個(gè)體中大部分的正確遺傳信息被忽略，而且當(dāng)所求問題的約束較嚴(yán)格時(shí)，會(huì)使種群被某些個(gè)體占領(lǐng)。

因此本文提出基因修復(fù)技術(shù)。例如：某染色體的基因鏈長(zhǎng)為n，染色體中“0”基因所在位置為zero＿index，則該染色體的修復(fù)流程如圖5所示。相比傳統(tǒng)遺傳算法中對(duì)錯(cuò)誤個(gè)體的處理方法，基因修復(fù)技術(shù)既能利用錯(cuò)誤個(gè)體的有用信息、維持種群多樣性，又能消除錯(cuò)誤個(gè)體對(duì)整個(gè)程序的影響。

3.8 IGA 的算法流程

上文介紹了算法的設(shè)計(jì)思路、改進(jìn)之處及一些相關(guān)規(guī)則，IGA 的算法流程如圖6所示。

4 數(shù)值實(shí)驗(yàn)

4.1 算法性能實(shí)驗(yàn)

為驗(yàn)證IGA 的優(yōu)越性，同時(shí)考慮到本文與文獻(xiàn)［5］的研究均為箱區(qū)內(nèi)的多場(chǎng)橋調(diào)度問題，故以文獻(xiàn)［5］中的算例（見文獻(xiàn)中EX1）作為數(shù)值實(shí)驗(yàn)對(duì)象，在Pentium 1.6GHz PC上（與文獻(xiàn)［5］中實(shí)驗(yàn)環(huán)境相同）進(jìn)行20次實(shí)驗(yàn)。實(shí)驗(yàn)中IGA 的各項(xiàng)參數(shù)設(shè)置如下：

種群大小為300、交叉概率為0.4、連續(xù)兩次變異概率分別為0.1與0.08，算法的最大迭代次數(shù)為1 000。將IGA 多次實(shí)驗(yàn)結(jié)果的均值與文獻(xiàn)［5］中的實(shí)驗(yàn)結(jié)果（文獻(xiàn)中前兩種方法）進(jìn)行對(duì)比，具體的比較指標(biāo)有集卡總等待時(shí)間（Total PM Waiting Time，TPMWT）和求解時(shí)間（solution time，ST）。兩者的實(shí)驗(yàn)結(jié)果對(duì)比詳見表1。

表1 實(shí)驗(yàn)結(jié)果對(duì)比表

其中CPLEX 及Li W K 兩方法均由文獻(xiàn)［5］提出。從表1可以看出，三種方法所得TPMWT 基本相同，但I(xiàn)GA 的求解速度遠(yuǎn)遠(yuǎn)優(yōu)于CPLEX 和Li W K。結(jié)果表明本文提出的IGA 是較優(yōu)的。

4.2 多場(chǎng)橋調(diào)度實(shí)驗(yàn)

本文采用煙臺(tái)港某碼頭的真實(shí)數(shù)據(jù)進(jìn)行多場(chǎng)橋調(diào)度實(shí)驗(yàn)，實(shí)驗(yàn)主要針對(duì)某2h內(nèi)碼頭某混堆箱區(qū)上的場(chǎng)橋裝卸任務(wù)，即在場(chǎng)橋數(shù)量Y=2 的情況下進(jìn)行實(shí)驗(yàn)。其中：裝卸任務(wù)、各任務(wù)位置、對(duì)應(yīng)集卡到達(dá)時(shí)刻、裝卸時(shí)長(zhǎng)、對(duì)應(yīng)集卡類型如表2所示，表中RT為任務(wù)對(duì)應(yīng)集卡到達(dá)作業(yè)位置的時(shí)刻，系統(tǒng)初始時(shí)刻為0；OT為任務(wù)所需的裝卸時(shí)長(zhǎng)；Type為任務(wù)對(duì)應(yīng)集卡類型，“0”代表外卡，“1”代表內(nèi)卡。

表2 實(shí)例的詳細(xì)情況

續(xù)表2

模型中的場(chǎng)橋大車移動(dòng)速度、集卡等待上限，以及各項(xiàng)成本率等常量參數(shù)取值如表3所示。

采用4.1 節(jié)實(shí)驗(yàn)中的算法參數(shù)設(shè)置，在Intel（R）CoreTM i5-2450M 2.50GHz的處理器，4GB內(nèi)存的PC 上進(jìn)行MATLAB 7.6.0編程求解。實(shí)驗(yàn)過程中，隨著遺傳代數(shù)的增加，最優(yōu)值與各代均值的收斂效果如圖7所示，算法進(jìn)化至604代時(shí)目標(biāo)值收斂于1 182.00 元，對(duì)應(yīng)的滿意解（個(gè)體）為：［1 4 5 7 3 9 11 12 14 15 21 23 19 17 26 0 2 6 8 10 13 16 18 20 25 24 22］。因此，兩臺(tái)場(chǎng)橋裝卸各個(gè)任務(wù)箱的先后順序?yàn)椋篩C1：1→4→5→7→3→9→11→12→14→15→21→23→19→17→26；YC2：2→6→8→10→13→16→18→20→25→24→22。

表3 參數(shù)取值

實(shí)驗(yàn)詳細(xì)運(yùn)行結(jié)果如表4所示，兩臺(tái)場(chǎng)橋在箱區(qū)內(nèi)各個(gè)貝位間的實(shí)時(shí)行走路徑如圖8所示。從圖8中可以看出兩臺(tái)場(chǎng)橋的路徑曲線無交點(diǎn)，說明求得的調(diào)度方案確實(shí)未出現(xiàn)場(chǎng)橋間的干擾或跨越。

表4 實(shí)驗(yàn)結(jié)果

續(xù)表4

在集裝箱碼頭實(shí)際作業(yè)中，場(chǎng)橋調(diào)度問題大都采用先到先服務(wù)（First Come First Service，F(xiàn)CFS）的方法。若采用FCFS的作業(yè)方式，則上述算例中集卡等待的港方附加成本和場(chǎng)橋大車移動(dòng)成本之和為1 690.00 元，且有2輛集卡的等待時(shí)間超過其上限，這在實(shí)際作業(yè)中會(huì)嚴(yán)重影響堆場(chǎng)內(nèi)的交通。而采用本文調(diào)度模型求得的優(yōu)化調(diào)度方案時(shí)集卡等待的港方附加成本和場(chǎng)橋大車移動(dòng)成本之和降低為1 182.00元，且只有1輛集卡等待超過上限。很顯然，該優(yōu)化調(diào)度方法的性能相比FCFS優(yōu)越很多。

4.3 不同任務(wù)規(guī)模下的多場(chǎng)橋調(diào)度實(shí)驗(yàn)

通過不同任務(wù)規(guī)模下的實(shí)驗(yàn)，進(jìn)一步驗(yàn)證所提調(diào)度方法的有效性。在實(shí)驗(yàn)過程中不改變算法的種群規(guī)模、交叉率、變異率、終止代數(shù)以及相關(guān)參數(shù)取值，只改變算例的任務(wù)規(guī)模與分布情況，實(shí)驗(yàn)結(jié)果對(duì)比與分析如表5所示，表中CPUtime用于統(tǒng)計(jì)算法的運(yùn)行時(shí)間，即算法效率指標(biāo)；EUBN（exceed upper bound number）表示超過等待上限的集卡數(shù)量）。

表5 不同任務(wù)規(guī)模的實(shí)驗(yàn)結(jié)果對(duì)比與分析

從表5中可以看出：隨著任務(wù)規(guī)模的增大，CPUtime呈線性增大且比較平緩，因此在問題的規(guī)模增大時(shí)，本文算法的計(jì)算時(shí)間不會(huì)呈幾何級(jí)數(shù)增長(zhǎng)。

隨著算例規(guī)模的增大，優(yōu)化后的EUBN基本呈遞增趨勢(shì)。當(dāng)EUBN≤1時(shí)，成本降低百分比隨規(guī)模呈遞增趨勢(shì)；當(dāng)EUBN＞1時(shí)，成本降低百分比隨規(guī)模呈下降趨勢(shì)。

以上分析進(jìn)一步論證了本文提出的多場(chǎng)橋調(diào)度方法的有效性，而且能在很短時(shí)間內(nèi)求得較優(yōu)的調(diào)度方案。

5 結(jié)束語(yǔ)

本文分析了集裝箱港口混堆箱區(qū)內(nèi)多臺(tái)場(chǎng)橋協(xié)同的調(diào)度問題，建立了混堆箱區(qū)內(nèi)的多場(chǎng)橋調(diào)度模型，并設(shè)計(jì)了求解模型的改進(jìn)遺傳算法。數(shù)值實(shí)驗(yàn)結(jié)果表明：本文所提算法能夠很好地求解類似問題；同時(shí)與傳統(tǒng)的場(chǎng)橋調(diào)度法（FCFS）相比，采用本文調(diào)度模型得到的方案不但可降低集卡等待的港方附加成本與場(chǎng)橋大車移動(dòng)的總成本，降低比例為5.18%～37.43%，而且可減少超過等待上限的集卡數(shù)量。因此，本研究可為混堆模式集裝箱碼頭的場(chǎng)橋調(diào)度提供較科學(xué)的指導(dǎo)依據(jù)，進(jìn)而提高碼頭的效益和整體服務(wù)水平。

本研究將各任務(wù)需要的裝卸時(shí)間視為已知，但實(shí)際作業(yè)中由于倒箱的影響，會(huì)使某些任務(wù)的裝卸時(shí)長(zhǎng)有所偏差。因此在本研究的基礎(chǔ)上，可將倒箱問題加入研究中，還可以進(jìn)一步研究多個(gè)箱區(qū)的多場(chǎng)橋聯(lián)合實(shí)時(shí)調(diào)度問題。

［1］KANG Haigui，LIU Yan，ZHOU Pengfei.Research on dynamic storage space allocation based on mixture storage［J］.Port &Waterway Engineering，2009（8）：73-77（in Chinese）.［康海貴，劉 艷，周鵬飛.基于混堆的集裝箱堆場(chǎng)動(dòng)態(tài)箱位分配研究［J］.水運(yùn)工程，2009（8）：73-77.］

［2］TAO Jinghui，WANG Min.Assign problem of container yard section based on mixed storage model［J］.Systems Engineering—Theory &Practice，2009，29（8）：185-192（in Chinese）.［陶經(jīng)輝，汪 敏.基于混堆模式的集裝箱堆場(chǎng)區(qū)段分配［J］.系統(tǒng)工程理論與實(shí)踐，2009，29（8）：185-192.］

［3］ZHENG Hongxing，DU Liang，DONG Jian.Optimization model on container slot allocation in container yard with mixed storage mode［J］.Journal of Transportation Systems Engineering and Information Technology，2012（1）：153-159（in Chinese）.［鄭紅星，杜 亮，董 鍵.混堆模式下集裝箱堆場(chǎng)箱位指派優(yōu)化模型［J］.交通運(yùn)輸系統(tǒng)工程與信息，2012（1）：153-159.］

［4］ZHENG Hongxing，WANG Xiaowei，DONG Jian，et al.Optimization method on container slot allocation in container yard with mixed storage mode［J］.Journal of Wuhan University of Technology：Transportation Science &Engineering，2013，37（1）：1-5（in Chinese）.［鄭紅星，王曉薇，董 鍵，等.混堆模式下集裝箱堆場(chǎng)箱區(qū)指派優(yōu)化方法［J］.武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2013，37（1）：1-5.］

［5］FAN Jiajing.Space allocation for container terminal based on mixed storage model［J］.Journal of Zhejiang University of Science and Technology，2013，25（3）：168-175（in Chinese）.［范佳靜.基于混堆模式的集裝箱堆場(chǎng)空間分配研究［J］.浙江科技學(xué)院學(xué)報(bào)，2013，25（3）：168-175.］

［6］ZHANG Hailin，JIANG Zhibin.Simulation studies of heuristic approaches for dynamic scheduling of container terminal operations［J］.International Journal of Modeling and Simulation，2008，28（4）：410-422.

［7］GUO Xi，HUANG Shellying.Performing a＊search for yard crane dispatching in container terminals［C］／／Proceedings of International Conference on Tools with Artificial Intelligence.2008，1：263-267.

［8］GUO Xi，HUANG Shellying，HSU Wenjing，et al.Dynamic yard crane dispatching in container terminals with predicted vehicle arrival information［J］.Advanced Engineering Informatics，2011，25（3）：472-484.

［9］LEE Derhorng，CAO Zhi，CHEN Jianghang，et al.Load scheduling of multiple yard crane systems in container terminal with buffer areas［J］.Transportation Research Record，2009，2097（1）：70-77.

［10］LI Wenkai，WU Yong，PETERING M E H，et al.Discrete time model and algorithms for container yard crane scheduling［J］.European Journal of Operational Research，2009，198（1）：165-172.

［11］LI Wenkai，GOH Mark，WU Yong，et al.A continuous time model for multiple yard crane scheduling with last minute job arrivals［J］.International Journal of Production Economics，2012，136（2）：332-343.

［12］LEE B K，KIM K H.Comparison and evaluation of various cycle-time models for yard cranes in container terminals［J］.International Journal of Production Economics，2010，126（2）：350-360.

［13］HU Zhihua.Improved discrete time model for container yard crane scheduling［C］／／Proceedings of the 3rd International Joint Conference on Computational Science and Optimization.Washington，D.C.，USA：IEEE Computer Society，2010：34-37.

［14］HE Junliang，CHANG Daofang，MI Weijian et al.A hybrid parallel genetic algorithm for yard crane scheduling［J］.Transportation Research Part E：Logistics and Transportation Review，2010，46（1）：136-155.

［15］CHANG Daofang，JIANG Zuhua，YAN Wei，et al.Developing a dynamic rolling-horizon decision strategy for yard crane scheduling［J］.Advanced Engineering Informatics，2011，25（3）：485-494.

［16］CAO Jinxin，LEE Derhorng，CHEN Jianghang，et al.The integrated yard truck and yard crane scheduling problem：Benders'decomposition-based methods［J］.Transportation Research Part E：Logistics and Transportation Review，2010，46（3）：344-353.

［17］YAN Wei，HUANG Youfang，CHANG Daofang，et al.An investigation into knowledge-based yard crane scheduling for container terminals［J］.Advanced Engineering Informatics，2011，25（3）：462-471.

［18］REN Wei.Yard crane scheduling with time window and dynamic demand strategy based on resource sharing［J］.International Journal of Digital Content Technology and its Applications，2012，6（8）：213-221.

［19］ZHENG Hongxing，YU Kai.Yard crane scheduling model and algorithm in mixture storage block［J］.Computer Engineering and Applications，DOI：10.3778／j.issn.1002-8331.1303-0464（in Chinese）.［鄭紅星，于 凱.混堆集裝箱箱區(qū)內(nèi)場(chǎng)橋調(diào)度模型與算法［J］.計(jì)算機(jī)工程與應(yīng)用，Doi：10.3778／j.issn.1002-8331.1303-0464.］

［20］NG W C，MAK K L.Yard crane scheduling in port container terminals［J］.Applied Mathematical Modeling，2005，29（3）：263-276.