基于微進化算法的鐵路物流中心集裝箱裝卸資源調度優化

李悅，宋瑞，陳旭超

(北京交通大學 城市交通復雜系統理論與技術教育部重點實驗室，北京 100044)*

0 引言

近幾年，共享經濟的熱潮為我國的物流行業帶來了新的發展思路.在集裝箱港口裝卸資源調度方面，丁一等[1]研究了集裝箱碼頭的實時調度問題，設立主緩沖區以及接力區，使用接力作業減少外集卡和自動引導小車的等待時間；樂美龍等[2]提出了以最大完工時間和作業時間標準差最小化的多目標函數的集裝箱碼頭岸橋作業均衡調度優化問題；秦進等[3]研究了考慮岸橋交叉及安全作業距離約束的多船卸船任務的岸橋調度問題；梁承姬等[4]研究了基于帶時間窗的集裝箱作業任務的場橋調度問題.在鐵路集裝箱中心站裝卸資源調度研究方面；Zeng M等[5]通過結合Simio動態仿真系統模擬鐵路集裝箱中心站的物流系統，改變集裝箱列車到達時間等相關參數進行優化資源配置；Guo等[6]針對鐵路集裝箱場站的軌道門吊的調度問題，提出了一個考慮門吊安全距離、走行時間，門吊交叉等約束的混合整數規劃模型，并使用離散人工蜂群算法對模型進行求解.唐連生等[7]研究了帶有干涉約束的軌道吊調度問題，建立了混合整數規劃模型并提出了一種求解該問題的改進遺傳算法.目前有關集裝箱裝卸調度方面的研究多從集裝箱港口、車站角度出發，目標函數主要為最小化平均裝卸作業時間、最小化門吊最大作業時間，最大化門吊利用率等方面，而較多研究并沒有將物聯網和物流信息共享平臺加入考慮范疇內.

本文以鐵路物流中心集裝箱功能區為研究對象建立了基于物聯網的裝卸資源的調度優化模型，模型以外集卡平均延誤時間最短和軌道門吊最大作業時間最小為目標函數；主要考慮門吊間不能相互跨越、門吊前后序作業時刻等約束.基于該問題的動態性，設計了適用于裝卸資源調度問題的微進化算法對模型進行求解，最后以西安鐵路物流中心為案例背景進行算例分析，驗證模型及算法的有效性.

1 基于物聯網的集裝箱功能區裝卸調度模型

1.1 問題描述

每個需要由外集卡完成取送作業的集裝箱，都帶有一個允許開始作業時刻和預計完成作業時刻的時間窗(由集卡司機提交).基于以上考慮，本文具體研究帶有時間窗的集裝箱裝卸資源調度問題，重點考慮到軌道門吊的最大作業時間和集裝箱外集卡的延誤時間(其中集卡司機的滿意度由延誤時間這個指標來評價)，該延誤時間指的是外集卡集裝箱作業任務的實際完成時刻與其在提交預約申請時獲得的預計完成時刻之間的差值.

選用三維立體坐標圖的形式對集裝箱功能區整個裝卸作業區進行表示，每個箱位對應一個坐標號，包含每個集裝箱裝卸位置對應的行(x軸)、貝位(y軸)和層數(z軸)[8].假設集裝箱列車每節車廂及每輛集卡占用三維立體坐標圖上的一個標準箱位的單元格，如圖1所示.例如，列車裝卸線2行2貝1層的坐標為(2，2，1)，堆場箱區3行1貝2層的集裝箱位置坐標為(5，1，2).

圖1 坐標示意圖

為了便于建立模型進行求解，做以下假設：集裝箱列車進入功能區前，各個集裝箱的堆存位置已知；計劃時段內的每個集裝箱的允許最早開始作業時刻和期望完成作業時刻已知；外集卡按預約時刻準時到達；在裝卸作業過程中，不發生故障；假設列車、集卡停在期望位置；假設軌道門吊大車、小車及吊具均保持勻速運動；不考慮裝卸作業區集卡的擁堵.

1.2 符號定義

本文涉及到的符號定義如表1、表2及表3所示：

表1 集合定義表

表2 模型參數表

表3 決策變量表

1.3 裝卸調度模型構建

F=min(λ1maxTc+λ2minTt)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

其中,式(1)為目標函數，為最小化軌道門吊的最大作業時間與最小化計劃時段內所有外集卡平均延誤時間的加權平均值.式(2)～(8)為約束條件.式(2)確保各軌道門吊的作業箱量的總和與該時段總的作業任務量相同.式(3)確保外集卡的裝卸作業任務的開始時刻應當晚于其在系統上提交的到達作業指定位置的時刻.式(4)確保每一次作業任務只能由一個軌道門吊完成.式(5)確保同一門吊上一個任務完成至移動到下一個任務的起始時刻不大于下一個任務的開始時刻.式(6)和(7)定義作業i和i′的先后順序關系，即Yi,i′的屬性.式(8)保證避免不同軌道吊之間的橫跨干涉作業：假設作業i和i′同時進行操作，且作業順序i

每個軌道門吊針對每一集裝箱任務的作業時間由兩部分組成：一是完成集裝箱任務i的作業時長，二是移動至其后序任務i′的移動時長：

(9)

軌道門吊在兩任務間的移動指的是從第i個集裝任務的終止位置移動至其后序任務i′的起始位置.具體作業流程是軌道門吊大車移動時長：

(10)

軌道門吊c對于集裝箱任務i的從起始位置到終止位置作業的流程可細分為：吊具空載下降、吊具重載提升、大車移動至終止作業貝位、小車移動至終止作業所在行數、吊具重載下降、吊具空載提升.

(11)

外集卡的平均延誤時間Tt為：所有外集卡的實際作業完成時刻與其期望完成時刻之間的差值，當某集裝箱任務提前完成時，該集裝箱任務的延誤時間取0.

(13)

2 微進化算法

選用微進化算法進行模型求解.微觀進化算法(Micro-evolution Algorithm，MEA)是一種基于傳統遺傳算法(GA)改進的算法.當環境信息發生變化時，微進化算法(MEA)中的原始對偶算子(PDM)可以更好地應對動態環境的突變.例如列車晚點或是外集卡司機出現突發情況，提交了一個新的預計到達時刻，使得集裝箱作業任務的允許開始作業時刻及期望完成作業時刻發生變化時，微進化算法可以更加高效地找到新環境下的裝卸調度方案.兩個算法的主要區別在于兩個方面：首先，微觀進化算法是基于基因結構進化設計的，而遺傳算法是基于基因位進化設計的[9- 10].第二，當環境變化時，微進化算子具有更靈活的應變能力.

2.1 編碼方案

本文采用整數編碼的方式，編碼方式如圖2所示：

圖2 染色體編碼方案

根據軌道門吊的分配和各個集裝箱裝卸作業任務的開始時間對染色體進行解碼，圖3，表4分別為一個染色體的編碼與解碼示例，表示由4個軌道門吊完成10個集裝箱裝卸作業任務.

圖3 染色體編碼示例

門吊序號集裝箱裝卸作業任務序號門吊序號集裝箱裝卸作業任務序號11-5-1032-7-423-948-6

2.2 染色體可行性判斷

(1)軌道門吊作業時間可行性判斷：一個軌道門吊不能同時作業于兩個集裝箱任務的約束；

(2)軌道門吊作業位置可行性判斷：不同軌道門吊作業時不能相互跨越.

該軌道門吊檢驗的流程圖如圖4所示：

圖4 軌道門吊作業時間位置可行性判斷流程圖

2.3 優勢基因結構

定義染色體中所有優勢基因的集合為優勢基因集，優勢基因集中全部優勢基因的遺傳信息及其位置信息組成的整體結構即為該個體的優勢基因結構，在微進化算法的交叉操作中，優勢基因結構將被保存到下一代.通常情況下，選取每一代種群中前5%～10%較優染色體，并將其中的相同基因作為優勢基因保存在優勢集中.

圖5 帶優勢基因的染色體示例

2.4 微進化算子

2.4.1 選擇策略

圖6 母本染色體片段

2.4.2 基于結構的交叉算子

(1)母本染色體從種群中隨機選擇.以部分集裝箱任務的調度方案對應的染色體片段為例，由于本文的分段編碼形式改變門吊編號時必須同時改變服務順序，交叉基于單個母本;

(2)如果染色體子代中有優勢基因，一般情況下，他們將會被重新選擇，或是直接處理來保證在交叉操作中這種優勢結構不會被摧毀.首先，對母本染色體中含有的所有基因，隨機選擇基因對，同時對優勢基因對進行保護使其不進行交叉操作；

(3)對母本中優勢基因對的編碼和位置進行判斷.如圖7所示，對同是門吊2服務的集裝箱順序進行交叉替換，交叉時可重復多次；如圖7所示，母本的后半段染色體同是第二順序服務的集裝箱門吊編號進行交叉，交叉可重復多次.

(a) 交叉操作(1)

(b) 交叉操作(2)

(4)調整序列后，最后后代對應以下兩種情況，如圖8所示：

圖8 產生子代的情況

2.4.3 改進的原始對偶(PDM)算子

當環境信息發生變化時，采用原始對偶(PDM)算子使該算法能夠更好地適應環境的突變.受自然界中的互補機制啟發，染色體可以采用原始對偶的方法進行編碼.在種群中已經被編碼的染色體稱為原始對偶(PDM)算子中的原始染色體.在某個距離空間內與原始染色體距離最大的染色體被稱為對偶染色體.

在裝卸資源調度問題中，原始染色體為：

它的對偶染色體為：

2.4.4 變異算子

根據裝卸調度問題的特殊性及本文分段編碼形式，變異不能只改變門吊基因或者集裝箱作業順序，對前半段和后半段基因同時進行變異操作，該種變異對軌道門吊的作業分配和軌道門吊的作業順序都有一定的影響，由于變異是尋求更好的基因對，因此不考慮優勢基因.如圖9所示，若將門吊編號3變為1，則門吊1服務的集裝箱總數增加一個，原來同樣門吊3服務的集裝箱順序則向前遞推.

圖9 變異操作

3 案例分析

本節主要通過案例分析來說明微觀進化算法的求解過程(MEA).本文以西安新筑鐵路綜合物流中心集裝箱裝卸作業區為案例，選取20ft集裝箱作為研究對象，集裝箱箱位相關數據選用文獻[11]中的案例數據.軌道門吊相關參數如表5所示.

表5 軌道門吊相關參數

在微進化算法種群規模為200，集裝箱的數量為分別設置為20、30、40、50和60.母本精英染色體保存比例為1%；染色體交叉率為60%；染色體變異率為4%；優勢基因選擇規則為選擇每一代適應度排名前10%的個體中相同位置出現的比例大于60%的基因作為優勢基因；原始對偶算子中原始染色體的選擇比例為1%；目標函數的權重系數λ1和λ2都設置為0.5.算法的終止條件為達到設定的迭代次數即輸出.

經過測算，當集裝箱的數量為40時，最優目標函數為21.415 925 min，即確定為最終結果.其中軌道門吊最大作業時間為42.157 min，外集卡平均延時為0.674 min.四臺軌道吊的作業時間標準差為2.9 min，表示軌道門吊作業時間相對較均衡；對外集卡取送的集裝箱實際與預計完成時刻進行對比，平均延誤時間小.對50次收斂至最優解的迭代過程進行統計分析，其中收斂速度最快的在第123代收斂至最優，收斂速度最慢的在第242代收斂至最優解.最優解的調度方案和作業信息如表6，表7所示，50次實驗結果的最好、最差以及平均迭代過程見圖10.數據選用表7中40個集裝箱的數據.

表6 40個集裝箱作業調度方案

表7 40個集裝箱作業軌道門吊信息

圖10 40個集裝箱微進化算法收斂過程示意圖

通過改變集裝箱的總數觀察并比較兩個算法的效率，部分比較測試結果如表8所示.可以看出，集裝箱個數為20時，MEA得到最優解的概率為95%，GA為88%，差距為7%；集裝箱個數為60時，兩者迭代得到最優解的概率的差距為18%.這說明微進化算法得到最優解的概率比傳統遺傳算法高，且問題越復雜越能體現其優勢.

表8 部分測試比較結果

基于物聯網平臺下的集裝箱軌道門吊調度問題是一種動態調度優化問題，司機可以根據時間提前更改預約到站時刻，因此此動態優化問題不存在固定的最優解，優化算法的目標是不僅是尋找靜態的極值點，而是盡可能準確地跟蹤極值點的動態變化的軌跡.本文設計以下算例對算法的動態優化能力進行測試.

假設在MEA和傳統GA中有4個動態變化，即在前600代中每200代改變一次集裝箱作業任務的允許開始作業時刻，期望完成作業時刻也會隨之變化，最大迭代次數設置為900.在迭代次數超過600代之后，比較兩種解決方案的最終優化結果.表9，表10為60個集裝箱最優調度方案和軌道門吊信息，圖11顯示了MEA和傳統GA在動態環境中的結果，數據選用表8中60個集裝箱的數據.

表9 60個集裝箱作業調度方案

表10 60個集裝箱作業軌道門吊信息

圖11 60個集裝箱動態環境下的變化曲線

從圖11可以看出，在所有的周期內MEA是優于傳統的遺傳算法的.MEA的性能曲線低于GA的性能曲線且波動幅度較均衡，GA曲線則波動較大，這意味著MEA的PDM算子能夠保持種群多樣性，并且在環境變化時使個體快速跳轉到新的最優點或附近.從600代到900代可以看出，MEA比GA更高效地找到最優解33.692 78 min，在迭代至773代時找到最優解，而GA則迭代至862代時才搜索到最優解.傳統遺傳算法所得的性能曲線幾乎沒有改善，而微進化算法在環境變化時能夠通過保持優勢基因結構快速找到最優解，這是由于在交叉和變異操作中優勢結構的破壞，傳統GA比MEA效率更低.

4 結論

本文研究了基于物聯網平臺下的裝卸資源調度多目標優化的動態問題，基于基因結構進化方法設計了求解該問題的微觀進化算法(MEA).根據實際作業情況設計了規模為40的集裝箱裝卸作業任務，最優目標函數為21.415 925 min，經過分析發現，各軌道門吊間的作業時間標準差較小，達到了均衡作業的效果，并且外集卡的平均延誤時間控制在1 min以內.通過觀察比較集裝箱總數的變化對算法的影響，發現微進化算法在復雜的環境中比傳統遺傳算法找到最優解的效率更高.在動態優化能力測試中，當環境變化時MEA較GA在穩定性方面有較大優勢，MEA通過保持優勢基因結構能夠更高效率地找到最優解，并且改進的對偶算子能捕捉變化的環境信息從而能更快地跳至最優解或附近.實驗結果表明，MEA比

常規遺傳算法在動態環境中具有更高的穩定性以及適應性.

在未來的研究中，一個主要的方向就是實現箱位的實時分配與資源調度動態性的結合，本文研究的MEA對動態資源的調度問題可以據此進一步研究.另外，應將MEA與更多動態優化方法進行比較，為解決實際問題提供更高效率的算法.

參考文獻:

[1]丁一, 陳杭欽, 林國龍. 成對自動堆垛起重機在集裝箱碼頭中的實時調度研究[J]. 重慶師范大學學報(自然科學版), 2017(2):11- 19.

[2]樂美龍, 徐根龍, 文洪蕊. 基于作業均衡的集裝箱碼頭岸橋作業調度優化[J]. 重慶交通大學學報(自然科學版), 2016(3):155- 161.

[3]秦進, 倪玲霖, 王承娜，等. 集裝箱碼頭岸橋調度優化模型及算法[J]. 西南交通大學學報, 2013(1):184- 192.

[4]梁承姬, 戴開梅. 基于集裝箱任務組時間窗的堆場場橋調度模型建立與求解[J]. 河南科學, 2013(4):477- 483.

[5]ZENG M, CHENG W, GUO P. Research of Railway Container Terminal Logistics System Modeling and Simulation[C]. International Conference On Mechanical Engineering and Control Automation 2016 (ICMECA 2016), 2016:287- 293.

[6]GUO P, CHENG W M, ZHANG Z Q. Gantry Crane Scheduling with Interference Constraints in Railway Container Terminals [J]. International Journal of Computational Intelligence Systems, 2013,6(2):244- 260.

[7]唐連生, 郭鵬. 鐵路集裝箱中心站裝卸設備優化調度研究[J]. 計算機工程與應用, 2012,48(2):211- 214.

[8]高鵬, 金淳, 韓慶平. 基于倒箱移動路徑的集裝箱堆場提箱作業優化模型[J]. 運籌與管理, 2012(1):19- 28.

[9]楊瑞馥. 致病性細菌微進化的研究進展[J]. 生命科學, 2009, 21(4):479- 484.

[10]許小健, 查日興. 一種新型群體智能優化算法——微進化算法[J].廈門理工學院學報, 2010, 18(3):38- 42.

[11]趙小毓. 基于物聯網的鐵路物流中心集裝箱功能區裝卸資源調度優化研究[D]. 北京：北京交通大學, 2017.