汽車滾裝碼頭泊位調度優(yōu)化模型與算法研究

張 帝, 梅子翹, 陳 峰, 趙一飛

(1.上海交通大學 機械與動力工程學院,上海 200240; 2.上海交通大學 安泰經(jīng)濟與管理學院,上海 200030; 3.上海交通大學 中美物流研究院,上海 200030)

0 引言

整車運輸有三種方式：公路、鐵路和水路。其中，水路運輸有兩種方式：集裝箱運輸和滾裝運輸。相較于集裝箱的兼容性運輸，滾裝運輸主要集中于商品車業(yè)務。經(jīng)過大量的文獻回顧，發(fā)現(xiàn)當前針對滾裝碼頭的研究多集中于運營管理[1]、布局設計[2]和發(fā)展現(xiàn)狀分析[3]，對于調度優(yōu)化的研究尚未得到較多的重視。

根據(jù)中國汽車流通協(xié)會和中港協(xié)滾裝碼頭分會的統(tǒng)計數(shù)據(jù)，本文整理出2015年到2019年全國汽車業(yè)務與滾裝業(yè)務的相關數(shù)據(jù)(表1)。在此期間，全國汽車產(chǎn)銷量波動下滑，但全國主要滾裝碼頭的汽車吞吐總量卻持續(xù)上漲，說明汽車市場的低迷對滾裝碼頭的影響較小；其次，除2016年外，全國主要滾裝碼頭汽車出口量和全國總出口量保持同幅上升，說明我國汽車出口業(yè)務正不斷發(fā)展；另外，全國汽車總進口量和全國主要滾裝碼頭汽車進口量存在波動，但滾裝進口量占總進口量比例基本穩(wěn)定在85%到90%之間，說明我國汽車進口業(yè)務主要依靠滾裝運輸。綜上，表明近年我國滾裝進出口業(yè)務不斷擴大。因此，在現(xiàn)階段對滾裝碼頭調度優(yōu)化問題展開研究是十分必要的。

表1 全國汽車業(yè)務與滾轉碼頭業(yè)務對比

碼頭優(yōu)化研究集中于泊位分配和裝卸資源分配。泊位分配問題是以最小化船舶服務時間等為目標，為一組船舶分配泊位。依布局情況，泊位可分為離散泊位、連續(xù)泊位和混合泊位，本文集中于研究混合泊位問題：如圖 1，碼頭分為多個泊段，船舶一次可占據(jù)多個泊段。另外，本文還考慮現(xiàn)實中存在的河流截斷現(xiàn)象，如圖 1所示的間斷狀泊位布局。該問題涉及較多空間和時間約束：時間約束包括靠離泊時間和裝卸時間等；空間約束涉及泊位布局和泊段長度等。因此，即使小規(guī)模的泊位分配問題也有較多約束。

圖1 間斷泊位布局

裝卸資源分配因碼頭類型而異，滾裝碼頭和集裝箱碼頭的主要差異有操作、形式和計算復雜度三方面：在操作方面，集裝箱碼頭的岸橋是在船與集卡之間進行集裝箱轉移的工具，集卡和船停靠在岸橋旁，因此，岸橋操作范圍固定，并且它的裝卸效率和數(shù)量也固定。而滾裝碼頭的勞動力是在船與堆場之間進行商品車轉移的主要介質，船靠泊位置固定，但商品車所屬堆區(qū)不同，故勞動力操作范圍不固定。另外，工人的操作效率和碼頭每個時間段擁有的數(shù)量也不一定。在形式上，集裝箱碼頭直接對岸橋調度，而滾裝碼頭直接對每個勞動力調度較難，且每日裝卸量差別較大，碼頭長期雇傭大量勞動力較為浪費，故采用第三方外包，碼頭方根據(jù)其次日每時間段最高裝卸量(勞動力數(shù)量不定)制定次日靠泊計劃，因此，滾轉碼頭需對每個時間段的勞動力裝卸量進行分配調度。在計算復雜度上，集裝箱碼頭需指定某艘船在某時間段使用的岸橋數(shù)量，而滾裝碼頭需指出某艘船在某時間段占用的裝卸數(shù)量，在處理數(shù)量級上，集裝箱船處理對象集裝箱數(shù)量一般遠遠小于滾裝船處理對象商品車的數(shù)量，因此，兩問題面對的計算復雜度不同。

滾裝作業(yè)有四個重要時間點：靠泊、開工、完工和離泊。裝卸資源直接影響開完工時間，進而影響離泊時間。圖 2是三艘滾裝船的兩種勞動力配置方案，船舶1、2、3需處理500、300和300輛車，在每個時間段中勞動力總裝卸能力為400、200、500、500。方案一中船舶3圖示代表其于時間點4靠泊，時間段4分配300裝卸能力，于時間點5離泊，其他船舶的圖示解釋類似。方案一需4個時間段，最晚離泊時間為時間點5，而方案二需3個時間段，且最晚離泊時間為時間點4。經(jīng)勞動力優(yōu)化配置，在同等條件下可降低等泊時間和泊位占用時間。因此，研究泊位和勞動力聯(lián)合調度問題對于滾裝碼頭的發(fā)展至關重要。

圖2 勞動力分配實例

1 文獻綜述

本文主要考慮四個因素：(1)泊位不連續(xù)布局：間斷布局會給計算造成一定影響，本文采用預處理方式，在泊位間斷處設置不可停靠的虛擬泊段；(2)潮汐因素：潮汐會對水流向和水位造成影響，船舶在合適的條件下才可靠離泊；(3)混合泊位布局及纜樁因素：考慮到系纜要求，將碼頭按照纜樁分布分割為多個不同長度的泊段，船舶靠泊可以占用多個連續(xù)的泊段；(4)勞動力因素：船舶離泊時間的確定依賴于裝卸工作的耗時，而裝卸時間由勞動力分配決定。因此，本文研究在潮汐影響下的滾裝碼頭不規(guī)則混合泊位分配和勞動力分配的聯(lián)合調度問題，針對上述復雜情況，建立混合整數(shù)模型，設計遺傳算法和啟發(fā)式算法內外嵌套的算法對模型進行求解。

2 問題描述及模型

以船舶總服務時間最小為目標，同時考慮泊位和勞動力，決策船舶靠泊位置、靠離泊時間、開完工時間和裝卸計劃。問題可作如下數(shù)學描述：已知泊段集合，一定時間范圍內，有一組船靠泊，需為每艘船安排靠泊方案。每艘船i∈先提交確報時間tri，依據(jù)靠泊指令，消耗TBRi從錨地駛到泊位，于tsi靠泊，耗費waiti進行系纜關檢，完成后隨時可開始裝卸。在完成作業(yè)后，于tli離泊(需耗費TBLi解纜)。制定計劃時還需考慮：(1)潮汐：靠離泊時間須在潮水高潮時間點范圍內；(2)泊位：泊段j在時間段t，最多被一艘船占用。每個泊段都有靠泊順序，泊段j的靠泊順序k最多被一艘船占用；(3)勞動力：在時間段t，總裝卸量不可超過碼頭可用裝卸能力Work Capacityt。

2.1 假設條件

(1)裝卸不同品牌的車輛，消耗的裝卸能力相同。

(2)系纜、關檢、解纜等時間提前已知。

2.2 參數(shù)與變量

模型參數(shù)定義如下：

porti：i船的跳板位置，0-1值，0為右，1為左；

Tided：第d個潮水的高潮時間點，連續(xù)值；

LenthOfBerthj：j泊段的長度，連續(xù)值；

LenthOfShipi：i船的長度，連續(xù)值；

TBRi：i船在錨地的等待時間和從錨地駛到泊位的時間的總和，連續(xù)值；

TBLi：i船解纜所需時間，連續(xù)值；

waiti：i船一關三檢等所需時間，連續(xù)值；

tri：i船確報時間，連續(xù)值；

WorkCapacityt：碼頭t時間段的裝卸能力，整數(shù)；

Leavej：j泊段的最早可用時間，連續(xù)值；

LeftAdvance：左舷船靠離泊提前時間，連續(xù)值；

LeftDely：左舷船靠離泊延遲時間，連續(xù)值；

RightAdvance：右舷船靠離泊提前時間，連續(xù)值；

RightDely：右舷船靠離泊延遲時間，連續(xù)值；

M：一個很大的常數(shù)。

模型變量定義如下：

xi,j,k：i船是否在j泊段的第k個次序靠泊，0-1變量，1為i船在j泊位的第k個次序靠泊，0為其他；

tsi：i船的靠泊時間，連續(xù)值；

tli：i船的離泊時間，連續(xù)值；

ArriveTidei,d：i船是否在第d個潮水靠泊，0-1變量，1為i船在第d個潮水靠泊，0為其他；

LeaveTidei,d：i船是否在第d個潮水離泊，0-1變量，1為i船在第d個潮水離泊，0為其他；

Sequencei1,i2,j：在j泊段上，船是否在i2前靠泊，0-1變量，1為船i1在i2前靠泊，0為其他；

StartWorkit：i船是否在t時段開始裝卸工作，0-1變量，1為船i在t時段開始裝卸工作，0為其他；

EndWorkit：i船是否在t時段結束裝卸工作，0-1變量，1為船i在t時段結束裝卸工作，0為其他；

ActualWorkit：i船在t時段占用的裝卸能力，整數(shù)變量；

WorkTime：i船是否在t時段進行裝卸工作，0-1變量，1為船i在t時段進行裝卸工作，0為其他。

2.3 模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

tsi≥tri+TBRi,?i∈

(8)

tsi≥Leavej-(1-xij0)·M,?i∈,?j∈

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

ActualWorki,t≥0,?i∈,?i∈

(19)

ActualWorki,t≤WorkTimei,t·M,?i∈,?i∈

(20)

(21)

(22)

(23)

(24)

tsi1≤tli2-(1-Sequecnei2,i1,j)·M,?i1∈,?i2∈,?j∈

(25)

(26)

(27)

(28)

(29)

(30)

(31)

xi,j,k∈{0,1},?j∈,?i∈,?k∈

(32)

ArriveTidei,d,LeaveTidei,d∈{0,1},?i∈,?d∈

(33)

Sequencei1,i2,j∈{0,1},?i1∈,?i2∈,?j∈

(34)

StartWorki,t,EndWorki,t,WorkTimei,t∈{0,1},?i∈,?t∈

(35)

ActualWorki,t∈,?i∈,?t∈

(36)

式(1)到(7)為船舶靠泊的潮汐約束條件，式(8)保證船舶可以在規(guī)定的時間內從錨地駛到泊位，式(9)保證船舶在泊位可用時才靠泊，式(10)到(11)保證每艘船有開完工時間，式(12)限制船舶解纜后才離泊，式(13)限制船舶完成關檢后才開工，式(14)保證開完工按順序執(zhí)行，式(15)到(17)確定裝卸時間段，式(18)到(22)保證船舶在碼頭裝卸能力下完成工作，式(23)保證每艘船占用連續(xù)的泊段，式(24)保證船舶的安全間距，式(25)到(27)保證船舶依次靠泊，式(28)確保服務每艘船，式(29)保證每個泊位的每個次序最多安排一艘船，式(30)保證每艘船在任意泊段內，最多占用一個次序，式(31)限制船舶在每個泊段按次序靠泊。

3 算法設計

泊位分配屬于NP-hard問題，較多學者[20～22]已成功地將遺傳算法應用于碼頭調度問題。船舶計劃順序是實際調度考慮的重要因素，而遺傳算法染色體結構恰好與其相吻合。因此，本文設計遺傳算法和啟發(fā)式算法內外嵌套的算法，外環(huán)由遺傳算法生成多種船舶計劃順序，內環(huán)由啟發(fā)式獲取計劃順序的適應值。

3.1 遺傳算法

3.1.1 染色體編碼與適應值

采用自然數(shù)編碼，染色體的基因為船舶ID。染色體表示計劃順序，如“1432”表示在制定生產(chǎn)計劃時，先使用啟發(fā)式算法計算出對船舶1最有利的方案，在此基礎上再依次安排船舶4、3和2，最后得到整體調度計劃。船舶總服務時間即為染色體適應值。

3.1.2 初始種群

按照排列組合方式進行初始化：當船舶小于等于4艘時，將所有排列方式作為初始種群；當大于4艘時，采用隨機生成方式。設置多區(qū)域并行進化，每個區(qū)域有父、子和精英三個種群，初始化時將所有個體添加到父種群中，進化過程中不斷更新子種群和精英種群。

3.1.3 進化算子

為使種群不斷進化，本文設計如下進化算子：

(1)選擇算子：使用輪盤賭方式。不斷循環(huán)地將選中個體添加到子種群中，直到其數(shù)量到達預定閾值。

(2)交叉算子：先生成一個概率值，若其低于交叉率，則選中一艘船，然后從子種群中隨機挑兩條染色體，交換這兩條染色體中選中船舶的位置，流程如圖3。

圖3 交叉算子流程

(3)變異算子：先生成概率值，若低于變異率，則從子種群中挑選個體，并交換其染色體上任意兩個基因的位置，流程如圖4。

圖4 變異算子流程

(4)新血液算子：隨機生成新個體，添加到子種群中。

(5)保持種群大小算子：當種群規(guī)模達到一定量，刪除部分劣質個體。

(6)擾動算子：不斷將最優(yōu)個體轉移到精英種群中，若超過一定次數(shù)未能轉移，則觸發(fā)進化策略，隨機將精英個體復制到父種群中。

3.1.4 并行規(guī)則及中止規(guī)則

設置多區(qū)域并行進化，經(jīng)過一定次數(shù)迭代，將第一階段每個區(qū)域最佳個體合并到第二階段區(qū)域，并進行再次進化。設置最大進化次數(shù)作為算法終止條件。

3.2 啟發(fā)式算法

給定染色體，計算其適應值：

(1) 根據(jù)船舶的tr、TBR，計算其最早靠泊時間EarlyTime

(2)根據(jù)船舶的長度，枚舉船舶所有可停靠泊段的組合{BerthList1,BerthList2,…}

(3)根據(jù)泊位情況，計算出其最早可用的時間，記為{BerthTime1,BerthTime2,…}，記其中最小可用時間對應的泊段組合的組號為S，則其最早可用時間為BerthTimes

(4)記靠泊時間為ts，若EarlyTime>BerthTimes，ts=EarlyTime；否則ts=BerthTimes

(7)根據(jù)ts、wait，計算船舶開工時間StartWork

(8)根據(jù)貨物量，從t=StartWork開始，遍歷每個WorkCapacityt，計算船舶完工時間EndWork，并記錄使用的勞動力情況ActualWork

(9)記離泊時間為tl，賦值tl=EndWork+TBL

(12)根據(jù)當前ts,tl,StartWork,EndWork,ActualWork及BerthLists，輸出船舶計劃內容，更新泊位和勞動力使用情況，算法結束。

4 數(shù)值實驗與案例分析

實驗運行于Intel Core i5 2.30GHzCPU，采用C#開發(fā)算法程序，調用ILOG CPLEX 12.8求解模型。

4.1 數(shù)值實驗

實驗中遺傳算法種群規(guī)模為50，交叉概率為90%，變異概率為1%，進化次數(shù)為10。使用2種方法求解：(1)使用CPLEX求解混合整數(shù)規(guī)劃模型(1小時計算時間上限)；(2)使用遺傳算法求解。實驗結果如表2，表中時段為給定時間范圍，30分鐘為一個時段；間斷數(shù)是碼頭間斷數(shù)；潮汐數(shù)是給定高潮時間點數(shù)量。GAP為遺傳算法與CPLEX結果的差距：GAP=(ObjGA-ObjCPLEX)/ObjCPLEX。另外，標注“-”為在規(guī)定時間內未獲得任何可行解。

基于表2可知：使用CPLEX求解混合整數(shù)規(guī)劃模型，即使只包含10艘船，也無法在規(guī)定時間內得到可行解。相反，遺傳算法耗時較短，其計算時間不會隨著規(guī)模的提高而顯著增加，結果與CPLEX計算結果平均GAP僅為3.11%。結果表明該算法能有效解決不同規(guī)模大小的滾裝碼頭泊位分配和勞動力分配聯(lián)合調度問題。

表2 數(shù)值實驗結果

4.2 案例分析

根據(jù)上海海通國際汽車碼頭有限公司的實際運營數(shù)據(jù)，對所提出算法的實用性進行驗證分析。選擇15次實際調度數(shù)據(jù)進行測試。該碼頭泊段為38個，存在2個間斷處(故虛擬2個泊段)。碼頭裝卸工人每日工作8小時，每2小時需休息1小時，1小時最多可裝卸400輛車。實驗結果如表3所示，其中計劃科為實際調度結果，節(jié)約時間為實際結果與遺傳算法結果的差值，以小時為單位。根據(jù)表3所示結果可知：

表3 案例實驗結果

(1)使用CPLEX 直接求解，對于貨物較多的5艘船或6艘船以上，在1小時內未能求出最優(yōu)解，部分案例會求得可行解，但比實際計劃科調度的結果都差。

(2)應用所提出的遺傳算法求解實際算例，所得結果較CPLEX的結果平均GAP僅為1%。

(3)應用所提出的遺傳算法求解實際算例，計算結果都比實際調度的結果好，平均可節(jié)約24.97小時。

根據(jù)案例分析結果，證明本文所提出的算法在實際運營中能夠幫助相關決策人員高效地為碼頭生成科學優(yōu)化的調度方案。與當前實際排產(chǎn)的方法相比，所提出的遺傳算法不僅計算時間短，而且能有效地降低船舶的服務時間，有利于碼頭的發(fā)展與進步。另外，自2021年4月起，本文所提算法已完成與海通汽車滾裝碼頭管理系統(tǒng)的應用集成。

5 結語

本文針對滾裝碼頭混合泊位分配和勞動力分配聯(lián)合調度問題，考慮潮汐時間窗對船舶靠離泊的影響、間斷泊位布局和纜樁分布對于船舶泊位分配的影響、勞動力對船舶裝卸貨時間的影響，以最小化船舶總服務時間為目標，建立混合整數(shù)規(guī)劃模型，設計遺傳算法和啟發(fā)式算法內外嵌套的組合算法對問題進行求解，外環(huán)為多種群并行進化的遺傳算法，輸出船舶計劃順序，內環(huán)為啟發(fā)式算法，計算指定船舶計劃順序的目標函數(shù)值。設計并生成多組數(shù)值實驗，證明數(shù)學模型的正確性、算法的高效性以及多場景的高度柔性。實踐案例進一步表明算法能夠高效生成優(yōu)化的調度方案，性能遠優(yōu)于商業(yè)求解器與人工調度。

致謝

感謝上海海通國際汽車碼頭有限公司以及該公司鄭剛、施曦等人對本文理論研究與應用測試所做出的大力支持與積極貢獻！