基于博弈論的鐵路集裝箱中心站裝卸作業研究

王清斌， 王翠萍， 肖勤飛

(大連海事大學 交通運輸工程學院，遼寧 大連 116026)

0 引言

鐵路集裝箱中心站作為集裝箱運輸體系中的重要節點，其作業效率和服務水平會在很大程度上影響全程集裝箱運輸的時間和物流服務質量。在鐵路集裝箱中心站作業過程中，各多式聯運經營人都希望充分占用中心站的裝卸資源使任務裝卸時間最短，從而達到全程運輸效益的最優。這種不同裝卸任務間的利益沖突本質上是對中心站有限資源的競爭，若不考慮這種競爭因素，會導致部分裝卸任務的等待時間過長，降低服務質量和客戶滿意度。故在考慮裝卸任務競爭因素的條件下，對不同裝卸作業流程下的裝卸設備進行合理高效的調度，對于提高鐵路集裝箱中心站整體作業質量，保障鐵路貨運服務水平具有重要意義。

目前，對于集裝箱場站的裝卸設備調度問題，國內外學者更加關注港口的集疏運作業活動，以減少裝卸作業時間或成本為目標，采取建模求解、仿真分析等方法進行研究[1～6]。由于港口和鐵路集裝箱中心站在作業設備、場站布局、轉運流程等方面都存在較大的差異，現有研究成果很難直接應用于中心站。同時對鐵路集裝箱中心站內裝卸設備協調調度問題的研究還不夠深入，王力等[7]以裝卸任務完成時間最短為目標，研究鐵路集裝箱中心站軌道門吊的作業調度問題，確定最優的集裝箱裝卸作業順序。唐連生等[8]研究了帶有干涉約束的軌道式門式起重機(軌道吊)調度問題。Guo P等[9]綜合考慮門吊位置、安全距離和非交叉約束，研究軌道門吊的調度。梁劍等[10]將內集卡的任務調度和箱位分配問題進行集成，對鐵路集裝箱中心站集裝箱專列卸箱作業的效率進行研究。以上研究僅以場站作業系統中特定的作業環節或集裝箱的單一流向為研究對象,缺少以中心站整個集裝箱轉運系統為對象的研究，或者是與所有裝卸作業相關的設備之間的集成規劃與調度。雖也有少數學者研究場站所有作業環節裝卸設備的協調調度問題，如：常祎妹等[11]以裝卸總完成時間最短為目標，研究集裝箱鐵水聯運下集裝箱碼頭鐵路作業區龍門吊、集卡和場橋的協同調度問題。Dong L等[12]在提出虛擬評價值概念的基礎上，以最小化裝卸時間為目標，采用仿真的優化方法，對鐵路集裝箱中心站集裝箱裝卸作業中設備的配置和裝卸策略進行優化。但都是以所有任務總裝卸完成時間最短為目標來分配裝卸機械、集卡等設備，確定不同裝卸任務的順序，未曾考慮到裝卸任務間的競爭關系。

綜上所述，現有鐵路集裝箱中心站的裝卸設備調度問題大多只考慮一種裝卸設備或單一集裝箱流向，且都未考慮到裝卸任務之間的競爭性因素。本文同時考慮了四種集裝箱流向的裝卸工藝流程，協調調度各裝卸作業環節中的龍門吊、集卡、正面吊等設備，在裝卸任務之間互相競爭的條件下，建立裝卸作業的博弈論模型并求解，為鐵路集裝箱中心站制定科學的裝卸作業計劃提供決策支持。

1 問題描述

鐵路集裝箱中心站裝卸作業系統包括裝車作業系統和卸車作業系統，因裝、卸車作業工藝只是流向相反而流程相同，故本文僅以卸車作業系統為例進行研究。

圖1 鐵路集裝箱中心站卸車系統作業流程

如圖1所示，鐵路集裝箱中心站的裝卸任務，根據不同的裝卸工藝流程可以分為4類，分別為：

(1)軌道門吊把集裝箱裝卸到外集卡上，直接運出中心站；

(2)軌道門吊把集裝箱裝卸至內集卡，集卡把集裝箱從主裝卸作業區運送到輔助堆場，由正面吊進行堆碼作業；

(3)軌道門吊把集裝箱裝卸在主堆場堆存；

(4)軌道門吊把集裝箱從此列列車換裝到其他集裝箱列車。

不同的裝卸作業流程會占用同一種裝卸設備形成競爭，鐵路集裝箱中心站在制定裝卸作業計劃過程中，應在考慮充分利用裝卸資源、縮短總裝卸時間的前提下，兼顧各裝卸任務對有限裝卸資源的這種競爭性需求，合理調配裝卸資源，優化作業順序，達到各裝卸任務之間的利益均衡(即達到所有裝卸任務均能接受的任務最短完成時間)。

在鐵路集裝箱中心站裝卸作業調度過程中，考慮到裝卸任務的競爭性因素，多式聯運經營人都是出于個人理性，追求自己利益的最大化，所以此競爭問題為非合作博弈問題。博弈的四要素為：

(1)博弈的局中人。將不同的裝卸任務看作非合作博弈模型中的局中人；

(2)博弈策略。將與每個裝卸任務每道工序里可選的裝卸資源作為可行策略；

(3)博弈次序。按照先來先服務(FCFS)的博弈次序來進行裝卸任務的調度；

(4)博弈方的得益或支付。將各裝卸任務完成時間的倒數映射為收益函數。

這樣，鐵路集裝箱中心站內裝卸任務調度問題就可轉化為尋求非合作博弈模型的Nash均衡點問題，在該均衡點上，即可得到滿足各裝卸任務利益均衡的調度結果。

通常在非合作博弈模型中，每個局中人會綜合考慮其他局中人的信息而選擇最有利于自己的策略。而在本文中局中人所選擇的策略是鐵路集裝箱中心站在考慮到各裝卸任務之間的競爭性因素后，分別站在不同裝卸任務的角度來替它們進行的策略選擇。

2 基于非合作博弈的裝卸資源調度模型

2.1 模型假設

(1)集裝箱類型統一；

(2)裝卸設備每次只能裝卸一個集裝箱；

(3)裝卸作業開始時，集裝箱的流向和所需裝卸工藝以及在堆場的位置已知；

(4)任務不可拆分；

(5)裝卸設備完成裝卸任務的過程連續，在裝卸過程中無故障發生；

(6)不考慮裝卸設備準備時間；

(7)所有的任務機會均等，不存在優先權；

(8)同一個任務的集裝箱流向相同，即裝卸工藝相同；

(9)同一類型設備的單位作業時間相同。

2.2 非合作博弈建模

將裝卸資源調度數學模型映射為非合作博弈模型，標準形式為：

G={P,(Sr)r∈N,(Ur)r∈N}

其中，P表示裝卸任務集合，即P={P1,P2,…,Pr,…,Pn}，同一時間段內共有n個待裝卸任務；Sr表示裝卸任務Pr可選裝卸設備的策略集合，Sr={sr1,sr2,…,srm(r)}，其中m(r)為局中人Pr的策略數；Ur表示裝卸任務Pr在采用策略srg時的收益函數，1≤g≤m(r);N={1,2,…,n}。

給出如下定義：①裝卸任務Pr包含gr道工序，npr表示任務Pr的集裝箱總量；

②Yk(k=1,2,3)是軌道門吊，集卡與正面吊設備集合，yk1∈Yk為第k種設備集合中第l臺設備，Nk代表三種設備的數量，k=1,2,3;l=1,2,…,Nk；

⑥vtyk：設備yk裝卸一個集裝箱的操作時間，k=1,2,3；

⑦tyk1：設備yk1開始空閑的時間，即最早可用時間，k=1,2,3;1=1,2,…,Nk；

(1)效用函數

局中人Pr選擇策略srg時的效用函數為：

(1)

定義1策略組合X*是n個局中人非合作博弈的一個納什均衡解，如果X*滿足：

Ur(X*|srg)≤Ur(X*),r=1,2,…,n;g=1,…,m(r)

其中，(X*|srg)表示只有局中人Pr將策略組合X*中自己的策略替換為srg，其他局中人的策略不變。

在鐵路集裝箱中心站中，每一個任務Pr從其策略集Sr中選取某一種策略，組成n個任務博弈的策略組合X。根據納什均衡定義，目標函數為

(2)

根據N人有限非合作博弈納什均衡的性質，當且僅當局中人混合策略達到納什均衡時，適應度函數取得最小值0，即當且僅當X=X*時，目標函數取最小值0；否則對每一個局中人Pr，單獨將自身策略變為srg時均不能獲得更多收益，任意X≠X*，ω≥0。因此在博弈的混合策略組合中只有納什均衡點的目標函數值最小。

(2)約束條件

①保證每個集裝箱同一時間內有且只被一臺裝卸設備進行裝卸作業。

(3)

(4)

②保證每個裝卸設備至多只有一個前序作業。

(5)

③保證每個裝卸設備至多只有一個后序作業。

(6)

④設備作業結束時間等于開始時間、操作時間和等待時間之和。

?yk1∈Yk,?k∈{1,2,3};1=1,2,…,Nk

(7)

3 算法設計

Nash均衡的求解是NP-hard問題，求解較為復雜，本文借鑒生物學進化理論，提出了一種求解博弈問題的遺傳算法。在算法的迭代過程中，個體會根據觀察到的博弈結果向自身的最優解進化，且同時向群體中表現最好的同伴進化。每個裝卸任務都會根據進化過程中的個體極值和群體極值，不斷地調整自己的策略，最終趨向博弈的均衡點。

3.1 染色體編碼

圖2 基于裝卸設備編碼方式的染色體編碼

圖2為一個染色體編碼示例，表示一個由6個不同的裝卸任務，3臺軌道門吊、5輛集卡和2臺正面吊組成的裝卸作業任務，其中裝卸任務1、2、4包含三道工序，裝卸任務3、5、6包含一道工序。軌道門吊編號為1、2、3，集卡編號為4、5、6、7、8，正面吊編號為9、10。由圖可知，裝卸任務1的三道工序分別由編號為1的軌道門吊、編號為5的集卡和編號為10的正面吊操作，編號1的軌道門吊先完成任務1的第一道工序，再進行任務6的第一道工序。

3.2 適應度函數

根據上文，適應度函數為：

(8)

當每個任務隨著策略的改變卻不能獲得更好的收益時，認為問題達到了Nash均衡，此時

(9)

3.3 算法的解碼操作

染色體解碼按照先到先服務(FCFS)規則來進行算法設計，結合非合作博弈裝卸任務調度特征，為每個設備指定一個作業序列。

(3)建立包含全部裝卸任務第一道工序的集合:Q={Br1|0≤r

3.4 算法的進化操作

選擇算子采取最佳保留的方式，在用輪盤賭方式選擇之后，讓目前種群中適應度值最優的個體復制進入下一代的遺傳過程中。此方法的優點是保證得到的算法結果是歷代中適應度值最優的個體。交叉算子采用兩點交叉法，對被交叉的染色體后部分進行修復。對于變異算子的設計，與傳統的變異算子相同，但是在變異過程中，考慮到被選擇的待變異基因對應于某一具體裝卸任務某一工序的可選裝卸設備，因此，當變異時，算法控制它只能選擇可選的裝卸設備進行變異。

4 實例仿真與分析

鐵路集裝箱中心站需要完成15個裝卸任務，總集裝箱數量為100。該集裝箱中心站配備有4臺龍門吊，分別用數字1、2、3、4表示；3輛內集卡，用數字5、6、7表示；2輛正面吊，用數字8、9表示。同時龍門吊、集卡、正面吊作業一個集裝箱的平均時間為2.5min、4.2min、2.6min[13]。任務的類別、集裝箱數量及每道工序可選裝卸設備如表1所示。

表1 裝卸任務基本信息

遺傳算法設計的初始輸入參數如表2所示。

表2 面向遺傳算法的基本輸入參數設計

根據初始條件，采用上述遺傳算法對模型進行了調度仿真，收斂圖和仿真結果(裝卸任務的調度甘特圖)如圖3、4所示

圖3 遺傳算法收斂圖

圖4 裝卸任務達到Nash均衡點后的調度甘特圖

從圖3可以看出，算法在第100代達到Nash均衡,第500代的任務完成時刻與第100代相同，這表明在算法達到Nash均衡后,每個裝卸任務均認為其裝卸完成時刻已達到最優而不愿打破該均衡狀態，表明模型和算法的可行性與有效性。圖4為任務的均衡狀態下的調度甘特圖，數字表示裝卸任務的工序編號，例如0602表示裝卸任務6的第二道工序，1001表示裝卸任務10的第一道工序。由圖可看出各裝卸任務的工序所選的裝卸設備和每一裝卸設備作業工序的順序，例如，裝卸任務8的三道工序分別由設備2、6、9作業；裝卸設備1分別作業任務2、1、6、7、9的第一道工序。

考慮到現實中集裝箱中心站所需完成的任務的特征差異，分析不同作業情形對結果的影響，根據每次調度的總任務數、總集裝箱數量和集裝箱數量標準差，設計8種不同的算例，分別進行20次獨立試驗取平均值，并將得到的均衡解與傳統的以中心站所有裝卸任務完成時間最小為目標得到的最優解進行比較。各算例初始信息及兩種方法結果的對比見表。

表3 8種算例初始信息及兩種方法結果對比

從結果對比來看，各算例最大完工時刻均衡解均等于最優解或大于最優解1%左右，這是因為均衡解是通過各個博弈方之間的相互制約和相互作用來獲得各自利益的滿足。最優解求解的目的是想要得到最優的資源配置情況，即達到總體效用的最大化，兩種求解方法自然會產生一定的偏差。

等待時間差指的是同一調度過程中裝卸任務等待時間的最大與最小間的差值，與等待時間標準差指標一起體現了各任務等待時間的差異性和離散性，是衡量裝卸任務間公平程度的指標。實驗結果表明，在處理鐵路集裝箱中心站卸車作業優化問題中，本文提出的博弈論方法得到的均衡解與傳統方法的最優解相比，各算例等待時間差和等待時間標準差均小10%左右，各任務等待時間較為均衡，這充分體現了博弈論方法兼顧各方利益，提高裝卸作業服務質量和滿意度的效果。對各任務集裝箱數量差異較大的算例，如算例2、4、8，均衡解與最優解的等待時間差和等待時間標準差的差異更大，這種效果更加明顯。

算例5和算例6的均衡解和最優解等待時間差與等待時間標準差幾乎無差異，這說明在任務數少的情況下，考慮各任務間的均衡性意義不大。

5 結論

本文在鐵路集裝箱中心站不同裝卸任務之間競爭的前提下，研究了中心站的裝卸資源調度及作業順序問題，建立了非合作博弈的裝卸資源調度模型并設計遺傳算法求解。結果表明，考慮各裝卸任務之間競爭性因素的均衡解與不考慮競爭性因素的最優解相比，最大完工時刻和平均等待時間略多1%，但等待時間標準差和等待時間差減少10%左右。因此，本研究考慮競爭性因素雖然對中心站作業效率產生了較小的影響，但卻明顯提高了裝卸任務之間的公平性，使每個裝卸任務的等待時間都較為均衡，提高了客戶滿意度，對輔助鐵路中心站制定科學合理的作業計劃更具有現實意義。