秦鑒

(中鐵第一勘察設(shè)計院集團有限公司，陜西 西安 710043)

?

【交通運輸】

鐵路同類適盤貨物裝載方案優(yōu)化研究

秦鑒

(中鐵第一勘察設(shè)計院集團有限公司，陜西 西安 710043)

結(jié)合鐵路貨物裝載約束條件，構(gòu)建了使用托盤的同類長方體貨物鐵路貨車裝載優(yōu)化模型，首先提出了改進二維布局優(yōu)化算法求解托盤在車廂底面的布局方式，再確定托盤貨件在車廂內(nèi)的最佳堆碼層數(shù)，得到貨物的裝車優(yōu)化方案。實例分析結(jié)果表明，該算法是一種求解鐵路同類適盤貨物裝載問題的有效方法。

鐵路運輸；適盤貨物；裝載方案；優(yōu)化

托盤運輸是鐵路集裝化運輸?shù)闹匾獌?nèi)容，良好的貨物裝載方案會給鐵路集裝化運輸帶來更大的經(jīng)濟效益。托盤裝載貨物和貨車裝載托盤集裝件均屬于三維裝箱問題的研究范疇，不同的是托盤一般沒有側(cè)面支撐保護，裝載時需要更加注意貨物堆碼的穩(wěn)定性?，F(xiàn)有的三維裝箱算法都是基于一定的假設(shè)進行的，這些算法在條件復(fù)雜的實際應(yīng)用中會受到很大的限制。

解決三維裝箱問題主要有基于啟發(fā)式算法和遺傳算法兩類比較有代表性的方法。George等[1]首次提出了三維裝箱問題的啟發(fā)式算法，并引入了“層”的概念。Bischoff等[2]對多種基于“層”的算法進行了總結(jié)和比較，得出貨物的種類數(shù)影響裝箱結(jié)果的好壞的結(jié)論。Pisinger[3]在墻壁支撐的理論基礎(chǔ)上提出了一種新的基于“層”的啟發(fā)式算法，該算法雖然提高了裝載效率，但是有時候上層貨物沒有足夠的支撐面，貨物整體結(jié)構(gòu)的穩(wěn)定性較差。Eley[4]提出了基于同類貨物塊的啟發(fā)式算法，該算法的思想是首先將相同的貨物組成貨物塊，再通過貨物塊組合得到完整的布局方案。劉勝等[5]提出了求解三維裝箱問題的啟發(fā)式正交二叉樹搜索算法。張德富等[6]提出了一種求解三維裝箱問題的多層啟發(fā)式搜索算法。那日薩等[7]提出了一種基于“塊”和“空間”的啟發(fā)式搜索算法。Gehring等[8]首次將遺傳算法應(yīng)用到了三維裝箱問題的求解當中，為后來遺傳算法求解裝箱問題奠定了理論基礎(chǔ)。孫洪禮等[9]提出了基于空間分解的包含啟發(fā)式規(guī)則的混合遺傳算法，對弱異類貨物裝箱方案進行求解，啟發(fā)式規(guī)則應(yīng)用在遺傳算法的解碼過程中。朱向等[10]針對帶重心平衡約束的三維裝箱問題，基于框架式布局思想，設(shè)計雙層混合遺傳算法進行求解。陳澤爽等[11]提出了多約束三維裝箱問題的混合遺傳算法。Kucuk等[12]利用混合進化算法求解三維裝箱問題，并實現(xiàn)了貨物在集裝箱內(nèi)的可視化。孟唯娟[13]對同類貨物的托盤裝箱問題進行了研究，并利用VC6.0開發(fā)工具設(shè)計托盤裝載優(yōu)化軟件。

適盤貨物裝車問題涉及貨物在托盤上堆碼和托盤集裝件在貨車車廂內(nèi)堆碼兩個過程，需要綜合考慮兩個階段的裝載方案，比一般的同類物品三維裝箱問題更加復(fù)雜，需要考慮更多的約束條件。目前，國內(nèi)對鐵路適盤貨物裝車問題的研究相對較少，缺乏成熟的算法和相應(yīng)的商業(yè)軟件。本文結(jié)合鐵路貨運中的實際約束條件，構(gòu)建了同類長方體適盤貨物的裝車優(yōu)化模型，并給出了相應(yīng)的求解算法，為下一步鐵路集裝化裝載軟件的開發(fā)提供理論基礎(chǔ)。

1 問題描述

同類長方體適盤貨物鐵路貨車裝載優(yōu)化問題可以描述為：將一批數(shù)量較大的相同品類的長方體貨物裝載到托盤上，并將托盤集裝件裝車，在滿足鐵路貨物裝車約束條件下，貨車載貨數(shù)量最多或者載貨空間利用率最大。

鑒于裝載問題的復(fù)雜性，本文對該問題做出以下假設(shè)：

(1)所有貨物或者貨物包裝均為長方體，并且具有相同的尺寸與重量；

(2)托盤和鐵路貨車都簡化為長方體；

(3)貨物或者貨物包裝有側(cè)面和底面的區(qū)分，只有底面可以作為支撐面；

(4)托盤集裝件放置方向與貨車車廂面平行或者正交；

(5)忽略貨物間的擠壓變形對裝載的影響；

(6)長方體貨物為均質(zhì)貨物，重心在其幾何中心；

(7)貨物屬于同一貨主，并且到達同一目的地。

2 數(shù)學模型

2.1 目標函數(shù)

該問題是一個多變量組合優(yōu)化問題，優(yōu)化目標定義為：在滿足鐵路貨物裝車約束條件下，貨車載貨數(shù)量最多或者載貨空間利用率最大。貨車載貨總數(shù)量與貨物在托盤上的布局、托盤集裝件在貨車車廂內(nèi)的布局、托盤集裝件在車廂內(nèi)的堆碼層數(shù)和貨物在托盤上的堆碼層數(shù)有關(guān)。選擇貨車載貨數(shù)量最大和載貨空間利用率最大為優(yōu)化目標的目標函數(shù)可分別表示為：

(1)

(2)

2.2 約束條件

該問題考慮的約束條件及其描述見表1。

表1 模型約束條件及描述Table 1 Model constraint conditions and description

3 算法設(shè)計

適盤貨物裝車問題需要確定貨物在托盤上的堆碼層數(shù)、托盤集裝件在車廂內(nèi)的堆碼層數(shù)、貨物在托盤平面的布局方案和托盤集裝件在車廂底面的布局方案。托盤和貨物最佳堆碼層數(shù)與車廂高度、重車重心高、托盤貨件重心高以及貨車和托盤最大載重量等諸多因素有關(guān)，在設(shè)計算法時應(yīng)對影響因素進行劃分，分階段進行求解。貨物在托盤平面和托盤集裝件在車廂底面的布局方案則利用改進的二維局部優(yōu)化算法求解。

圖1 貨車車廂裝載托盤集裝件剖面圖Fig.1 Section diagram of pallet racking loaded boxcar

3.1 貨物和托盤堆碼層數(shù)的確定

貨車車廂堆碼托盤集裝件示意圖如圖1所示，當車廂高度、托盤高度和貨物高度一定時，在不考慮其他裝車約束條件的情況下，貨物的最大堆碼層數(shù)和托盤堆碼層數(shù)有關(guān)，當確定托盤堆碼層數(shù)之后，貨物的最大堆碼層數(shù)也就確定了。在車廂高度內(nèi)，托盤堆碼層數(shù)越多，貨物可利用堆碼高度就越小，所以減少托盤堆碼層數(shù)有機會增加貨物堆碼層數(shù)。

但是托盤有最大承載能力約束和重心高約束，貨車有最大載重量約束和重車重心高約束，貨物有最大抗壓強度的約束，這些約束條件影響著貨物實際最大堆碼層數(shù)，貨物在托盤上的最佳堆碼層數(shù)由這些約束條件綜合決定。

假設(shè)車廂內(nèi)堆碼t(t≥1)層托盤，T表示車廂最大允許堆碼托盤貨件層數(shù)，首先考慮托盤的重心高約束和車廂高度約束，計算出貨物在托盤上的初始堆碼方案，再檢驗是否滿足托盤最大載重量、貨車最大載重量、重車重心高和貨物最大堆碼強度等約束條件，如不滿足，調(diào)整貨物堆碼層數(shù)，從上往下逐層減少，直到滿足約束條件為止。同理可計算出t=1,2,…，T時的貨物堆碼層數(shù)方案，選擇貨車載貨數(shù)量最多的方案作為最佳方案；當貨車載貨數(shù)量相同時，選擇使用托盤數(shù)量最少的方案作為最佳方案。算法流程詳見圖2。

圖2 貨物裝載層數(shù)確定算法流程圖Fig.2 Flowchart of determination algorithm of goods loading layers

3.2 貨物和托盤二維布局方案的確定

貨物在托盤底面放置時應(yīng)盡可能地鋪滿托盤底面，使得托盤底面積利用率最大；托盤集裝件也需要盡可能地鋪滿貨車底面。這就是矩形的二維布局優(yōu)化問題：在一個已知長和寬的大矩形中盡可能地擺放已知長和寬的相同的小矩形，確定一種擺放方案使得平面利用率最大。假設(shè)大矩形的長和寬分別為L和W，小矩形的長和寬分別為l和w，大矩形中擺放的小矩形數(shù)量為n，S為平面利用率，則該問題的目標函數(shù)可以表示為：

(3)

矩形的二維布局優(yōu)化算法較多，文獻[14]中提出了一種比較簡潔有效的二維布局結(jié)構(gòu)圖，該結(jié)構(gòu)圖將矩形平面分成了4塊進行布局，本文將這4塊分別稱為block1、block2、block3和block4，如圖3所示。該算法將圖中的a、b、d作為基礎(chǔ)變量，從小到大進行變化，通過各塊之間的結(jié)構(gòu)關(guān)系計算圖中其他參數(shù)值。當a、b、d的值確定以后，其他參數(shù)c、e、f、g、h的值都可以相應(yīng)地計算出來，這樣就可以確定整個平面的布局。

圖3 文獻中的二維布局結(jié)構(gòu)示意圖Fig.3 Illustration of two-dimensional layout structure in the literature

本文對WANG等[14]文獻中的二維布局結(jié)構(gòu)圖進行改進，將a、b、d、e同時作為基礎(chǔ)變量進行變化，e不再是通過關(guān)系式直接計算出來的靜態(tài)值，這樣擴大了二維布局問題解的空間。根據(jù)block1和block2的寬度的不同，布局結(jié)構(gòu)分為兩種情況：

(1)當block1的寬度小于block2的寬度時，e從?cw/l」到?L/l」進行變化。當el≤cw時，g的取值為?(L-cw)/w」；當el>cw時，g的取值為?(L-el)/w」，二維布局結(jié)構(gòu)圖如圖4a所示。

(2)當block1的寬度大于block2的寬度時，e從0到?cw/l」進行變化，g的取值為?(L-el)/w」，二維布局結(jié)構(gòu)圖如圖4b所示。

圖4 改進的二維布局結(jié)構(gòu)圖Fig.4 Structure chart of improved two-dimensional layout

在改進的二維布局結(jié)構(gòu)圖中，矩形塊block1和block4緊貼大矩形的左側(cè)邊線擺放，block2和block3則緊貼大矩形的右側(cè)邊線擺放。在參數(shù)e變化過程中，大矩形中間可能會出現(xiàn)矩形塊block5，對于block5繼續(xù)利用本算法求解布局結(jié)構(gòu)，形成循環(huán)嵌套，得到最終的布局結(jié)構(gòu)。為方便描述，對算法中的符號定義見表2。

表2 算法相關(guān)參數(shù)定義Table 2 Relevant parameter definition of the algorithm

改進的二維布局優(yōu)化算法流程偽代碼如下：

ReadL，W，l，wamax←int(L/l);bmax←int(W/w);nlast←amax*bmax;ForbFrom0tobmaxstep1h←int((W-b*w)/l);ForaFrom0toamaxstep1c←int((L-a*l)/w);FordFrom0toint(W/l)step1f←int((W-d*l)/w);Ifd*lnlastThennlast←n0;記錄二維布局參數(shù);ElseForeFromint(c*w/l)toint(L/l)step1Ifc*w>e*lTheng←int((L-c*w)/w);Elseg←int((L-e*l)/w);n1←a*b+c*d+e*f+g*h;計算L'和W';ReadL'，W'計算n2;n0←n1+n2;Ifn0>nlastThennlast←n0;記錄二維布局參數(shù);

在改進的二維布局優(yōu)化算法中，當e=?cw/l」，并且gw≤al時，該算法的計算結(jié)果與文獻[14]相同。所以，本文提出的改進的二維布局優(yōu)化算法是對文獻[14]中算法的一種擴展。

4 實例分析

周康等[15]提出了規(guī)則貨物包裝的托盤裝載優(yōu)化方案，并進行了實例計算。本文利用C#編程語言實現(xiàn)了同類直方體貨物托盤裝載優(yōu)化算法，并與文獻中結(jié)果比較，驗證算法的有效性。

實例描述為：某品牌方便面，外包裝尺寸為580 mm×325 mm×330 mm，重量為6 kg；托盤規(guī)格為1 200 mm×1 000 mm×150 mm，重量為15 kg；貨車車型為P64，尺寸為15 500 mm×2 796 mm×2 705 mm，自重25.4 t，載重58 t，空車重心高為1 310 mm，地板面至軌面高為1 143 mm，轉(zhuǎn)向架中心距為11 700 mm，容積為116 m3，設(shè)計貨物的裝載方案。

利用本文提出的裝載算法求得的裝載信息見表3，托盤裝載貨物的二維布局圖見圖5；貨車裝載托盤集裝件二維俯視圖見圖6，側(cè)視圖見圖7。

表3 裝載計算結(jié)果信息表Table 3 Information table of loading calculation result

圖6 貨車裝載托盤貨件俯視圖Fig.6 Top view of pallet loaded boxcar

圖7 貨車裝載托盤貨件側(cè)視圖Fig.7 Side view of pallet loaded boxcar

文獻[15]在未考慮貨物裝車后重心橫、縱向合理位置和重車重心等約束條件下，計算出貨車最多裝載貨物1 080件，比本文算法的計算結(jié)果少180件，表明了本文算法在計算同類直方體貨物的裝載方案時能得到更優(yōu)結(jié)果。同時，本文提出的裝載算法具有一般性，能夠很好地處理非標準尺寸包裝件的裝載問題，并且在計算過程中考慮了貨物重心位置等約束條件，保證了裝載方案的可行性。

5 結(jié)語

本文討論了同類直方體適盤貨物的裝車優(yōu)化問題，結(jié)合鐵路貨運實際約束條件，綜合考慮貨物在托盤上堆碼和托盤集裝件在車廂內(nèi)堆碼兩個過程設(shè)計裝載優(yōu)化算法。在模型約束條件方面，除了本文所考慮的約束條件外，還包括其他實際運輸中的約束，比如貨物屬于不同的貨主、到達不同的目的地、有不同的卸貨順序、中途取貨、使用不同類型托盤混裝以及避免貨車車輛集重裝載等；同時，適盤貨物除了包裝規(guī)則的直方體貨物，還會涉及到一些非規(guī)則包裝的貨物，裝載時有時也會有貨物拼裝的情況。這些問題的裝載優(yōu)化算法有待于今后進一步研究，然后集成開發(fā)鐵路托盤集裝裝載軟件，并進行三維顯示。

[1]GEORGE J A, ROBINSON D F. A heuristic for packing boxes into a container[J]. Computers & Operations Research, 1980, 7(3): 147-156.

[2]BISCHOFF EE, MARRIOTT M D. A comparative evaluation of heuristics for container loading[J]. European Journal of Operational Research, 1990, 44(2): 267-276.

[3]PISINGER D. Heuristics for the container loading problem[J]. European Journal of Operational Research, 2002, 141(2): 382-392.

[4]ELEY M. Solving container loading problems by block arrangement[J]. European Journal of Operational Research, 2002, 141(2): 393-409.

[5]劉勝，朱鳳華，呂宜生，等．求解三維裝箱問題的啟發(fā)式正交二叉樹搜索算法[J]．計算機學報，2015，38(8)：1530-1542．

[6]張德富，彭煜，張麗麗．求解三維裝箱問題的多層啟發(fā)式搜索算法[J]．計算機學報，2012，35(12)：2553-2560．

[7]那日薩，韓琪瑋，林正奎．三維多箱異構(gòu)貨物裝載優(yōu)化及其可視化[J]．運籌與管理，2015，24(4)：76-82．

[8]GEHRING H ， BORFELDT A. A genetic algorithm for solving the container loading problem[J]. International Transaction Operational Research, 1997, 4(5/6):401-418.

[9]孫洪禮，王周敬．同類貨物集裝箱裝載問題的啟發(fā)式算法[J]．計算機應(yīng)用與軟件，2011，28(4)：193-195．

[10]朱向，雷定猷．帶平衡約束三維裝箱問題的雙層混合遺傳算法[J]．交通運輸系統(tǒng)工程與信息，2015，15(2)：203-209．

[11]陳澤爽，何健明，林逵．多約束三維裝箱問題的混合遺傳算法[J]．現(xiàn)代計算機(專業(yè)版)，2011 (1)：14-19．

[12]KUCUK M, ERMIS M. A new hybrid evolutionary algorithm for three-dimensional packing problems[C]// 2010 IEEE International Conference on Systerns Man and Cybernetics (SMC). IEEE, 2010: 4029-4034.DOI:10.1109/ICSMC.2010.5642203.

[13]孟唯娟．托盤裝載優(yōu)化系統(tǒng)的研究與開發(fā)[D]．天津：天津科技大學，2010．

[14]WANG Z J, LI K W. Layer-layout-based heuristics for loading homogeneous items into a single container[J]. Journal of Zhejiang University SCIENCE A, 2007, 8(12): 1944-1952.

[15]周康，何世偉，游玲君．鐵路適盤貨物裝載方案優(yōu)化研究[J]．鐵道貨運，2013 (9)：52-57．

Optimization of railway pallet-suited freight loading scheme

QIN Jian

(China Railway First Survey and Design Institute Group Ltd., Xi′an 710043, China)

∶We construct an optimization model for similar rectangular freights loaded freight trains with pallets based on railway freight loading constraints. We initially solve pallets layout of carriage bottom with improved two-dimensional layout optimization algorithm. We further determine optimal stacking pallet layers in a carriage, and obtain optimal loading scheme. Instance analytical results show that the model is effective for solving railway similar pallet applied freight loading problem.

∶railway transportation; pallet-suited freight; loading scheme; optimization

10.3976/j.issn.1002-4026.2016.05.017

2016-01-09

秦鑒(1990—)，男，助理工程師，研究方向為鐵路勘察設(shè)計。Email：1171432853@qq.com

U294.3

A