周玉清，韓曉龍

（上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306）

0 引言

集裝箱港口是由岸橋，運(yùn)輸工具、場橋、堆場等組成的復(fù)雜系統(tǒng)。集裝箱港口作業(yè)是由港口設(shè)備相互組合、相互協(xié)同完成的，這些設(shè)備的作業(yè)效率也直接影響了集裝箱港口的作業(yè)效率。大型港口平均每天要處理幾萬TEU（Twenty-feet Equivalet Unit）的集裝箱，因此港口設(shè)備之間相互協(xié)同作業(yè)的效率對于保證時(shí)間和成本效益非常重要，如何提高集裝箱港口作業(yè)效率已成為當(dāng)前集裝箱港口研究重點(diǎn)關(guān)注的內(nèi)容。目前我國集裝箱港口主要采用的集裝箱裝卸船的工藝流程為船舶 → 岸邊集裝箱起重機(jī)→ 集卡→集裝箱龍門起重機(jī) →堆場。這種裝卸工藝往往會(huì)出現(xiàn)設(shè)備之間相互等待的現(xiàn)象，造成設(shè)備之間的操作不協(xié)調(diào)，而集裝箱跨運(yùn)車（Straddle Carrier，SC）［1］可以從碼頭到堆場進(jìn)行水平運(yùn)輸作業(yè)，也可以進(jìn)行堆場的堆碼、搬運(yùn)和裝卸作業(yè)，可跨越箱列，還可跨越鐵路線路，實(shí)現(xiàn)一機(jī)多用，無需依靠起重機(jī)，減少運(yùn)輸設(shè)備與起重機(jī)的對齊抓取等作業(yè)環(huán)節(jié)、場橋等機(jī)械設(shè)備的使用等，可有效解決設(shè)備之間操作不協(xié)調(diào)的問題。當(dāng)前跨運(yùn)車技術(shù)在國外發(fā)展已到一定高度，國內(nèi)無人跨運(yùn)車技術(shù)正處于高速發(fā)展的階段，因此研究跨運(yùn)車在港口內(nèi)的調(diào)度問題至關(guān)重要。

針對運(yùn)輸設(shè)備與岸橋之間協(xié)調(diào)問題，一些專家對提高岸橋使用率、優(yōu)化改進(jìn)岸橋作業(yè)模式以及運(yùn)輸設(shè)備作業(yè)模式進(jìn)行研究，以提高港口作業(yè)效率：Goodchild 等［2］通過理論分析和數(shù)學(xué)演算證明了雙循環(huán)岸橋的可行性，得出岸橋雙循環(huán)操作可以減少10%的操作時(shí)間；Zhang 等［3］考慮集裝箱在船舶上的裝載情況，優(yōu)化岸橋最小作業(yè)循環(huán)次數(shù)；常祎妹等［4］考慮裝卸同步作業(yè)約束以及生產(chǎn)調(diào)度中的不確定因素，研究了不確定條件下的岸橋同步裝卸問題；孫清臣等［5］針對當(dāng)前集裝箱碼頭采用的雙循環(huán)集卡操作策略，得出雙循環(huán)操作策略平均能減少20%的裝卸作業(yè)時(shí)間，并減少集卡空載率；高熙等［6］設(shè)計(jì)了一種包含線性時(shí)間復(fù)雜度的岸橋最優(yōu)調(diào)度構(gòu)造算法，并證明了算法的高效性。

還有一些專家針對岸橋與水平運(yùn)輸設(shè)備等進(jìn)行聯(lián)合調(diào)度研究來解決港口設(shè)備不協(xié)調(diào)的問題：余孟齊等［7］考慮集裝箱之間優(yōu)先關(guān)系，研究了集裝箱碼頭岸橋和集卡的集成調(diào)度問題；Vahdani 等［8］整合了岸橋分配與內(nèi)集卡共享，通過將內(nèi)集卡分享到不同的碼頭岸線來實(shí)現(xiàn)碼頭工作量與內(nèi)集卡之間的平衡；梁承姬等［9］采用滾動(dòng)窗策略研究岸橋集卡的聯(lián)合調(diào)度問題，并用遺傳算法進(jìn)行求解，用以應(yīng)對集裝箱碼頭突發(fā)事件的發(fā)生；Chen 等［10］采用三階段算法研究岸橋與集卡的集成調(diào)度，采用啟發(fā)式算法產(chǎn)生岸橋作業(yè)時(shí)間表，再進(jìn)行集卡調(diào)度，最后得出完整的調(diào)度方案；李坤等［11］關(guān)注了集卡與軌道吊的聯(lián)系，以最小最大完工時(shí)間為目標(biāo)，設(shè)計(jì)了兩階段禁忌算法求解；馬孫豫等［12］研究了雙小車岸橋與自動(dòng)導(dǎo)引小車（Automated Guided Vehicle，AGV）的協(xié)同調(diào)度問題，以AGV 調(diào)度為主，建立以卸船作業(yè)最末任務(wù)結(jié)束時(shí)間最小化為目標(biāo)的模型，采用多層編碼粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法進(jìn)行求解；張笑菊等［13］研究了岸橋同貝同步裝卸時(shí)多環(huán)節(jié)作業(yè)協(xié)調(diào)問題，并設(shè)計(jì)啟發(fā)式算法求解。

以上研究以岸橋與集卡為主要研究對象，都能有效提高碼頭作業(yè)效率，但當(dāng)跨運(yùn)車引入碼頭后，岸橋緩存區(qū)將大大影響碼頭作業(yè)效率。

在緩存區(qū)容量限制下，岸橋與跨運(yùn)車之間的聯(lián)合調(diào)度問題研究較少。湯鵬飛等［14］研究了在岸橋下方設(shè)置岸橋緩存區(qū)，對ALV（Autonomous Land Vehicle）行走路徑進(jìn)行優(yōu)化；Kress 等［15］構(gòu)建了帶緩存區(qū)單循環(huán)岸橋與跨運(yùn)車的聯(lián)合調(diào)度模型，并將彈射鏈加入禁忌搜索（Tabu Search，TS）方法中進(jìn)行求解；朱家棟［16］以跨運(yùn)車到達(dá)碼頭前沿時(shí)間已知的背景下，將岸橋緩存區(qū)具體化為岸橋下車道，考慮了岸橋小車不能帶箱跨越跨運(yùn)車等實(shí)際情況，研究了岸橋與跨運(yùn)車同步裝船作業(yè)的優(yōu)化問題，設(shè)計(jì)了雙層遺傳算法進(jìn)行求解；Chen等［17］建立跨運(yùn)車雙循環(huán)作業(yè)模型，利用禁忌搜索和模擬退火算法求解，發(fā)現(xiàn)在相同碼頭配置下，跨運(yùn)車比AGV 作業(yè)效率更高；安東等［18］研究了集裝箱跨運(yùn)車在中小型碼頭的應(yīng)用模式，為跨運(yùn)車進(jìn)一步發(fā)展與應(yīng)用提供理論基礎(chǔ)；Pellegrini 等［19］驗(yàn)證了在解決二次分配問題時(shí)，與禁忌搜索算法相比，響應(yīng)性禁忌搜索算法穩(wěn)定性更強(qiáng)。

現(xiàn)有的關(guān)于岸橋與跨運(yùn)車的聯(lián)合作業(yè)研究中，都在以岸橋或跨運(yùn)車的固定作業(yè)序列下，研究另一方的作業(yè)序列優(yōu)化，而未考慮岸橋與跨運(yùn)車作業(yè)序列都不固定情況下，雙方的聯(lián)合作業(yè)問題；且研究都是在岸橋單循環(huán)策略（岸橋先卸后裝）或岸橋只卸只裝下的研究，而岸橋雙循環(huán)作業(yè)（岸橋可裝可卸）與跨運(yùn)車的雙循環(huán)操作有更大的經(jīng)濟(jì)效益。因此本文將在岸橋與跨運(yùn)車作業(yè)序列都不固定的情況下，研究雙循環(huán)策略下岸橋與跨運(yùn)車的聯(lián)合作業(yè)序列優(yōu)化問題來降低總體完工時(shí)間。

1 問題描述

岸橋與跨運(yùn)車的聯(lián)合作業(yè)過程中，岸橋?qū)⒋系募b箱放在其對應(yīng)的緩存區(qū)，直接由集裝箱跨運(yùn)車搬運(yùn)和堆場堆碼，兩者互不干涉；但當(dāng)緩存區(qū)內(nèi)箱位放滿時(shí)，依然不可避免地出現(xiàn)等待時(shí)間。因此安排合理的岸橋與跨運(yùn)車聯(lián)合作業(yè)序列和緩存區(qū)容量，可有效解決以跨運(yùn)車作為水平運(yùn)輸設(shè)備與岸橋進(jìn)行聯(lián)合裝卸集裝箱作業(yè)時(shí)產(chǎn)生的時(shí)空協(xié)調(diào)問題。

岸橋與跨運(yùn)車在港口中的聯(lián)合作業(yè)情況如圖1 所示。對于出口箱作業(yè)，跨運(yùn)車將集裝箱從堆場運(yùn)送至相應(yīng)岸橋緩存區(qū)后離開進(jìn)行下一個(gè)集裝箱作業(yè)，岸橋?qū)⒕彺鎱^(qū)內(nèi)集裝箱進(jìn)行裝船作業(yè)；對于進(jìn)口箱作業(yè)，岸橋?qū)⒓b箱從船舶上卸載放至其緩存區(qū)后進(jìn)行下一個(gè)集裝箱作業(yè)，跨運(yùn)車將岸橋緩存區(qū)集裝箱送至堆場相應(yīng)位置。岸橋的雙循環(huán)策略中，岸橋無需進(jìn)行“先卸后裝”作業(yè)，當(dāng)岸橋?qū)⑦M(jìn)口箱放置到緩存區(qū)后，若緩存區(qū)內(nèi)有出口箱，可就近選擇將出口箱放置船上，這樣減少了岸橋空箱作業(yè)時(shí)間?？邕\(yùn)車雙循環(huán)策略中，當(dāng)跨運(yùn)車將進(jìn)口箱從岸橋緩存區(qū)運(yùn)送到堆場中時(shí)，可選擇不返回岸橋緩存區(qū)進(jìn)行進(jìn)口箱任務(wù)，而可就近選擇進(jìn)行出口箱任務(wù)，這樣減少了跨運(yùn)車空車返回的時(shí)間，可降低跨運(yùn)車空載率。

圖1 岸橋與跨運(yùn)車的聯(lián)合作業(yè)流程Fig.1 Joint operation flow of quay crane and straddle carrier

本文以岸橋與跨運(yùn)車為研究對象，針對雙循環(huán)策略下岸橋與跨運(yùn)車的聯(lián)合作業(yè)序列優(yōu)化問題，以總完工時(shí)間最小為目標(biāo)，考慮岸橋緩存區(qū)容量限制、岸橋與跨運(yùn)車聯(lián)合操作、安全時(shí)間等約束，建立雙循環(huán)策略下岸橋與跨運(yùn)車聯(lián)合作業(yè)的混合整數(shù)規(guī)劃模型。然后設(shè)計(jì)基于貪婪算法的響應(yīng)性禁忌搜索算法，得出最優(yōu)的岸橋與跨運(yùn)車聯(lián)合裝卸作業(yè)序列。最后，通過算例數(shù)值分析，討論緩存區(qū)容量大小、跨運(yùn)車數(shù)量，岸橋與跨運(yùn)車配比對于岸橋與跨運(yùn)車協(xié)同調(diào)度的影響。

2 模型建立

2.1 模型假設(shè)

1）不同岸橋下方設(shè)置緩存區(qū)的容量大小保持一致；

2）跨運(yùn)車一次作業(yè)一個(gè)集裝箱，不考慮多載情況；

3）不考慮跨運(yùn)車移動(dòng)過程中的交通堵塞情況，不考慮翻箱問題；

4）岸橋裝卸任意集裝箱的時(shí)間相同、跨運(yùn)車裝卸任意集裝箱時(shí)間相同，跨運(yùn)車攜箱與空箱移動(dòng)速度相同。

2.2 符號說明

參數(shù)與變量如表1 所示。其中Rkj為人工變量，用來路徑中保證不出現(xiàn)子回路，表示任務(wù)優(yōu)先級，任務(wù)越靠后變量Rkj越大。

表1 參數(shù)符號說明Tab.1 Description of parameter symbols

集裝箱進(jìn)出緩存區(qū)時(shí)刻如表2 所示，規(guī)定集裝箱離開與進(jìn)入緩存區(qū)的時(shí)刻為岸橋或跨運(yùn)車將集裝箱在緩存區(qū)內(nèi)提起或放下的時(shí)刻。

表2 緩存區(qū)內(nèi)時(shí)間變量的描述Tab.2 Description of time variable in buffer

2.3 建立模型

本文主要目的是通過優(yōu)化岸橋與跨運(yùn)車聯(lián)合作業(yè)序列，以降低全局完工時(shí)間，因此以最小化最大完工時(shí)間為目標(biāo)，建立混合整數(shù)規(guī)劃模型。

目標(biāo)函數(shù)（3）表示，最小化最大完成任務(wù)時(shí)刻。對于出口箱，完成任務(wù)時(shí)刻為岸橋?qū)⒓b箱放置在船上的時(shí)刻；對于進(jìn)口箱，完成任務(wù)時(shí)刻為跨運(yùn)車將集裝箱放置在堆場中的時(shí)刻。約束（4）（5）表示總完工時(shí)間為最晚結(jié)束任務(wù)的時(shí)刻。

M表示一個(gè)極大的數(shù)。約束（6）～（14）表示關(guān)于岸橋操作約束。約束（6）（7）表示同一個(gè)岸橋一次只能處理一個(gè)集裝箱。約束（8）避免了每個(gè)岸橋的作業(yè)序列出現(xiàn)子回路。約束（9）（10）表示岸橋開始執(zhí)行第一個(gè)任務(wù)的時(shí)刻，約束（9）表示如果岸橋第一任務(wù)為進(jìn)口箱，則岸橋開始時(shí)刻大于等于0；約束（10）表示如果岸橋第一任務(wù)為出口箱，則岸橋開始操作的時(shí)刻大于跨運(yùn)車將集裝箱放入緩存區(qū)的時(shí)刻以及安全時(shí)間之和。約束（11）表示岸橋處理兩個(gè)任務(wù)之間的時(shí)間間隔大于岸橋在兩個(gè)任務(wù)之間的空載移動(dòng)時(shí)間。約束（12）表示岸橋結(jié)束處理任務(wù)i的時(shí)刻與開始處理任務(wù)i的時(shí)刻之差大于岸橋處理任務(wù)的時(shí)間。

約束（15）～（24）表示關(guān)于跨運(yùn)車操作的約束。約束（15）（16）保證同一輛跨運(yùn)車僅有一個(gè)后續(xù)任務(wù)和一個(gè)前序任務(wù)。約束（17）（18）表示在虛擬出發(fā)點(diǎn)派出的跨運(yùn)車與返回虛擬結(jié)束點(diǎn)的跨運(yùn)車的數(shù)量為一個(gè)定值。約束（19）表示跨運(yùn)車不能從后續(xù)任務(wù)返回前序任務(wù)，不能直接從虛擬出發(fā)點(diǎn)到虛擬結(jié)束點(diǎn)，不能自循環(huán)。約束（20）（21）表示跨運(yùn)車開始執(zhí)行第一個(gè)任務(wù)的時(shí)刻，約束（20）表示每個(gè)跨運(yùn)車負(fù)責(zé)的任務(wù)回路中，如果跨運(yùn)車第一任務(wù)為出口箱，則跨運(yùn)車開始時(shí)刻大于等于跨運(yùn)車從初始位置到達(dá)任務(wù)點(diǎn)的時(shí)間；約束（21）如果跨運(yùn)車第一任務(wù)為進(jìn)口箱，則跨運(yùn)車開始時(shí)刻比岸橋?qū)⒓b箱放入緩存區(qū)的時(shí)刻以及安全時(shí)間之和大。約束（22）表示跨運(yùn)車處理兩個(gè)任務(wù)之間的時(shí)間間隔比跨運(yùn)車在兩個(gè)任務(wù)之間的移動(dòng)時(shí)間大。約束（23）表示跨運(yùn)車結(jié)束處理任務(wù)i的時(shí)刻與開始處理任務(wù)i的時(shí)刻之差，大于跨運(yùn)車處理任務(wù)的時(shí)間。

約束（25）～（36）表示關(guān)于緩存區(qū)的約束。約束（25）表示在k岸橋的j任務(wù)進(jìn)入緩存區(qū)之前，緩存區(qū)中的集裝箱數(shù)不超過緩存區(qū)容量。約束表示規(guī)定每個(gè)集裝箱任務(wù)，必須在緩存區(qū)內(nèi)停留tb的時(shí)間。約束（26）（27）表示安全時(shí)間約束；約束（28）（29）表示滿足決策變量的限制。例如約束（28）表示，當(dāng)j為出口箱，i為出口箱，i進(jìn)入緩存區(qū)的時(shí)刻小于j進(jìn)入緩存區(qū)的時(shí)刻，即Yki

3 算法設(shè)計(jì)

3.1 基本思想

本文所建模型的求解計(jì)算難度較大，屬于NP 難問題。針對研究問題與模型特點(diǎn)，本文在求解岸橋和跨運(yùn)車聯(lián)合作業(yè)序列時(shí)容易出現(xiàn)死鎖問題，因此在計(jì)算時(shí)會(huì)出現(xiàn)大量不可行解。而蟻群算法、遺傳算法、模擬退火算法等屬于概率性原理算法，應(yīng)用于解決本文中問題時(shí)，局部搜索能力差，容易錯(cuò)失最優(yōu)解。禁忌搜索（TS）算法可對局部進(jìn)行大量搜索，更容易得到可行解，因此禁忌搜索算法較適合于本文的求解。

TS 算法是一種逐步尋優(yōu)的鄰域搜索算法，從初始解出發(fā)，標(biāo)記已經(jīng)解得的局部最優(yōu)解或求解過程。然而傳統(tǒng)TS算法對初始解的依賴性很強(qiáng)，且很難對某一特定問題確定有效的禁忌長度，難以避免搜索過早收斂，從而陷入局部最優(yōu)，錯(cuò)失全局最優(yōu)解。因此本文設(shè)計(jì)基于貪婪算法的響應(yīng)性禁忌搜索算法用于求解模型，算法采用貪婪算法得到比較好的初始解，用多種鄰域搜索策略將集中性搜索和多樣性搜索策略相結(jié)合，保證鄰域的多樣性與集中性，且加入響應(yīng)性禁忌搜索（Reactive Tabu Search，RTS）適時(shí)改變禁忌長度，加強(qiáng)TS 搜索機(jī)制，以求得全局最優(yōu)解。

3.2 基于貪婪算法的響應(yīng)性禁忌搜索算法

3.2.1 算法總流程

本文首先利用貪婪算法生成初始解，隨后利用禁忌搜索算法改進(jìn)初始解，從而搜尋出更好更優(yōu)的解。算法流程如圖2 所示。

圖2 算法流程Fig.2 Algorithm flowchart

1）貪婪算法生成初始解流程。

步驟1 利用貪婪算法生成初始岸橋作業(yè)序列。

（a）將岸橋任務(wù)按照最早可開始時(shí)間從早到晚的順序排列，得到集合Lk。

（b）集合Lk中的第一個(gè)運(yùn)輸任務(wù)作為第一臺岸橋任務(wù)集合K1的第一個(gè)任務(wù)，即K1={li}，計(jì)算該岸橋完成任務(wù)的工作時(shí)間T(K1)。將li從Lk刪除。

（c）更新所有任務(wù)的最早開始時(shí)間，除li外所有進(jìn)口箱開始時(shí)間推遲T(K1) +t，t為岸橋空箱返回船的時(shí)間，若出口箱最早開始時(shí)間小于T(K1)，則出口箱最早開始時(shí)間更新為T(K1)，否則不變。

（d）若Lk≠?，返回步驟1（a），否則，進(jìn)入步驟1（e）。

（e）岸橋k的作業(yè)任務(wù)分配完成，任務(wù)集合為K1。開始為下一個(gè)岸橋分配任務(wù)，直到所有岸橋任務(wù)分配完成。

步驟2 根據(jù)岸橋作業(yè)序列，忽略跨運(yùn)車分配問題以及緩存區(qū)容量問題，僅考慮集裝箱從起點(diǎn)到達(dá)終點(diǎn)的運(yùn)輸時(shí)間，生成集裝箱最早作業(yè)時(shí)間表以及最晚作業(yè)時(shí)間表。

步驟3 確定跨運(yùn)車運(yùn)輸序列。根據(jù)集裝箱作業(yè)時(shí)間表，按照集裝箱作業(yè)時(shí)間表中的優(yōu)先關(guān)系，運(yùn)用貪婪算法為多輛跨運(yùn)車分配運(yùn)輸任務(wù)。

（a）將跨運(yùn)車作業(yè)任務(wù)按最晚開始時(shí)間從早到晚的順序排序，排序集合為L。

（b）集合L中的第一個(gè)運(yùn)輸任務(wù)lki(k∈K，i∈J)作為第一輛車輛任務(wù)集合V1的第一個(gè)任務(wù)，即V1={lki}，并計(jì)算該車輛完成該任務(wù)的工作時(shí)間T(V1)，此時(shí)第一輛車輛為距離任務(wù)lki出發(fā)地最近的車輛，從L中刪除lki。

（c）從集合L中尋找出發(fā)地與任務(wù)lki目的地的距離較近的任務(wù)集合，并從中尋找最晚出發(fā)時(shí)刻小于或等于完成任務(wù)lki時(shí)刻的任務(wù)。分別計(jì)算完成該任務(wù)的時(shí)刻，取完成任務(wù)時(shí)刻最小的任務(wù)lkj作為該車輛的第二個(gè)任務(wù)，并將該任務(wù)加入V1，更新T(V1)，從L中刪除lkj。

（d）根據(jù)步驟3（c）依次為第一輛車輛分配任務(wù)，當(dāng)所有任務(wù)的最晚出發(fā)時(shí)刻小于T(V1)時(shí)，第一輛車輛的運(yùn)輸任務(wù)分配完成，任務(wù)集合為V1。開始為第二位車輛分配任務(wù)。

（e）依次按照步驟3（b）～（d），依次為所有車輛分配任務(wù)，直到所有車輛以及所有任務(wù)分配完成。

步驟4 初始值生成。根據(jù)所生成的岸橋與跨運(yùn)車的作業(yè)序列，考慮緩存區(qū)容量，調(diào)整岸橋與跨運(yùn)車的實(shí)際作業(yè)時(shí)刻表，并計(jì)算岸橋與跨運(yùn)車完成任務(wù)的最大時(shí)刻W。

2）改進(jìn)解流程。

步驟5 初始化。W作為初始值，將此時(shí)的岸橋作業(yè)序列以及跨運(yùn)車作業(yè)序列作為初始解S。

步驟6 輸入算法參數(shù)：最大迭代次數(shù)rmax、最大候選集數(shù)目nmax、候選集N、禁忌表1（Tabu1）、禁忌長度（T1）、禁忌表2（Tabu2）和禁忌長度（T2）。

步驟7 根據(jù)Tabu1、T1，利用交換、逆序等方式產(chǎn)生候選序列，作為岸橋作業(yè)序列，將此序列加入Tabu1。

步驟8 根據(jù)岸橋作業(yè)序列，利用貪婪算法生成跨運(yùn)車作業(yè)序列。根據(jù)Tabu2、T2，利用交換、逆序等方式產(chǎn)生候選序列，作為跨運(yùn)車作業(yè)序列，將該候選解加入候選集N，n=n+1，若n

步驟9 對N中的候選解進(jìn)行解碼計(jì)算，選出當(dāng)前最優(yōu)解S'，記錄其適應(yīng)度值W(S')。

步驟10 更新當(dāng)前最優(yōu)解，更新Tabu2，將W(S')代入RTS 策略（見4.3.3 節(jié)RTS 算法），動(dòng)態(tài)調(diào)整T2。

步驟11 禁忌搜索算法迭代終止檢驗(yàn)。檢驗(yàn)是否達(dá)到最大迭代次數(shù)：若是，則進(jìn)入步驟13；若不是，則進(jìn)入步驟12。

步驟12 更新Tabu1，將W(S')代入RTS 算法（見4.2.4節(jié)RTS 算法），動(dòng)態(tài)調(diào)整T1，進(jìn)入步驟7。

步驟13 輸出全局最優(yōu)解。

3.2.2 編碼方式

編碼方式如表3 所示。表3 中任務(wù)的編號11 表示第1 臺岸橋的第1 個(gè)任務(wù)。第二列表示每個(gè)岸橋處理任務(wù)的優(yōu)先級，數(shù)字越小優(yōu)先級越高，例如第1 個(gè)岸橋任務(wù)序列為11-12-13-14-15，第二個(gè)岸橋的任務(wù)序列為23-22-24-21-25。第三列表示跨運(yùn)車處理任務(wù)的優(yōu)先級序列；第四列表示跨運(yùn)車編號，例如任務(wù)11 由編號為1 的跨運(yùn)車進(jìn)行操作，跨運(yùn)車作業(yè)序列為，SC1：11-14-15-25，SC2：12-13-23，SC3：22-21-24。

表3 編碼表Tab.3 Coding table

3.2.3 鄰域結(jié)構(gòu)設(shè)計(jì)

禁忌搜索算法鄰域設(shè)置。禁忌搜索基于鄰域變換進(jìn)行搜索，確定鄰域操作至關(guān)重要。本文選用3 種應(yīng)用于車輛路徑問題的鄰域結(jié)構(gòu)，操作時(shí)隨機(jī)選擇其中一種。例如跨運(yùn)車任務(wù)優(yōu)先級序列為φ={1，2，3，4，5，6}，陰影處為隨機(jī)選擇的兩個(gè)任務(wù)i和j。

1）Exchange：隨機(jī)選擇任務(wù)i和j的位置互換，得到：1-4-3-2-5-6，則跨運(yùn)車序列為11-21-13-12-22-23。

圖3 ExchangeFig.3 Exchange

2）2-Opt：隨機(jī)選擇任務(wù)i和j之間的任務(wù)逆序，得到：1-5-4-3-2-6。

圖4 2-OptFig.4 2-Opt

3）Glover 等［20］提出了一個(gè)多樣性搜索策略的方法程序，通過定義步長對置換重新排序，從當(dāng)前全局最優(yōu)解創(chuàng)建新解。從步長（step）2 開始，每次重新啟動(dòng)算法時(shí)，步長都會(huì)增加，必要時(shí)循環(huán)回到原始步長。

多樣性搜索策略程序步驟。

步驟1 初始化。

1.1）令當(dāng)前全局最優(yōu)解為初始解S；

1.2）令k=1，start=step，j=start，η為一個(gè)空集。

步驟2 生成鄰域解。

2.1）將元素j加入集合η中，令S(k)=?(j)；

2.2）令k=k+1；

2.3）若j

2.4）若start>1，則start=start-1，j=start，否則結(jié)束。

2.5）如果j?η，則進(jìn)入步驟2.1）；否則進(jìn)入步驟2.3）。

為說明上述方法，考慮以下置換示例。

原解為：φ={1，2，3，4，5，6}。

選擇步長step=2，算法初始化的第一次迭代將初始變量j轉(zhuǎn)換為2，在本例中，該迭代導(dǎo)致j的變化范圍為公差為2的等差數(shù)列，則S中的元素逐個(gè)被φ(j)取代。在本例中n=6。在start=2 時(shí)的第一次迭代之后，得到以下部分置換：S={2，4，6，_，_，_}。

最后，通過步驟2（d）的傳遞將start設(shè)置為1，并獲得以下完整排列S={2，4，6，1，3，5}。以這種方式，對于每個(gè)步長，獲得不同的排列，以擴(kuò)大鄰域搜索范圍。

3.2.4 禁忌對象與禁忌長度

禁忌對象為任務(wù)序列。針對3 個(gè)不同的鄰域搜索方法設(shè)置3 個(gè)不同的禁忌表。禁忌長度為每個(gè)禁忌對象在禁忌表中的儲(chǔ)存時(shí)間。禁忌長度過短，可能進(jìn)入循環(huán)無法跳出；禁忌長度過長，可能造成搜索空間很小，搜索不充分。RTS算法通過在搜索過程中改變禁忌長度來避免此問題。RTS中禁忌長度T的選擇基于解的重復(fù)次數(shù)與禁忌長度改變時(shí)間差。調(diào)整規(guī)則有兩種方式：第一個(gè)方式是當(dāng)解S兩次連續(xù)重復(fù)出現(xiàn)之間的間隔regap在所設(shè)定的最大間隔gapmax之內(nèi)，增加禁忌長度T=T×increase，擴(kuò)大當(dāng)前的搜索區(qū)域；第二種方式是當(dāng)前時(shí)間距離上次禁忌長度改變的時(shí)間超過預(yù)先設(shè)定的值，減少禁忌長度T=T×decrease，加強(qiáng)局部區(qū)域的搜索。當(dāng)解S'的重復(fù)次數(shù)repeat，超過預(yù)先規(guī)定的解重復(fù)的最大次數(shù)remax，則將解S'加入禁忌表 。其中，increase為禁忌長度增加比例；decrease為禁忌長度減少比例。

RTS 算法具體步驟如下：

步驟1 初始化RTS 相關(guān)參數(shù)。

步驟2 RTS 算法框架。

2.1）生成候選解，找出當(dāng)前最優(yōu)解。

2.2）把當(dāng)前最優(yōu)解存入Hash 表，判斷是否重復(fù)：若重復(fù)，轉(zhuǎn)步驟2.3）；反之轉(zhuǎn)步驟2.5）。

2.3）解重復(fù)次數(shù)repeat=repeat+1，若repeat>remax，轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟2.4）。

2.4）判斷重復(fù)間隔regap，若regap>gapmax，禁忌長度T=T×increase；否則轉(zhuǎn)步驟4。

2.5）判斷當(dāng)前時(shí)間距離上次禁忌長度發(fā)生改變的時(shí)間是否超過預(yù)設(shè)值，若超過，則T=T×decrease，轉(zhuǎn)步驟4。

步驟3 逃離機(jī)制。跳出當(dāng)前搜索區(qū)域，利用多樣性搜索策略，即策略3（見3.2.3 節(jié)3））重新生成初始解進(jìn)行搜索。

步驟4 算法終止。達(dá)到預(yù)先設(shè)定最大迭代步數(shù)，算法終止。

4 數(shù)值算例分析

4.1 算例設(shè)計(jì)與求解結(jié)果

算例中設(shè)備參數(shù)來源于文獻(xiàn)［5，15，21］。設(shè)置3 個(gè)岸橋，4 個(gè)跨運(yùn)車，每個(gè)岸橋有5 個(gè)需要裝卸的集裝箱，共15 個(gè)任務(wù)。表4 為參數(shù)，表5 為任務(wù)集合。

表4 參數(shù)Tab.4 Parameter

表5 任務(wù)集合Tab.5 Task collection

利用基于貪婪算法的響應(yīng)性禁忌搜索算法對該算例進(jìn)行求解，算法收斂情況如圖5 所示。最終得到的目標(biāo)函數(shù)值為2 345 s，任務(wù)序列如表6 所示。在該算例下岸橋與跨運(yùn)車的聯(lián)合作業(yè)序列：岸橋1 為12-15-14-11-13，岸橋2 為22-24-23-21-25，岸橋3 為34-33-32-31-35；跨運(yùn)車1 為14-15-11-12，跨運(yùn)車2 為21-24-25-32，跨運(yùn)車3 為23-22-31-33；跨運(yùn)車4 為35-13-34，具體調(diào)度安排如表7。

圖5 基于貪婪算法的響應(yīng)性禁忌搜索算法收斂圖Fig.5 Convergence graph of responsive tabu search algorithm based on greedy algorithm

表6 聯(lián)合作業(yè)任務(wù)序列Tab.6 Joint operation task sequence

表7 岸橋與跨運(yùn)車調(diào)度表Tab.7 Scheduling table of quay crane and straddle carrier

通過表7 可以看出在岸橋與跨運(yùn)車雙循環(huán)操作策略下，岸橋無需直接開始裝卸作業(yè)，具有一定的緩沖時(shí)間，這是由于跨運(yùn)車到達(dá)緩存區(qū)需要一定的時(shí)間，或在調(diào)度安排下，跨運(yùn)車從堆場運(yùn)輸出口箱至緩存區(qū)需要一定的運(yùn)輸時(shí)間。

4.2 性能分析

為驗(yàn)證本文算法有效性，參考文獻(xiàn)［16］設(shè)計(jì)算例，將本文算法與CPLEX、傳統(tǒng)禁忌搜索算法、遺傳算法求解結(jié)果進(jìn)行分析比較，結(jié)果如表8 所示。

從表8 中，可以看出當(dāng)任務(wù)量較少時(shí)，CPLEX 計(jì)算速度較快，兩者計(jì)算目標(biāo)值相等，而當(dāng)任務(wù)量達(dá)到15 時(shí)，CPLEX計(jì)算時(shí)間大于90 min，而本文算法計(jì)算時(shí)間為26 s，且計(jì)算結(jié)果無偏差。

表8 算法性能分析表Tab.8 Algorithm performance analysis table

與傳統(tǒng)禁忌搜索算法相比，本文算法在求解速度上具有明顯優(yōu)勢，且求解效果更好，而當(dāng)任務(wù)規(guī)模達(dá)到45 時(shí)，傳統(tǒng)算法很難搜索出可行解。因此基于貪婪算法的響應(yīng)性禁忌搜索算法可很好地解決跨運(yùn)車與岸橋的調(diào)度問題；與遺傳算法相比，本文算法在求解速度與求解效果方面都具有明顯優(yōu)勢。

4.3 參數(shù)配比實(shí)驗(yàn)研究及結(jié)論

本節(jié)將重點(diǎn)分析緩存區(qū)容量與跨運(yùn)車的數(shù)量、岸橋與跨運(yùn)車數(shù)配比對總體作業(yè)時(shí)間快慢的影響。為評估緩存區(qū)容量的設(shè)置以及跨運(yùn)車數(shù)對整個(gè)調(diào)度過程產(chǎn)生的影響，利用上述算例數(shù)據(jù)設(shè)置兩組實(shí)驗(yàn)。

實(shí)驗(yàn)1 緩存區(qū)與跨運(yùn)車影響分析。

實(shí)驗(yàn)1 設(shè)置集裝箱量為15，其中出口箱量為8，進(jìn)口箱量為7。岸橋數(shù)為3，改變緩存區(qū)容量與跨運(yùn)車數(shù)量進(jìn)行實(shí)驗(yàn)。該實(shí)驗(yàn)算例中，跨運(yùn)車數(shù)設(shè)置為1～9，緩存區(qū)容量設(shè)置為1～4，用以觀察緩存區(qū)與跨運(yùn)車對完工時(shí)間、岸橋平均使用率、跨運(yùn)車平均使用率、岸橋等待時(shí)間的變化。實(shí)驗(yàn)中，岸橋與跨運(yùn)車使用率計(jì)算如式（37）（38）所示：

每組實(shí)驗(yàn)取10 次有效值的平均值。實(shí)驗(yàn)結(jié)果如圖6～9所示。

圖6 完工時(shí)間比較Fig.6 Completion time comparison

如圖6 所示，從橫向上來看，在任務(wù)量相同的情況下，跨運(yùn)車數(shù)的增加，可顯著減少總完工時(shí)間。當(dāng)跨運(yùn)車數(shù)為1時(shí)，在四種緩存區(qū)的情況下，總完工時(shí)間都是最長的，而當(dāng)跨運(yùn)車的數(shù)增加到8 時(shí)總完工時(shí)間達(dá)到最小。當(dāng)跨運(yùn)車數(shù)超過6 后，緩存區(qū)容量大小不再影響總體完工時(shí)間。從縱向上來看，緩存區(qū)容量的增加可減少總體運(yùn)行時(shí)間，當(dāng)緩存區(qū)數(shù)量為3 時(shí)，再次增加緩存區(qū)容量，將無法影響完工時(shí)間。這是由于岸橋緩存區(qū)有足夠的容量放置岸橋以及跨運(yùn)車放置的集裝箱，因此岸橋與跨運(yùn)車可相對更加獨(dú)立地進(jìn)行裝卸工作，減少了等待時(shí)間，因此完工時(shí)間減少。

如圖7 所示，岸橋的平均使用率呈階梯式增長。當(dāng)緩存區(qū)容量為3、4 時(shí)，5 臺跨運(yùn)車即可達(dá)到局部最優(yōu)；而緩存區(qū)容量為1、2 時(shí)，需要7 臺跨運(yùn)車。因此合適的緩存區(qū)可以在保證岸橋使用率的情況下，減少跨運(yùn)車的使用。

圖7 岸橋平均使用率比較Fig.7 Comparison of average utilization rate of quay crane

如圖8 所示，跨運(yùn)車的平均使用率呈增長趨勢。與岸橋平均使用率（圖7）不同的是，當(dāng)跨運(yùn)車數(shù)達(dá)到局部最優(yōu)后，繼續(xù)增加跨運(yùn)車，跨運(yùn)車使用效率會(huì)減小，這是由于跨運(yùn)車設(shè)備過多而造成跨運(yùn)車等待時(shí)間增加。因此對于決策者來說，安排大量的跨運(yùn)車可降低作業(yè)時(shí)間成本，提高岸橋使用效率，但這種情況下會(huì)出現(xiàn)跨運(yùn)車使用率降低的情況。

圖8 跨運(yùn)車使用率比較Fig.8 Comparison of average utilization rate of straddle carriers

從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，緩存區(qū)與跨運(yùn)車充足時(shí)，跨運(yùn)車的使用效率在70%～85%，而岸橋的使用效率只有55%～65%，結(jié)合圖9 所示，岸橋的等待時(shí)間穩(wěn)定在400 s 左右，這是因?yàn)楫?dāng)出口箱數(shù)量大于進(jìn)口箱數(shù)量時(shí)，總會(huì)有岸橋需要等待跨運(yùn)車將出口箱運(yùn)至緩存區(qū)。因此提高跨運(yùn)車的性能或減少待裝箱任務(wù)到岸橋緩存區(qū)的距離，雙循環(huán)策略的優(yōu)勢將更加明顯。從該實(shí)驗(yàn)中可以看到，緩存區(qū)的設(shè)置可以明顯降低完工時(shí)間，提升岸橋與跨運(yùn)車的使用效率，在該算例下，緩存區(qū)容量為3 即可滿足系統(tǒng)最優(yōu)。

圖9 岸橋等待時(shí)間Fig.9 Waiting time of quay crane

實(shí)驗(yàn)2 岸橋與跨運(yùn)車配比影響分析。

目前我國傳統(tǒng)碼頭岸橋與集卡配比一般需要達(dá)到1∶5，而岸橋與集裝箱跨運(yùn)車配比一般只需要1∶3 即可完成相關(guān)任務(wù)（配比數(shù)據(jù)來源于振華重工）。傳統(tǒng)碼頭一般為岸橋配置固定數(shù)量的集卡進(jìn)行作業(yè)，而本文研究的是跨運(yùn)車可以為任意一個(gè)岸橋服務(wù)，因此探究岸橋與跨運(yùn)車總體系統(tǒng)配比具有重要意義。

實(shí)驗(yàn)2 中，設(shè)置岸橋數(shù)量為3，進(jìn)行岸橋與跨運(yùn)車配比研究。分別設(shè)置3 組實(shí)驗(yàn)，3 組實(shí)驗(yàn)的裝箱量分別為15、30、45。緩存區(qū)容量設(shè)置為3，每組實(shí)驗(yàn)中岸橋與跨運(yùn)車配比分別為1∶1（3-3），3∶4（3-4），3∶5（3-5），1∶2（3-6），3∶7（3-7），3∶8（3-8），1∶3（3-9）?！埃ǎ眱?nèi)為“（岸橋數(shù)-跨運(yùn)車數(shù)）”。每組實(shí)驗(yàn)中集裝箱量分別為15、30、45，用以觀察在不同任務(wù)量的情況下，岸橋與跨運(yùn)車配比對聯(lián)合作業(yè)的影響。實(shí)驗(yàn)結(jié)果如圖10～12 所示。

圖10 完工時(shí)間變化情況Fig.10 Change of completion time

圖11 岸橋使用率變化情況Fig.11 Changes in utilization rate of quay crane

通過實(shí)驗(yàn)結(jié)果可以看到，隨著岸橋與跨運(yùn)車配比增大，總完工時(shí)間逐漸減少。如圖12 所示，岸橋與跨運(yùn)車配比為3∶8 時(shí)，跨運(yùn)車使用率出現(xiàn)峰值，此時(shí)再次增加跨運(yùn)車，跨運(yùn)車使用率減少，而完工時(shí)間沒有明顯變化。這是由于在緩存區(qū)的限制下，跨運(yùn)車等待時(shí)間增長，造成擁堵情況。因此在雙循環(huán)策略下，無需按照多個(gè)跨運(yùn)車服務(wù)同一個(gè)岸橋進(jìn)行操作，可根據(jù)岸橋數(shù)與任務(wù)量，安排岸橋與跨運(yùn)車的總體系統(tǒng)配比，此時(shí)可以減少跨運(yùn)車使用，減少碼頭設(shè)備量。

圖12 跨運(yùn)車使用率變化情況Fig.12 Changes in utilization rate of straddle carriers

5 結(jié)語

本文引入雙循環(huán)操作策略，研究了岸橋與跨運(yùn)車的聯(lián)合作業(yè)序列優(yōu)化問題，以雙循環(huán)岸橋和跨運(yùn)車為研究對象，考慮了岸橋緩存區(qū)容量限制，岸橋雙循環(huán)操作以及跨運(yùn)車雙循環(huán)運(yùn)輸策略，建立了以總完工時(shí)間最小化為目標(biāo)的數(shù)學(xué)規(guī)劃模型。針對禁忌搜索算法的局限性，設(shè)計(jì)了基于貪婪算法的響應(yīng)性禁忌搜索算法進(jìn)行求解并設(shè)計(jì)算例，驗(yàn)證了模型與算法的有效性。最后設(shè)計(jì)實(shí)驗(yàn)，對比岸橋緩存區(qū)容量和跨運(yùn)車對完工時(shí)間、岸橋與跨運(yùn)車使用率的影響，又研究了岸橋與跨運(yùn)車數(shù)配比情況。最終得到算例實(shí)驗(yàn)下最優(yōu)的跨運(yùn)車數(shù)量、岸橋緩存區(qū)容量，以及合理的岸橋與跨運(yùn)車配比。結(jié)果表明：緩存區(qū)的設(shè)置可明顯減少完工時(shí)間、提高岸橋與跨運(yùn)車使用率，雙循環(huán)策略下設(shè)置合理的岸橋與跨運(yùn)車聯(lián)合作業(yè)序列，可減少跨運(yùn)車的使用數(shù)量，減少碼頭設(shè)備。

本文在研究岸橋與跨運(yùn)車的聯(lián)合調(diào)度問題時(shí)，未考慮跨運(yùn)車的翻箱問題，跨運(yùn)車作為可自主在堆場與岸橋之間作業(yè)的運(yùn)輸設(shè)備，在堆場以及岸橋緩存區(qū)中可能存在翻箱問題，因此可以進(jìn)一步考慮跨運(yùn)車的翻箱問題。由于跨運(yùn)車速率、堆場與碼頭前沿之間的距離對跨運(yùn)車使用率以及總體作業(yè)時(shí)間影響較大，因此在大型碼頭，未來還可以考慮岸橋、跨運(yùn)車以及其他運(yùn)輸設(shè)備的聯(lián)合調(diào)度問題。