周玉清，韓曉龍

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

0 引言

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

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

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

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

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

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

1 問題描述

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

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

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

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

2 模型建立

2.1 模型假設(shè)

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

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

3）不考慮跨運車移動過程中的交通堵塞情況，不考慮翻箱問題；

4）岸橋裝卸任意集裝箱的時間相同、跨運車裝卸任意集裝箱時間相同，跨運車攜箱與空箱移動速度相同。

2.2 符號說明

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

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

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

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

2.3 建立模型

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

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

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

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

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

3 算法設(shè)計

3.1 基本思想

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

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

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

3.2.1 算法總流程

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

圖2 算法流程Fig.2 Algorithm flowchart

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）改進解流程。

步驟5 初始化。W作為初始值，將此時的岸橋作業(yè)序列以及跨運車作業(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è)序列。根據(jù)Tabu2、T2，利用交換、逆序等方式產(chǎn)生候選序列，作為跨運車作業(yè)序列，將該候選解加入候選集N，n=n+1，若n

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

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

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

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

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

3.2.2 編碼方式

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

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

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

圖3 ExchangeFig.3 Exchange

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

圖4 2-OptFig.4 2-Opt

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

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

步驟1 初始化。

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

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

步驟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?η，則進入步驟2.1）；否則進入步驟2.3）。

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

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

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

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

3.2.4 禁忌對象與禁忌長度

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

RTS 算法具體步驟如下：

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

步驟2 RTS 算法框架。

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

2.2）把當前最優(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）判斷當前時間距離上次禁忌長度發(fā)生改變的時間是否超過預(yù)設(shè)值，若超過，則T=T×decrease，轉(zhuǎn)步驟4。

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

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

4 數(shù)值算例分析

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

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

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

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

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

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

4.2 性能分析

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

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

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

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

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

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

實驗1 緩存區(qū)與跨運車影響分析。

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

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

圖6 完工時間比較Fig.6 Completion time comparison

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

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

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

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

圖8 跨運車使用率比較Fig.8 Comparison of average utilization rate of straddle carriers

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

圖9 岸橋等待時間Fig.9 Waiting time of quay crane

實驗2 岸橋與跨運車配比影響分析。

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

實驗2 中，設(shè)置岸橋數(shù)量為3，進行岸橋與跨運車配比研究。分別設(shè)置3 組實驗，3 組實驗的裝箱量分別為15、30、45。緩存區(qū)容量設(shè)置為3，每組實驗中岸橋與跨運車配比分別為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ù)-跨運車數(shù)）”。每組實驗中集裝箱量分別為15、30、45，用以觀察在不同任務(wù)量的情況下，岸橋與跨運車配比對聯(lián)合作業(yè)的影響。實驗結(jié)果如圖10～12 所示。

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

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

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

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

5 結(jié)語

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

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