自動化堆場混合堆存模式下雙軌道吊協同調度策略與優化

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

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

0 引言

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

1 問題描述

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

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

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

2 雙對等式ARMG調度模型

2.1 假設條件

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

2.2 符號變量說明

2.3 目標函數

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

（2）最小化ARMGa 中完成裝船任務的最大結束時刻：

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

2.4 約束條件

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

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

3 算法設計

3.1 調度機制

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

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

圖2 ARMGa與ARMGb作業序列示意圖

3.2 算法步驟

3.2.1 序列編碼和解碼與交接點決策

（1）ARMGa 操作序列?；诎稑蛘{度結果對所有箱任務采用自然數編碼，每個染色體代表一種所有箱任務的隨機排序，長度代表箱任務數量N。并按照下列啟發式策略循環N-1 次操作，得到ARMGa 操作序列：

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

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

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

Step4：完成該卸船箱在作業序列中的順序調整。尋找編碼中下一個卸船箱，反復執行step1-step3，直到遍歷完所有卸船箱。

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

Step1：在ARMGa 編碼的隨機序列中，提取屬于同一個箱區任務，得到對應序列。

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

Step3：將Step1的結果隨機排列，得到ARMGb隨機操作序列；

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

下面用箱區1的10個箱任務為例對上述編碼進行說明：-1表示卸船箱，+1表示裝船箱。

表1 ARMGb編碼生成

（3）交接點選擇策略。交接點選擇在相對貝位。這里針對箱任務所在目的貝位的中間位置。當箱任務的目的貝在箱區中間區域前端，則只由ARMGa 作業，反之則選擇目的貝位與海側的中間位置作為交接點。

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

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

3.2.4 適應值函數設置。適應值函數通常與目標函數關聯。通過對所有ARMGa任務最大結束時刻、箱區作業時刻以及箱區作業成本這三個目標函數分別設置加權系數得到一個組合函數，并將這個組合函數的倒數作為適應值。

4 案例結果分析

4.1 案例說明

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

4.2 結果分析

為比較雙對等式ARMG 接力模式與協同程度，設計以下四種調度組合策略，證明本文算法的優越性。分別設計4 類實驗案例，每組任務規模設置為10、20、40、80、100。

策略1：接力調度+交接點固定；策略2：接力調度+交接點變化；策略3：協同調度+交接點固定；策略4：協同調度+交接點變化。

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

綜上，從效率和成本兩個方面評價，箱區交接點變化更具有優勢，對船公司和碼頭都是有利的。

圖3 箱區結束任務時刻

圖4 ARMGa裝船任務結束時刻

圖5 箱區裝卸成本

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

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

5 結語

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