王清斌， 王翠萍， 肖勤飛

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026)

0 引言

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

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

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

1 問題描述

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

圖1 鐵路集裝箱中心站卸車系統(tǒng)作業(yè)流程

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

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

(2)軌道門吊把集裝箱裝卸至內(nèi)集卡，集卡把集裝箱從主裝卸作業(yè)區(qū)運(yùn)送到輔助堆場(chǎng)，由正面吊進(jìn)行堆碼作業(yè)；

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

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

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

在鐵路集裝箱中心站裝卸作業(yè)調(diào)度過程中，考慮到裝卸任務(wù)的競(jìng)爭(zhēng)性因素，多式聯(lián)運(yùn)經(jīng)營(yíng)人都是出于個(gè)人理性，追求自己利益的最大化，所以此競(jìng)爭(zhēng)問題為非合作博弈問題。博弈的四要素為：

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

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

(3)博弈次序。按照先來先服務(wù)(FCFS)的博弈次序來進(jìn)行裝卸任務(wù)的調(diào)度；

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

這樣，鐵路集裝箱中心站內(nèi)裝卸任務(wù)調(diào)度問題就可轉(zhuǎn)化為尋求非合作博弈模型的Nash均衡點(diǎn)問題，在該均衡點(diǎn)上，即可得到滿足各裝卸任務(wù)利益均衡的調(diào)度結(jié)果。

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

2 基于非合作博弈的裝卸資源調(diào)度模型

2.1 模型假設(shè)

(1)集裝箱類型統(tǒng)一；

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

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

(4)任務(wù)不可拆分；

(5)裝卸設(shè)備完成裝卸任務(wù)的過程連續(xù)，在裝卸過程中無故障發(fā)生；

(6)不考慮裝卸設(shè)備準(zhǔn)備時(shí)間；

(7)所有的任務(wù)機(jī)會(huì)均等，不存在優(yōu)先權(quán)；

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

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

2.2 非合作博弈建模

將裝卸資源調(diào)度數(shù)學(xué)模型映射為非合作博弈模型，標(biāo)準(zhǔn)形式為：

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

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

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

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

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

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

(1)效用函數(shù)

局中人Pr選擇策略srg時(shí)的效用函數(shù)為：

(1)

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

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

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

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

(2)

根據(jù)N人有限非合作博弈納什均衡的性質(zhì)，當(dāng)且僅當(dāng)局中人混合策略達(dá)到納什均衡時(shí)，適應(yīng)度函數(shù)取得最小值0，即當(dāng)且僅當(dāng)X=X*時(shí)，目標(biāo)函數(shù)取最小值0；否則對(duì)每一個(gè)局中人Pr，單獨(dú)將自身策略變?yōu)閟rg時(shí)均不能獲得更多收益，任意X≠X*，ω≥0。因此在博弈的混合策略組合中只有納什均衡點(diǎn)的目標(biāo)函數(shù)值最小。

(2)約束條件

①保證每個(gè)集裝箱同一時(shí)間內(nèi)有且只被一臺(tái)裝卸設(shè)備進(jìn)行裝卸作業(yè)。

(3)

(4)

②保證每個(gè)裝卸設(shè)備至多只有一個(gè)前序作業(yè)。

(5)

③保證每個(gè)裝卸設(shè)備至多只有一個(gè)后序作業(yè)。

(6)

④設(shè)備作業(yè)結(jié)束時(shí)間等于開始時(shí)間、操作時(shí)間和等待時(shí)間之和。

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

(7)

3 算法設(shè)計(jì)

Nash均衡的求解是NP-hard問題，求解較為復(fù)雜，本文借鑒生物學(xué)進(jìn)化理論，提出了一種求解博弈問題的遺傳算法。在算法的迭代過程中，個(gè)體會(huì)根據(jù)觀察到的博弈結(jié)果向自身的最優(yōu)解進(jìn)化，且同時(shí)向群體中表現(xiàn)最好的同伴進(jìn)化。每個(gè)裝卸任務(wù)都會(huì)根據(jù)進(jìn)化過程中的個(gè)體極值和群體極值，不斷地調(diào)整自己的策略，最終趨向博弈的均衡點(diǎn)。

3.1 染色體編碼

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

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

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

根據(jù)上文，適應(yīng)度函數(shù)為：

(8)

當(dāng)每個(gè)任務(wù)隨著策略的改變卻不能獲得更好的收益時(shí)，認(rèn)為問題達(dá)到了Nash均衡，此時(shí)

(9)

3.3 算法的解碼操作

染色體解碼按照先到先服務(wù)(FCFS)規(guī)則來進(jìn)行算法設(shè)計(jì)，結(jié)合非合作博弈裝卸任務(wù)調(diào)度特征，為每個(gè)設(shè)備指定一個(gè)作業(yè)序列。

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

3.4 算法的進(jìn)化操作

選擇算子采取最佳保留的方式，在用輪盤賭方式選擇之后，讓目前種群中適應(yīng)度值最優(yōu)的個(gè)體復(fù)制進(jìn)入下一代的遺傳過程中。此方法的優(yōu)點(diǎn)是保證得到的算法結(jié)果是歷代中適應(yīng)度值最優(yōu)的個(gè)體。交叉算子采用兩點(diǎn)交叉法，對(duì)被交叉的染色體后部分進(jìn)行修復(fù)。對(duì)于變異算子的設(shè)計(jì)，與傳統(tǒng)的變異算子相同，但是在變異過程中，考慮到被選擇的待變異基因?qū)?yīng)于某一具體裝卸任務(wù)某一工序的可選裝卸設(shè)備，因此，當(dāng)變異時(shí)，算法控制它只能選擇可選的裝卸設(shè)備進(jìn)行變異。

4 實(shí)例仿真與分析

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

表1 裝卸任務(wù)基本信息

遺傳算法設(shè)計(jì)的初始輸入?yún)?shù)如表2所示。

表2 面向遺傳算法的基本輸入?yún)?shù)設(shè)計(jì)

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

圖3 遺傳算法收斂圖

圖4 裝卸任務(wù)達(dá)到Nash均衡點(diǎn)后的調(diào)度甘特圖

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

考慮到現(xiàn)實(shí)中集裝箱中心站所需完成的任務(wù)的特征差異，分析不同作業(yè)情形對(duì)結(jié)果的影響，根據(jù)每次調(diào)度的總?cè)蝿?wù)數(shù)、總集裝箱數(shù)量和集裝箱數(shù)量標(biāo)準(zhǔn)差，設(shè)計(jì)8種不同的算例，分別進(jìn)行20次獨(dú)立試驗(yàn)取平均值，并將得到的均衡解與傳統(tǒng)的以中心站所有裝卸任務(wù)完成時(shí)間最小為目標(biāo)得到的最優(yōu)解進(jìn)行比較。各算例初始信息及兩種方法結(jié)果的對(duì)比見表。

表3 8種算例初始信息及兩種方法結(jié)果對(duì)比

從結(jié)果對(duì)比來看，各算例最大完工時(shí)刻均衡解均等于最優(yōu)解或大于最優(yōu)解1%左右，這是因?yàn)榫饨馐峭ㄟ^各個(gè)博弈方之間的相互制約和相互作用來獲得各自利益的滿足。最優(yōu)解求解的目的是想要得到最優(yōu)的資源配置情況，即達(dá)到總體效用的最大化，兩種求解方法自然會(huì)產(chǎn)生一定的偏差。

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

算例5和算例6的均衡解和最優(yōu)解等待時(shí)間差與等待時(shí)間標(biāo)準(zhǔn)差幾乎無差異，這說明在任務(wù)數(shù)少的情況下，考慮各任務(wù)間的均衡性意義不大。

5 結(jié)論

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