基于析取圖的鐵水聯(lián)運港口設備協(xié)同調(diào)度方法

劉文茜，朱曉寧，王 力，遲美燕，閆 偉

(1.北京交通大學 交通運輸學院, 北京 100044；2.中國國家鐵路集團有限公司 辦公廳, 北京 100844)

作為綜合交通運輸體系中的重要運輸組織形式，貨物多式聯(lián)運在國際貿(mào)易中逐漸表現(xiàn)出優(yōu)勢和特色。從具有廣闊內(nèi)陸腹地的國家或區(qū)域看，貨物多式聯(lián)運體系建設的關鍵在于“鐵-水”聯(lián)運。2019年國家發(fā)改委在《關于加快推進鐵路專用線建設的指導意見》中明確提出：至2025年，沿海主要港口和長江沿線主要港口全部實現(xiàn)鐵路入港。這一政策不僅為港口吸引了更多箱流，同時也增加了設備作業(yè)量，使得港口集裝箱作業(yè)更為復雜。在此背景下，需要依據(jù)現(xiàn)有港口資源，調(diào)整集裝箱集疏運組織及設備作業(yè)調(diào)度方案，以促進港口鐵路作業(yè)與水運作業(yè)的融合。

鐵路作業(yè)區(qū)作為港口銜接鐵路運輸與水路運輸?shù)年P鍵區(qū)域，其裝卸作業(yè)組織是支撐鐵水聯(lián)運港口集裝箱快速轉運的重要環(huán)節(jié)，這對作業(yè)過程涉及的多項設備調(diào)度作業(yè)計劃的配合和銜接提出了較高要求。目前許多學者對這類問題展開了研究，但多集中于單作業(yè)模式下的港口設備調(diào)度優(yōu)化，對聯(lián)運模式下的設備協(xié)同作業(yè)優(yōu)化研究相對較少，且優(yōu)化目標較為單一[1]。Chen等[2]通過約束規(guī)劃模型和三階段算法優(yōu)化集裝箱在碼頭前沿和堆場之間的裝卸作業(yè)，同時考慮任務作業(yè)順序優(yōu)先級及集卡的走行路徑。Lu等[3]考慮集卡走行速度變化及場吊吊具升降時間，設計基于排隊思想的粒子群優(yōu)化算法求解岸橋-集卡-場吊協(xié)同調(diào)度問題，但沒有考慮集卡的具體走行路徑。Assadipour等[4]提出對場橋和岸橋協(xié)同調(diào)度的分析框架，并通過設備的協(xié)同調(diào)度有效縮短了集裝箱周轉時間。Kaveshgar等[5]基于混合流水車間思想，針對進口箱卸箱過程，研究岸側裝卸、轉運設備兩階段作業(yè)調(diào)度問題，同時考慮集裝箱作業(yè)順序優(yōu)先級約束、交叉干擾和安全距離約束。Yang等[6]著眼于自動化場站，以最小化作業(yè)完工時間為目標，建立雙層規(guī)劃模型，上層對岸橋-AGV-場橋之間的協(xié)同作業(yè)進行決策，下層實現(xiàn)AGV路徑規(guī)劃，防止擁堵現(xiàn)象。Yue等[7]從客戶滿意度和設備作業(yè)效率角度出發(fā)，通過建立兩階段多目標混合整數(shù)規(guī)劃模型優(yōu)化集裝箱碼頭設備配置及調(diào)度聯(lián)合作業(yè)問題，以提升碼頭競爭力。張思等[8]針對設備效率差異，研究不確定因素下的岸橋-集卡協(xié)同調(diào)度，并提出粒子群算法與禁忌搜索相結合的混合算法進行求解。以鐵路集裝箱作業(yè)場站為背景，王力等[9]以最小化作業(yè)完工時間為目標，建立軌道門吊調(diào)度優(yōu)化模型，有效縮短了集裝箱裝卸作業(yè)時間。Chen等[10]基于“時-空-狀態(tài)”網(wǎng)，建立自動化軌道門吊和全自動導軌車協(xié)同調(diào)度模型，目標是車輛周轉時間最小。然而，目前對鐵路入港模式下聯(lián)運港口鐵路作業(yè)區(qū)設備協(xié)同調(diào)度問題的研究較少，常祎妹等[11]針對“車船直取”集裝箱作業(yè)流程，在考慮設備運行速度的變化及設備作業(yè)安全距離約束的基礎上，優(yōu)化相關設備的協(xié)同作業(yè)。Yan等[12]分析存在緩存區(qū)的港口鐵路作業(yè)區(qū)和堆場之間的作業(yè)過程，以軌道門吊為主，集卡和堆場正面吊為輔，建立3種設備的集成調(diào)度優(yōu)化模型，將最早可用設備策略與遺傳算法相結合求解問題。

總之，現(xiàn)有對集裝箱裝卸作業(yè)的優(yōu)化研究大多針對鐵路集裝箱場站、港口堆場、港口岸側等單一運輸方式下的多設備協(xié)同調(diào)度問題，未能反映鐵水聯(lián)運模式下的鐵路作業(yè)與港口作業(yè)的銜接關系。除此以外，既有研究優(yōu)化目標較為單一，且多對問題進行了簡化，未充分考慮可能影響集裝箱裝卸轉運作業(yè)的多種現(xiàn)實約束。本文重點關注將鐵路線引入碼頭后方后，鐵路與水運兩個運輸系統(tǒng)融合后的節(jié)點作業(yè)優(yōu)化，考慮實際作業(yè)中集裝箱作業(yè)順序優(yōu)先級約束，研究混合裝卸模式下鐵路作業(yè)區(qū)軌道門吊、集卡、場吊協(xié)同調(diào)度多目標優(yōu)化問題，并進一步規(guī)劃集卡在各區(qū)域之間的走行。

1 問題描述與建模

1.1 影響因素分析及問題界定

鐵路入港模式下，列車裝卸作業(yè)的引入對港口作業(yè)組織、作業(yè)調(diào)度等提出了新要求，港口的資源分配與利用也影響著鐵水聯(lián)運箱轉運作業(yè)效率，港口作業(yè)調(diào)度人員需要分析和界定關鍵作業(yè)環(huán)節(jié)相關影響因素。

(1)貨物到達率及轉運數(shù)量。出口方向，港口作業(yè)調(diào)度人員能夠從鐵路車站提前獲取到港列車信息，因此鐵路箱到達時刻已知，且較為穩(wěn)定；進口方向，港口作業(yè)調(diào)度人員依據(jù)集裝箱到港情況提報運輸計劃，按照取送車情況安排轉運方案。因此，在較短的給定時間周期內(nèi)，依據(jù)轉運方案需要進行轉運的聯(lián)運箱方向、堆存位置、數(shù)量等為本文研究的多階段設備協(xié)同調(diào)度問題的輸入，進而對設備作業(yè)任務的執(zhí)行順序及作業(yè)時間進行決策。

(2)堆場面積及數(shù)量。堆場面積及數(shù)量決定了港口能容納轉運集裝箱的數(shù)量，在一般港口作業(yè)組織中，需要對集裝箱按方向、按作業(yè)類型進行箱位指派，確保其堆存位置便于作業(yè)且滿足堆場作業(yè)能力，即堆場空間資源分配問題。在既定布局下，集裝箱堆存位置作為本文研究問題的輸入，在此基礎上對設備的作業(yè)序列和任務分配進行決策，減少設備的空駛距離。

(3)設備的分配與調(diào)度。聯(lián)運箱的轉運在作業(yè)層面涉及列車裝卸設備、水平運輸設備以及堆場作業(yè)設備，三者的作業(yè)能力共同影響聯(lián)運箱的轉運效率，需要對調(diào)度方案進行協(xié)同決策，使任務各階段作業(yè)緊密銜接，減少不必要的等待時間。在實際作業(yè)中，設備可能出現(xiàn)故障等不確定情形，通常解決方法是在已有作業(yè)方案的基礎上進行重調(diào)度，保證作業(yè)的順利進行。本文根據(jù)集裝箱轉運需求，制定各階段設備初始協(xié)同作業(yè)計劃，暫不考慮設備故障情形下的重調(diào)度問題。

港口各區(qū)域主要作業(yè)組織關系見圖1。

圖1 港口各區(qū)域主要作業(yè)組織關系圖

基于以上分析，貨物到達率及轉運數(shù)量，堆場面積及數(shù)量對本文研究的多階段設備協(xié)同調(diào)度問題不產(chǎn)生直接影響。本文著重圍繞鐵水聯(lián)運箱“卸車-堆存”和“提箱-裝車”需求，根據(jù)確定的列車裝卸車任務，對一定周期內(nèi)需轉運的集裝箱進行調(diào)度，確定各階段作業(yè)設備的任務執(zhí)行順序和作業(yè)時間，從調(diào)度作業(yè)層面優(yōu)化設備的使用。港口的設備協(xié)同調(diào)度問題與混合流水車間問題相似，具有多工序、多機并行的特點，其主要區(qū)別為：

圖2 集裝箱碼頭鐵路作業(yè)區(qū)與堆場布置示意

(1)時間差異性。首先，任務作業(yè)時間具有差異性，某一設備處理同一類型任務的作業(yè)時間不同，取決于該任務的存儲位置及目標位置；其次，設備銜接時間具有差異性，取決于任務作業(yè)類型。

(2)接續(xù)緊密性。各階段作業(yè)之間不存在緩沖區(qū)，相互接續(xù)的兩個作業(yè)設備需要同時到達任務取送點，此時才能結束上一階段作業(yè)并開始下一步作業(yè)。

(3)雙向作業(yè)性。三階段作業(yè)具有正向和反向兩種作業(yè)流程約束且同時進行，兩種方向的作業(yè)流程存在嚴格的先后關系，即進口方向遵循“堆場提箱-水平運輸-鐵路區(qū)裝車”的流程，出口方向遵循“鐵路區(qū)卸車-水平運輸-堆場存箱”的流程。

1.2 問題描述

鐵路裝卸線引入碼頭后方后，港口集裝箱箱流作業(yè)類型和設備作業(yè)調(diào)度都將發(fā)生改變，增加了集裝箱裝卸、轉運作業(yè)組織的復雜度?？紤]現(xiàn)實中港口堆場的既有資源和配置，鐵路箱將與公路箱共用堆場設備資源，即不另外設置鐵路堆場。鐵路出口箱隨列車到達港口鐵路作業(yè)區(qū)，經(jīng)由軌道門吊卸至內(nèi)部集卡，集卡通過短駁運輸將集裝箱運送到堆場出口箱區(qū)，再由場吊將集裝箱堆存至指定位置，進口箱作業(yè)過程相反。整個作業(yè)過程涉及多個區(qū)域軌道門吊、集卡、進口區(qū)場吊和出口區(qū)場吊等多項設備，若單獨考慮每個作業(yè)區(qū)設備的調(diào)度作業(yè)，即使軌道門吊、場吊分別實現(xiàn)作業(yè)時間最短，能夠保證作業(yè)區(qū)域自身的效率，然而各階段作業(yè)之間缺乏配合，若集裝箱完成卸車作業(yè)后到達堆場，但場吊不執(zhí)行該箱的堆存作業(yè)，則會引起任務沖突，嚴重時可能產(chǎn)生死鎖現(xiàn)象。除此以外，集卡負責各區(qū)域之間的短駁，由于不設置區(qū)域間緩沖區(qū)，集卡任務作業(yè)順序同樣影響軌道門吊和場吊的調(diào)度，若集裝箱完成裝卸作業(yè)時未安排集卡接續(xù)，會引起設備長時間占用，造成資源浪費，同時影響后續(xù)任務的執(zhí)行。因此，港口需要根據(jù)鐵路裝卸線引入后箱流作業(yè)類型的增加和流程的變化，對整個作業(yè)過程涉及的多項作業(yè)設備進行協(xié)同調(diào)度，保證港口作業(yè)效率。

因此，本文以最小化作業(yè)完工時間以及設備空駛時間為優(yōu)化目標，調(diào)整軌道門吊、集卡、場吊各設備的集裝箱任務執(zhí)行順序以及集卡在各區(qū)域的接續(xù)方案。

本問題涉及的港口主要作業(yè)區(qū)域布置見圖2，在混合裝卸作業(yè)模式下，即列車上某一位置出口箱卸下后，無需等待整列車卸空，軌道門吊可進行進口箱的裝車作業(yè)，因此列車同一位置上裝卸作業(yè)任務可能發(fā)生沖突。如圖2所示，進口箱3、5、6的目標車廂分別裝有出口箱1、2、4，必須先將對應位置出口箱卸下才能進行進口箱的裝車作業(yè)。另外，在集裝箱堆場進口箱區(qū)中，位于上層的集裝箱必須先于下層集裝箱提走，否則將產(chǎn)生翻箱作業(yè)，如箱3、5；出口箱區(qū)目標箱位在底層的集裝箱必須先于上層完成堆存作業(yè)，如箱1、2。綜上，在多設備協(xié)同作業(yè)過程中可能產(chǎn)生多種矛盾沖突的情況，需要分別做出處理。

(1)裝卸作業(yè)順序沖突

解決作業(yè)順序沖突的方法主要有兩種：一是規(guī)定作業(yè)順序優(yōu)先級，二是設置交接緩沖區(qū)。若在鐵路作業(yè)區(qū)設置緩沖區(qū)用于暫存卸下的出口箱，則會增加軌道門吊作業(yè)任務，產(chǎn)生額外的時間消耗，本文通過設置集裝箱作業(yè)順序優(yōu)先級來滿足部分集裝箱裝卸作業(yè)的先后要求。

(2)任務死鎖現(xiàn)象

各項設備作業(yè)方案之間需要高度配合，避免因任務沖突無設備接續(xù)而產(chǎn)生死鎖現(xiàn)象。而在聯(lián)運作業(yè)中，鐵路作業(yè)區(qū)具有較強的時間約束性，因此以鐵路作業(yè)區(qū)軌道門吊為核心設備，以其作業(yè)序列為主，進一步協(xié)調(diào)集卡和場吊的作業(yè)。

本文中各軌道門吊、場吊負責固定的作業(yè)區(qū)域，故對應設備承擔的任務已知，通過優(yōu)化各設備作業(yè)任務的執(zhí)行順序可減少任務之間的銜接時間，各任務作業(yè)距離通過曼哈頓距離表示。集卡的行駛時間與作業(yè)類型密切相關，若為集卡分配“重去重回”的任務，如集卡在堆場完成交箱后直接裝載進口集裝箱前往鐵路作業(yè)區(qū)，則能夠減少該車輛的空駛距離，從而提高集卡利用率，因此需要為集卡合理分配任務并確定集卡路徑。

1.3 模型假設

為了使模型更合理，本文提出以下假設：

(1)集裝箱在列車、堆場的位置已知。

(2)軌道門吊、場吊所分配的集裝箱裝卸作業(yè)任務對象已知，但各設備所負責的集裝箱裝卸作業(yè)任務的執(zhí)行順序未知。

(3)進口箱和出口箱堆存在不同箱區(qū)。

(4)不考慮翻箱作業(yè)。

(5)一半集卡初始位置在鐵路作業(yè)區(qū)，一半在堆場。

1.4 符號定義

符號及定義見表1。

1.5 數(shù)學模型

根據(jù)1.2節(jié)的問題描述，建立鐵水聯(lián)運設備協(xié)同調(diào)度模型，優(yōu)化場站各設備作業(yè)序列及任務作業(yè)時間。

(1)目標函數(shù)

表1 符號及定義

作業(yè)效率是場站運營管理的關注重點，提高作業(yè)效率能夠加快集裝箱的在站中轉速度，減少在站停留時間。同時，在相同作業(yè)完工時間下，不同作業(yè)設備的利用率也有所差異。兩個任務接續(xù)時，完成當前任務后前往距離較近的下一任務可減少空駛距離，提高設備利用率。因此從作業(yè)效率和設備利用率兩方面開展多目標優(yōu)化，最小化最晚完工時刻和設備空駛時間，有助于提升作業(yè)銜接的緊密程度，提高港口海鐵聯(lián)運的作業(yè)水平。目標函數(shù)為

(1)

(2)

minf=α1f1+α2f2

(3)

式(1)從場站作業(yè)效率的角度最小化作業(yè)最晚完工時刻，即軌道門吊結束作業(yè)的時刻或者場吊結束作業(yè)的時刻；式(2)從場站設備利用率的角度最小化設備總空駛時間，時間由軌道門吊、集卡、場吊3種設備在任務接續(xù)時的空駛距離和移動速度計算得到；目標函數(shù)為式(3)，通過比例系數(shù)調(diào)整兩個目標之間的權重。

(2)約束條件

鐵水聯(lián)運設備協(xié)同調(diào)度問題受諸多約束限制，在作業(yè)流程上，相鄰兩道工序的作業(yè)設備必須同時到達任務交接點才能夠開始或結束各自的作業(yè)，對于出口任務和進口任務，兩者流程相反。對于任務本身的作業(yè)，必須滿足設備處理時間，以及設備在任務間移動的時間需求。從設備的作業(yè)序列來看，其負責的任務必須滿足接續(xù)關系，即后一任務必須在前一任務結束后才能開始，保證作業(yè)的連貫性。

鐵路作業(yè)區(qū)軌道門吊作業(yè)約束為

(4)

(5)

(6)

?i′∈Jg∩U?g∈G

(7)

(8)

(9)

(10)

(11)

式(4)、式(5)定義了軌道門吊對任務的作業(yè)開始時刻，對于每個出口任務，軌道門吊為第一道工序，則該任務作業(yè)開始時刻不得早于門吊結束前一任務的時刻加上移動至該任務起點的銜接時間；對于每個進口任務，軌道門吊為第三道工序，則該任務作業(yè)開始時刻不得早于集卡(第二道工序)將其運到交接區(qū)的時間。式(6)、式(7)約束了軌道門吊對任務的結束時刻，式(6)表示其結束時刻不早于開始時刻加上移動時間及裝卸作業(yè)時間，式(7)表示對于出口任務，軌道門吊必須等集卡接走該任務后才能結束。式(8)表示軌道門吊最晚完工時刻，即所有軌道門吊中最后一個結束任務的時刻。對于已知任務分配的軌道門吊，式(9)表示每個任務有且只能有某一個后續(xù)任務，且只有一個起始任務和結束任務。式(10)表示每個任務有且只能有某一個前續(xù)任務，且只有一個起始任務和結束任務。式(11)表示任意兩個任務之間只能存在一種作業(yè)先后順序，即不可能存在任務i在任務i′之前且任務i在任務i′之后的情況。

轉運設備集卡作業(yè)約束為

(12)

(13)

(14)

(15)

(16)

(17)

?i′∈L?k∈K

(18)

?i′∈U?k∈K

(19)

(20)

(21)

(22)

(23)

(24)

(25)

式(12)規(guī)定集卡當前任務的起點到達時刻，即集卡上一任務結束時刻加上行駛到當前任務點的時間。式(13)～式(15)定義集卡對任務的作業(yè)開始時刻，對于每個出口任務，不得早于軌道門吊與其交接該任務的時刻，對于每個進口任務，不得早于場吊與其交接該任務的時刻，且滿足集卡到達后裝載時間需要。式(16)表示集卡當前任務的終點到達時刻需滿足運輸時間要求。式(17)～式(19)約束集卡對任務的結束時刻，即對于出口任務，為場吊將該任務取走的時刻，對于進口任務，為軌道門吊將該任務取走的時刻。式(20)表示每個任務有且只能有一個后續(xù)任務，且由一個集卡負責。式(21)表示每個任務有且只能有一個前續(xù)任務，且由一個集卡負責。式(22)、式(23)保證每個集卡有且只能有一個起始任務和一個結束任務。式(24)為集卡連續(xù)作業(yè)約束。式(25)表示任意兩個任務之間只能存在一種作業(yè)先后順序，即不可能存在任務i在任務i′之前且任務i在任務i′之后的情況。

堆場場吊作業(yè)約束為

(26)

(27)

(28)

?i′∈Jg∩L?y∈Y

(29)

(30)

(31)

(32)

(33)

式(26)、式(27)定義場吊對任務的作業(yè)開始時刻，對于每個進口任務，場吊為第一道工序，則該任務作業(yè)開始時刻不得早于場吊結束前一任務的時刻加上移動至該任務起點的銜接時間；對于每個出口任務，場吊為第三道工序，該任務作業(yè)開始時刻不得早于集卡(第二道工序)將集裝箱運到交接區(qū)的時刻。式(28)、式(29)約束場吊對任務的結束時刻，式(28)表示其結束時刻不早于開始時刻加上移動時間及裝卸作業(yè)時間，式(29)表示對于進口任務，場吊必須等集卡接走該任務后才能結束。式(30)表示場吊最晚完工時刻，即所有場吊中最后一個結束任務的時刻。對于已知任務分配的場吊，式(31)表示每個任務有且只能有某一個后續(xù)任務，且只有一個起始任務和結束任務。式(32)表示每個任務有且只能有某一個前續(xù)任務，且只有一個起始任務和結束任務。式(33)表示任意兩個任務之間只能存在一種作業(yè)先后順序，即不可能存在任務i在任務i′之前且任務i在任務i′之后的情況。

任務作業(yè)順序優(yōu)先級約束為

(34)

(35)

(36)

式(34)表示軌道門吊必須先將列車上某位置出口箱卸下才能裝載對應位置進口箱。式(35)表示集卡運輸?shù)牧熊嚹澄恢蒙线M口箱必須在其他集卡取走該位置出口箱后才能交接。式(36)表示堆場作業(yè)中場吊必須先將上層集裝箱取走才能提取下層，堆存作業(yè)則相反。

2 求解算法

港口的多設備協(xié)同調(diào)度問題具有多工序、多機并行的特點，其實質(zhì)與生產(chǎn)中的混合流水車間調(diào)度問題相似，屬于為NP-hard問題[5]，無法在多項式時間內(nèi)求出精確結果，需要采用啟發(fā)式算法求解。目前遺傳算法和禁忌搜索算法已被廣泛使用在生產(chǎn)調(diào)度問題中[1]，考慮本問題與混合流水車間問題的區(qū)別，以及對多目標同時進行優(yōu)化的特點，本文將禁忌搜索的思想與析取圖特點相結合，提出變鄰域禁忌搜索算法，設計4種基于析取圖的鄰域算子，能夠適應本問題特點，有效避免迂回搜索，實現(xiàn)全局優(yōu)化。

2.1 初始可行解

(1)初始解生成

用3個序列分別表示軌道門吊、集卡和場吊的作業(yè)分配和順序，各軌道門吊和場吊規(guī)定作業(yè)區(qū)域內(nèi)負責的任務集已知，只需對其作業(yè)執(zhí)行順序進行決策。在本文研究場景下，設備之間需要密切配合，且各作業(yè)之間存在作業(yè)執(zhí)行順序優(yōu)先級約束，若采用隨機方法生成初始解，會產(chǎn)生大量不可行解，故以軌道門吊為核心設備生成初始作業(yè)序列，再通過啟發(fā)式規(guī)則依次確定場吊和集卡的作業(yè)序列，可避免任務矛盾或沖突的情形，6個集裝箱初始解生成示例見圖3。

圖3 初始解生成步驟

初始解生成步驟為

Step1根據(jù)軌道門吊g的已知任務分配，對其負責的出口任務i∈Jg∩U隨機生成部分作業(yè)序列，共計m1個部分序列。

Step2對各軌道門吊剩余進口任務i′∈Jg∩L按照執(zhí)行順序優(yōu)先級(i,i′)∈Φ依次隨機選擇符合要求的位置執(zhí)行插入操作，形成軌道門吊完整作業(yè)序列βg。

Step3根據(jù)各軌道門吊作業(yè)序列βg中任務順序及箱區(qū)依次確定各場吊作業(yè)序列γy，若屬于同一場吊的任務i,i′∈Jy對應不同軌道門吊的作業(yè)序號相同，則進行隨機排序，對于不滿足作業(yè)執(zhí)行順序優(yōu)先級(i,i′)∈Ψ要求的任務組進行位置交換操作，若此任務組對應的軌道門吊相同i,i′∈Jg，則同時交換其軌道門吊作業(yè)位置。

Step4根據(jù)軌道門吊作業(yè)序列βg和場吊作業(yè)序列γy依次將任務分配給集卡，生成集卡作業(yè)序列ωk。

(2)構建析取圖(Disjunctive Graph)

圖4 6個集裝箱任務析取圖示例

2.2 鄰域算子2.2.1 構建鄰域

在關鍵路徑上進行鄰域操作，即調(diào)整當前最晚結束作業(yè)的任務路徑，能夠更容易改變最優(yōu)解，并且減小問題搜索空間，提高算法尋優(yōu)效率。在本問題中，各階段設備作業(yè)序列之間具有較強的關聯(lián)性，以軌道門吊為核心設備，對其作業(yè)序列采用4種鄰域結構生成候選解，即通過調(diào)整設備作業(yè)任務的執(zhí)行順序改變?nèi)蝿臻g接續(xù)時間，從而優(yōu)化最晚完工時刻。

(1)移動操作

①隨機選擇某設備關鍵塊(作業(yè)序列片段)的某個任務，將其移動至該片段其他任意位置。4種鄰域結構示例見圖5，原關鍵路徑a—abcd—d經(jīng)操作后變?yōu)閍—acbd—d。

②隨機選擇某設備關鍵塊(作業(yè)序列片段)的某個任務，將其移動至同一設備非關鍵路徑(其他作業(yè)片段)某一位置。如圖5所示，原關鍵路徑a—abcd—d經(jīng)操作后變?yōu)閍—abd—d。

圖5 4種鄰域結構示例

(2)交換操作

①隨機交換某設備關鍵塊(作業(yè)序列片段)內(nèi)任意兩個任務。如圖5所示，原關鍵路徑a—abcd—d經(jīng)操作后變?yōu)閍—adcb—d。

②隨機選擇某設備關鍵塊(作業(yè)序列片段)內(nèi)的某個任務，將該任務與同一設備其他作業(yè)片段上的隨機一項任務進行作業(yè)順序交換。如圖5所示，原關鍵路徑a—abcd—d經(jīng)操作后變?yōu)閍—abed—d。

針對以上鄰域操作，可進一步確定新的集卡和場吊作業(yè)序列，刪除圖G中對應任務連接的全部析取弧，重新構建圖G′沒有環(huán)路且滿足作業(yè)順序優(yōu)先級約束則操作成功，否則重新執(zhí)行鄰域操作。根據(jù)新析取圖計算候選解的評價值。

2.2.2 選擇策略

本文采用第一個改進解優(yōu)先策略(First Improved Strategy)進行下一次迭代基礎解的選擇，即依次對候選解進行估值，當產(chǎn)生第一個改進解時，即目標函數(shù)優(yōu)于當前內(nèi)部迭代基礎解時，則選擇該改進解為本次搜索的最優(yōu)解進入下一次迭代，在禁忌表中記錄解的移動。若候選解數(shù)量達到候選集合長度，則選擇當前候選集合中的最優(yōu)解作為下一次迭代的開始。

2.3 禁忌表

(1)禁忌對象

禁忌對象需要有效表示鄰解的產(chǎn)生過程，且不能過于復雜。對于移動操作，以(i,m,a,b)記錄一次動作，表示將任務i從設備m的a位置移動到b位置；對于交換操作，以(m,i,i′) 記錄一次動作，與(m,i′,i)意義相同，即交換設備m的任務i與任務i′。對于每個周期的最優(yōu)動作，依次將其加入禁忌表，當禁忌表滿足長度要求時，則按照先進先出規(guī)則(FIFO)更新禁忌表，即刪除最先進入隊列的禁忌對象，再在隊尾加入新產(chǎn)生的禁忌對象。

(2)禁忌長度

禁忌表的長度用來限制每個移動禁止出現(xiàn)的周期，長度過小會導致搜索陷入循環(huán)；反之，長度過大則會過度限制搜索空間，故本文采用動態(tài)禁忌長度來解決這個問題，禁忌長度即為當前鄰域搜索開始時關鍵路徑長度的一半。

(3)特赦準則

當某個禁忌對象重復出現(xiàn)時，若該移動產(chǎn)生的新解優(yōu)于歷史最優(yōu)解，則滿足特赦準則，接受該解，并將該對象從禁忌表當前位置移動到隊尾。

算法總體流程見圖6。

圖6 算法總體流程圖

3 模擬計算與結果分析

3.1 參數(shù)設置

本文港口鐵路作業(yè)區(qū)有1條集卡走行線、2條裝卸作業(yè)線，配置3臺軌道門吊，堆場進口箱區(qū)和出口箱區(qū)分別配置2臺場吊，由集卡負責各區(qū)域間的銜接。根據(jù)港口運營相關數(shù)據(jù)，算例中相關軌道門吊、集卡、場吊等關鍵技術參數(shù)取值見表2。集裝箱堆碼位置已知，任務間距離按照各坐標數(shù)值差絕對值之和計算。本文模型和算法通過Inter(R) Core(TM) i7-10875H處理器，PyCharm 2017.3.2編程實現(xiàn)。

表2 參數(shù)設置

3.2 小算例結果

通過20個集裝箱任務對算例計算結果進行展示，其中10個進口箱，10個出口箱，集裝箱任務見表3，其中L1-x為集裝箱在鐵路作業(yè)區(qū)卸箱作業(yè)線位置；(x,y)為卸箱的堆存位置坐標，x為排編號，y為列編號。

表3 集裝箱任務信息

20個集裝箱任務作業(yè)計劃的結果見圖7，由圖7可知，每一個任務都經(jīng)過了3道作業(yè)流程，出口箱由軌道門吊卸下后經(jīng)集卡運送至出口箱區(qū)，再由場吊進行堆存作業(yè)；進口箱由場吊取出后經(jīng)集卡運送至鐵路作業(yè)區(qū)，再由軌道門吊進行裝車作業(yè)。采用混合裝卸模式時，即進口箱與出口箱交替作業(yè)，提高了軌道門吊的設備利用率，且集卡在完成當前任務的運輸后，不用返回原作業(yè)區(qū)，能夠有效減少集卡的空駛距離，提高集裝箱轉運效率。對于進口箱區(qū)場吊，不用等待列車全部卸空即可開始作業(yè)，有助于縮短總作業(yè)完成時刻。算例結果表明，本文提出的算法可以有效得到3種設備協(xié)同調(diào)度作業(yè)方案，避免任務沖突的同時提高作業(yè)效率，為場站實際運營提供參考。

圖7 小算例作業(yè)流程

3.3 裝卸模式對比實驗

通過算例對比先卸后裝模式及混合裝卸模式。算例涉及60個任務，其中30個進口箱，30個出口箱，3臺軌道門吊，4臺場吊，6輛集卡。若采用先卸后裝模式，則軌道門吊需完成全部卸車任務后方可進行裝車作業(yè)，若采用混合裝卸模式，則軌道門吊可直接對空車廂進行裝車作業(yè)。兩種模式作業(yè)方案結果見表4。

表4 裝卸模式對比實驗結果 s

若采用先卸后裝模式，則軌道門吊必須先完成全部卸車作業(yè)，即先進行出口箱的卸車—水平運輸—出口箱區(qū)堆存作業(yè)，此時所有集卡在鐵路作業(yè)區(qū)和出口箱區(qū)之間周轉，產(chǎn)生較多空駛距離，且進口箱區(qū)場吊開始時處于空置狀態(tài)，直至全部卸車作業(yè)完成，集卡再前往進口箱區(qū)，將進口集裝箱運送至鐵路作業(yè)區(qū)再空駛返回進口箱區(qū)取下一個集裝箱，此種模式會使集卡產(chǎn)生較多空駛距離，從而導致任務接續(xù)時間較長，影響總完工時刻。而在混合裝卸模式下，某一出口箱卸下后即可進行對應位置的裝箱作業(yè)，此時鐵路作業(yè)區(qū)軌道門吊和進口箱區(qū)場吊可同步作業(yè)，在鐵路作業(yè)區(qū)的集卡取完出口箱后送往出口箱區(qū)，再直接前往進口箱區(qū)取進口任務箱，然后送往鐵路作業(yè)區(qū)進行裝車作業(yè)，有效減少了空駛距離。由表4可知，先卸后裝模式下作業(yè)完工時間10次平均值為6 522.3 s，混合裝卸模式下作業(yè)完工時刻10次平均值為4 551.5 s，效率提升了30.2%；設備空駛時間10次平均值則分別為12 231.1、5 955.6 s。綜上所述，混合裝卸模式即進口箱和出口箱進行交替作業(yè)時能夠有效縮短作業(yè)完工時刻和設備空駛時間，有助于提高鐵水聯(lián)運集裝箱裝卸、轉運作業(yè)效率和設備利用率。

進一步，對兩種裝卸模式下設備空駛時間的具體組成進行對比分析，結果見圖8。設備空駛時間分別由軌道門吊空駛時間、集卡空駛時間和場吊空駛時間組成，由圖8可知，集卡空駛時間在兩種裝卸模式下變化最大，說明集卡的重空銜接作業(yè)是影響整個作業(yè)過程效率的主要因素。在混合裝卸模式下，場吊的空駛時間相比于先卸后裝模式變化較小，軌道門吊空駛距離則有所減少，集卡空駛時間明顯減少，此時集卡完成當前任務后無需返回原先作業(yè)區(qū)，而是直接等待當前區(qū)域待提取集裝箱，能夠有效提高集卡利用率，從而提高鐵水聯(lián)運作業(yè)效率。

圖8 不同裝卸模式下設備空駛時間

3.4 關鍵因素分析

首先采用一組大規(guī)模算例來測試本文提出的算法效率，共涉及200個任務，其中100個進口箱，100個出口箱，3臺軌道門吊，4臺場吊，8輛集卡。目標函數(shù)由兩部分組成，相互具有一定的制約關系。在優(yōu)先保證集裝箱裝卸作業(yè)效率的基礎上，同時考慮兩者的量級關系，通過模擬實驗將后續(xù)實驗中目標函數(shù)比例系數(shù)定為α1=0.8,α2=0.2。通過提出的變鄰域禁忌搜索算法對一定時間周期內(nèi)軌道門吊-集卡-場吊聯(lián)合作業(yè)調(diào)度計劃進行決策，從目標函數(shù)值、作業(yè)完工時刻、設備空駛時間和計算時間四個方面描述10次實驗，結果見表5。

表5 大規(guī)模算例實驗結果

10次實驗結果表明本文提出的算法表現(xiàn)良好，能在較短時間內(nèi)能取得理想結果，目標函數(shù)值、作業(yè)完工時刻、設備空駛時間3項最優(yōu)解與平均值的GAP值分別為3.7%、4.6%和3.2%。由表5可知，當總目標函數(shù)值最小時，作業(yè)完工時刻和設備空駛時間并不同時最優(yōu)，即在可能出現(xiàn)等待下一任務銜接的情景時，設備會優(yōu)先選擇距離較遠的可立即執(zhí)行任務。此時設備空駛時間增加，而總作業(yè)完工時刻變少。相反，若要減少設備空駛時間，則當某項設備進度較快時，可能引起等待時間的增加，從而延長總作業(yè)完工時刻。因此，在實際作業(yè)中，可以根據(jù)場站作業(yè)效率及空駛成本的要求，選擇合適的比例系數(shù)。

設備的數(shù)量配置會對設備協(xié)同調(diào)度作業(yè)的效率產(chǎn)生影響，若某類設備不足，則可能造成其他環(huán)節(jié)設備作業(yè)能力冗余，從而產(chǎn)生空置時間。另外，若設備發(fā)生故障問題，則也會影響可用設備數(shù)量。本文以軌道門吊為核心作業(yè)資源，量化分析其數(shù)量變化對作業(yè)完成時刻、設備空駛時間、設備平均空置時間等產(chǎn)生的影響，結果見表6。

表6 軌道門吊設備數(shù)量靈敏度分析

由表6可知，軌道門吊數(shù)量的減少會使作業(yè)完成時刻增加，設備空駛時間增加，設備平均空置時間有所下降，其原因在于軌道門吊數(shù)量變少，則其余軌道門吊需要負責的作業(yè)區(qū)域變大，使得其空駛距離增加，此外，鐵路作業(yè)區(qū)作業(yè)效率下降也會導致集卡的等待時間增加，影響其周轉效率，最終導致總作業(yè)完工時刻延長。反之，增加軌道門吊的數(shù)量，總作業(yè)完成時刻有所提前，設備空駛距離減少，然而軌道門吊作業(yè)能力富余，使得其空置時間增加，可進一步考慮增加集卡的數(shù)量來滿足鐵路作業(yè)區(qū)的需求。綜上，在實際作業(yè)中，可根據(jù)具體的設備使用成本以及作業(yè)完成時刻要求對設備配置方案進行決策。

4 結論

本文主要對鐵路裝卸線入港背景下聯(lián)運港口鐵路作業(yè)區(qū)與堆場的協(xié)同作業(yè)方法進行研究，考慮作業(yè)過程中涉及的軌道門吊、集卡、場吊3種設備的相互配合，首先對裝卸設備的作業(yè)序列進行決策，在此基礎上進一步確定集卡在各作業(yè)區(qū)間的銜接方案。此外，本文基于軌道門吊混合裝卸作業(yè)模式，建立集裝箱作業(yè)順序優(yōu)先級約束，增加了問題的復雜性。最后，本文通過一組60個任務的算例對比分析了不同裝卸模式的作業(yè)效率，通過涉及200個任務的大規(guī)模算例驗證了變鄰域禁忌算法的高效性，分析了不同軌道門吊數(shù)量對最晚完工時刻、設備空駛時間、設備平均空置時間等關鍵指標的敏感性，并提出提高設備作業(yè)效率的相關建議。實驗結果表明，混合裝卸模式能夠有效縮短作業(yè)完工時刻和設備空駛時間，且算法能在較短時間內(nèi)求得較優(yōu)解，GAP值不超過4.6%。

在實際作業(yè)中，可能出現(xiàn)設備故障等突發(fā)問題，針對此類情況，可以通過調(diào)整模型的輸入如設備數(shù)量、作業(yè)范圍等參數(shù)，利用本文提出的方法重新生成新的作業(yè)計劃來應對。此外，也可考慮實際作業(yè)過程中的不確定風險，未來進一步研究設備協(xié)同作業(yè)調(diào)度魯棒優(yōu)化及重調(diào)度作業(yè)優(yōu)化等問題。