考慮裝船機聯機作業的煤炭出口碼頭裝船作業調度優化

馮鵬 郭子堅 姜影 曹震 徐星璐

摘要：為提高煤炭出口碼頭作業效率和服務水平，對裝船作業調度進行優化。在考慮裝船機聯機作業的前提下，以最小化煤炭出口碼頭作業線運行能耗成本和船舶在港時間成本為目標，綜合考慮作業流程約束和泊位、垛位和作業線的作業唯一性約束，建立混合整數規劃模型，并設計基于仿真解碼方案的遺傳算法求解。用實例驗證模型的可行性和算法的有效性。結果表明，研究成果可為具有工藝流程復雜、裝船機聯機作業等特點的煤炭出口碼頭裝船作業調度問題提供較好的解決方案。

關鍵詞：

煤炭出口碼頭; 裝船作業; 作業線調度; 聯機作業; 遺傳算法

中圖分類號：? U691+.3

文獻標志碼：? A

收稿日期： 2020-08-04

修回日期： 2021-01-06

基金項目：

國家重點研發計劃（2020YFE0201200）

作者簡介：

馮鵬（1996—），男，山西晉城人，碩士研究生，研究方向為港口規劃與港口物流，（E-mail）fengpeng1996@mail.dlut.edu.cn;

郭子堅（1965—），男，遼寧沈陽人，教授，博士，研究方向為港口規劃與港口物流，（E-mail）zjguo@dlut.edu.cn

Scheduling optimization of loading operation in coal export

terminals considering union operation of ship loaders

FENG Peng， GUO Zijian， JIANG Ying， CAO Zhen， XU Xinglu

（

State Key Laboratory of Coastal and Offshore Engineering， Dalian University of Technology， Dalian 116024， Liaoning， China）

Abstract：

In order to improve the efficiency and service level of coal export terminals， the loading operation scheduling is optimized. A mixed integer programming model is established with considering union operation of ship loaders. The model objective is to minimize the energy consumption cost of the operation lines of coal export terminals and the time cost of ships berthing at terminals. The model constraints are the operation process constraint and the uniqueness constraints of berths， stock positions and operation lines. A genetic algorithm based on the simulation decoding scheme is designed to solve the model. The feasibility of the model and the validity of the algorithm are verified by a case. The results indicate that the research results can provide a better solution to the scheduling problem of loading operation in coal export terminals with the features of complex technological process and union operation of ship loaders.

Key words：

coal export terminal; loading operation; operation line scheduling; union operation; genetic algorithm

0 引 言

煤炭在我國的能源結構中占有重要地位。由于煤炭供需關系在地域分布上的差異，我國煤炭存在大規模的“西煤東調”“北煤南運”現象。港口作為煤炭運輸鏈的樞紐，其服務水平的提升是保障我國煤炭運輸體系高效、流暢的關鍵。隨著煤炭運輸需求逐年攀升，煤炭出口碼頭的通過能力和服務水平亟待提高。然而，由于城市的不斷發展和擴張，港口的發展空間大大減小，促使港口由新建、擴建碼頭的粗放式發展模式，向發展“智慧港口”的方向轉變。

煤炭出口碼頭裝船工藝流程具有較強的專業性和特殊性，主要包括利用取料線上的取料機將煤炭從相應垛位取出，經前端橫向連接線運往相應裝船線，并由與之相連的裝船機完成裝船。為提高作業效率，碼頭配置移動式裝船機，在條件允許的情況下可為相鄰泊位裝船，既可單機作業，也可聯機作業[1]。因此，在制訂裝船線調度方案時，不僅要考慮聯機作業的高效性和靈活性，而且要盡可能降低裝船機移泊作業對其原本對應泊位裝船作業的影響。由于船舶需求量與碼頭垛位堆存量的差異，一艘船往往需要從多個垛位取煤。另外，為滿足配煤需求，取料線和取料機配置形式一般為“一線雙機”，布置在同一取料線上的兩臺取料機可在堆存不同煤種的兩個垛位按比例取煤，并在取料線上混合后進行裝船。

在堆場作業調度方面：錢國棟[2]通過建立煤炭碼頭堆場作業優化模型，提出堆場管理優化措施;王翼展等[3]以極小化作業完成時間為目標，在堆取料機可在工作區任意位置結束工作的條件下，給出多項式時間最優算法;VAN VIANEN等[4]以減少列車等待時間、提升碼頭作業效率為目標，對堆取料機調度進行了仿真研究;HU等[5]針對堆取料機調度問題，以完成時間最短為目標，建立混合整數規劃模型，并設計了遺傳算法進行求解;KALINOWSKI等[6]將取料機調度問題表示為混合整數規劃問題，并設計了常數因子近似算法和分支定界精確算法進行求解。在裝船、卸車作業調度方面：宓為建等[7]針對煤炭碼頭裝船調度問題，建立泊位與機械聯合調度模型，并設計了多目標遺傳算法進行求解;邰世文等[8]針對煤炭碼頭卸車調度問題，以卸車效率最大和列車在港時間最短為目標，提出多目標優化模型，并設計了遺傳算法進行求解;DE PAULA等[9]針對煤炭出口碼頭綜合調度問題提出并行遺傳算法，以提高碼頭通過能力;MENEZES等[10]針對散貨出口碼頭調度問題，考慮皮帶機路徑限制，提出使用分支定價算法求解的數學規劃模型;BURDETT等[11]將煤炭出口碼頭綜合調度問題轉化為柔性車間調度問題，并使用元啟發式算法求解;UNSAL等[12]考慮了散貨出口碼頭的泊位、取料機和堆場調度問題，提出改進的Benders分解算法求解規劃模型;PRATAP等[13]針對散貨進口碼頭堆場作業和列車調度優化問題，通過建立混合整數線性規劃模型，采用兩種啟發式算法進行求解。已有研究對煤炭碼頭工藝流程的約束不夠充分，導致與實際生產作業情況存在偏差，特別是對配置移動式裝船機，可在相鄰泊位聯機作業的多泊位連續布置煤炭碼頭，仍缺少優化調度的解決方案。

本文結合煤炭出口碼頭裝船作業實際情況，在考慮裝船機聯機作業的前提下，通過建立以最小化煤炭出口碼頭作業線運行能耗成本和船舶在港時間成本為目標的混合整數規劃模型，設計基于仿真解碼方案的遺傳算法，對該調度問題進行優化研究。模型和求解方法可為具有工藝流程復雜、裝船機聯機作業等特點的煤炭出口碼頭制訂合理、高效的裝船作業調度方案提供決策依據。

1 模型構建

1.1 問題描述

煤炭出口碼頭是專業化程度極高的大宗散貨碼頭。由于碼頭單船作業量較大，而堆場垛位容量有限，通常需從多個垛位取料才能滿足船舶需求。同時，碼頭還需保證煤炭種類或發熱量等主要性質符合船舶需求。由于堆場堆存煤種通常難以完全滿足船舶的多樣需求，所以許多大型煤炭出口碼頭發展配煤工藝來實現煤炭供求的靈活匹配。配煤是指裝船過程中，將從同一取料線兩側按一定比例取兩種煤在取料線上混合，達到需求后將煤經連接線和裝船線裝入船艙的過程。若某垛位的堆存煤種與船舶需求煤種相同或性質相近，則無需配煤就可取料裝船，這種作業模式稱為單裝。在現代大型煤炭出口碼頭的裝船作業中，配煤和單裝作業均占相當大的比重，但無論何種作業模式，均占用一組作業線（取料線、連接線、裝船線各一條）連續完成。為便于描述和建模，定義從一個垛位取料（配煤時兩個垛位），經一組作業線連續裝載至一艘船的過程，為該船的一項裝船任務。

船舶到港后，依據其靠泊優先級在相應泊位依次靠泊，完成輔助作業后針對各項裝船任務依據作業優先級在指定作業線上依次進行取料裝船作業，待船舶完成其全部裝船任務后，解纜離泊。受碼頭工藝流程限制，各作業線在任意時刻僅能服務一項裝船任務，各項裝船任務需按照一定次序先后作業，且不同裝船任務切換時還需考慮裝船機移泊時間和不可跨越等約束，調度難度較大。因此，本文為規劃期內的到港船舶指定靠泊優先級和靠離泊時刻，并為其裝船任務指定作業線、作業優先級和開始時刻，使得煤炭出口碼頭作業線運行能耗成本和船舶在港時間成本最低。

為方便建模和求解，假設：①船舶到港時刻（到達港池而非錨地的時刻）和靠泊泊位均已知;②船舶在港時間從船舶到港算起，到解纜離泊為止;③裝船任務的取料垛位、取料量和作業時間均已知;④同一裝船任務的作業過程不可中斷;⑤不考慮碼頭設備故障等因素。

1.2 符號說明

（1）集合和下標。

I和J分別表示到港船舶和裝船任務集合，i∈I，j∈J;T為時刻集合，t∈T;K和P分別表示泊位和垛位集合，k∈K，p∈P;取料線、連接線、裝船線集合分別用U、V、W表示，u∈U，v∈V，w∈W。

（2）參數。Au、Av、Aw分別為取料線u、連接線v、裝船線w的單次啟動能耗成本;Eu、Ev、Ew分別為取料線u、連接線v、裝船線w運輸煤炭的單位能耗成本;Ei為船i在港時間單位成本;tarri為船i到港時刻;τtri、τauxi、τuni分別為船i回旋、輔助作業和解纜時間;dj、τtaj分別為任務j裝船量和作業時間;πk，k′為裝船機從泊位k移動到泊位k′的時間;M為充分大的正實數。βi，k、θi，j、δj，k、γj，p、αw，k、αu，v，w、αp，p′，u均為0-1變量：若船i在泊位k靠泊，則βi，k=1，否則βi，k=0;若任務j屬于船i，則θi，j=1，否則θi，j=0;若任務j屬于泊位k，則δj，k=1，否則δj，k=0;若任務j從垛位p取料，則γj，p=1，否則γj，p=0;若裝船線w可達泊位k，則αw，k=1，否則αw，k=0;若連接線v可達取料線u和裝船線w，則αu，v，w=1，否則αu，v，w=0;若取料線u可達垛位p和p′，則αp，p′，u=1，否則αp，p′，u=0。

（3）變量。決策變量包括zi，i′、zj，j′、yj，u、yj，v、yj，w，均為0-1變量。若船i與i′屬于同一個泊位，且前者靠泊優先級高于后者，則zi，i′=1，否則zi，i′=0。若任務j與j′占用同一垛位或作業線，且前者作業優先級高于后者，則zj，j′=1，否則zj，j′=0。若任務j分別占用取料線u、連接線v和裝船線w，則yj，u，yj，v，yj，w=1，否則yj，u，yj，v，yj，w=0。其他變量中：au、av、aw分別表示取料線u、連接線v、裝船線w的啟動次數;tmooi、tdepi分別為船i靠、離泊時刻;tsj為任務j開始時刻;xj，t為0-1變量，若t時刻任務j正在進行，則xj，t=1，否則xj，t=0。

1.3 目標函數及其約束條件

以最小化煤炭出口碼頭作業線運行能耗成本（包括啟動能耗成本和運輸能耗成本）和船舶在港時間成本為目標，構建優化模型如下：

min F|F=

uAuau+vAvav+wAwaw+

juEuyj，u+vEvyj，v+

wEwyj，wdj+i（tdepi-tarri）Ei

（1）

s.t.

zi，i′+zi′，i=kβi，kβi′，k， i≠i′

（2）

tmooi′≥max（tarri′+τtri′，tdepi-M（1-zi，i′）），

i≠i′

（3）

tdepi=maxj（（tsj+τtaj）θi，j）+τuni

（4）

tsj+M（1-θi，j）≥tmooi+τauxi

（5）

zj，j′+zj′，j=maxp，u，v，w（（γj，pγj′，p），（yj，uyj′，u），

（yj，vyj′，v），（yj，wyj′，w））， j≠j′

（6）

tsj′≥tsj+τtaj-M（1-zj，j′）+wyj，wyj′，w·

kk′δj，kδj′，k′πk，k′， j≠j′

（7）

t+M（1-xj，t）≥tsj

（8）

t-M（1-xj，t）

（9）

txj，t=τtaj

（10）

uyj，uvyj，vwyj，w=1

（11）

yj，u≤pp′

（12）

yj，v≤uwyj，uyj，wαu，v，w

（13）

yj，w≤kδj，kαw，k

（14）

jkxj，tyj，wδj，kk≤j

kxj，tyj，w′δj，kk+

M1-

jxj，tyj，w′， w

（15）

w-w′≤1-jxj，tyj，wθi，j·

jxj，tyj，w′θi，jM+1， w≠w′

（16）

式（1）為目標函數，其中：啟動能耗成本由各作業線啟動次數和單次啟動能耗成本計算，表達式為

uAuau+vAvav+wAwaw;運輸能耗成本由各作業線煤炭運輸量和單位能耗成本計算，表達式為juEuyj，u+vEvyj，v+wEwyj，wdj;船舶在港時間成本由其在港時間和單位時間成本計算，表達式為itdepi-tarriEi。

約束條件中：式（2）對同一泊位船舶的靠泊優先級進行約束;式（3）表示船舶在到港并回旋，且相應泊位的前船離泊后才可靠泊;式（4）表示船舶在完成其所有裝船任務后方可解纜離泊;式（5）表示在船舶靠泊并完成輔助作業前，不可開始裝船作業;式（6）對占用同一資源的兩項任務進行作業優先級約束;式（7）表示若兩項任務占用同一資源，則優先級較低者應在優先級較高者完成作業后開始作業，且若二者占用同一裝船線，則還需考慮裝船機移泊時間;式（8）～（10）保證同一裝船任務作業過程不可中斷;式（11）表示一項裝船任務需且僅需占用取

料線、連接線和裝船線各一條;式（12）～（14）對任務占用資源的可達性關系進行約束;式（15）保證裝船機不進行交叉作業;式（16）表示僅相鄰兩臺裝船機可聯機作業。

2 遺傳算法設計

煤炭出口碼頭裝船調度問題具有復雜、隨機、多約束等特點，是典型的NP難問題。遺傳算法具有全局搜索的特征，且搜索速度較快[14]，在求解此類問題上具有獨特的優勢。當前遺傳算法已廣泛應用于調度問題的求解，且取得了較好的實際效果。

2.1 染色體編碼

本研究的決策變量包括到港船舶靠泊優先級，裝船任務作業優先級，以及占用作業線等。染色體由5個序列構成，見表1。

表1中：MoorOrder為船舶靠泊優先級序列，bi表示船i在相應泊位上的靠泊優先級（bi值越小，船i的靠泊優先級越高）;TaskOrder為裝船任務作業優先級序列，cj表示任務j的作業優先級（cj值越小，任務j在相應作業線上的優先級越高）;BeltBQ、BeltBC、BeltBM分別表示裝船任務占用的取料線、連接線、裝船線序列，ej、fj、gj分別表示任務j占用的取料線、連接線、裝船線。

2.2 初始化種群及染色體解碼

初始種群的生成規則如下：

（1）MoorOrder序列。依據船舶靠泊泊位隨機生成。

（2）TaskOrder序列。對同一泊位，靠泊優先級較高的船舶，其裝船任務作業優先級也較高。據此原則，生成裝船任務作業優先級序列的步驟如下：① 隨機生成作業優先級;②對靠泊同一泊位的兩艘船，若靠泊優先級較高者的裝船任務作業優先級編號最大值，大于靠泊優先級較低者的裝船任務作業優先級編號最小值，則交換兩項任務的作業優先級編號;③重復步驟②，直至滿足原則為止。

（3）BeltBQ、BeltBM序列：在可達該裝船任務所占垛位和泊位的取料線和裝船線中隨機選擇。

（4）BeltBC序列：在可達所選取料線和裝船線的連接線中隨機選擇。

本文使用遺傳算法生成調度方案，仿真得到碼頭在各調度方案下的運行結果，統計各作業線啟動次數、作業量和各船舶在港時間等指標，求得目標函數值，并將其倒數作為適應度函數。

2.3 遺傳算子

使用輪盤賭和保優策略進行選擇。針對染色體序列特點，設計以下3種交叉策略。

（1） 整體單點交叉，見圖1。

此策略可能導致以下3種新染色體序列不滿足約束條件的情況，需修正：

①若在MoorOrder序列中同一泊位的兩艘船靠泊優先級相等，則交叉部分保留，未交叉部分以缺失的優先級編號替換。

②若在TaskOrder序列中兩項裝船任務作業優先級相等，則交叉部分保留，未交叉部分以缺失的優先級編號替換。

③若TaskOrder序列與MoorOrder序列矛盾，則修正原則同生成初始種群時對TaskOrder序列的修正原則。

（2）TaskOrder序列多點交叉，見圖2。圖2中，r1～r4為交叉點位置。此策略可能導致TaskOrder序列中兩項裝船任務作業優先級相等，或TaskOrder序列與MoorOrder序列矛盾的情況，修正原則同上。

（3）BeltBQ、BeltBC、BeltBM序列多點交叉，見圖3。圖3中，r1～r4為交叉點位置。

同時，設計3種變異策略：針對MoorOrder序列，在同一泊位中隨機選擇兩艘船，交換其靠泊優先級;針對BeltBM序列，在可達任務相應泊位的其他裝船線中隨機選擇一條不同的裝船線;針對TaskOrder序列，隨機選擇兩項任務，交換其作業優先級，修正原則同上。

計算時，以一定概率隨機選擇一種策略進行交叉或變異。

3 實例分析

以我國某煤炭出口碼頭為例，將利用本文提出的優化模型得到的調度方案（優化方案）與調研得到的碼頭實際調度方案（現行方案）進行對比分析，驗證模型和算法有效性。該碼頭包括3個泊位、40個垛位、3條取料線、2條連接線、3條裝船線，見圖4。

規劃期內碼頭到港13艘船，到港時刻見表2，現行方案見圖5。以⑥號船為例：該船在第1天2：06到港，2：40靠泊于2#泊位;在完成輔助作業后，其4項裝船任務（編號24、25、26、27）分別于?? 4：20、6：40、15：10、4：20開始作業，并分別于6：40、13：50、17：00、15：10完成;在最后一項任務（編號26）完成后，該船解纜，并于17：10離泊。

碼頭調度優化方案見圖6。現行方案和優化方案的作業線分配情況見表3。在⑥號船作業過程中，其26、27號任務占用本泊位的裝船線BM2進行裝船，24、25號任務占用1#泊位的裝船線BM1，因此，27與24、25號任務可同時進行，實現了裝船機的聯機作業，提高了碼頭作業效率。由于碼頭工藝流程限制，26和27號任務均需占用取料線BQ2，無法同時作業，優化方案為二者分配了相同的裝船線，待27號任務完成后26號任務緊接著占用裝船線BM2作業。與現行方案相比，優化方案中裝船線BM1的啟動次數減少了一次。

通過優化，碼頭作業線總啟動次數從102次減為81次（減少20.6 %，見表4），大大簡化了人員操作，改善了裝船作業連續性，從而使作業效率得以提高。同時，作業線啟動次數的減少也為碼頭節省了2 300 kW·h的電能。不過，作業線運行能耗主要與裝船量有關，在裝船量不變且碼頭設備保持現狀的情況下，能耗優化空間有限。能耗優化目標可通過使用清潔能源或更新節能設備等措施實現。

另外，與現行方案相比，優化方案中船舶平均在港時間減少11.6%（3.04 h，見圖7），最后一艘船離港時刻提前7 h。以作業時間相對重合的①、⑦號船為例進行分析：兩船分別靠泊于1#、2#泊位，在優化方案中①號船的裝船機聯機作業集中在⑦號船完成輔助作業前，在⑦號船完成輔助作業后，BM2（SL2）即返回2#泊位，與BM3（SL3）聯機為⑦號船作業，停靠在1#泊位的①號船則繼續由BM1（SL1）單機作業。與現行方案相比，①號船聯機作業時間從7.33 h減少至3.50 h，而⑦號船單機作業時間從0增加至4.17 h。這樣的調度方式，使得⑦號船提前12 h離泊，從而使其后的⑧號船得以提前靠泊裝船，而①號船雖延后4 h離泊，但由于其后的②號船到港較晚，所以并未對1#泊位后續船舶的裝船作業造成影響。由此可以看出，通過合理的資源調配和作業優先級調整，優先保障較繁忙泊位的裝船作業，能在總體上有效減少船舶在港時間，提高煤炭出口碼頭的服務水平。

4 結 論

通過深入分析煤炭出口碼頭裝船作業的復雜流程和現實約束，在考慮裝船機聯機作業的前提下，以最小化煤炭出口碼頭作業線運行能耗成本和船舶在港時間成本為目標，綜合考慮作業流程約束，泊位、垛位和作業線的作業唯一性約束等，建立混合整數規劃模型，設計基于仿真解碼方案的遺傳算法，對其調度問題進行優化研究。最后，利用本文提出的調度優化模型對實例進行計算，優化方案下規劃期內碼頭作業線總啟動次數減少20.6%，船舶平均在港時間減少11.6%，最后一艘船提前7 h離港，優化效果良好。本文研究成果可為具有工藝流程復雜、裝船機聯機作業等特點的煤炭出口碼頭制訂合理、高效的裝船作業調度方案提供決策依據，從而進一步提升煤炭出口碼頭服務水平，為我國煤炭運輸鏈的高效和流暢運行提供保障。

參考文獻：

[1]岳金燦， 周運文， 郭建睿. 關于煤炭裝船碼頭移動式裝船機聯機作業的探討[J]. 港工技術， 2013， 50（1）： 13-15. DOI： 10.16403/j.cnki.ggjs2013.01.008.

[2]錢國棟. 曹妃甸港煤碼頭堆場作業管理及優化設計研究[D]. 秦皇島： 燕山大學， 2015.

[3]王翼展， 張安， 陳永， 等. 煤炭碼頭堆取料機的調度問題[J]. 杭州電子科技大學學報（自然科學版）， 2019， 39（6）： 88-93. DOI： 10.13954/j.cnki.hdu.2019.06.016.

[4]VAN VIANEN T， OTTJES J， LODEWIJKS G. Simulation-based rescheduling of the stacker-reclaimer operation[J]. Journal of Computational Science， 2015， 10： 149-154. DOI： 10.1016/j.jocs.2014.06.004.

[5]HU Dayong， YAO Zhenqiang. Stacker-reclaimer scheduling in a dry bulk terminal[J]. International Journal of Computer Integrated Manufacturing， 2012， 25（11）： 1047-1058. DOI： 10.1080/0951192X.2012.684707.

[6]KALINOWSKI T， KAPOOR R， SAVELSBERGH M W P. Scheduling reclaimers serving a stock pad at a coal terminal[J]. Journal of Scheduling， 2017， 20： 85-101. DOI： 10.1007/s10 951-016-0495-8.

[7]宓為建， 王郡嫻， 張曉華， 等. 基于多目標遺傳算法的煤碼頭泊位與機械聯合調度[J]. 上海海事大學學報， 2016， 37（2）： 46-52. DOI： 10.13340/j.jsmu.2016.02.009.

[8]邰世文， 商劍平. 煤炭碼頭卸車調度問題多目標優化模型及算法[J]. 運籌與管理， 2018， 27（6）： 91-99. DOI： 10.12005/orms.2018.0138.

[9]DE PAULA M R， BOLAND N， ERNST A T， et al. Throughput optimisation in a coal export system with multiple terminals and shared resources[J/OL]. Computers and Industrial Engineering， 2019， 134： 37-51. DOI： 10.1016/j.cie.2019.05.021.

[10]MENEZES G C， MATEUS G R， RAVETTI M G. A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports[J]. European Journal of Operational Research， 2017， 258： 926-937. DOI： 10.1016/j.ejor.2016.08.073.

[11]BURDETT R L， CORRY P， YARLAGADDA P K D V， et al. A flexible job shop scheduling approach with operators for coal export terminals[J]. Computers and Operations Research， 2019， 104： 15-36. DOI： 10.1016/j.cor.2018.11.019.

[12]UNSAL O， OGUZ C. An exact algorithm for integrated planning of operations in dry bulk terminals[J]. Transportation Research Part E， 2019， 126： 103-121. DOI： 10.1016/j.tre.2019.03.018.

[13]PRATAP S， KUMAR B M， SAXENA D， et al. Integrated scheduling of rake and stockyard management with ship berthing： a block based evolutionary algorithm[J]. International Journal of Production Research， 2016， 54（14）： 4182-4204. DOI： 10.1080/00207543.2015.1111535.

[14]艾立紅， 韓曉龍. 考慮能耗的自動化碼頭裝卸設備協調調度[J]. 上海海事大學學報， 2018， 39（4）： 26-31. DOI： 10.13340/j.jsmu.2018.04.005.

（編輯 賈裙平）