陳小紅

（西安鐵路職業(yè)技術(shù)學(xué)院 陜西 西安710014）

集裝箱運(yùn)輸中存在著大量的空箱運(yùn)輸， 造成運(yùn)輸資源的極大浪費(fèi)，使鐵路集裝箱運(yùn)輸業(yè)蒙受了重大損失。 關(guān)于鐵路空箱調(diào)運(yùn)的問(wèn)題已引起了很多學(xué)者的重視，并進(jìn)行了相應(yīng)的研究。 張得志、謝如鶴等學(xué)者從鐵路集裝箱運(yùn)輸市場(chǎng)的實(shí)際情況出發(fā), 建立了基于顧客偏好的模糊規(guī)劃模型和帶時(shí)間窗的規(guī)劃模型，并應(yīng)用遺傳算法對(duì)其進(jìn)行了求解[1]。 彭華、朱慶生教授等以最大限度地提高區(qū)域內(nèi)空箱的利用率和減小空箱調(diào)度的成本為目標(biāo)，建立了在一個(gè)計(jì)劃期內(nèi)的鐵路集裝箱空箱動(dòng)態(tài)優(yōu)化調(diào)度模型， 運(yùn)用遺傳算法對(duì)模型進(jìn)行求解，解決了在一個(gè)計(jì)劃期內(nèi)，如何最優(yōu)化地對(duì)每個(gè)工作日的空箱進(jìn)行區(qū)域性調(diào)度的問(wèn)題[2]。 由于空車調(diào)配和空箱調(diào)配的相似性，空車調(diào)配問(wèn)題的文獻(xiàn)[3-5]也有借鑒作用。

上述模型多以空箱調(diào)運(yùn)費(fèi)用最低為目標(biāo)[1-2，6]，且未給出具體算法[6]；而在實(shí)際生產(chǎn)中，鐵路部門空箱調(diào)運(yùn)的目的還是減少運(yùn)營(yíng)成本，追求效益最大化，所以應(yīng)該建立以效益最大化為目標(biāo)的模型。 本文以效益最大化為目標(biāo)函數(shù)建立了重箱協(xié)調(diào)下的單一箱型空箱調(diào)運(yùn)模型，設(shè)計(jì)了雙決策變量下的遺傳算法，最后給出了一個(gè)具體算例，對(duì)現(xiàn)場(chǎng)實(shí)際有一定的借鑒作用。

1 考慮重箱運(yùn)輸?shù)目障湔{(diào)運(yùn)模型的建立

1.1 參數(shù)及決策變量描述

在一個(gè)區(qū)域內(nèi)，有n 個(gè)集裝箱辦理站，每個(gè)車站每天將從區(qū)域外運(yùn)輸?shù)奖菊镜募b箱卸貨后， 會(huì)產(chǎn)生a 個(gè)空箱，而當(dāng)天該站又有貨物需要運(yùn)出，該車站的最大發(fā)送量為b。當(dāng)該車站的最大貨運(yùn)需求b 大于空箱產(chǎn)生量a 時(shí)，就需要從其他有多余空箱的車站調(diào)配。 如何運(yùn)送集裝箱貨物及如何調(diào)配空箱使鐵路運(yùn)輸部門收益最大。

1) 決策變量

xij：從i 站運(yùn)往j 到達(dá)站的集裝箱重箱數(shù)；

yij：從i 站調(diào)配到j(luò) 站進(jìn)行裝箱的空箱數(shù)；

2)參數(shù)

ai：第i 個(gè)車站產(chǎn)生的集裝箱空箱數(shù)；

bij：i 站到j(luò) 站的集裝箱貨運(yùn)需求，也就是i 站到j(luò) 站的最大發(fā)送量；

cij：從i 站到j(luò) 站調(diào)配單位空箱所產(chǎn)生的調(diào)運(yùn)費(fèi)用；

dij：從i 站到j(luò) 站運(yùn)送集裝箱貨物的單位收益；

Mij：i 站到j(luò) 站之間的集裝箱運(yùn)輸能力限制。

1.2 目標(biāo)函數(shù)與約束條件的確定

1)目標(biāo)函數(shù)的確定

在實(shí)際運(yùn)輸生產(chǎn)中，鐵路作為一個(gè)企業(yè)，其最終目標(biāo)是要追求效益最大化。 當(dāng)集裝箱重箱發(fā)送量不能滿足貨運(yùn)需求時(shí)，還應(yīng)考慮產(chǎn)生的運(yùn)輸收益損失。 運(yùn)輸收益損失與請(qǐng)求箱兌現(xiàn)率及每類貨物的財(cái)務(wù)影子價(jià)格有關(guān)， 貨物價(jià)值越高，影子價(jià)格就越高。

對(duì)于整個(gè)系統(tǒng)的重空箱數(shù)調(diào)配， 目標(biāo)還是謀求效益最大化。 這時(shí)，效益影響因素則包括：①集裝箱重箱運(yùn)輸收入；②空箱運(yùn)輸費(fèi)用；③未滿足運(yùn)輸需求的運(yùn)輸收益損失。目標(biāo)函數(shù)可表述為：

ρij為i 站到j(luò) 站的集裝箱單位運(yùn)量的影子價(jià)格；bij-xij為i站到j(luò) 站的未滿足貨運(yùn)需求的集裝箱量。

2)約束條件

①對(duì)空箱供給站I 的約束條件

對(duì)供給站i 來(lái)說(shuō)，應(yīng)該滿足空箱供給不小于空箱需求。也就是該站的空箱產(chǎn)生量應(yīng)不小于本站的空箱需求量(重箱發(fā)送量)加上運(yùn)往需求站J(由供給站i 所供應(yīng)的需求站集合)的空集裝箱量。 即：

②對(duì)空箱需求站J 的約束條件

同樣， 對(duì)于需求站j， 應(yīng)該滿足空箱供給不小于空箱需求。 也就是該站的空箱產(chǎn)生量加上由需求站調(diào)運(yùn)到本站的空箱量，應(yīng)不小于本站的空箱需求量。 即：

③對(duì)重箱發(fā)送量的約束條件

優(yōu)化后的計(jì)劃裝箱數(shù)應(yīng)該不大于該站的集裝箱貨運(yùn)需求。 即：

④運(yùn)輸能力約束條件

考慮重箱協(xié)調(diào)下的空箱調(diào)運(yùn)時(shí)， 空箱源站至需求站之間的運(yùn)輸能力限制應(yīng)該包括空箱運(yùn)輸能力限制和重箱運(yùn)輸能力限制。

⑤非負(fù)約束及整數(shù)約束

本式的意義為： 該模型中所有決策變量均大于等于零且為整數(shù)，否則無(wú)意義。

1.3 空箱調(diào)運(yùn)優(yōu)化模型

通過(guò)以上的分析， 可以得到一個(gè)空箱調(diào)運(yùn)優(yōu)化模型[SECRM]1：

2 模型的算法設(shè)計(jì)

2.1 解的編碼和初始化

本模型具有兩個(gè)決策變量，故染色體由兩部分組成，需要對(duì)這兩個(gè)決策變量分別進(jìn)行編碼。 本文采用十進(jìn)制基因矩陣對(duì)其編碼，如下所示。

其中，Yp代表第p 個(gè)染色體1 部分，yij是相應(yīng)的決策變量，表示從i 站發(fā)往j 站的空箱數(shù)量； Xp代表第p 個(gè)染色體2部分，xij是相應(yīng)的決策變量，表示從i 站發(fā)往j 站的重箱運(yùn)量。若xij和yij滿足模型的約束條件(1)、(2)、(3)和(4)，則由此構(gòu)成的染色體編碼(矩陣YX)，表示了原問(wèn)題的一個(gè)可行解。 顯然，由此構(gòu)成的染色體的基因型與其表現(xiàn)型是完全一致的， 它不僅具有編碼簡(jiǎn)單、直觀，而且易于遺傳操作算法實(shí)現(xiàn)的特點(diǎn)。

初始化算法具體構(gòu)造如下：

假定約束條件只有空重箱供給與需求的約束， 運(yùn)輸能力約束條件暫不考慮，只需在實(shí)際求解中加入約束判斷就行，使其初始解滿足所有約束條件。

輸入?yún)?shù)：第i 車站的空箱產(chǎn)生數(shù)；第i 車站至第j 車站的貨運(yùn)需求，并可求出第i 車站的總貨運(yùn)需求bi，其中i∈[1,n]，j∈[1,n]。

輸出結(jié)果：空箱調(diào)配矩陣Y，Y=yij，i，j∈[1,n]

重箱發(fā)送矩陣X，X=xij，i，j∈[1,n]，

算法1：對(duì)yij初始化

步驟1：隨機(jī)產(chǎn)生行號(hào)i，i∈[1,n]，隨機(jī)產(chǎn)生列號(hào)j，j∈[1,n]。

步驟2：計(jì)算矩陣Y 中的元素Yij

If i=j or ai≤biyij=0

//保證空箱不能從富余站運(yùn)往富余站，即兩次調(diào)運(yùn)

步驟3：更新ai=ai-yij，aj=aj+yij

步驟4：重復(fù)步驟1～3，直到所有的行列都設(shè)置完畢。 保留新的ai，aj。

算法2：對(duì)xij初始化

步驟1：隨機(jī)產(chǎn)生行號(hào)i，i∈[1,n]，隨機(jī)產(chǎn)生列號(hào)j，j∈[1，n]。

步驟2：計(jì)算矩陣Y 中的元素xij

If i=j or ai≤bixij=0

Else if ai≥bixij=bij//此時(shí)的ai是對(duì)yij初始化后的ai。

Else xij=min{bij，ai}

步驟3：更新ai=ai-xij，bi=bi-xij

步驟4：重復(fù)步驟1～3，直到所有的行列都設(shè)置完畢。

易知：由初始化算法得出的每組空重箱運(yùn)輸量xij和yij都滿足約束條件(1)式、(2)式、(3)式，故計(jì)算出的染色體YX 為原問(wèn)題的一個(gè)可行解。該算法采用隨機(jī)數(shù)自動(dòng)生成行號(hào)和列號(hào)，使得初始種群更加具有廣泛性和多樣性， 并能保證初始解相對(duì)于目標(biāo)函數(shù)而言得出的是一個(gè)適中的解。

2.2 適應(yīng)度函數(shù)的計(jì)算

用目標(biāo)函數(shù)值評(píng)價(jià)染色體適應(yīng)度的大小。

2.3 染色體交叉算子設(shè)計(jì)

對(duì)染色體1 部分的交叉：

從上式可知，rij是0-1 矩陣，因?yàn)镽em 矩陣存儲(chǔ)是否需要取整即除以2 的余數(shù)(0 或1)。

也就是使

從上易知，余數(shù)矩陣Rem 有多個(gè)分解法，且經(jīng)上述交叉操作后的后代都是可行的[1-2]。

對(duì)染色體2 部分的交叉：

因?yàn)槿旧w1 部分改變， 染色體2 部分就會(huì)相應(yīng)改變，他們之間有著一一對(duì)應(yīng)的關(guān)系。 故對(duì)染色體1 部分進(jìn)行交叉操作，就意味著對(duì)染色體2 部分進(jìn)行交叉操作，只要再對(duì)染色體2 部分根據(jù)新的集裝箱空箱產(chǎn)生量進(jìn)行一下重新分配。 具體步驟如下：

對(duì)染色體1 部分的變異：

步驟2：計(jì)算子矩陣Vp×q中的發(fā)送量和需求量。

步驟3：重新對(duì)Vp×q分配空箱，按初始算法1 生成新的子矩陣。

對(duì)染色體2 部分的變異：

同理，對(duì)染色體2 部分不用再設(shè)計(jì)算法變異，只要再對(duì)染色體2 部分根據(jù)新的集裝箱空箱產(chǎn)生量進(jìn)行一下重新分配。具體步驟如下：

3 具體算例

設(shè)某路局管轄6 個(gè)大型集裝箱辦理站，各車站的空箱產(chǎn)生和最大需求情況如表1 所列，各車站至其它車站的重箱運(yùn)輸收入和空箱調(diào)運(yùn)費(fèi)用分別如表2 和表3 所列，規(guī)定重箱單位收益損失和空箱運(yùn)輸單位收入相同，各車站之間的運(yùn)輸能力假定不受限制。 假定遺傳參數(shù)： 交叉概率pc=0.6，pm=0.1， 種群大小colony-size=30。 求空箱調(diào)運(yùn)和重箱發(fā)送的最優(yōu)調(diào)度方案。

可知，車站1、4 是空箱源站，車站2、3、5、6 是空箱目的站。 經(jīng)計(jì)算機(jī)仿真，計(jì)算模型()，得最大運(yùn)輸收益為54 320元， 空箱調(diào)運(yùn)和重箱發(fā)送的最優(yōu)調(diào)度方案如表4 和表5 所示。

4 結(jié)束語(yǔ)

模型[SECRM]1 具有如下的特點(diǎn)：

表1 各車站的空箱產(chǎn)生和最大需求情況Tab.1 The supply and maximum demand of empty container in the stations

表2 各車站至其他車站的重箱運(yùn)輸單位收入Tab. 2 Heavy container transportation unit revenue from one station to the other stations

表3 各車站至其他車站的空箱調(diào)運(yùn)費(fèi)用Tab.3 The stations’ cost of empty container reposition

表4 各站的空箱調(diào)運(yùn)數(shù)Tab.4 The stations’ empty container reposition number

1)目標(biāo)是謀求效益最大化，考慮了裝箱運(yùn)輸收入，空箱調(diào)運(yùn)費(fèi)用和未滿足運(yùn)輸需求的收益損失，其中裝箱運(yùn)輸收入對(duì)目標(biāo)值具有正效應(yīng)，其他兩項(xiàng)對(duì)目標(biāo)值具有負(fù)效應(yīng)。

2) 在考慮運(yùn)輸能力時(shí)把重箱運(yùn)輸能力和空箱運(yùn)輸能力同時(shí)考慮進(jìn)來(lái)，符合現(xiàn)場(chǎng)實(shí)際。

3)考慮的是單一標(biāo)準(zhǔn)箱型下的模型，以后的模型可以在此基礎(chǔ)上擴(kuò)展到不同尺寸不同類型的集裝箱。

4)對(duì)空箱供需量與重箱裝卸量進(jìn)行了合理銜接，重箱的裝卸差決定了空箱的供給量，空箱需求的滿足量又反過(guò)來(lái)影響了重箱裝運(yùn)量。 顯然，將重箱和空箱聯(lián)合納入優(yōu)化要比單純的空箱優(yōu)化更準(zhǔn)確。

表5 各站的重箱發(fā)送數(shù)Tab.5 The stations’ heavy container sending number

當(dāng)然，該模型只是考慮單一箱型的空箱調(diào)運(yùn)，實(shí)際貨物運(yùn)輸當(dāng)中存在多種運(yùn)輸路徑，不同尺寸的箱型間有無(wú)可替代性，時(shí)效性對(duì)箱源的影響等,可建立較為復(fù)雜的考慮多方面影響因素的空箱調(diào)運(yùn)模型。

[1] 張得志,謝如鶴,黃孝章.鐵路集裝箱空箱調(diào)度模型及求解算法[J].中國(guó)鐵道科學(xué),2003,24(3):125-129.

ZHANG De-zhi,XIE Ru-he,HUANG Xiao-zhang.Dispatch model and solution algorithm of railway empty container[J].China Railway Science,2003,24(3):125-129.

[2] 彭華.鐵路集裝箱空箱動(dòng)態(tài)優(yōu)化調(diào)度研究[D].重慶：重慶大學(xué)機(jī)電學(xué)院，2008.

[3] 李宗平，夏劍鋒.基于時(shí)間約束的鐵路空車調(diào)配模型與算法[J].西南交通大學(xué)學(xué)報(bào)，2005,3（40）：361-365.

LI Zong-ping XIA Jian-feng.Time restraint-based model and algorithm for raiway empty wagon distribution[J].Journal of Southwest Jiaotong University,2005,3(40):361-365.

[4] 梁棟,林柏梁，嚴(yán)賀祥，等.車種代用情況下的鐵路空車調(diào)配研究[J].鐵道學(xué)報(bào)，2005，4(27)：1-5.

LIANG Dong,LIN Bo-liang,YAN He-xiang,et al.Study of raiway empty car distribution with substitution of empty car types[J].Journal of the China Railway Society,2005,4(27):1-5.

[5] 雷中林,何世偉，宋瑞，等.鐵路空車調(diào)配問(wèn)題的隨機(jī)機(jī)會(huì)約束模型及遺傳算法[J].鐵道學(xué)報(bào),2005，27(5):1-5.

LEI Zhong -lin,HE Shi -wei,SONG Rui,et al.Stochastic chance-constrained model and genetic algorithm for empty car distribution in raiway transportaton[J].Joural of the China Railway Society,2005,27(5):1-5.

[6] 計(jì)明軍，王清斌，張新宇，等.沿海港口集裝箱空箱調(diào)運(yùn)策略的優(yōu)化模型[J].運(yùn)籌與管理，2014,1（23）：80-89.

JI Ming-jun,WANG Qing-bin,ZHANG Xin-yu,et al.Optimal model for allocation and transportation strategies of empty containers between coastal ports [J].Operations Research and Management Science,2014,1(23):80-89.