鐵路集裝箱中心站多軌道吊柔性協(xié)同調(diào)度優(yōu)化

周勇，張杰，鐘祾充，李文鋒，王國棟

(1.武漢理工大學(xué)，交通與物流工程學(xué)院，武漢430063；2.遼寧港口集團有限公司，專業(yè)能力中心，遼寧大連116001)

0 引言

鐵路集裝箱中心站(簡稱“中心站”)是集裝箱多式聯(lián)運的重要節(jié)點，中心站軌道吊承擔(dān)著進出站列車的絕大部分裝卸作業(yè)，其運作效率對整個多式聯(lián)運系統(tǒng)的作業(yè)效率有著重要影響。多軌道吊協(xié)同調(diào)度主要指根據(jù)裝卸調(diào)度模式和作業(yè)規(guī)則確定軌道吊的裝卸作業(yè)序列，使軌道吊的總完工時間最小，提高鐵路中心站的生產(chǎn)運營效率。

國內(nèi)外學(xué)者針對鐵路中心站軌道吊協(xié)同裝卸調(diào)度(Rail Mounted Gantry Crane Collaborative Scheduling，RMGCS)問題做了諸多研究，根據(jù)軌道吊作業(yè)區(qū)域的限定，可以將其裝卸調(diào)度模式分為固定范圍和柔性范圍。固定范圍裝卸調(diào)度模式研究方面：王力等[1]通過劃分軌道吊的作業(yè)區(qū)域避免多軌道吊之間的作業(yè)沖突；HE等[2]將固定范圍內(nèi)軌道吊調(diào)度問題轉(zhuǎn)換成路徑規(guī)劃問題以及軟時間窗約束問題；KRESS等[3]將多軌道吊的調(diào)度優(yōu)化問題分解為集裝箱任務(wù)分配問題和軌道吊作業(yè)區(qū)域動態(tài)劃分問題；陳雷雷等[4]建立了固定范圍模式下單軌道吊多類型任務(wù)復(fù)合作業(yè)下的整數(shù)規(guī)劃調(diào)度模型；OTTO等[5]將多軌道吊調(diào)度問題分解為單軌道吊的作業(yè)序列規(guī)劃問題。柔性范圍裝卸調(diào)度模式研究方面：劉勇等[6]將中心站軌道吊配置問題劃分為軌道吊柔性調(diào)度問題和數(shù)量優(yōu)化配置問題，設(shè)計了基于使用權(quán)分配的遺傳算法進行求解；王力[7]建立了考慮多軌道吊間非交叉和安全距離約束的柔性范圍裝卸混合調(diào)度優(yōu)化模型，使用遺傳算法求解模型并和固定裝卸范圍下的調(diào)度模型進行對比；常祎妹等[8]在建立鐵水聯(lián)運混合整數(shù)規(guī)劃模型中考慮了多龍門吊間的干擾和安全距離的現(xiàn)實約束。

綜上所述，固定范圍裝卸調(diào)度模式通過劃分靜態(tài)或動態(tài)的軌道吊固定作業(yè)區(qū)域來避免軌道吊間可能產(chǎn)生的作業(yè)沖突問題，但是同時也增加了各軌道吊的空閑時間，降低了利用率。柔性范圍裝卸調(diào)度模式則可以滿足靈活的任務(wù)分配需求，每臺軌道吊均可得到充分利用，獲得更高的作業(yè)效率和負荷均衡率。然而，柔性范圍協(xié)同調(diào)度問題可能存在因安全距離和多軌道吊間干涉約束導(dǎo)致的軌道吊相互避讓現(xiàn)象，如何判斷軌道吊間的干涉，從而減少避讓產(chǎn)生的等待時間，也是需要解決的問題。因此，本文針對柔性范圍協(xié)同調(diào)度問題，基于軌道吊的連續(xù)運行模式，提出同時考慮作業(yè)干涉約束和安全距離約束的多軌道吊柔性協(xié)同裝卸調(diào)度策略。

麻雀搜索算法(Sparrow Search Algorithm，SSA)是XUE[9]提出的一種新型群智能優(yōu)化算法，具有自組織性好、前期收斂速度快等優(yōu)點，但易陷入局部最優(yōu)。一些研究對該算法進行改進，例如，文獻[10]和文獻[11]等。這些改進雖然提高了算法跳出局部最優(yōu)的能力，但是仍存在發(fā)現(xiàn)者的安全值適應(yīng)度不足，加入者的局部搜索精度差等缺點。本文針對RMGCS 問題，提出一種改進的麻雀搜索算法(Improved Sparrow Search Algorithm，ISSA)，該算法利用自適應(yīng)步長因子非線性動態(tài)遞減更新發(fā)現(xiàn)者安全值，通過修改加入者向最優(yōu)位置的移動方式提高搜索精度，從整體上降低算法計算復(fù)雜度，最后，采用LOV 規(guī)則將麻雀個體從實數(shù)向量轉(zhuǎn)換成集裝箱作業(yè)序列，快速、高效地實現(xiàn)求解RMGCS 問題，并與常用的群智能優(yōu)化算法進行了對比研究。

1 問題描述與建模

1.1 問題描述

以大連鐵路集裝箱中心站為例，其主作業(yè)區(qū)包括：兩條鐵路裝卸線、堆場、集卡通道、3臺軌道吊和若干集卡等。本文以列車集裝箱裝卸作業(yè)為研究對象，針對RMGCS 問題，基于軌道吊連續(xù)運行模式，采用多作業(yè)線柔性范圍裝卸混合調(diào)度模式進行研究。其中，由于采取的是柔性范圍調(diào)度模式，即未限定各軌道吊的作業(yè)區(qū)域，各軌道吊在作業(yè)期間可能出現(xiàn)相互干涉，因此，需要在數(shù)學(xué)模型中設(shè)置安全作業(yè)距離約束來保證各軌道吊不會出現(xiàn)干涉甚至交叉現(xiàn)象。為清晰闡述所研究問題，對列車、軌道吊、堆場進行編號，方法如下：

(1)沿鐵路裝卸線，將列車車頭至車尾方向定義為正方向，依次對車廂和堆場列位編號。

(2)以垂直并遠離鐵路裝卸線的方向定義為正方向，依次對堆場排位編號。

(3)沿列車車頭至車尾方向依序?qū)壍赖蹙幪枴?/p>

根據(jù)上述規(guī)定，中心站多軌道吊作業(yè)場景編號具體如圖1所示，其中，m為堆場總排位數(shù)，u為堆場總列位數(shù)。

圖1 中心站主堆場編號示意Fig.1 Numbering diagram of main yard in railway container terminal

1.2 模型假設(shè)

建立的中心站多軌道吊調(diào)度優(yōu)化模型遵照以下假設(shè)：

(1)集裝箱箱型一致，均為40 ft；

(2)集裝箱裝卸計劃已知；

(3)軌道吊的平均速度已知；

(4)每個集裝箱的裝卸視為1個任務(wù)；

(5)相鄰軌道吊的安全距離設(shè)為4個貝位；

(6)軌道吊為連續(xù)運行模式，即正常情況下軌道吊作業(yè)不暫停。

1.3 模型的構(gòu)建

模型同時考慮軌道吊大車和小車的移動，模型所涉及的符號和說明如表1所示。

表1 模型中的符號和說明Table 1 Symbols and descriptions in model

(1)目標函數(shù)

本文以總完工時間為性能指標，目標函數(shù)為

(2)約束條件

式(2)表示各軌道吊裝卸任務(wù)的總量等于集裝箱的總箱量；式(3)表示進行裝卸任務(wù)的軌道吊數(shù)量約束，每1 集裝箱僅由1 臺軌道吊完成；式(4)和式(5)表示每臺軌道吊進行集裝箱裝卸作業(yè)的前、后作業(yè)約束，式(4)表示每1個集裝箱至多有1個緊前任務(wù)，式(5)表示每1個集裝箱至多有1個緊后任務(wù)；式(6)表示每臺軌道吊完成單個集裝箱的時長約束；式(7)表示每個軌道吊兩個連續(xù)作業(yè)間的時間關(guān)系約束；式(8)表示所有集裝箱任務(wù)只被分配1 次；式(9)表示軌道吊之間的安全作業(yè)距離約束，表示在柔性調(diào)度過程中，各軌道吊在作業(yè)總完工時間內(nèi)的任意時刻兩相鄰軌道吊之間的距離必須大于安全距離，同時，滿足此條件又可以保證各軌道吊之間不會出現(xiàn)交叉，即滿足軌道吊間的非交叉作業(yè)約束。

本文構(gòu)建數(shù)學(xué)模型的思路與文獻[7]類似，目標函數(shù)都是集裝箱任務(wù)總完工時間，但在約束條件設(shè)置過程中有所區(qū)別。文獻[7]對軌道吊大車和小車采用的是相同的平均運行速度，本文依據(jù)實際情況，區(qū)別了軌道吊大車和小車的平均運行速度，同時，分別計算軌道吊大車和小車的運行時間后，取較大值作為執(zhí)行單個任務(wù)或空走過程的運行時間。此外，文獻[7]將安全距離約束設(shè)置為：在裝卸集裝箱時，需保證編號較大的軌道吊所操作的集裝箱的起始和終止貝位都大于編號較小的軌道吊所操作的集裝箱的起始和終止貝位。而本文的安全距離約束條件式(9)設(shè)置為：保證相同時刻下相鄰軌道吊間保持安全距離即可，保留了獲取更多滿足安全距離約束的調(diào)度方案的可能性。同時，本文將非交叉作業(yè)約束蘊含到安全距離約束中，而文獻[7]區(qū)分兩個約束。

2 算法設(shè)計與模型求解

2.1 麻雀搜索算法的改進

麻雀搜索算法是基于麻雀群聚尋找食物并躲避捕食者行為的啟發(fā)而提出的一種群智能優(yōu)化算法。SSA主要依據(jù)發(fā)現(xiàn)者、加入者和偵察者各自的更新規(guī)則更新位置，適應(yīng)度值高的麻雀被選擇為發(fā)現(xiàn)者，麻雀種群中除發(fā)現(xiàn)者外其余為加入者，部分比例的麻雀會充當(dāng)偵察者的角色，SSA算法基本原理和位置更新規(guī)則參見文獻[9]。本節(jié)針對中心站RMGCS問題的特點，改進麻雀搜索算法，提高算法的尋優(yōu)性能，并完成其離散化，使其能夠應(yīng)用于求解RMGCS問題。

2.1.1 發(fā)現(xiàn)者更新公式的改進

根據(jù)發(fā)現(xiàn)者位置更新規(guī)則，安全值Sv為一定值，當(dāng)警示值R2

因此，本文采取安全值Sv非線性動態(tài)遞減的策略替換SSA中固定Sv的方式[12]，從而動態(tài)調(diào)整全局和局部搜索性能。安全值的更新方式為

式中：g為當(dāng)前迭代次數(shù)；gmax為最大迭代次數(shù)；Sv、Svmax、Svmin分別為安全值、安全值最大值和安全值最小值。安全值Sv遞減曲線如圖2所示。

圖2 安全值Sv 遞減曲線Fig.2 Safety value decreasing curve

由圖2 可知，Sv非線性動態(tài)遞減策略使得Sv在整個迭代過程中呈現(xiàn)一個倒S型的遞減趨勢，迭代開始時，Sv能在較長時間取值較大，保證大多數(shù)麻雀處于非危險狀態(tài)，便于在全局尋找到更好的覓食位置；迭代后期，種群局部聚集，較小的Sv可增加麻雀采取反捕食行為的概率，提高局部搜索的精度。

2.1.2 加入者更新公式的改進

為減少向原點的收斂趨勢，使加入者麻雀在全維度上向所跟隨的發(fā)現(xiàn)者靠攏，因此，刪除加入者時向原點收斂的迭代步驟，同時，簡化時的位置更新方式，修改后的加入者位置更新公式為

2.1.3 麻雀搜索算法的離散化

SSA 的連續(xù)性特點導(dǎo)致其不能解決離散的RMGCS 問題，因此，本文基于LOV 規(guī)則[13]完成迭代過程中產(chǎn)生的非整數(shù)麻雀個體向集裝箱裝卸任務(wù)整數(shù)作業(yè)序列的映射。

式中：δp,q為第p個麻雀降序排列后獲得的序列在第q維上的位置；πp,q為第p個麻雀經(jīng)LOV規(guī)則變換后在第q維上的位置。

2.2 編碼設(shè)計

采用整數(shù)順序編碼，每只麻雀表示1組D個集裝箱編號組成的序列，位置公式為

式中：D為軌道吊裝卸任務(wù)包含的集裝箱個數(shù)；xp,q為第p個麻雀個體第q維上的集裝箱的編號。

2.3 適應(yīng)度函數(shù)

麻雀個體的適應(yīng)度函數(shù)Ff表示各軌道吊完成所有任務(wù)的總完工時間，以0時刻作為任務(wù)開始時間，計算式為

2.4 軌道吊任務(wù)分配策略

由于采取的是柔性范圍裝卸調(diào)度模式，未限定各軌道吊的作業(yè)區(qū)域，即未提前分配好各軌道吊需要執(zhí)行的集裝箱任務(wù)，同時，根據(jù)本文的編碼方式，算法求解是對包含所有集裝箱任務(wù)的作業(yè)序列進行迭代尋優(yōu)，因此，進行作業(yè)序列求解的前提是根據(jù)集裝箱作業(yè)序列和設(shè)定的任務(wù)分配策略依次將各個集裝箱任務(wù)分配給各軌道吊。

任務(wù)分配過程是體現(xiàn)多軌道吊柔性協(xié)同調(diào)度優(yōu)化的關(guān)鍵步驟，因此，為更清楚地描述多軌道吊的任務(wù)分配過程，提前給出設(shè)計的符號和說明，如表2所示。

表2 任務(wù)分配中的符號和說明Table 2 Symbols and instructions in task assignment

根據(jù)產(chǎn)生的軌道吊作業(yè)序列，按如下流程將作業(yè)任務(wù)序列分配給各軌道吊：

Step 1 輸入作業(yè)序列，轉(zhuǎn)到Step 3。

Step 2 隨機更新作業(yè)序列，轉(zhuǎn)到Step 3。

Step 3 根據(jù)作業(yè)序列判斷當(dāng)前任務(wù)i是否為最后一項任務(wù)，若是，則退出分配；如果不是，讀取當(dāng)前任務(wù)的位置信息，并轉(zhuǎn)到Step 4。

Step 4 判斷當(dāng)前任務(wù)i的Ps,i是否在之前，若不是，轉(zhuǎn)到Step 5；若是，則把當(dāng)前任務(wù)i分配給軌道吊1，進行干涉判斷。若不干涉，轉(zhuǎn)到Step 8；若干涉，轉(zhuǎn)到Step 2。

Step 5 判斷當(dāng)前任務(wù)i的Ps,i是否在和之間，若不是，轉(zhuǎn)到Step 6；若是，則把當(dāng)前任務(wù)i分配給和中較小的軌道吊，進行干涉判斷。若不干涉，轉(zhuǎn)到Step 8；若干涉，則分給另一軌道吊，進行干涉判斷(若不干涉，轉(zhuǎn)到Step 8；若干涉，轉(zhuǎn)到Step 2)。

Step 6 判斷當(dāng)前任務(wù)i的Ps,i是否在和之間，若不是，轉(zhuǎn)到Step 7；若是，則把當(dāng)前任務(wù)i分配給和中較小的軌道吊，進行干涉判斷。若不干涉，轉(zhuǎn)到Step 8；若干涉，則分給另一軌道吊，進行干涉判斷(若不干涉，轉(zhuǎn)到Step 8；若干涉，轉(zhuǎn)到Step 2)。

Step 7 把當(dāng)前任務(wù)i分配給軌道吊3，進行干涉判斷。若不干涉，轉(zhuǎn)到Step 8；若干涉，轉(zhuǎn)到Step 2。

Step 8 更新該軌道吊的時間和位置信息，查詢下一任務(wù)序號，轉(zhuǎn)到Step 3。

2.5 軌道吊干涉判斷

在多軌道吊柔性協(xié)同調(diào)度優(yōu)化中，如何判斷在任務(wù)分配過程中被分配任務(wù)的軌道吊在執(zhí)行任務(wù)時是否滿足數(shù)學(xué)模型中設(shè)置的軌道吊間的安全作業(yè)距離約束是一個關(guān)鍵要點。

在進行軌道吊間的干涉判斷過程中，為避免因比較每時刻3 臺軌道吊之間的位置而產(chǎn)生的較大計算量，此處設(shè)定僅需比較執(zhí)行任務(wù)i過程中，軌道吊大車、小車達到初始位置和目標位置時4個時刻3 臺軌道吊之間的距離是否小于安全距離作為干涉判斷標準。

以1 個實例進行描述，假設(shè)把第i個任務(wù)分配給軌道吊2，本文軌道吊運行是建立在連續(xù)運行模式之上，因此，可以獲得如下數(shù)據(jù)：為當(dāng)前任務(wù)i的開始時刻；分別為軌道吊2 大車、小車到達當(dāng)前任務(wù)i初始位置的時刻；分別為軌道吊2 大車、小車到達當(dāng)前任務(wù)i目標位置的時刻。

圖3 各軌道吊大車在執(zhí)行任務(wù)過程中的位置Fig.3 Location of each RMG during task

2.6 解碼設(shè)計

解碼以一個樣本量為12 的裝卸算例作為示例。

(1)輸入集裝箱作業(yè)序列Xi=[10,6,1,3,5,9,7,11,2,12,8,4]。

(2)根據(jù)任務(wù)分配方式，獲得每個集裝箱分配到的軌道吊的編號，如圖4所示。

圖4 集裝箱作業(yè)序列與軌道吊對應(yīng)圖Fig.4 Corresponding diagram of container operation sequence and RMG

(3)計算每個集裝箱的完工時間，即

(4)輸出集裝箱作業(yè)順序和各集裝箱匹配的軌道吊，即軌道吊1作業(yè)順序為[1,3,2,4]，軌道吊2作業(yè)順序為[6,5,7,8]，軌道吊3 作業(yè)順序為[10,9,11,12]。

2.7 ISSA算法求解步驟

基于ISSA求解多軌道吊調(diào)度優(yōu)化問題的主要步驟如下：

Step 1 設(shè)置麻雀種群規(guī)模Mn，發(fā)現(xiàn)者占比Pn等參數(shù)。

Step 2 在搜索空間內(nèi)，隨機產(chǎn)生初始麻雀種群。

Step 3 根據(jù)麻雀種群中各麻雀個體的作業(yè)序列進行任務(wù)分配。

Step 4 計算每只麻雀的適應(yīng)度值，選出并記錄當(dāng)前最佳適應(yīng)度值及其對應(yīng)麻雀個體，以及當(dāng)前最差適應(yīng)度值及其對應(yīng)麻雀個體。

Step 5 根據(jù)發(fā)現(xiàn)者更新規(guī)則更新發(fā)現(xiàn)者序列，并依據(jù)LOV規(guī)則進行離散化。

Step 6 根據(jù)加入者更新規(guī)則更新加入者序列，并依據(jù)LOV規(guī)則進行離散化。

Step 7 根據(jù)偵察者更新規(guī)則更新偵察者序列，并依據(jù)LOV規(guī)則進行離散化。

Step 8 判斷迭代次數(shù)是否滿足終止條件，滿足則輸出最優(yōu)麻雀個體，結(jié)束算法；否則，轉(zhuǎn)到Step 3進行下一次迭代。

ISSA求解RNGCS問題流程如圖5所示。

圖5 ISSA求解RMGCS問題流程Fig.5 Process of RMGCS problem solved by ISSA

3 算例分析

為驗證ISSA算法求解考慮作業(yè)干涉約束和安全距離約束的RMGCS 問題的有效性，分別使用SSA、ISSA、標準粒子群算法(PSO)和遺傳算法(GA)求解4 種樣本量的裝卸作業(yè)算例。各算法均采用Matlab 編程，操作系統(tǒng)為Win10，處理器為Intel(R)Core(TM)i5-4210@1.70 GHz，內(nèi)存為4 GB。

為保證各算法求解效果的可靠性，選取多組裝卸作業(yè)算例，以大連鐵路集裝箱中心站的軌道吊運行數(shù)據(jù)進行計算求解，其中，軌道吊大車平均運行速度vb=120 m?min-1，小車平均運行速度vs=90 m?min-1；所有算法的種群規(guī)模均為100，迭代1000次，進行各算法的算法參數(shù)的獨立仿真，最終選定如下參數(shù)：SSA 和ISSA 發(fā)現(xiàn)者占比為0.4；偵察者占比為0.2；SSA 安全值Sv=0.8；ISSA 安全值最大值Svmax=0.9，安全值最小值Svmin=0.4；GA交叉概率為0.8，變異概率為0.2；PSO 個體學(xué)習(xí)因子為0.2，群體學(xué)習(xí)因子為0.1。

本文采用上述的各算法設(shè)定參數(shù)，對4種樣本規(guī)模的算例分別進行50 次仿真并取平均值，進行算法性能的比較說明，其中4種樣本規(guī)模的算例包含從30，60，90，120 個集裝箱，即小規(guī)模到大規(guī)模的算例。求解結(jié)果如表3所示，其中，Tavg為平均總完工時間；Ts為平均求解1次需要的時間。

表3 各算法求解結(jié)果Table 3 Results of each algorithm

由表3 可知，隨著樣本規(guī)模的擴大，各算法間的求解性能差異逐漸擴大，總體來說ISSA 針對不同樣本量均有更好的求解性能，同時，迭代前期收斂速度快，相對標準SSA、PSO 和GA 算法適應(yīng)性更強。

選取樣本規(guī)模為45 的裝卸作業(yè)任務(wù)作為算例，具體任務(wù)信息如表4所示。

表4 樣本量為45的裝卸箱作業(yè)任務(wù)Table 4 Loading and unloading task with sample size of 45

運用本文提出的ISSA算法對算例進行50次仿真，將運算結(jié)果與CM裝卸調(diào)度模式[7](CM，軌道吊固定范圍作業(yè)，順序卸裝)的求解結(jié)果進行比較，結(jié)果如表5所示，其中，Tmax為最大的總完工時間；Tmin為最小的總完工時間；TCM為CM 調(diào)度模式的總完工時間。

通過表5 的比較結(jié)果可知，柔性協(xié)同調(diào)度模式可使裝卸作業(yè)的總完工時間縮短15.5%，大大減少了軌道吊的作業(yè)時間，提高了中心站軌道吊利用率。

表5 ISSA與CM的比較結(jié)果Table 5 Comparison results of ISSA and CM

50 次仿真計算中，獲得的最好一次最優(yōu)解為325.2 s，對應(yīng)的各軌道吊裝卸調(diào)度方案如表6所示，此方案下各軌道吊的大車走行圖如圖6所示。

圖6 最優(yōu)解下軌道吊大車走行圖Fig.6 Traveling diagram of RMG under optimal solution

表6 最優(yōu)作業(yè)序列Table 6 Optimal operation sequence

從圖6 可以看出，各軌道吊在運行過程中，兩兩相鄰的軌道吊之間會始終保持大于安全距離的間隔，保證各軌道吊在正常的裝卸箱作業(yè)時不會出現(xiàn)相互干擾，并且，各軌道吊的負荷均衡率較高，3臺軌道吊的完工時間也基本接近。

4 結(jié)論

(1)針對RMGCS問題，基于軌道吊連續(xù)運行模式，提出了同時考慮作業(yè)干涉約束和安全距離約束的鐵路集裝箱中心站多軌道吊柔性協(xié)同裝卸調(diào)度策略，建立了目標函數(shù)為最小化集裝箱任務(wù)總完工時間的混合整數(shù)規(guī)劃數(shù)學(xué)模型。

(2)結(jié)合RMGCS問題特性，提出了一種改進的麻雀搜索算法，首先，設(shè)計了能夠解決多軌道吊作業(yè)沖突的任務(wù)分配策略和多軌道吊之間的干涉判斷方法；其次，利用自適應(yīng)步長因子的方式非線性動態(tài)遞減更新發(fā)現(xiàn)者安全值，平衡全局搜索和局部搜索；再次，修改加入者向最優(yōu)位置的移動方式，增強了加入者搜尋最優(yōu)位置的能力；最后，采用LOV規(guī)則將麻雀個體從實數(shù)向量轉(zhuǎn)換成集裝箱作業(yè)序列，實現(xiàn)了ISSA 算法對考慮作業(yè)干涉和安全距離約束的RMGCS問題的求解。

(3)選取不同裝卸作業(yè)算例，分別使用ISSA與標準SSA、PSO 和GA 算法求解考慮作業(yè)干涉和安全距離約束的RMGCS問題。結(jié)果表明：所構(gòu)建的模型和算法能夠快速有效求解不同規(guī)模的RMGCS問題，同時縮短集裝箱任務(wù)的總完工時間，提高了軌道吊作業(yè)的均衡性和使用效率。