鐵路同類適盤貨物裝載方案優化研究

秦鑒

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

?

【交通運輸】

鐵路同類適盤貨物裝載方案優化研究

秦鑒

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

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

鐵路運輸；適盤貨物；裝載方案；優化

托盤運輸是鐵路集裝化運輸的重要內容，良好的貨物裝載方案會給鐵路集裝化運輸帶來更大的經濟效益。托盤裝載貨物和貨車裝載托盤集裝件均屬于三維裝箱問題的研究范疇，不同的是托盤一般沒有側面支撐保護，裝載時需要更加注意貨物堆碼的穩定性。現有的三維裝箱算法都是基于一定的假設進行的，這些算法在條件復雜的實際應用中會受到很大的限制。

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

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

1 問題描述

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

鑒于裝載問題的復雜性，本文對該問題做出以下假設：

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

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

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

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

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

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

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

2 數學模型

2.1 目標函數

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

(1)

(2)

2.2 約束條件

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

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

3 算法設計

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

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

3.1 貨物和托盤堆碼層數的確定

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

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

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

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

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

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

(3)

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

圖3 文獻中的二維布局結構示意圖Fig.3 Illustration of two-dimensional layout structure in the literature

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

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

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

圖4 改進的二維布局結構圖Fig.4 Structure chart of improved two-dimensional layout

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

表2 算法相關參數定義Table 2 Relevant parameter definition of the algorithm

改進的二維布局優化算法流程偽代碼如下：

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;記錄二維布局參數;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;記錄二維布局參數;

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

4 實例分析

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

實例描述為：某品牌方便面，外包裝尺寸為580 mm×325 mm×330 mm，重量為6 kg；托盤規格為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，轉向架中心距為11 700 mm，容積為116 m3，設計貨物的裝載方案。

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

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

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

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

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

5 結語

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

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

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

[7]那日薩，韓琪瑋，林正奎．三維多箱異構貨物裝載優化及其可視化[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]孫洪禮，王周敬．同類貨物集裝箱裝載問題的啟發式算法[J]．計算機應用與軟件，2011，28(4)：193-195．

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

[11]陳澤爽，何健明，林逵．多約束三維裝箱問題的混合遺傳算法[J]．現代計算機(專業版)，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]孟唯娟．托盤裝載優化系統的研究與開發[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]周康，何世偉，游玲君．鐵路適盤貨物裝載方案優化研究[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—)，男，助理工程師，研究方向為鐵路勘察設計。Email：1171432853@qq.com

U294.3

A