重箱協(xié)調(diào)下的單一空箱調(diào)運模型與算法

陳小紅

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

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

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

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

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

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

1) 決策變量

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

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

2)參數(shù)

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

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

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

dij：從i 站到j 站運送集裝箱貨物的單位收益；

Mij：i 站到j 站之間的集裝箱運輸能力限制。

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

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

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

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

ρij為i 站到j 站的集裝箱單位運量的影子價格；bij-xij為i站到j 站的未滿足貨運需求的集裝箱量。

2)約束條件

①對空箱供給站I 的約束條件

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

②對空箱需求站J 的約束條件

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

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

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

④運輸能力約束條件

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

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

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

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

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

2 模型的算法設計

2.1 解的編碼和初始化

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

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

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

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

輸入?yún)?shù)：第i 車站的空箱產(chǎn)生數(shù)；第i 車站至第j 車站的貨運需求，并可求出第i 車站的總貨運需求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：對yij初始化

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

步驟2：計算矩陣Y 中的元素Yij

If i=j or ai≤biyij=0

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

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

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

算法2：對xij初始化

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

步驟2：計算矩陣Y 中的元素xij

If i=j or ai≤bixij=0

Else if ai≥bixij=bij//此時的ai是對yij初始化后的ai。

Else xij=min{bij，ai}

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

步驟4：重復步驟1～3，直到所有的行列都設置完畢。

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

2.2 適應度函數(shù)的計算

用目標函數(shù)值評價染色體適應度的大小。

2.3 染色體交叉算子設計

對染色體1 部分的交叉：

從上式可知，rij是0-1 矩陣，因為Rem 矩陣存儲是否需要取整即除以2 的余數(shù)(0 或1)。

也就是使

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

對染色體2 部分的交叉：

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

對染色體1 部分的變異：

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

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

對染色體2 部分的變異：

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

3 具體算例

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

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

4 結(jié)束語

模型[SECRM]1 具有如下的特點：

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

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

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

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

1)目標是謀求效益最大化，考慮了裝箱運輸收入，空箱調(diào)運費用和未滿足運輸需求的收益損失，其中裝箱運輸收入對目標值具有正效應，其他兩項對目標值具有負效應。

2) 在考慮運輸能力時把重箱運輸能力和空箱運輸能力同時考慮進來，符合現(xiàn)場實際。

3)考慮的是單一標準箱型下的模型，以后的模型可以在此基礎上擴展到不同尺寸不同類型的集裝箱。

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

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

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

[1] 張得志,謝如鶴,黃孝章.鐵路集裝箱空箱調(diào)度模型及求解算法[J].中國鐵道科學,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] 彭華.鐵路集裝箱空箱動態(tài)優(yōu)化調(diào)度研究[D].重慶：重慶大學機電學院，2008.

[3] 李宗平，夏劍鋒.基于時間約束的鐵路空車調(diào)配模型與算法[J].西南交通大學學報，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] 梁棟,林柏梁，嚴賀祥，等.車種代用情況下的鐵路空車調(diào)配研究[J].鐵道學報，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)配問題的隨機機會約束模型及遺傳算法[J].鐵道學報,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] 計明軍，王清斌，張新宇，等.沿海港口集裝箱空箱調(diào)運策略的優(yōu)化模型[J].運籌與管理，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.