自動化堆場混合堆存模式下雙軌道吊協(xié)同調(diào)度策略與優(yōu)化

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

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

0 引言

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

1 問題描述

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

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

圖1 自動化集裝箱碼頭整體布局

2 雙對等式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)度計劃期內(nèi)，已知每個箱任務(wù)的操作類型（裝/卸）、在船上以及堆場的存放位置；（4）ARMG、AGV可用數(shù)量已知，且每個設(shè)備一次只處理一個集裝箱；（5）ARMG、AGV 空/重載與行駛速度以及設(shè)備的裝卸效率已知；（6）進(jìn)出口箱允許堆存在同箱區(qū)，各箱區(qū)貝位容量充足；（7）暫不考慮翻箱作業(yè)。

2.2 符號變量說明

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

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

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

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

2.4 約束條件

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

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

3 算法設(shè)計

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

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

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

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

3.2 算法步驟

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

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

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

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

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

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

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

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

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

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

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

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

表1 ARMGb編碼生成

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

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

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

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

4 案例結(jié)果分析

4.1 案例說明

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

4.2 結(jié)果分析

為比較雙對等式ARMG 接力模式與協(xié)同程度，設(shè)計以下四種調(diào)度組合策略，證明本文算法的優(yōu)越性。分別設(shè)計4 類實驗案例，每組任務(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é)束時刻。通過比較策略4與策略3、策略2與策略1各曲線發(fā)現(xiàn)，交接點(diǎn)變化因減少雙ARMG等待時間，既有利于箱區(qū)裝卸效率，又提高了船舶完成裝船箱效率，且隨著任務(wù)規(guī)模的遞增，調(diào)度方案效果更為明顯。圖5所示為箱區(qū)的裝卸成本，策略1 與策略2 的曲線、策略3與策略4的曲線均基本重疊，表明交接點(diǎn)固定和相對變化對箱區(qū)裝卸成本無明顯差異。

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

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

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

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

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

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

5 結(jié)語

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