蔣敏敏，添 玉，黃 渭，范勤勤

（1.中山大學(xué)南方學(xué)院 商學(xué)院，廣東 廣州 510970；2.上海海事大學(xué) 物流工程學(xué)院，上海 201306）

0 引言

目前，全球貿(mào)易處于高速發(fā)展中，世界貨物進(jìn)出口量也隨之迅速增長(zhǎng)，海上運(yùn)輸以貨運(yùn)成本低且運(yùn)輸量大的優(yōu)勢(shì)，在全球貿(mào)易中占據(jù)不可動(dòng)搖的地位。作為聯(lián)系海上運(yùn)輸與內(nèi)陸腹地的港口正面臨著集裝箱激增的巨大壓力，另外隨著勞動(dòng)力成本不斷增加以及環(huán)保理念日益深入人心，必然驅(qū)使港口向自動(dòng)化、智能化的方向發(fā)展。自動(dòng)化集裝箱碼頭堆場(chǎng)作業(yè)系統(tǒng)不僅是碼頭內(nèi)外作業(yè)區(qū)域的連接樞紐，而且保障了整個(gè)碼頭進(jìn)出貨物的均衡性，其裝卸工藝和設(shè)備也決定整個(gè)碼頭運(yùn)營(yíng)效率。場(chǎng)橋是堆場(chǎng)的主要裝卸設(shè)備，其調(diào)度過程十分復(fù)雜，目前國(guó)內(nèi)外學(xué)者對(duì)雙場(chǎng)橋調(diào)度問題有一定研究。針對(duì)單一作業(yè)模式下雙場(chǎng)橋調(diào)度問題，邵乾虔，等[1]考慮進(jìn)口箱疏港過程中翻箱作業(yè)不能跨貝進(jìn)行的現(xiàn)實(shí)約束，并建立動(dòng)態(tài)優(yōu)化模型并求解；景貞文，等[2]針對(duì)雙軌道吊作業(yè)進(jìn)口箱優(yōu)先權(quán)分配問題，提出9條優(yōu)先權(quán)分配規(guī)則以及直接避讓和動(dòng)態(tài)暫存區(qū)兩種非優(yōu)先軌道吊避讓方案；范厚明，等[3]考慮場(chǎng)橋?qū)嶋H作業(yè)中的安全距離，建立混合整數(shù)規(guī)劃模型，運(yùn)用遺傳算法求解；Gharehgozli，等[4]以場(chǎng)橋完成任務(wù)時(shí)間和由于被動(dòng)移動(dòng)和等待造成非正常作業(yè)時(shí)間為目標(biāo)研究雙場(chǎng)橋調(diào)度，建立混合整數(shù)規(guī)劃模型，并運(yùn)多重啟發(fā)式算法求解。針對(duì)雙場(chǎng)橋調(diào)度過程中交接問題，Zhou，等[5]提出交換點(diǎn)的概念，并用優(yōu)化算法求解最小化延遲時(shí)間和延遲的工作數(shù)量；魏晨，等[6]考慮不可跨越式ASC 之間的空間約束，以最小化任務(wù)完成時(shí)間為目標(biāo)函數(shù)建立整數(shù)規(guī)劃模型并求解，減少因時(shí)空同步和干涉造成的等待；丁一，等[7]考慮接力、緩沖區(qū)、碰撞等條件約束，建立以最小化外集卡和船舶延時(shí)為目標(biāo)函數(shù)的不對(duì)稱的多旅行商模型，求解優(yōu)化雙自動(dòng)化軌道吊調(diào)度；Huang，等[8]提出一種利用裝載小車側(cè)面作業(yè)的雙自動(dòng)化軌道吊(ARMG)在線調(diào)度方法，用非零博弈策略建立雙場(chǎng)橋調(diào)度模型，并提出一步前瞻算法和兩步前瞻算法；周嫻靜，等[9]通過固定存、取箱貝位研究跨越式雙自動(dòng)化軌道吊調(diào)度，考慮上自動(dòng)化軌道吊作業(yè)同一貝位任務(wù)時(shí)避免碰撞約束，建立多目標(biāo)混合整數(shù)規(guī)劃模型。上述文獻(xiàn)缺乏多場(chǎng)橋調(diào)度、交接貝位選擇與協(xié)同策略的集成考慮，因此，本文以自動(dòng)化堆場(chǎng)為對(duì)象，考慮混合堆存模式下對(duì)等式ARMG 工藝特性和能耗成本，提出協(xié)同調(diào)度模型和策略，優(yōu)化存取順序以及交接點(diǎn)決策，改善自動(dòng)化堆場(chǎng)裝卸性能。

1 問題描述

目前，自動(dòng)化集裝箱碼頭堆場(chǎng)布局采用垂直碼頭岸線為主，如荷蘭Euromax 碼頭、巴塞羅那港口（BEST）碼頭以及廈門遠(yuǎn)海和上海洋山港四期，如圖1所示。每個(gè)箱區(qū)兩側(cè)分別設(shè)有平行軌道，配置兩臺(tái)對(duì)等式ARMG，需保持一定安全距離，不能相互跨越。雖然該布置會(huì)降低裝卸設(shè)備的靈活性和可靠性，但可以提高場(chǎng)地利用率，降低投資成本，且可進(jìn)行海側(cè)、陸側(cè)及接力作業(yè)，提高堆場(chǎng)效率。箱區(qū)海側(cè)端部配置支架系統(tǒng)，有效緩解耦合剛性矛盾，采取混合堆存模式，既可堆放出口箱，也可臨時(shí)存儲(chǔ)進(jìn)口箱。一是提高ARMG 裝卸效率，如ARMG 作業(yè)卸船箱到指定位置后，可以順便提取附近的裝船箱至支架，減少空駛時(shí)間；二是提高AGV 裝卸效率；三是碼頭整個(gè)運(yùn)作系統(tǒng)由水平運(yùn)輸、岸橋作業(yè)以及堆場(chǎng)作業(yè)系統(tǒng)組成，每個(gè)環(huán)節(jié)都相互影響，AGV和堆場(chǎng)裝卸協(xié)同終將改善船舶裝卸效率。

上述作業(yè)模式增加了系統(tǒng)柔性，但對(duì)裝卸設(shè)備的調(diào)度提出更高要求。自動(dòng)化堆場(chǎng)裝卸效率與雙對(duì)等式ARMG 的調(diào)度策略和交接貝有關(guān)，所以可視為均衡優(yōu)化問題，即保持堆場(chǎng)穩(wěn)定有序作業(yè)的同時(shí)提高整個(gè)碼頭的運(yùn)作效率。因此，使用堆場(chǎng)裝卸完工時(shí)刻評(píng)價(jià)雙ARMG 協(xié)同程度，采用雙ARMG 行駛距離評(píng)價(jià)堆場(chǎng)作業(yè)成本，采用海側(cè)ARMG 完成所有裝船箱的結(jié)束時(shí)刻評(píng)價(jià)碼頭整體作業(yè)效率。

圖1 自動(dòng)化集裝箱碼頭整體布局

2 雙對(duì)等式ARMG調(diào)度模型

2.1 假設(shè)條件

（1）集港在裝船作業(yè)過程之前已經(jīng)完成，疏港在裝船作業(yè)過程之后進(jìn)行；（2）假設(shè)岸橋調(diào)度結(jié)果已知，這里岸橋調(diào)度的任務(wù)以簇任務(wù)形式定義，且簇任務(wù)約束關(guān)系已知；（3）調(diào)度計(jì)劃期內(nèi)，已知每個(gè)箱任務(wù)的操作類型（裝/卸）、在船上以及堆場(chǎng)的存放位置；（4）ARMG、AGV可用數(shù)量已知，且每個(gè)設(shè)備一次只處理一個(gè)集裝箱；（5）ARMG、AGV 空/重載與行駛速度以及設(shè)備的裝卸效率已知；（6）進(jìn)出口箱允許堆存在同箱區(qū)，各箱區(qū)貝位容量充足；（7）暫不考慮翻箱作業(yè)。

2.2 符號(hào)變量說明

2.3 目標(biāo)函數(shù)

（1）最小化所有ARMG中最大結(jié)束時(shí)刻：

（2）最小化ARMGa 中完成裝船任務(wù)的最大結(jié)束時(shí)刻：

（3）最小化所有ARMG行駛路程：

2.4 約束條件

式（4）-式（7）表示ARMG 一次只能執(zhí)行一個(gè)箱任務(wù)，且都要被執(zhí)行，一旦被執(zhí)行不能中斷。式（8）表示一個(gè)集裝箱只被分配箱區(qū)一個(gè)貝位。式（9）、式（10）表示同一個(gè)ARMG執(zhí)行相鄰任務(wù)的時(shí)間邏輯關(guān)系。式（11）、式（12）表示同一箱區(qū)的ARMG 任何時(shí)刻不可少于兩個(gè)貝位的時(shí)間間隔且不得跨越操作。式（13）-式（15）表示箱任務(wù)在堆場(chǎng)存放和交接位置的要求。式（16）-式（19）表示對(duì)于同一裝船箱任務(wù)的設(shè)備環(huán)節(jié)的時(shí)間邏輯關(guān)系及先后順序要求：ARMGb-ARMGa-AGV。式（20）-式（23）表示對(duì)于同一卸船箱任務(wù)的設(shè)備環(huán)節(jié)的時(shí)間邏輯關(guān)系及先后順序要求：AGV-ARMGa-ARMGb。式（24）、式（25）表示每一個(gè)ARMGa、ARMGb在先裝后卸的情況下需分別與岸橋、ARMGa作業(yè)順序一致。

該模型的特征在于，并未要求ARMGb的作業(yè)序列完全遵照ARMGa，而只在ARMGa先裝后卸的情形下，ARMGb才須與ARMGa接力調(diào)度。增加雙ARMG的工作柔性，在一定程度上能提高雙ARMG 協(xié)同調(diào)度效果。此外，雙ARMG 作業(yè)過程中的碰撞和跨越問題采用時(shí)間上連續(xù)性處理。

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

3.1 調(diào)度機(jī)制

針對(duì)ARMG 的調(diào)度問題，大多文獻(xiàn)假設(shè)ARMGb遵守ARMGa的作業(yè)序列，雖然簡(jiǎn)化了計(jì)算和執(zhí)行難度，但一定程度上造成大量的空駛、等待和被迫移動(dòng)，浪費(fèi)設(shè)備資源。

本文提出：僅在ARMGa先后兩個(gè)箱任務(wù)為先裝后卸時(shí)，ARMGb 須按照ARMGa 的序列完成，其他情況下可以按照當(dāng)前任務(wù)的優(yōu)先程度選擇，如圖2 所示。交接點(diǎn)位置的選取，傳統(tǒng)方案是將箱區(qū)中間貝位選作交接貝，常常出現(xiàn)一臺(tái)ARMG任務(wù)量過重，而另一臺(tái)相對(duì)空閑，箱區(qū)中間貝位擁擠，其他貝位閑置，箱區(qū)資源浪費(fèi)。因此，應(yīng)改變固定式接力方式，將交接點(diǎn)作為相對(duì)位置進(jìn)行選擇，實(shí)現(xiàn)雙對(duì)等式ARMG均衡且柔性作業(yè)，如圖2所示。

圖2 ARMGa與ARMGb作業(yè)序列示意圖

3.2 算法步驟

3.2.1 序列編碼和解碼與交接點(diǎn)決策

（1）ARMGa 操作序列?；诎稑蛘{(diào)度結(jié)果對(duì)所有箱任務(wù)采用自然數(shù)編碼，每個(gè)染色體代表一種所有箱任務(wù)的隨機(jī)排序，長(zhǎng)度代表箱任務(wù)數(shù)量N。并按照下列啟發(fā)式策略循環(huán)N-1 次操作，得到ARMGa 操作序列：

step1：從編碼序列中找到第i 個(gè)卸船箱，i＜N，執(zhí)行step2。

step2：判斷第i個(gè)卸船箱后續(xù)的編碼序列中箱任務(wù)屬性，若是卸船箱，則跳過，繼續(xù)尋找下一個(gè)元素，直到找到裝船箱，執(zhí)行step3。

Step3：判斷step1 與step2 找到的兩個(gè)箱任務(wù)是否屬于同一艘船舶且也屬于同一個(gè)箱區(qū)，若是，則一定概率將兩個(gè)編碼元素交換，若不是，則不作任何操作，然后執(zhí)行step4。

Step4：完成該卸船箱在作業(yè)序列中的順序調(diào)整。尋找編碼中下一個(gè)卸船箱，反復(fù)執(zhí)行step1-step3，直到遍歷完所有卸船箱。

（2）ARMGb操作序列編碼。將ARMGa的每個(gè)箱任務(wù)拆分為兩個(gè)操作任務(wù)，其中一個(gè)由ARMGa自身作業(yè)，另一個(gè)則由ARMGb 完成。因此ARMGb 作業(yè)序列生成如下：

Step1：在ARMGa 編碼的隨機(jī)序列中，提取屬于同一個(gè)箱區(qū)任務(wù)，得到對(duì)應(yīng)序列。

Step2：在 Step1 上各加上每個(gè) ARMGa 操作任務(wù)數(shù)量，得到新的自然數(shù)編碼；

Step3：將Step1的結(jié)果隨機(jī)排列，得到ARMGb隨機(jī)操作序列；

Step4：按照類似上文ARMGa操作序列的啟發(fā)式策略得到ARMGb最終操作序列。

下面用箱區(qū)1的10個(gè)箱任務(wù)為例對(duì)上述編碼進(jìn)行說明：-1表示卸船箱，+1表示裝船箱。

表1 ARMGb編碼生成

（3）交接點(diǎn)選擇策略。交接點(diǎn)選擇在相對(duì)貝位。這里針對(duì)箱任務(wù)所在目的貝位的中間位置。當(dāng)箱任務(wù)的目的貝在箱區(qū)中間區(qū)域前端，則只由ARMGa 作業(yè)，反之則選擇目的貝位與海側(cè)的中間位置作為交接點(diǎn)。

3.2.2 不可行和重復(fù)序列修正。隨機(jī)生成或迭代后的個(gè)體修正策略：（1）不可行序列修正：通過已知岸橋作業(yè)箱任務(wù)順序及簇任務(wù)約束關(guān)系修正：（2）重復(fù)序列修正：搜尋每代重復(fù)個(gè)體，并采用部分逆反變異操作生成新個(gè)體替換原染色體，得到新種群作為下一代，保持了種群的多樣性。

3.2.3 染色體選擇交叉變異。（1）染色體選擇：采用輪盤賭的方法對(duì)染色體進(jìn)行選擇。（2）染色體交叉：采用部分匹配交叉方法。（3）染色體變異：采用部分逆反變異方法。

3.2.4 適應(yīng)值函數(shù)設(shè)置。適應(yīng)值函數(shù)通常與目標(biāo)函數(shù)關(guān)聯(lián)。通過對(duì)所有ARMGa任務(wù)最大結(jié)束時(shí)刻、箱區(qū)作業(yè)時(shí)刻以及箱區(qū)作業(yè)成本這三個(gè)目標(biāo)函數(shù)分別設(shè)置加權(quán)系數(shù)得到一個(gè)組合函數(shù)，并將這個(gè)組合函數(shù)的倒數(shù)作為適應(yīng)值。

4 案例結(jié)果分析

4.1 案例說明

以青島某自動(dòng)化集裝箱碼頭為例，整體布局和水平運(yùn)輸交通規(guī)則如圖1 所示。岸橋裝卸交換區(qū)域共7條行駛車道，堆場(chǎng)箱區(qū)數(shù)量為10個(gè)，每箱區(qū)共32個(gè)貝位，編號(hào)從海側(cè)向陸側(cè)依次遞增，每個(gè)貝位寬13m，9列5層，可容納45個(gè)集裝箱。某船舶需要操作的進(jìn)出口集裝箱的位置及簇任務(wù)劃分和約束關(guān)系可通過船舶配載計(jì)劃獲得。ARMGa 初始位置在1 貝位，ARMGb 初始位置在 32 貝位，L-AGV 初始位置在緩沖車道，各設(shè)備完成所有任務(wù)后須回到初始位置。

4.2 結(jié)果分析

為比較雙對(duì)等式ARMG 接力模式與協(xié)同程度，設(shè)計(jì)以下四種調(diào)度組合策略，證明本文算法的優(yōu)越性。分別設(shè)計(jì)4 類實(shí)驗(yàn)案例，每組任務(wù)規(guī)模設(shè)置為10、20、40、80、100。

策略1：接力調(diào)度+交接點(diǎn)固定；策略2：接力調(diào)度+交接點(diǎn)變化；策略3：協(xié)同調(diào)度+交接點(diǎn)固定；策略4：協(xié)同調(diào)度+交接點(diǎn)變化。

4.2.1 交接點(diǎn)決策分析比較。圖3 顯示了箱區(qū)裝卸效率曲線，圖4 顯示箱區(qū)完成裝船箱的最大結(jié)束時(shí)刻。通過比較策略4與策略3、策略2與策略1各曲線發(fā)現(xiàn)，交接點(diǎn)變化因減少雙ARMG等待時(shí)間，既有利于箱區(qū)裝卸效率，又提高了船舶完成裝船箱效率，且隨著任務(wù)規(guī)模的遞增，調(diào)度方案效果更為明顯。圖5所示為箱區(qū)的裝卸成本，策略1 與策略2 的曲線、策略3與策略4的曲線均基本重疊，表明交接點(diǎn)固定和相對(duì)變化對(duì)箱區(qū)裝卸成本無(wú)明顯差異。

綜上，從效率和成本兩個(gè)方面評(píng)價(jià)，箱區(qū)交接點(diǎn)變化更具有優(yōu)勢(shì)，對(duì)船公司和碼頭都是有利的。

圖3 箱區(qū)結(jié)束任務(wù)時(shí)刻

圖4 ARMGa裝船任務(wù)結(jié)束時(shí)刻

圖5 箱區(qū)裝卸成本

4.2.2 調(diào)度策略分析比較。由圖3可知，在交接點(diǎn)固定的情況下，相對(duì)于協(xié)同調(diào)度，接力調(diào)度時(shí)箱區(qū)結(jié)束更早。因?yàn)榇藭r(shí)，前者ARMGb 重進(jìn)重出的比例下降，增加雙ARMG 空駛時(shí)間，降低了箱區(qū)的裝卸效率。而圖4 說明協(xié)同調(diào)度有助于船舶的裝卸效率。因?yàn)殡pARMG盡可能提高了岸橋裝船箱相對(duì)于卸船箱的優(yōu)先級(jí)。此外，圖5表明不管是交接點(diǎn)固定還是變化，雙ARMG 協(xié)同調(diào)度都會(huì)導(dǎo)致箱區(qū)成本上升。因?yàn)閰f(xié)同調(diào)度降低了箱區(qū)重進(jìn)重出程度，增加被迫移動(dòng)次數(shù)，導(dǎo)致空駛距離增加。

由此得出以下結(jié)論：一是船舶裝卸效率與堆場(chǎng)箱區(qū)效率一定程度上存在負(fù)相關(guān)關(guān)系（前者為全局目標(biāo)，后者為局部目標(biāo)），即船舶裝卸效率最大化，會(huì)導(dǎo)致堆場(chǎng)裝卸效率下降，成本增加；二是調(diào)度策略影響裝卸重進(jìn)重出比例，其值越高越有助于降低堆場(chǎng)成本；三是交接點(diǎn)動(dòng)態(tài)產(chǎn)生會(huì)減少ARMG 的無(wú)效等待時(shí)間，有利于堆場(chǎng)裝卸效率。

5 結(jié)語(yǔ)

自動(dòng)化集裝箱堆場(chǎng)的協(xié)同調(diào)度有利于提高船舶的整體裝卸效率。本文創(chuàng)新之處在于：一是考慮混堆模式下雙對(duì)等式ARMG 的調(diào)度策略；二是引入空間上的交接方式因素。通過模擬實(shí)驗(yàn)比較各種情形的優(yōu)劣，發(fā)現(xiàn)船舶裝卸效率與堆場(chǎng)裝卸效率和作業(yè)成本存在背反關(guān)系，其中，交接點(diǎn)的決策是影響堆場(chǎng)作業(yè)成本的重要因素。