海鐵聯(lián)運港口混合作業(yè)模式下軌道吊與集卡協(xié)同調度

李舒儀，韓曉龍

（上海海事大學物流科學與工程研究院，上海 201306）

（*通信作者電子郵箱13097021834@163.com）

0 引言

近年來，我國多式聯(lián)運發(fā)展速度較快，國家陸續(xù)出臺相關政策。2017 年，國家出臺的《“十三五”國家信息化規(guī)劃》提出在重要的集裝箱港口逐步推進直通鐵路建設，力爭在2020 年完成集裝箱鐵水聯(lián)運的年運量增長10%的發(fā)展目標。但由于我國多式聯(lián)運一直處于起步階段，尤其碼頭與集裝箱班列的銜接并不順暢。在整個海鐵聯(lián)運過程中，海鐵聯(lián)運港口鐵路作業(yè)區(qū)是銜接鐵路運輸和水路運輸?shù)闹匾?jié)點。作為這一運輸鏈的重要節(jié)點，優(yōu)化鐵路作業(yè)區(qū)裝卸設備調度可以有效提高集裝箱在鐵路運輸和水路運輸中的周轉速度。

大多數(shù)研究集中在傳統(tǒng)集裝箱碼頭和鐵路中心站的裝卸設備調度問題上。He等［1］將軌道吊調度問題轉為帶時間窗的車輛路徑問題；Nossack 等［2］在堆場垂直于岸邊的布局下，將軌道吊調度問題分解為車輛路徑問題和無沖突調度問題，運用分支定界算法實現(xiàn)了中等規(guī)模下在多項式時間內(nèi)求得精確解；Sha等［3］從能耗角度，考慮輪胎吊禁止相互跨越、安全距離等實際約束；Galle 等［4］結合軌道吊調度問題與倒箱問題同時設計局部搜索啟發(fā)式算法解決問題；He 等［5］兼顧集裝箱到達時間和裝卸數(shù)量的不確定性，以最小化延遲時間為目標；李坤等［6］關注了集卡與軌道吊的聯(lián)系，以最小最大完工時間為目標，設計了兩階段禁忌算法求解；Kaveshgar等［7］研究了岸橋與集卡的協(xié)同調度問題；Bazgosha等［8］以集裝箱最小完工時間為目標，提出了三種方法來解決鐵路中心站軌道吊作業(yè)序列和箱位分配優(yōu)化問題；Li等［9］以最小化列車停留時間為目標，并考慮移動時間窗、安全距離等實際約束，采用動態(tài)分支定界算法求解模型；Guo 等［10］研究了鐵路集裝箱站軌道吊調度問題，考慮門吊的安全距離、走行時間等約束；Stephan 等［11］研究集裝箱在列車間轉運以及裝卸，并通過區(qū)分軌道吊轉運方向、停止準則和距離約束等來構建模型并分析運算復雜度。

因海鐵聯(lián)運港口同一般港口、一般鐵路中心站的布局模式與作業(yè)模式相比，有很多不同，有必要專門進行海鐵聯(lián)運港口作業(yè)設備調度的研究。近年來，已經(jīng)有越來越多的研究與海鐵聯(lián)運有關。劉勇等［12］研究了集裝箱海鐵聯(lián)運港口鐵路作業(yè)區(qū)“船舶-堆場-列車”模式的設備配置，兼顧作業(yè)時間窗約束；武惠榮［13］研究了“船舶-堆場-列車”作業(yè)模式下軌道吊調度問題；常祎妹等［14］在“船舶-堆場-列車”作業(yè)模式下研究海鐵聯(lián)運港口軌道吊、集卡和場橋協(xié)同調度問題，并考慮集卡堵塞的影響；Luo 等［15］設計了全新鐵路作業(yè)區(qū)，在“船舶-堆場-列車”作業(yè)模式下，以每個計劃周期內(nèi)的軌道吊為研究對象；李曉培［16］在“船舶-堆場-列車”作業(yè)模式下，以最小化軌道吊的最大完工時間為目標，將“岸橋-集卡-軌道吊”集成調度問題轉化成混合流水車間調度問題；Yan等［17］在“船舶-列車”作業(yè)模式下，設計了一種具有自適應水平和回溯策略的定制滾動計劃方法。

在現(xiàn)有的海鐵聯(lián)運港口作業(yè)設備調度的研究中，針對“船舶-列車”和“船舶-堆場-列車”這兩種作業(yè)模式下的研究相對較多，即研究分別是在船舶時刻表和班列時刻表完全重合和完全不重合情況下進行的。隨著海鐵聯(lián)運的發(fā)展，列車和船舶之間的協(xié)同性大幅提高，使鐵路和水上運輸?shù)臒o縫銜接有了可能。在海鐵聯(lián)運港口，列車作業(yè)區(qū)的集裝箱能直接轉運至碼頭前沿的船舶上，但由于不確定因素的干擾，船舶計劃和列車計劃往往存在不完全重合的情況。為加快集裝箱的周轉，海鐵聯(lián)運港口利用該時間窗將一些集裝箱運至碼頭前沿，其余集裝箱再進入堆場堆存，這符合海鐵聯(lián)運集裝箱裝卸作業(yè)高效化原則，利用這種時間窗的重合性來降低裝吊操作次數(shù)，有利于提高海鐵聯(lián)運港口的裝卸作業(yè)能力，在海鐵聯(lián)運港口實際作業(yè)中得到開展。

相較于傳統(tǒng)集裝箱港口作業(yè)，海鐵聯(lián)運港口增加了列車裝卸和中轉作業(yè)，這對泊位和岸橋的調度沒有影響。編組后的集裝箱班列進入到鐵路作業(yè)區(qū)，在和碼頭交換集裝箱后離開海鐵聯(lián)運港口。本文關注海鐵聯(lián)運港口鐵路作業(yè)區(qū)和碼頭的時間銜接情況，即在保證不耽誤班期和船期的情況下，優(yōu)化鐵路作業(yè)區(qū)軌道吊和集卡協(xié)同調度問題來最小化最大軌道吊完工時間。

1 問題描述與建模

1.1 問題描述

我國研究的海鐵聯(lián)運港口作業(yè)模式主要有“船舶-列車”和“船舶-堆場-列車”兩種。

“船舶-堆場-列車”作業(yè)模式裝卸流程下：以出口集裝箱為例，鐵路作業(yè)區(qū)的軌道吊將到達的集裝箱班列上的集裝箱卸下并等待集卡，集卡到后，軌道吊將集裝箱放在集卡上，然后集卡將其運往堆場，場橋再把集裝箱安放于分配好的位置上；待船舶到達后，集卡將堆場中的集裝箱運到碼頭前沿，由岸橋完成裝船工作。堆場區(qū)在整個作業(yè)過程中起著緩存的作用，相當于多了一次中轉，使得海鐵聯(lián)運港口的運輸效率偏低。

“船舶-列車”作業(yè)模式裝卸作業(yè)流程較為簡單，以出口集裝箱為例，鐵路作業(yè)區(qū)軌道吊將到達班列上的集裝箱轉移到集卡上，然后集卡完成從鐵路作業(yè)區(qū)到碼頭前沿的水平運輸，載有集裝箱的集卡到達碼頭前沿，由岸橋將集裝箱卸載至等待的船舶上。

“船舶-堆場-列車”作業(yè)模式相較“船舶-列車”作業(yè)模式，從作業(yè)工序來說，前者多了一個堆場作業(yè)環(huán)節(jié)，相當于多了一次中轉，那么在運輸成本及換裝時間方面，“船舶-列車”作業(yè)模式優(yōu)于“船舶-堆場-列車”作業(yè)模式；從協(xié)同組織水平看，后者省去了中間堆場的銜接環(huán)節(jié)，節(jié)省了作業(yè)時間及堆場資源，但對車船的協(xié)調性要求很高。

現(xiàn)如今國內(nèi)鐵路和港口的協(xié)同作業(yè)組織水平不是很高，由于不確定因素的干擾，往往導致船舶和班列的時刻表部分重合。針對船舶與列車在碼頭交匯時時間窗部分重合的特點，提出了“船舶-堆場-列車”和“船舶-列車”兩種模式相混合的一種調度模型。以出口集裝箱為例，在該模式下，部分出口箱在列車卸下后直接裝運至船舶上從而減去了堆場中轉的二次吊運環(huán)節(jié)，而剩余出口箱則卸載至堆場等待后續(xù)船舶裝船。以出口集裝箱為例，混合作業(yè)模式下作業(yè)示意圖如圖1。首先，把班列上集裝箱進行分類；然后，在船期和班期內(nèi)，將符合裝船條件的集裝箱（岸邊箱）采用“船舶-列車”模式，其余放入堆場的集裝箱（堆存箱）采用“船舶-堆場-列車”模式。在一次卸車裝船或卸船裝車過程中，由于集裝箱的屬性不同，使用到兩種模式，為簡明化，把這種作業(yè)流程命名為混合作業(yè)模式。

圖1 混合作業(yè)模式下裝卸作業(yè)流程Fig.1 Loading and unloading operation process in hybrid operation mode

集裝箱海鐵聯(lián)運作業(yè)場地多為長窄型，場地布局圖如圖2。以卸車裝船過程為例，軌道吊從前序任務的目標位置空駛至后序集裝箱的初始位置后，吊起集裝箱，再走行到后序集裝箱的目標位置：若是岸邊箱，軌道吊在等待集卡到達后，軌道吊作業(yè)以放至集卡上為結束；若是堆存箱，則以放至列車堆場中的箱位為止。影響軌道吊作業(yè)時長的主要因素有相鄰兩次裝卸作業(yè)間的空走時間和等待時間，即軌道吊的操作順序。

圖2 海鐵聯(lián)運港口布局Fig.2 Layout of rail-water intermodal terminal

本文優(yōu)化目標為：在混合作業(yè)模式下，構建軌道吊和集卡的協(xié)同調度模型，確定軌道吊和集卡操作順序、軌道吊作業(yè)時間和集卡作業(yè)時間。

1.2 模型假設

本文提出如下4點假設：

1）軌道吊和集卡的作業(yè)效率恒定；

2）裝卸計劃已知，且各個任務的起訖點已知；

3）軌道吊的操作時間和集裝箱裝卸計劃已知，且船舶和列車的允許作業(yè)時間已知；

4）不考慮軌道吊放箱時間；

1.3 符號與變量說明

參數(shù)與變量如表1所示。

表1 參數(shù)說明表Tab.1 Parameter and variable description table

1.4 模型描述

本文建立的混合整數(shù)規(guī)劃模型為

式（1）為目標函數(shù)，表示裝卸作業(yè)最大完成時間最小化，其中最大完成時間為最后一項任務的軌道吊作業(yè)完成時間；式（2）～（7）表示軌道吊或集卡有且僅有一個前序作業(yè)或后序作業(yè)；式（8）～（10）表示軌道吊的安全操作約束，包括安全距離約束和不能相互跨越的約束，即編號較小的軌道吊應在較小的貝位號區(qū)域工作，編號較大的軌道吊應在較大的貝位號區(qū)域工作。式（11）和式（12）要求軌道吊的后序集裝箱作業(yè)開始時間必須要晚于前序集裝箱作業(yè)完成時間以及軌道吊從前序作業(yè)位置移動至后序作業(yè)位置的時間。如果后序集裝箱去向為岸邊，且軌道吊比集卡抵達得更早，則還需加上軌道吊等待集卡的時間。等待時間是集卡到達時間和軌道吊抵達時間之間的差。式（13）和式（14）要求集卡的后序集裝箱的作業(yè)開始時間晚于前序集裝箱作業(yè)完成時間以及集卡從前序作業(yè)位置空駛至后序作業(yè)位置的時間。如果集卡比軌道吊抵達得更早，則需加上集卡等待軌道吊的時間。其中Wwi表示后序去向岸邊的集裝箱任務中集卡等待軌道吊的時間；式（15）表示軌道吊作業(yè)開始時間與完成時間的關系；式（16）表示集卡作業(yè)開始時間與完成時間的關系；式（17）表示同一卸車裝船任務中，軌道吊的作業(yè)完成時間必須早于或等于集卡的作業(yè)開始時間；式（18）和式（19）表示集卡的最大完成時間應不大于船舶允許作業(yè)時間；所有變量都是非負量。

2 混合遺傳算法

軌道吊和集卡的協(xié)同調度問題已由文獻［18］證明是NP_hard 問題。針對遺傳算法在局部搜索能力方面的不足，將啟發(fā)式規(guī)則與遺傳算法相結合，設計了求解軌道吊與集卡協(xié)同調度問題的混合遺傳算法（Hybrid Genetic Algorithm，HGA），算法流程如圖3所示。

圖3 混合遺傳算法流程Fig.3 Hybrid genetic algorithm flowchart

1）編碼。

采用基于優(yōu)先級的編碼，每一個基因對應一個任務，給分配一個隨機生成的0～1 的優(yōu)先級值，染色體依據(jù)優(yōu)先級值生成。任務編碼如6-3-1-2-5-4。

2）啟發(fā)式規(guī)則。

本文引入集裝箱碼頭中比較有效的作業(yè)方式，并在多變量約束下設計了一個“雙層調度”規(guī)則。具體流程如圖4所示。

圖4 任務分配流程Fig.4 Task allocation flowchart

基于軌道吊的任務屬性，即上一任務的完工時間、任務編號和上一任務的目標位置，建立3*G維的特征矩陣來實現(xiàn)對每個軌道吊的控制。同理，建立2*W維的特征矩陣來實現(xiàn)對每個集卡的控制。

染色體上的每個基因依次分配到軌道吊和集卡，一旦任務分配完成，便根據(jù)式（8）～（10）先后更新軌道吊和集卡的特征矩陣。

第一層為軌道吊調度層。首先將最早可用時間、干涉情況、與任務位置的距離和編號依次作為軌道吊的選擇條件，把任務分配給合適的軌道吊；其次通過限制軌道吊的移動來滿足軌道吊的安全操作約束。

第二層為集卡調度層。檢查集裝箱的屬性，若為堆存箱，則進行下一個任務分配；若為岸邊箱，將最早可用時間和編號依次作為集卡的選擇條件，將任務分配給合適的集卡；然后通過限制設備的移動來滿足順序作業(yè)約束。

3）解碼。

隨機產(chǎn)生的染色體如6-3-1-2-5-4，已知各集裝箱的去往方向為：0-0-1-0-1-1，1表示岸邊箱，需要集卡作業(yè)；0表示堆存箱，不需要集卡作業(yè)。若1 號軌道吊、2 號軌道吊、1 號集卡和2 號集卡參與調度，在任務分配后的軌道吊作業(yè)序列表：1-1-2-2-1-2，集卡作業(yè)序列表：無-無-1-無-2-1。其中1號軌道吊操作順序為集裝箱6-3-5，2 號軌道吊操作順序為集裝箱1-2-4，1號集卡操作順序為集裝箱1-4，2號集卡操作順序為集裝箱4。

4）適應度函數(shù)。

目標函數(shù)值越小，說明適應度值越大，個體適應度越高。

5）最優(yōu)個體保存。

若當前最優(yōu)個體的目標值在允許作業(yè)時間內(nèi)，則保存下來；反之，則不予保留。

6）順序交叉（Order Crossover，OX）。

本文采用OX方式，如圖5所示。

圖5 OXFig.5 OX

7）兩點變異。

為了避免算法陷入局部最優(yōu)，本文采用兩點變異方式進行染色體變異。具體步驟如下：

第1步 設定一個變異概率（Mutation Probability，MP）。

第2 步 對每一個個體，隨機生成一個（0，1）內(nèi)的隨機數(shù)i。

第3步 如果i＞MP，則實施變異操作；否則，不變異。

第4 步 選取兩個基因位，再將這兩個位置上的基因互換，獲得新的個體。

3 模擬計算與實驗分析

本文設備參數(shù)的數(shù)據(jù)來源于文獻［14］和文獻［17］，如表2和表3所示。

表2 設備基本參數(shù)Tab.2 Basic parameters of equipment

表3 模型基本參數(shù) 單位：mTab.3 Basic parameters of the model unit：m

為較好地解決軌道吊與集卡的協(xié)同調度問題，本文設計了蟻群優(yōu)化（Ant Colony Optimization，ACO）算法來同混合遺傳算法進行對比分析。ACO算法的流程如圖6所示。

圖6 ACO算法流程Fig.6 Flowchart of ACO algorithm

ACO算法過程如下：

步驟1 生成初始種群。

步驟2 隨機產(chǎn)生任務序列。

步驟3 計算轉移概率。螞蟻選擇該任務的概率與距離，和當前連接支路上所包含的信息有關。這里根據(jù)式（8）～（10）來跳過不能爬行到這個點的螞蟻。

步驟4 任務分配。和混合遺傳算法的任務分配規(guī)則一樣。

步驟5 修改禁忌表。為了強制螞蟻進行合法的游走，不能游走已訪問過的點和到不了的點。

步驟6 重復步驟3～5，直到全部的點游走過。更新所有路徑上的信息素。

步驟7 記錄本次迭代的路徑，更新當前的最優(yōu)路徑，清空禁忌表。

步驟8 判斷是否達到預定的迭代次數(shù)：若是，算法結束；若不是，種群全部死去，轉步驟2進行下一次迭代。

基于以上思想，開始編程實現(xiàn)，圖7 所示為同等迭代次數(shù)下兩種算法的收斂曲線，可以看出混合遺傳算法（HGA）相較于蟻群優(yōu)化（ACO）算法，迭代次數(shù)較少，計算速度較快。

圖7 HGA和ACO算法收斂曲線對比Fig.7 Convergence curve comparison of HGA and ACO algorithm

為進一步驗證混合遺傳算法的優(yōu)越性。參照文獻［16］來設計針對軌道吊與集卡協(xié)同調度的13個算例，分別采用HGA和ACO算法進行驗算。表4為岸邊箱占總集裝箱比為1的情況下的13個算例結果。遺傳算法基本參數(shù)如表5所示，同時比較遺傳算法得到的結果和CPLEX（IBM ILOG CPLEX Optimization Studio V12.9）直接求解的最優(yōu)目標值，objHGA表示混合遺傳算法獲得的目標值，objCPLEX表示CPLEX 獲得的目標值?？梢酝ㄟ^遺傳算法獲得的目標值與通過CPLEX獲得的目標值之間的差距GAP來衡量混合遺傳算法的解的有效性：

表4 不同數(shù)據(jù)規(guī)模的實驗結果Tab.4 Experimental results of different data scales

表5 混合遺傳算法基本參數(shù)Tab.5 Basic parameters for hybrid genetic algorithm

分析可知，對于所有算例，混合遺傳算法在計算效率上均優(yōu)于CPLEX 和ACO 算法，且計算效率的優(yōu)勢隨著問題規(guī)模的增大越來越明顯。從計算結果看，混合遺傳算法略優(yōu)于ACO算法，與CPLEX 相比，平均GAP 值僅為2.08%，這表明所提出的遺傳算法是有效的。總之，根據(jù)表4 的實驗結果，該模型有效地解決了軌道吊和集卡的協(xié)同調度問題，并且所提出的混合遺傳算法通過了很好的測試，驗證為解決海鐵聯(lián)運港口軌道吊和集卡的協(xié)同調度問題的較優(yōu)算法。

混合遺傳算法的穩(wěn)定性測試：以集裝箱數(shù)為90，5 臺軌道吊和8 輛集卡、岸邊箱占比分別為0.4 和0.6，進行30 次實驗得到的結果如表6。從表6 可以看出，在大規(guī)模算例下，混合算法依然發(fā)揮較好的穩(wěn)定性。

表6 混合遺傳算法的穩(wěn)定性測試Tab.6 Stability test of hybrid genetic algorithm

班列上的集裝箱種類和數(shù)目是變化的，若要保證班期和船期不延誤，那么軌道吊數(shù)量和集卡數(shù)量也應根據(jù)實際情況有所變動。在混合作業(yè)模式下，集裝箱數(shù)量、岸邊箱占比、軌道吊數(shù)量和集卡數(shù)量，是影響軌道吊最大完工時間和集卡最大完工時間的四個重要因素，合理的設備配比和調度是提高班列和船舶正點率的重要手段。本文分別選取3 臺軌道吊和6 輛集卡、4 臺軌道吊和6 輛集卡、5 臺軌道吊和8 輛集卡對不同岸邊箱占比不同數(shù)目的集裝箱進行了60 組實驗，每組實驗進行30次，取每組實驗平均值，實驗結果如表7所示。

1）為研究不同集裝箱數(shù)量不同岸邊箱占比對完工時間的影響，以4 臺軌道吊6 輛集卡為例，集裝箱數(shù)量分別為30、40、50、60、90，岸邊箱占比分別為0、0.4、0.6 和0.8，軌道吊完工時間的變化如圖8所示。

圖8 不同集裝箱數(shù)量不同岸邊箱占比下軌道吊完工時間Fig.8 Completion time of rail-mounted gantry crane under different container numbers and different proportions of quayside containers

從圖8 可以看出，當集裝數(shù)量是某一確定的數(shù)量時，隨著岸邊箱占比的增加，軌道吊完工時間也隨之增加。當集裝箱數(shù)量從30 增加到90 時，可以明顯地看出，隨著岸邊箱占比的提高，軌道吊完工時間增加的幅度越大。從表7 較明顯地可以看出，集卡完工時間的變化類似于軌道吊完工時間的變化，就不展開描述了。故當班列上的岸邊箱較多時，應適當提高軌道吊數(shù)量，才能有效降低集裝箱在港停留時間。

表7 不同設備配置下的實驗結果 單位：minTab.7 Experimental results under different equipment configurations unit：min

2）為研究軌道吊數(shù)量和集卡數(shù)量對完工時間的影響。以岸邊箱占比為0.6 為例，當軌道吊數(shù)目增加以及集卡數(shù)目增加時，觀察完工時間的變化情況，如圖9 所示（注：第一次變化指從3 臺軌道吊6 輛集卡增加到4 臺軌道吊6 輛集卡，完工時間減少的值；第二次變化指從4 臺軌道吊6 輛集卡增加到5 臺軌道吊8輛集卡，完工時間減少的值）。

圖9 不同集裝箱數(shù)量不同設備配置下完工時間的變化Fig.9 Change of completion time under different container numbers and different configurations

從圖9 可看出，集裝箱數(shù)量較少時，軌道吊數(shù)目和集卡數(shù)目的變化對軌道吊完工時間和集卡完工時間產(chǎn)生的影響不大。但當集裝箱數(shù)量達到60和90時，完工時間減少的值較明顯增大，說明此時設備配比不是最佳的。進而在固定4 臺軌道吊的情況下，改變集卡數(shù)量來確定最佳設備配比，實驗結果如表8 所示。從表8 看出，當集裝數(shù)量為60 和岸邊箱占比為0.6 時，集卡數(shù)量從6 輛增加至8 輛時，邊際效益值較高，而集卡數(shù)量從8 繼續(xù)增加時，邊際效益值明顯減少，故最佳設備配比為4 臺軌道吊8 輛集卡；同理，90 個集裝箱的設備配比為4臺軌道吊8輛集卡。

表8 不同集卡數(shù)量下作業(yè)完成時間Tab.8 Operation completion time of different numbers of container trucks

還發(fā)現(xiàn)在岸邊箱占比為0.4 的情況，集卡數(shù)量的增加不一定會減少完工時間，這說明當岸邊箱占比較低時，集卡數(shù)量增加到一定時，反而會使軌道吊完工時間延長，故當班列上集裝箱的岸邊箱占比有所變化時，有必要根據(jù)具體的情況調整設備配比。

4 結語

在船舶和班列的時刻表不完全重合時，對混合作業(yè)模式下軌道吊和集卡的協(xié)同調度優(yōu)化的研究，為海鐵聯(lián)運港口的運營與管理提供了優(yōu)化思路，在一定程度上可幫助海鐵聯(lián)運港口提高綜合競爭力。在今后的研究中為使問題更復雜，將建立軌道吊、集卡和岸橋的集成調度模型；還將軌道吊和集卡的數(shù)量作為決策變量，均衡各軌道吊和集卡的作業(yè)量，以及考慮列車或船舶晚點情況下，研究設備最佳配比問題。