鐵路集裝箱空箱調(diào)運(yùn)問題的遺傳算法*

段 剛，張 慧，陳 莉，李引珍，劉永莉，陳志忠

(1.蘭州交通大學(xué)交通運(yùn)輸學(xué)院，甘肅 蘭州 730070;2.蘭州鐵路局貨運(yùn)處，甘肅 蘭州 730070;3.蘭州城市學(xué)院數(shù)學(xué)學(xué)院，甘肅 蘭州 730070)

由于我國地區(qū)經(jīng)濟(jì)發(fā)展不平衡、各區(qū)域貨物流量不均衡以及集裝箱辦理站之間集裝箱到發(fā)量的不平衡，導(dǎo)致鐵路適箱貨源和箱源分布也不平衡。即使在同一地區(qū)，也會(huì)因季節(jié)和時(shí)間的變化而出現(xiàn)某一段時(shí)間集裝箱空箱積壓，另一段時(shí)間短缺的現(xiàn)象，從而導(dǎo)致空箱調(diào)運(yùn)。頻繁地進(jìn)行空箱調(diào)運(yùn)不但浪費(fèi)鐵路運(yùn)能，而且空箱在運(yùn)輸途中支出的各種費(fèi)用也給鐵路運(yùn)輸企業(yè)增加了負(fù)擔(dān)。集裝箱的日常管理費(fèi)用通常可以分為:空箱調(diào)運(yùn)費(fèi)、堆存費(fèi)、修理費(fèi)、集裝箱租賃費(fèi)、吊裝費(fèi)和其他費(fèi)用，而集裝箱空箱調(diào)運(yùn)費(fèi)用占總費(fèi)用的1/4。因此，優(yōu)化空箱調(diào)運(yùn)方案并設(shè)計(jì)出高效的算法，對于減少空箱調(diào)運(yùn)成本，提高鐵路運(yùn)能和集裝箱使用效率，具有十分現(xiàn)實(shí)的意義。

1 研究現(xiàn)狀

鐵路空箱調(diào)運(yùn)與空車調(diào)配問題無論從模型構(gòu)造上還是求解方法上都非常相似，因此可以借鑒。熊紅云等［1］和張得志等［2］采用矩陣表示染色體的遺傳算法分別求解鐵路空車和空箱調(diào)運(yùn)問題，他們設(shè)計(jì)的交叉算子均對2個(gè)染色體的均值運(yùn)算和取余運(yùn)算的結(jié)果進(jìn)行代數(shù)和計(jì)算，從而得到新的染色體，變異算子也都是對染色體子矩陣中的元素進(jìn)行調(diào)整，區(qū)別是一個(gè)采用整數(shù)編碼，一個(gè)采用十進(jìn)制編碼。果鵬文等［3］采用振蕩法解決大規(guī)模路網(wǎng)上的空車調(diào)配問題，在事先不知道某個(gè)區(qū)段空車排空方向的前提下，預(yù)先人為指定該區(qū)段的空車排空方向，作為初始方案，使得區(qū)段上中間站的空車流，能夠按照一定的原則歸并到前方技術(shù)站;然后對初始方案進(jìn)行計(jì)算，對區(qū)段空車方向不斷進(jìn)行調(diào)整，反復(fù)計(jì)算，直到指定的空車方向與計(jì)算結(jié)果相符合時(shí)為止。雷中林等［4］針對運(yùn)輸需求等不確定性建立了空車調(diào)配的隨機(jī)機(jī)會(huì)約束模型，并設(shè)計(jì)了遺傳算法求解。林柏梁等［5］設(shè)計(jì)了分步優(yōu)化迭代算法求解線路能力約束下的鐵路空車調(diào)配問題。還有應(yīng)用神經(jīng)網(wǎng)絡(luò)法［6］、物體重心法［7］和區(qū)段中心優(yōu)化法［8］求解問題。在此，作者從鐵路運(yùn)輸實(shí)際出發(fā)，針對空箱調(diào)運(yùn)模型，設(shè)計(jì)了一種新的遺傳算法，可以高效求解空箱調(diào)運(yùn)問題。

2 空箱調(diào)運(yùn)問題的數(shù)學(xué)模型

2.1 參數(shù)與變量

S為空箱供應(yīng)站集合，S={1，2，…，m};D為空箱需求站集合，D={1，2，…，n};ai為 i站可供應(yīng)的空箱數(shù)，ai∈Z+，i∈S;bj為 j站需求的空箱數(shù)，bj∈Z+，j∈D;dij為 i站與 j站間的距離，i∈S，j∈D;xij為i站向j站調(diào)運(yùn)的空箱數(shù)，決策變量。

2.2 空箱調(diào)運(yùn)模型

空箱調(diào)運(yùn)模型如下:

(1)式為目標(biāo)函數(shù)，表示空箱調(diào)運(yùn)的總距離最小;(2)式與(3)式為空箱供應(yīng)與需求的平衡約束;(4)式為變量的非負(fù)和整數(shù)約束。

3 空箱調(diào)運(yùn)問題的遺傳算法

自從1975年Holland提出遺傳算法后，因?yàn)槠浜唵?、魯棒性好和并行?jì)算等特點(diǎn)，從而在工程技術(shù)、自動(dòng)控制、圖像處理、人工智能和管理科學(xué)等眾多領(lǐng)域得到了廣泛應(yīng)用。本文提出一種新的遺傳算法，通過交叉與變異操作，在保證解的可行性基礎(chǔ)上，能夠快速高效求解空箱調(diào)運(yùn)問題。

3.1 染色體的構(gòu)成及種群的初始化

采用整數(shù)編碼，以矩陣V表示一個(gè)染色體，

其中，xij∈Z+∪{0}，i∈S，j∈D 。顯然，基因 xij表示i站向j站調(diào)運(yùn)的空箱量，這樣，染色體的基因型與其表現(xiàn)型完全一致，無需解碼，因此以下對染色體和解不加區(qū)分。但要使得染色體可行，必須滿足供需平衡的條件。以下種群的初始化，交叉算子和變異算子的操作，均圍繞染色體的可行性來進(jìn)行。

初始種群的產(chǎn)生采用下面的算法［1－2］:

步驟1 隨機(jī)產(chǎn)生下標(biāo) i和 j，其中i∈ S，j∈D;

步驟2 計(jì)算 xij，xij=min{ai，bj};

步驟3 更新 ai和 bj，ai= ai－ xij，bj= bjxij;

步驟4 重復(fù)步驟1—步驟3，直到所有ai和bj都為0。

由上述算法產(chǎn)生的染色體必然對應(yīng)一組可行解，其分配思想就是隨機(jī)化的西北角法。

3.2 交叉算子

按交叉概率pc隨機(jī)選擇染色體V1和V2作為父個(gè)體，其中。為了使得交叉操作不破壞染色體的可行性，采用下面的方法產(chǎn)生子代染色體V3=(yij)和V4=(zij)。首先，令

其中，i∈ S，j∈ D，i和 j不同時(shí)為1，0 ＜ α ≤0.5。當(dāng)i=1，j≥2時(shí)，(9)式和(11)式的最小值皆取第1項(xiàng)，而當(dāng)j=1，i≥2時(shí)，兩式的最小值皆取第2項(xiàng)。α為交叉參數(shù)，是本遺傳算法中最重要的參數(shù)。實(shí)際上，文獻(xiàn)［1］和［2］中的交叉方法可以看作是本交叉算子的特例，即α取值為0.5，也就是對2個(gè)父代染色體的對應(yīng)基因求均值。而本文中，α取值更廣泛，這樣就能夠擴(kuò)大種群的多樣性。

(9)式和(11)式可以保證子代染色體每行的調(diào)運(yùn)量之和不會(huì)超過供應(yīng)量，每列的調(diào)運(yùn)量之和不會(huì)超過需求量，(10)式和(12)式能夠保證調(diào)運(yùn)量都非負(fù)，但卻不能保證等式成立，故需要對調(diào)運(yùn)量進(jìn)行調(diào)整以滿足平衡條件。

更新 yi1，j1，令 yi1，j1= φ +yi1，j1;遍歷 i，j，直至所有行列都滿足平衡。

3.3 變異算子

求解運(yùn)輸問題的表上作業(yè)法，其對基變量的調(diào)整采用閉合回路法。該方法雖然能保證解的可行性，但尋找閉合回路卻相當(dāng)耗時(shí)。本文借鑒該思想，采用基于矩形閉合回路的方法設(shè)計(jì)變異算子，可以大大減少計(jì)算量。

按變異概率pm選擇染色體V5=(wij)，隨機(jī)選擇 i0，j0，i1，j1，其中 i0∈S，j0∈D，i1∈S/{i0}，j1∈ D/{j0}。當(dāng) wi0，j0wi1，j1＞ 0 ，即 wi0，j0和 wi1，j1同時(shí)為正數(shù)，取δ=min{wi0j0，wi1j1}。然后在矩形閉合回路 wi0j0，wi0j1，wi1j1，wi1j0中進(jìn)行調(diào)整，令

其余基因wij取值不變，組成新的染色體V6。

3.4 評價(jià)函數(shù)和選擇操作

由于染色體的可行性以及目標(biāo)函數(shù)為線性函數(shù)，所以取目標(biāo)函數(shù)為評價(jià)函數(shù)，即:

其中，V=(xij)。

采用基于輪盤賭的選擇策略，詳見文獻(xiàn)［9］。

3.5 算法步驟

步驟1 初始化種群;

步驟2 通過交叉操作和變異操作產(chǎn)生子代染色體;

步驟3 計(jì)算每個(gè)染色體的評價(jià)函數(shù)，并記錄最優(yōu)染色體;

步驟4 通過輪盤賭選擇染色體;

步驟5 重復(fù)步驟2—步驟4，直到滿足停止條件。

其中，停止條件為可以定義為進(jìn)化的最大代數(shù)，也可以通過比較前后兩代最優(yōu)染色體的變化情況確定停止條件，本文采用前者。

4 實(shí)驗(yàn)仿真

以蘭州鐵路局為例，對該局內(nèi)集裝箱辦理站間的空箱調(diào)運(yùn)進(jìn)行優(yōu)化。圖1所示為蘭州局的18個(gè)集裝箱辦理站。這里取2009年某月的集裝箱運(yùn)輸數(shù)據(jù)，用以驗(yàn)證算法的有效性。各個(gè)集裝箱辦理站的空箱需求量、供應(yīng)量以及兩站之間的距離如表1所示，其中，距離為兩站之間的最短路徑長度。由于綠化、中堡、張家祠和鴛鴦鎮(zhèn)4個(gè)集裝箱辦理站到發(fā)集裝箱數(shù)量平衡，故沒有出現(xiàn)在表1中。因?yàn)榭傂枨罅繛?54箱，而總供應(yīng)量只有344箱，所以增加虛設(shè)供應(yīng)站S6，其供應(yīng)量為210箱。

圖1 蘭州鐵路局集裝箱辦理站示意圖Fig.1 Lanzhou Railway Bureau container handling stations

為了尋求交叉概率、變異概率以及交叉參數(shù)α的最佳取值，利用 VC6.0編程，在 Core 2 Duo＆2.2GHz、1G DDR2的惠普筆記本上運(yùn)行通過，在每組概率組合下都做了10次測試，其中群體規(guī)模為20，遺傳代數(shù)為600。首先令 α =0.1，Pm=0.1，交叉概率Pc在(0，1)區(qū)間每次變化0.05，評價(jià)函數(shù)的平均值和標(biāo)準(zhǔn)差的變化見圖2和圖3。顯然 Pc的最優(yōu)取值為0.65，在此基礎(chǔ)上，變異概率Pm在(0，1)內(nèi)每次變化0.05，同樣可以得到評價(jià)函數(shù)的均值和標(biāo)準(zhǔn)差變化情況，見圖4和圖5。從圖中可以看出，當(dāng)Pm大于0.65時(shí)，評價(jià)函數(shù)的均值幾乎相同，其標(biāo)準(zhǔn)差也比較接近，且都比較小，因此，選取 Pm=0.65。

表1 集裝箱辦理站間距離及供需表Table 1 The distance between container handling stations and supply and demand quantity

圖2 不同交叉概率下評價(jià)函數(shù)平均值Fig.2 The average value of evaluation function under different crossover probability

圖3 不同交叉概率下評價(jià)函數(shù)標(biāo)準(zhǔn)差Fig.3 The standard deviation value of evaluation function under different crossover probability

圖4 不同變異概率下評價(jià)函數(shù)平均值Fig.4 The average value of evaluation function under different mutation probability

圖5 不同變異概率下評價(jià)函數(shù)標(biāo)準(zhǔn)差Fig.5 The standard deviation value of evaluation function under different mutation probability

在最優(yōu)交叉概率和變異概率組合下，令α在區(qū)間［0.05，0.5］內(nèi)每次變化0.05，得到評價(jià)函數(shù)的均值和標(biāo)準(zhǔn)差，如圖6和圖7所示。當(dāng)α取值為0.1，0.35和0.5時(shí)，評價(jià)函數(shù)平均值都比較小，標(biāo)準(zhǔn)差也相差不多，所以可以任選一個(gè)，本文取α=0.1。

圖6 不同交叉參數(shù)值下評價(jià)函數(shù)均值Fig.6 The average value of evaluation function under different crossover parameter

圖7 不同交叉參數(shù)值下評價(jià)函數(shù)標(biāo)準(zhǔn)差Fig.7 The standard deviation value of evaluation function under different crossover probability

在以上各參數(shù)最優(yōu)取值下，通過本文設(shè)計(jì)的遺傳算法，當(dāng)計(jì)算到520代時(shí)達(dá)到最優(yōu)，評價(jià)函數(shù)為143689，收斂過程如圖8所示(其中，從390代到510代，評價(jià)函數(shù)都為143720，與最優(yōu)評價(jià)函數(shù)只相差31，圖中顯示不明顯)。采用LINGO 9.0軟件計(jì)算得到的最優(yōu)解如表2所示，計(jì)算時(shí)間不到1 s(LINGO 9.0最小計(jì)時(shí)單位為s)。本遺傳算法的計(jì)算時(shí)間僅為0.14 s，不但能得到上述最優(yōu)解，而且還能得到另外一組最優(yōu)解，如表3所示。不難看出，在表2中由金昌，蘭州北，嘉峪關(guān)和白銀市組成的閉合回路里，對調(diào)運(yùn)量進(jìn)行了1個(gè)單位的調(diào)整，即得到表3，而這正是本文中的變異操作。所以使用該遺傳算法，不僅能在不同的計(jì)算中得到這2組最優(yōu)解，還能在一次計(jì)算中同時(shí)得到這2組最優(yōu)解，而這是LINGO軟件做不到的。

圖8 遺傳算法收斂圖Fig.8 Genetic algorithm convergence figure

表2 應(yīng)用LINGO計(jì)算得到的最優(yōu)調(diào)運(yùn)量Table 2 The best solution solved by LINGO software container

表3 另外一組最優(yōu)調(diào)運(yùn)量Table 3 The other best solution solved by genetic algorithm container

5 結(jié)論

鐵路集裝箱空箱調(diào)運(yùn)優(yōu)化模型與空車調(diào)運(yùn)模型完全相同，因此，設(shè)計(jì)高效的算法就成為解決這類問題的關(guān)鍵。本文提出的遺傳算法，交叉操作是對父代染色體進(jìn)行線性組合并取整后經(jīng)過適當(dāng)調(diào)整得到子代染色體，變異操作則采用矩形閉合回路法。通過對蘭州鐵路局集裝箱辦理站的實(shí)例計(jì)算，表明該算法不但效率非常高，而且還能得到不同的最優(yōu)解。關(guān)于交叉參數(shù)α的取值問題，本文采用固定值，通過測試找到其最佳取值。如果在計(jì)算過程中，對α進(jìn)行調(diào)整，采用變參數(shù)法，或者直接對其進(jìn)行編碼并參與交叉和變異操作進(jìn)行自適應(yīng)調(diào)整，這樣會(huì)進(jìn)一步提高該算法的效率，以利于求解更大規(guī)模的問題，這將是我們下一步要研究的內(nèi)容。

［1］熊紅云，魯五一，溫紅艷.鐵路空車調(diào)配問題的遺傳啟發(fā)算法［J］.中國鐵道科學(xué)，2002，23(4):118－121.XIONG Hong-yun，LU Wu-yi，WEN Hong-yan.Hereditary heuristic algorithm for empty car distribution in railway transportation［J］.China Railway Science，2002，23(4):118－121.

［2］張得志，謝如鶴，黃孝章.鐵路集裝箱空箱調(diào)度模型及求解算法［J］.中國鐵道科學(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.

［3］果鵬文，褚 江，林柏梁.用振蕩法解大規(guī)模路網(wǎng)上的空車調(diào)配問題［J］.中國鐵道科學(xué)，2002，23(4):111－117.GUO Peng-wen，CHU Jiang，LIN Bo-liang.Reiterative adjusting method of empty wagon on large－scale railway network［J］.China Railway Science，2002，23(4):111－117.

［4］雷中林，何世偉，宋 瑞，等.鐵路空車調(diào)配問題的隨機(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 railway transportation［J］.Journal ofthe China Railway Society，2005，27(5):1－5.

［5］林柏梁，喬國會(huì).基于線路能力約束下的鐵路空車調(diào)配迭代算法［J］.中國鐵道科學(xué)，2008，29(1):93－96.LIN Bo-liang，QIAO Guo-hui.Iterative algorithm of railway network empty cars distribution based on restriction of route capacity［J］.China Railway Science，2008，29(1):93－96.

［6］黨建武.神經(jīng)網(wǎng)絡(luò)在鐵路空車調(diào)度問題中的應(yīng)用［J］.蘭州鐵道學(xué)院學(xué)報(bào)，1999，18(1):77－85.DANG Jian-wu.Application of neural networks to empty carriage scheduling in railway transportation［J］.Journal of Lanzhou Railway Institute，1999，18(1):77－85.

［7］紀(jì)嘉倫，林柏梁，李福志，等.用重心優(yōu)化方法求解鐵路網(wǎng)上空車調(diào)配問題［J］.鐵道學(xué)報(bào)，2001，23(3):109－113.JI Jia-lun，LIN Bo-linag，LI Fu-zhi，et al.Distribution of empty wagons on railway network by using the center－of－gravity－ optimization method［J］.Journal of the China Railway Society，2001，23(3):109－113.

［8］果鵬文，林柏梁，余 洋.大規(guī)模路網(wǎng)上空車調(diào)配的區(qū)段中心優(yōu)化法［J］.中國鐵道科學(xué)，2001，22(2):122－128.GUO Peng-wen，LIN Bo-liang，YU Yang.The section center optimization method of empty car adjustment on large － scale railway network［J］.China Railway Science，2001，22(2):122－128.

［9］Liu B.Stackelberg－Nash equilibrium for multilevel programming with multiple followers using genetic algorithms［J］.Computers and Mathematics with Applications，1998，36(7):79－89.