帶軸重約束貨物平衡裝載問題優(yōu)化研究

朱向

(湖南涉外經(jīng)濟(jì)學(xué)院管理學(xué)院，長(zhǎng)沙410205）

帶軸重約束貨物平衡裝載問題優(yōu)化研究

朱向*

(湖南涉外經(jīng)濟(jì)學(xué)院管理學(xué)院，長(zhǎng)沙410205）

針對(duì)考慮軸重約束集裝箱卡車貨物優(yōu)化裝載問題，建立以最大化裝載率和負(fù)重心偏離度為目標(biāo)，以平衡及軸重為約束條件的數(shù)學(xué)模型，設(shè)計(jì)改進(jìn)型貪婪自適應(yīng)搜索算法（IGASP）對(duì)問題進(jìn)行求解.算法先基于啟發(fā)式方法構(gòu)造布局方案，再結(jié)合重心邊界條件分析對(duì)獲得方案進(jìn)行可行性分析，對(duì)違反約束裝載率較高的方案提出了兩種重心調(diào)整的方法，進(jìn)而將有關(guān)過程融入貪婪自適應(yīng)搜索形成解的改進(jìn)機(jī)制實(shí)現(xiàn)問題優(yōu)化求解.基于現(xiàn)實(shí)算例的試驗(yàn)分析，證明所提方法求解帶軸重約束貨物平衡裝載問題具有較好效果.

物流工程；裝載布局；軸重約束；啟發(fā)式算法；重心平衡

1 引言

在公路貨運(yùn)中，為防止超載確保道路運(yùn)輸安全，國(guó)內(nèi)外相關(guān)法規(guī)對(duì)卡車最大裝載量做出限定，有的還規(guī)定相關(guān)車軸的最大承載能力，以滿足稱為軸重的車輛承載能力約束.企業(yè)為盡可能利用卡車裝載能力又防止出現(xiàn)超載，需對(duì)車廂內(nèi)貨物實(shí)施合理布局，在符合有關(guān)規(guī)定前提下最大化企業(yè)效益.軸重約束與裝載重心分布有關(guān)，即要求負(fù)載分布相對(duì)于各車軸承載能力平衡，這里將考慮這些因素的貨物裝載問題稱為帶軸重約束平衡裝載問題.

該類問題在貨物裝載領(lǐng)域近期有所關(guān)注，但相關(guān)研究仍顯不足.丘朝陽(yáng)對(duì)考慮裝載重量與軸重約束的裝載問題，設(shè)計(jì)基于整數(shù)規(guī)劃模型確定算法，適應(yīng)小規(guī)模問題快速求解[1].Li對(duì)多托盤布局于多卡車且考慮軸重約束裝載問題，建立了混合整數(shù)規(guī)劃模型[2].針對(duì)帶軸重約束單集裝箱裝載，Lim使用貪婪搜索完成物品布局，針對(duì)裝載率較高且違反相關(guān)約束方案，建立物品消去、層重排等整數(shù)規(guī)劃模型[3].裝載軟件Load Xpert提供了美國(guó)各車型裝載技術(shù)參數(shù)，實(shí)現(xiàn)軸重計(jì)算及生成合理裝載計(jì)劃，但難以判斷方案是否達(dá)到最優(yōu)[4].

2 問題描述及數(shù)學(xué)模型

2.1 問題描述

以單集裝箱卡車為裝載容器，待裝載貨物為一批類數(shù)為N、每類若干數(shù)量的長(zhǎng)方體、質(zhì)量均勻貨物，其擺放方向任意.帶軸重約束平衡裝載問題描述為：從N類貨物中選擇若干件進(jìn)行組合，以正交方式裝載于車內(nèi)廂，在貨物互不重疊、不超出車廂邊界及不違反車輛載重量和軸重約束的條件下，最大化裝載空間及其承載能力的利用，并使載荷分布盡量平衡.

2.2 數(shù)學(xué)模型

針對(duì)兩軸型集裝箱卡車貨物裝載，以其左后下角為坐標(biāo)原點(diǎn)，底板為X-Y平面，建立空間直角坐標(biāo)系：X軸平行于箱子縱中心線，方向從左向右；Y軸沿箱端，方向從后向前；Z軸垂直于底平面向上.定義變量：

P={P1,P2,…,PN}={pij|pij∈Pi,i=1,2,…,N,j=1, 2,…,nN}——N類裝載貨物集合；

aij,bij,hij,qij,vij——貨物pij的長(zhǎng)、寬、高、重量和體積；

uij=1或0—— 若 貨 物pij已 裝 箱 取1，否 則取0；

D——裝載合重心縱向位置偏離理想位置的距離；

建立數(shù)學(xué)模型：

式（1）中前兩部分為最大化車廂空間與載重利用，第三部分最大化負(fù)荷重心負(fù)偏離度，，權(quán)重系數(shù)α,β,λ根據(jù)貨物密度性質(zhì)選取.

式（2）～式（4）通過貨物及箱子尺寸、質(zhì)心位置及重心坐標(biāo)表示裝載物不超出箱子邊界；式（5）～式（7）以任意兩件貨物重心位置來表示相鄰各貨物間互不交叉；式（8）和式（9）為由力矩平衡原理推出的軸重約束；式（10）和式（11）為允許載重量和有效容積約束；式（12）為裝載貨物總數(shù)約束.

3 求解算法

貪婪自適應(yīng)搜索（Greedy Adaptive SearchProcedure,GASP）是一種融合貪婪算法和學(xué)習(xí)機(jī)制的高效搜索算法，可對(duì)全局空間進(jìn)行快速搜索[5].本文結(jié)合帶軸重約束裝載問題特點(diǎn)，將啟發(fā)式構(gòu)造法融入GASP算法，設(shè)計(jì)改進(jìn)型貪婪搜索算法IGASP對(duì)問題進(jìn)行求解：先用新極點(diǎn)法進(jìn)行布局方案構(gòu)造，再結(jié)合重心邊界條件進(jìn)行解的可行性分析和平衡改善，進(jìn)而設(shè)計(jì)改進(jìn)機(jī)制實(shí)現(xiàn)問題優(yōu)化求解.算法過程如圖1所示.

圖1 IGASP算法實(shí)施過程Fig.1 General scheme of the IGASP

3.1 布局方案構(gòu)造

按構(gòu)造布置法思想，布局過程將裝載對(duì)象和裝載空間的選擇結(jié)合起來，在啟發(fā)式規(guī)則引導(dǎo)下將貨物逐個(gè)裝入并構(gòu)造出解來.

（1）裝載貨物排序.

為了提高空間利用率，一般體積大、重量重的貨物先裝，體積小、重量輕的后裝，通過基于體積與重量聚簇排序方法實(shí)現(xiàn).

先按貨物體積聚簇，設(shè)Vmin與Vmax代表聚類區(qū)間上下極值，整個(gè)聚簇區(qū)間分為若干簇，每簇對(duì)應(yīng)區(qū)間為上下極值差的θ100，θ∈[1,100]，每簇對(duì)應(yīng)區(qū)間為Vi(θ) :

將所有簇按標(biāo)號(hào)i降序排列，再將簇內(nèi)貨物按重量降序排列，由此得到貨物序列.

（2）裝載位置選擇.

在一般極點(diǎn)法[6]基礎(chǔ)上，結(jié)合重量因素以對(duì)稱布局形式進(jìn)行裝載位置選擇.如圖2所示，當(dāng)長(zhǎng)、寬和高為lk、wk和hk貨物k放置于坐標(biāo)為（xk,yk,zk）的左后下角時(shí)，產(chǎn)生多個(gè)用于放置貨物的新的極點(diǎn)，它們由為坐標(biāo)為（xk+lk,yk,zk）、（xk,yk+wk,zk）和（xk,yk,zk+hk）的點(diǎn)投影到箱壁或鄰近貨物形成（圖2中實(shí)心點(diǎn)）.

圖2 極點(diǎn)形成過程Fig.2 The production of the EPs

因涉及軸重約束，結(jié)合力矩平衡原理定裝載位置及擺放方向.首先，記錄各裝載物重心至理想點(diǎn)所在垂面距離，并計(jì)算貨物重力相對(duì)垂面的力矩（跨垂面貨物按長(zhǎng)度比例分?jǐn)偅?，將垂面兩邊貨物產(chǎn)生力矩累加，每次將貨物分配至力矩和較小一邊裝載，實(shí)現(xiàn)水平方向平衡.其次，當(dāng)兩邊力矩值相等且存在多個(gè)極點(diǎn)時(shí)，以剩余空間最優(yōu)利用[6]選擇放置位置與方向.

（3）布局方案生成.

以貪婪方式對(duì)貨物序列中對(duì)象選擇極點(diǎn)裝入，對(duì)現(xiàn)有裝載模式中都找不到適合裝載位置的貨物先給予放棄，考慮序列中的下一對(duì)象，直至車廂裝滿或全部貨物分配裝入為止，得到完整布局方案.

3.2 可行性分析及重心調(diào)整

在初始布局基礎(chǔ)上，結(jié)合車廂裝載量與重心分布對(duì)車輛載重量和軸重等平衡裝載因素進(jìn)行分析，判定獲得方案是否可行；對(duì)位于邊界附近且裝載率高的非可行解，通過重心調(diào)整看能否使其滿足約束，以提高求解的質(zhì)量和效率.

（1）可行性分析.

基于建立坐標(biāo)-系進(jìn)-行受力及力矩平衡分析（如圖3所示，其中N1＜N2）：當(dāng)裝載合重心位于前軸位-置時(shí)，車輛最大承載重量為前軸最大承載重量N1；當(dāng)-合重心位于底板中心時(shí)，車輛可承載最大重量為2N1；-當(dāng)合-重心位于理想點(diǎn)c'時(shí)，可裝載最大重量達(dá)到N1-+N2；當(dāng)合重心位于后軸位置時(shí)，最大承載重量為-N-2.因此-，考慮軸重約束的車輛裝載重量一般在[N1, N1+N2]范圍內(nèi).

對(duì)于區(qū)間內(nèi)各裝載量的布局方案是否滿足軸重約束，還需結(jié)合重心位置，計(jì)算重心邊界條件來判定：

①若合重心位置在(0, c')內(nèi)時(shí)，由力矩平衡

②若合重心位置在(c', L)內(nèi)時(shí)，由力矩平衡

③若合重心位于點(diǎn)c'時(shí)，可裝載最大重量

圖3 重心邊界條件分析Fig.3 Analysis of boundary conditions of the CG

將裝載方案的重心位置與計(jì)算的邊界值對(duì)照，判斷方案是否滿足約束，并作為移動(dòng)或交換貨物實(shí)現(xiàn)重心調(diào)整的依據(jù)：當(dāng)裝載重心位于理想重心位置Xc′時(shí)，為理想的載荷分布，可實(shí)現(xiàn)最大承載量；當(dāng)計(jì)算確定合重心位于邊界Xl左邊時(shí)（圖3中Q2），應(yīng)通過貨物交換或移動(dòng)使重心向右移，且至少移至邊界Xl，使之靠近理想位置Xc′；當(dāng)合重心位于邊界Xr右邊（圖3中Q5），應(yīng)通過交換或移動(dòng)使重心向左靠近位置Xc′調(diào)整，且至少移至邊界Xr.

（2）重心調(diào)整及平衡改善.

由構(gòu)造法產(chǎn)生的裝載率高且僅違反軸重違反約束的方案，分析重心邊界條件與實(shí)際重心位置關(guān)系，結(jié)合重心移動(dòng)規(guī)則，通過貨物交換或移動(dòng)使方案具有可行性或改善重量分布.

①貨物交換.

對(duì)裝載率較高而違反軸重約束方案，若合重心位置靠近邊界，優(yōu)先考慮交換方法.

Step 1輸入違反軸重約束的裝載方案P.

Step 2分析位于重心位置兩邊貨物單元（個(gè)體或集合）的形狀與比重，將形狀相同或近似、比重存在差異的單元?dú)w入不同集合，按比重對(duì)各集合中單元以降序排列，比重相同單元中只保留一個(gè)，得到相應(yīng)集合序列UI(I=1,2,…).

Step 3計(jì)算UI中各單元重心至理想位置Xc′的距離，將其與單元比重相乘，按乘積降序排列UI中各單元，乘積相同單元只保留一個(gè)，得到新集合序列EI(I=1,2,…).

Step 4若EI≠?，分別從各集合EI(I=1,2,…)中選擇最大與最小的單元實(shí)施位置交換，記交換后方案為P′；否則，轉(zhuǎn)step6.

Step 5將各集合EI(I=1,2,…)中已經(jīng)歷交換的單元消去，轉(zhuǎn)step4.

Step 6輸出方案P′及新合重心位置.

②貨物移動(dòng).

若方案中貨物間存在空隙，通過貨物移動(dòng)滿足約束或改善重量分布.如圖4所示，虛線框所圍區(qū)域Di為貨物i可移動(dòng)范圍，實(shí)心原點(diǎn)為合重心理想位置.

圖4 貨物移動(dòng)示例Fig.4 An example of the moving of the freights

Step 1輸入裝載方案P，設(shè)任意裝載貨物j的重心為→rCMj，裝載貨物總質(zhì)量為，貨物合重心為，重心理想位置為→r′CM.

Step 2分析初始方案貨物及空隙分布，確定適合移動(dòng)貨物i及其可移動(dòng)范圍Di.

Step 3計(jì)算合重心從當(dāng)前位置→rCM移至或接近理想位置→r′CM，i的重心從當(dāng)前位置→rCMi移至新位置的坐標(biāo)

Step 4確定i移動(dòng)的目標(biāo)位置的坐標(biāo)

Step 5當(dāng)→r′i∈Di時(shí)，將貨物i從→r′移至→r′i（如圖4（a））.

Step 6當(dāng)→r′i?Di，將i移至最接近于→r′i的中間位置→r″（如圖4（b））.

Step 7轉(zhuǎn)step2確定新分布條件下i繼續(xù)調(diào)整，直至合重心不再改進(jìn).

Step 8輸出調(diào)整后方案P′及新合重心位置.

3.3 解的改進(jìn)

以迭代方式重排貨物序列,結(jié)合構(gòu)造法及平衡調(diào)整進(jìn)行新布局，在更大范圍搜索解.

Step 1輸入初始解裝載序列各貨物分值si；設(shè)分?jǐn)?shù)修改次數(shù)t初始值為1，分?jǐn)?shù)修改總循環(huán)次數(shù)Nt；分?jǐn)?shù)更改比重值為m，位置交換影響因子k，k的初值為1最大值為km.

Step 2由貨物重量和體積，確定初始序列中排序不變的貨物序列U及需重排的貨物序列Q.

Step 3當(dāng)k＜km時(shí)，計(jì)算分?jǐn)?shù)更改比重值m=sˉ(km-k)p；當(dāng)k≥km時(shí)，重置k為1.

Step 4修改Q中貨物序列分值si：前半部分改為si=si(1-m)，后半部分為si=si(1+m).

Step 5將經(jīng)分?jǐn)?shù)修改及重排后形成新貨物序列Qˉ合并至保留貨物序列U，組成新完整序列.

Step 6按照構(gòu)造法布局，并按平衡調(diào)整方法改善重心分布.

Step 7若調(diào)整后的方案可行，計(jì)算新方案目標(biāo)函數(shù)值并轉(zhuǎn)step9；否則轉(zhuǎn)step8.

Step 8按文獻(xiàn)[3]方法消去部分貨物，通過平衡調(diào)整策略改善重心，計(jì)算新方案目標(biāo)函數(shù)值.

Step 9當(dāng)t≤Nt時(shí)，令t=t+1，k=k+1，并轉(zhuǎn)step3.

Step 10將最大目標(biāo)函數(shù)值對(duì)應(yīng)方案作為最優(yōu)解輸出.

4 算例

為驗(yàn)證IGASP算法效果，任意選取某貨運(yùn)企業(yè)批次作業(yè)數(shù)據(jù)進(jìn)行試驗(yàn)，并將測(cè)試結(jié)果與企業(yè)實(shí)際裝載的方案對(duì)比.該批貨物數(shù)據(jù)如表1所示，裝載使用ISO-20標(biāo)準(zhǔn)集裝箱，長(zhǎng)、寬、高為：587 cm，233 cm和220 cm，允許最大載重量為28 080 kg，所用車型前、后車軸位置最大承載力-N1、-N2=9 070 kg，車輛標(biāo)記載重量Qˉ為18 140 kg.

表1 貨物數(shù)據(jù)表Table 2Data of the freights

計(jì)算待裝貨物的平均比重值，其比車廂容許裝載的重容比略大，則貨物為比重相對(duì)較大的一類對(duì)象，和容積利用相比，載重量更易接近其容許上限，裝載時(shí)可優(yōu)先考慮載重量的利用，則β的取值應(yīng)比α稍大；布局總要求是提高裝載率的基礎(chǔ)上達(dá)到重量均衡分布，目標(biāo)函數(shù)第三部分使方案滿足平衡條件并起加速搜索作用，則λ須取一定數(shù)值但比α和β小.由此確定權(quán)重取值范圍α∈[0.2,0.5]，β∈[0.3,0.6]，λ∈[0.1,0.3]，再結(jié)合上述要求進(jìn)行取值組合.權(quán)重為十分位時(shí)總組合數(shù)不超過9，組合密度還可根據(jù)具體試驗(yàn)結(jié)果調(diào)整.

表2 生成的裝載方案Table 2The loading scheme generated for the case

表2 生成的裝載方案（續(xù)）Table 2The loading scheme generated for the case（Continued）

以C++語(yǔ)言對(duì)IGASP算法編程，按文獻(xiàn)[5]確定改進(jìn)算法有關(guān)參數(shù)，使用實(shí)例數(shù)據(jù)試驗(yàn)，計(jì)算不同權(quán)重組合下最佳布局方案及其目標(biāo)函數(shù)值，取目標(biāo)值最大的方案為最優(yōu)布局方案，對(duì)應(yīng)權(quán)重取值α=0.3，β=0.4，λ=0.3.該方案中貨物配裝情況及布局位置如表2所示，裝載方案技術(shù)指標(biāo)如表3所示.

表3 裝載方案技術(shù)指標(biāo)對(duì)比Table 3Comparison of the indicators of the results for the two approaches

對(duì)重大件貨物的裝載，企業(yè)在實(shí)際操作中先裝大件貨物再充填小件貨物，并結(jié)合邊、角布局等經(jīng)驗(yàn)規(guī)則進(jìn)行.將企業(yè)現(xiàn)實(shí)裝載方案技術(shù)指標(biāo)列于表3，通過對(duì)比看出無論是裝載率還是平衡水平，求得方案布局效果都比現(xiàn)實(shí)裝載方案有明顯提升：現(xiàn)實(shí)方案有第3類1件和第7類2件貨物未獲裝載，而IGASP生成方案只第7類1件貨物未獲裝載；生成方案合重心實(shí)際縱向偏移也比現(xiàn)實(shí)裝載方案的小，兩者的合重心高及橫向偏移基本接近，說明IGASP在滿足軸重約束且達(dá)到較高裝載率的條件下很好實(shí)現(xiàn)了平衡裝載的要求.

5 研究結(jié)論

針對(duì)帶軸重約束集裝箱卡車貨物裝載問題，構(gòu)建包含裝載率、重心偏離目標(biāo)及軸重約束的數(shù)學(xué)模型；設(shè)計(jì)改進(jìn)極點(diǎn)法構(gòu)造布局方案，結(jié)合裝載重心平衡條件，提出布局方案可行性檢驗(yàn)及對(duì)非可行方案調(diào)整方法；將有關(guān)過程融入貪婪自適應(yīng)搜索機(jī)制，實(shí)現(xiàn)最優(yōu)方案搜索.通過基于現(xiàn)實(shí)算例的試驗(yàn)分析，證明了所提方法求解帶軸重約束的貨物裝載問題具有有效性.如何結(jié)合軸重等約束，進(jìn)一步完善貨物平衡裝載布局方法實(shí)現(xiàn)問題更高效求解值得深入研究.

[1]丘朝陽(yáng).考慮重量約束的集裝箱裝載問題[D].廣州：華南理工大學(xué)，2010.[QIU C Y.Container loading problem of weight limit[D].Guangzhou:South China University of Technology,2010.]

[2]Li D.A truck loading problem with axle weight consideration[D].New York:Binghamton University, 2010.

[3]Lim A,Ma H.The single container loading problem with axleweightconstraints[J].InternationalJournalof Production Economics,2013,144(1):358-369.

[4]CIE-TECH INC.LoadXpert[EB/OL],(2010-1-8) [2010-3-10].http://www.loadxpert.com.

[5]PerboliG,CrainicT.An efficient meta-heuristic formulti-dimensionalmulti-container packing[C]// Proceedings of seventh annual IEEE Conference on Automation Science and Engineering.Piscataway,N J: IEEE Press,2011:563-568.

[6]Crainic T,Perboli G.Extreme point-based heuristics for three-dimensional bin packing[J].Informs Journal on Computing,2008,20(3):368-384.

Optimization of Freights Loading Problem with Balancing and Axle Weight Constraints

ZHU Xiang
(School of Management,Hunan International Economics University，Changsha 410205,China)

To maximize of the utilization of the car capacity and the balancing level of the placement,an integer formulation model and an improved greedy adaptive search procedure(IGASP)are presented for the optimization of freights loading problem with balancing and axle weight constraints.Firstly,the algorithm use the designed construction heuristic to product the placements.Then,based on the analysis of boundary conditions of the center gravity,a feasibility analysis is introduced for the gained solutions,and two improvement procedures are designed for the ones with higher use rate but violate the axle weight constraints.Integrating these processes into the GASP,an improving procedure is further designed to search the optimal solution for the problem.The test with real world data demonstrates that the proposed algorithm is effective in solving the special freights loading problem with balancing and axle weight constraints.

logistics engineering;loading and layout;axle weight constraints;heuristic;balancing condition

1009-6744（2015）05-0164-08

U492.3

A

2015-05-13

2015-08-18錄用日期：2015-08-27

國(guó)家自然科學(xué)基金研究項(xiàng)目（71371193）.

朱向（1976-），男，湖南長(zhǎng)沙人，講師，博士. ＊

cszhuxiang@163.com