兼顧重心的最密堆積算法設(shè)計(jì)與實(shí)現(xiàn)

王紅娟 李航碩 葉松揚(yáng) 李儒林 肖洋洋

摘 ?要：該文針對(duì)目前物流行業(yè)迫切需要解決的貨物存儲(chǔ)空間利用率不高，長(zhǎng)途貨運(yùn)過程中因堆疊方式不當(dāng)造成貨車重心不穩(wěn)而存在一系列安全隱患等問題，提出一種兼顧重心的最密堆積算法。將存儲(chǔ)空間分層，通過掃描得到貨物體積、質(zhì)量、是否有特殊需求等參數(shù)，綜合G2LA重心算法及同、異構(gòu)貨物二維、三維空間最密堆積算法對(duì)貨物堆積方式進(jìn)行設(shè)計(jì)，以達(dá)到在保證運(yùn)輸過程中運(yùn)輸車輛重心穩(wěn)定的前提下，實(shí)現(xiàn)倉(cāng)儲(chǔ)空間利用率最大化的目的。本算法的設(shè)計(jì)與實(shí)現(xiàn)，對(duì)進(jìn)一步推動(dòng)物流行業(yè)的發(fā)展具有重大意義。

關(guān)鍵詞：重心問題；空間最密堆積；算法設(shè)計(jì)；倉(cāng)儲(chǔ)空間利用率；物流行業(yè)

中圖分類號(hào)：TP399 ? ? ?文獻(xiàn)標(biāo)志碼：A ? ? ? ? ?文章編號(hào)：2095-2945（2024）18-0028-05

Abstract： This paper aims at the problems that the logistics industry urgently needs to solve， such as the low utilization rate of cargo storage space and a series of security hidden dangers caused by the instability of truck center of gravity caused by improper stacking mode in the process of long-distance freight transport. In this paper， a densest stacking algorithm taking into account the center of gravity is proposed. The storage space is layered， and the parameters such as cargo volume， quality and whether there are special needs are obtained by scanning， and the goods stacking mode is designed by combining the G2LA center of gravity algorithm and the two-dimensional and three-dimensional packing algorithm of the same and heterogeneous goods， so as to achieve the purpose of maximizing the utilization rate of storage space on the premise of ensuring the stability of the center of gravity of transport vehicles. The design and implementation of this algorithm is of great significance to further promote the development of the logistics industry.

Keywords： center of gravity problem; space densest packing; algorithm design; warehouse space utilization; logistics industry

在大力提倡智慧物流的背景下，物流行業(yè)發(fā)展迅速的同時(shí)也存在一些問題，如貨物存儲(chǔ)時(shí)倉(cāng)儲(chǔ)空間利用率較低，在長(zhǎng)途運(yùn)輸過程中由于貨物堆疊方式不當(dāng)造成運(yùn)輸車輛重心不穩(wěn)而存在一系列安全隱患等問題。為此本文提出了一種兼顧重心問題的空間最密堆積算法設(shè)計(jì)，考慮貨物的質(zhì)量和體積等參數(shù)，對(duì)倉(cāng)儲(chǔ)空間進(jìn)行分層，綜合GL2A重心算法及同、異構(gòu)貨物二維、三維空間最密堆積算法對(duì)貨物進(jìn)行合理的堆放，在保證重心穩(wěn)定的前提下實(shí)現(xiàn)倉(cāng)儲(chǔ)空間利用率的最大化。

將同、異構(gòu)貨物二維[1]、三維[2]空間最密堆積算法和重心平衡約束算法[3]進(jìn)行融合，首先根據(jù)貨物體積、數(shù)量以及倉(cāng)儲(chǔ)空間的容量對(duì)倉(cāng)儲(chǔ)空間進(jìn)行分層，在判斷貨物類型是相同構(gòu)型或相異構(gòu)型后，采用同、異構(gòu)貨物空間利用率最大化算法在每層對(duì)貨物進(jìn)行排列以保證每層的空間利用率最大化，之后考慮重心問題進(jìn)行層交換、層平移、層旋轉(zhuǎn)調(diào)整，對(duì)調(diào)整后的方案通過評(píng)價(jià)函數(shù)進(jìn)行評(píng)價(jià)以最大程度地保證空間利用率最大化的基礎(chǔ)上實(shí)現(xiàn)運(yùn)輸過程中重心平衡的目的。

1 ?空間最密堆積算法

1.1 ?二維排列算法

首先來討論二維相同結(jié)構(gòu)的貨物排列方案[4-5]，設(shè)在給定的邊長(zhǎng)為A×B的矩形區(qū)域內(nèi)（上A、下A、左B、右B），盡可能多地放入邊長(zhǎng)為m×n的小矩形，假設(shè)m≥n，通過對(duì)m、n的各種排列組合，使得在裝載時(shí)對(duì)大矩形的2個(gè)邊長(zhǎng)A和B有更高的利用率，可以對(duì)m×n的小矩形進(jìn)行平移和旋轉(zhuǎn)對(duì)組合方案優(yōu)化。如圖1所示。

在圖2中，由于算法本身是按照矩形的外側(cè)進(jìn)行排列的，故而在進(jìn)行物體的空間利用排布時(shí)，可能會(huì)在中間區(qū)域形成較大的未被利用的部分，如圖中x的陰影部分，此時(shí)可以將陰影部分視作一個(gè)新的矩形，再次利用本算法進(jìn)行循環(huán)嵌套，直至剩余空間不足以存放貨物為止。最終效果圖如圖3所示。

1.2 ?三維排列算法

鑒于在結(jié)構(gòu)上完全一致的貨物三維空間排布使用率問題，以上述二維貨物的排布形式為基礎(chǔ)，采取分層的方法，將空間三維立方體的長(zhǎng)和寬的參數(shù)作為每一層的長(zhǎng)和寬的參數(shù)，沿著本層的法向量以單個(gè)貨物的參數(shù)為層高把三維空間分成不同的層，以此完成相同結(jié)構(gòu)三維空間排布的初步裝載布局。針對(duì)每一層的排布，就可以參考上述二維相同結(jié)構(gòu)貨物的排布方案，如圖4所示。以選定裝載空間左后下角作為坐標(biāo)原點(diǎn)O建立空間直角坐標(biāo)系，沿裝載空間立方體的各棱所在直線延伸分別建立X軸、Y軸、Z軸，且裝載空間的長(zhǎng)、寬、高參數(shù)分別為P、Q、R。

由于在上述方案中采用了分層的思想，這里對(duì)分層的方法作進(jìn)一步說明。在劃分層時(shí)，要沿著已建立的空間坐標(biāo)系的其中一條坐標(biāo)軸，層的高度就是沿著劃分層的軸的方向的長(zhǎng)度，進(jìn)而在指定的層進(jìn)行二維排布。因?yàn)樨浳镌谌S空間中能繞自身的長(zhǎng)寬高任一方向旋轉(zhuǎn)，都可以達(dá)到平行于裝載空間底面的狀態(tài)，故共有6種擺放方式，其中3種分層方式如圖5所示。

沿Z軸即箱體高度方向分層，二維布局矩形平面為P×Q。

沿Y軸即箱體長(zhǎng)度方向分層，二維布局矩形平面Q×R。

沿X軸即箱體寬度方向分層，二維布局矩形平面P×R。

2 ?G2LA重心平衡約束的裝載算法

2LA算法是解決近似立方體裝載的高效算法，展示出較高的空間利用率，本文基于G2LA算法通過研究目前存在的其他較為高效的基于塊裝填的近似立方體裝載的算法后通過4個(gè)重要環(huán)節(jié)組成的此類算法的研究模式并在此基礎(chǔ)上進(jìn)行了一定的改良，下面是對(duì)這4個(gè)重要環(huán)節(jié)進(jìn)行簡(jiǎn)述。

近似立方體裝載的空間約束的表達(dá)形式，不采用 G2LA 算法的 cover representation，而選擇采用更有利于形成更高空間利用率的基于矩陣的空間約束表達(dá)形式。

把G2LA算法選取的多異構(gòu)塊裝填方式變成選取簡(jiǎn)單異構(gòu)裝填方式，其意義是能夠和混合禁忌搜索算法的編碼模式相匹配。

通過盡可能縮小G2LA算法的以定義立方體的底面參考點(diǎn)來計(jì)算的anchor distance值來選用所提供裝載空間的方式，意義是能夠采用混合禁忌搜索算法的編碼模式來按照物品類型的順序來模擬裝載物品。示意圖如圖6所示。

簡(jiǎn)單塊選擇算法采用G2LA算法。G2LA算法示意圖如圖7所示。

G2LA算法示意圖參考點(diǎn)表示目前的搜索狀態(tài)。當(dāng)要裝填一個(gè)物品塊時(shí)，通過評(píng)價(jià)函數(shù)篩選最高效的M個(gè)物品塊所篩選出的裝填方式，對(duì)M個(gè)物品塊中的所有篩選出的一部分裝填方式，再次篩選出最高效的M個(gè)物品塊所形成的裝填方式，這樣每一次迭代要總共篩選2M個(gè)裝填方式。對(duì)這一部分裝填方式，雖然存在評(píng)價(jià)函數(shù)不能準(zhǔn)確描述剩余空間的情況但利用基于最大體積的貪婪算法可以得到一個(gè)較為完整的裝填方式。所以，對(duì)一個(gè)可裝填空間t和一個(gè)物品塊f（b），可以采用評(píng)價(jià)函數(shù)：f（t，f）=V+k·Vs。

3改進(jìn)型兼顧重心問題的異構(gòu)貨物空間利用率最大化算法

3.1異構(gòu)算法設(shè)計(jì)

繼續(xù)沿用相同結(jié)構(gòu)貨物裝載中分層的思想，在進(jìn)行相異結(jié)構(gòu)貨物裝載時(shí)，分為底層裝載和非底層裝載[6-7]。

3.1.1 ?底層裝載函數(shù)

選取相同結(jié)構(gòu)貨物分層步驟中的第一層作為底層，從坐標(biāo)原點(diǎn)處開始裝填，底層裝載函數(shù)的步驟如下。

1）從已知參數(shù)的貨物中選擇體積最大的貨物首先放入裝載空間，緊靠x=0，y=0，z=0處，并以此作為參考。計(jì)算此時(shí)本層的剩余空間參數(shù)，并列出剩余長(zhǎng)度、寬度及最大高度。

2）在其余貨物中挑選出符合體積參數(shù)符合剩余長(zhǎng)度、剩余寬度、最大高度的箱子，依據(jù)所求得的體積參數(shù)降序分布，選取體積最大的箱子放入裝載空間，隨后再次計(jì)算剩余長(zhǎng)度、剩余寬度、最大高度、判斷剩余空間是否還能夠放入箱子，循環(huán)遍歷，直至本層空間無法放入箱子為止（箱子可旋轉(zhuǎn)）。

3）返回裝載結(jié)果，本層剩余空間的長(zhǎng)度、寬度、最大高度，集裝箱的剩余空間。如圖8所示。

3.1.2 ?非底層裝載函數(shù)

底層裝載完成后，隨即開始進(jìn)行非底層裝載。同樣以該層的x=0，y=0處為起點(diǎn)開始裝填，具體裝載步驟如下：

1）篩選出體積小于剩余空間的所有箱子，并根據(jù)箱子的體積大小，對(duì)所有箱子進(jìn)行排序。選取體積最大的箱子首先放入裝載空間，作為參考點(diǎn)。

2）讀取參考點(diǎn)貨物的長(zhǎng)、寬、高參數(shù)，并將其高度參數(shù)作為當(dāng)前裝載層的最大高度，確定好層高后計(jì)算該層的剩余裝載空間。

3）在其余貨物中挑選出符合本層剩余空間參數(shù)的箱子，計(jì)算這些箱子的體積并依據(jù)體積降次排列。選取其中體積最大的箱子放入剩余空間。隨后再次計(jì)算剩余長(zhǎng)度、剩余寬度、最大高度，判斷剩余空間是否還能夠放入箱子，循環(huán)遍歷，直至本層空間無法放入箱子為止（箱子可旋轉(zhuǎn)）。

4）計(jì)算該層的剩余空間，并將本層剩余空間的長(zhǎng)、寬、高與上一層剩余空間的長(zhǎng)、寬、高相加，并計(jì)算其實(shí)際可利用空間的大小，循環(huán)遍歷所有剩余箱子的體積大小與之比較，若剩余實(shí)際可利用空間大于某個(gè)箱子的體積，則將上下兩層合為一層，放入對(duì)應(yīng)的箱子，循環(huán)遍歷直至無法放入（箱子可旋轉(zhuǎn)）。

5）返回裝箱結(jié)果，剩余貨物個(gè)數(shù)及長(zhǎng)寬高參數(shù)，剩余空間的最大剩余高度、最大剩余寬度、最大剩余長(zhǎng)度。

流程圖如圖9所示。

3.1.3 ?函數(shù)的應(yīng)用

1）在裝載空間大于0，并且待裝貨物中有體積參數(shù)小于裝載空間容積的箱子時(shí)，執(zhí)行底層裝載函數(shù)。

2）執(zhí)行非底層裝箱函數(shù)，在裝載空間高度大于待裝載箱子高度的情況下，循環(huán)執(zhí)行非底層裝載函數(shù)，（箱子可旋轉(zhuǎn)）直至沒有符合高度要求的箱子為止。

3）沿y軸增加，重復(fù)執(zhí)行步驟1、步驟2，直至沒有符合y軸剩余寬度的箱子為止。

流程圖如10所示。

3.2 ?兼顧重心的調(diào)整優(yōu)化策略

采用上述的算法已經(jīng)可以得到初步的裝填方式，但需要測(cè)試結(jié)果是否滿足貨物重心位置約束[6-7]。為了能讓重心位置偏移量在可控的范圍內(nèi)，依據(jù)貨物分層裝填的特點(diǎn)，對(duì)各層物品進(jìn)行同層旋轉(zhuǎn)、上下層交換、同層水平移動(dòng)等操作來實(shí)現(xiàn)重心位置的優(yōu)化。

1）同層旋轉(zhuǎn)。依據(jù)同一層“重”物在該層的幾何中心為經(jīng)驗(yàn)，進(jìn)行旋轉(zhuǎn)，來調(diào)整重心。

2）上下層交換。通過對(duì)相同的層之間進(jìn)行交換，以將“重”物置于下層的經(jīng)驗(yàn)來改變各層的位置來調(diào)整重心。

3）同層水平移動(dòng)。考慮將同層的物品按“重”物居中的經(jīng)驗(yàn)，通過水平移動(dòng)層內(nèi)物品來調(diào)整重心。

4 ?實(shí)例計(jì)算與結(jié)果分析

在JavaScript、Python的腳本語言和Django框架下基本完成了對(duì)該算法的檢測(cè)并可對(duì)裝填結(jié)果進(jìn)行三維圖像仿真展示[8-9]。為確認(rèn)提出方案的可行性，采用算例數(shù)據(jù)進(jìn)行試運(yùn)行，7個(gè)算例的子算例有100個(gè)，箱子類型由少到多，異構(gòu)性從弱到強(qiáng)，通過Python程序計(jì)算7組算例數(shù)據(jù)的體積利用率同時(shí)記錄計(jì)算時(shí)間，算例結(jié)果見表1，仿真結(jié)果如圖11所示。

由表1可以發(fā)現(xiàn)，隨著箱子類型數(shù)量的增多，體積利用率呈現(xiàn)上升趨勢(shì)，計(jì)算時(shí)間較短且不會(huì)隨箱子類型的增多而延長(zhǎng)計(jì)算時(shí)間。

5結(jié)論

隨著智慧物流的不斷發(fā)展，在運(yùn)輸過程中物體最密堆積空間利用率問題和重心偏移的物體越來越被重視，本文基于G2LA重心算法和同、異構(gòu)貨物二維、三維最密堆積算法提出了改進(jìn)型兼顧重心問題的異構(gòu)貨物空間利用率最大化算法，初步解決了在空間利用率最大化的前提下運(yùn)輸過程中重心不穩(wěn)的問題，對(duì)于智慧物流的發(fā)展具有重要意義。

參考文獻(xiàn)：

[1] 景堃，周圣林，潘華.基于混合遺傳算法的飛機(jī)轉(zhuǎn)運(yùn)集裝箱布局優(yōu)化設(shè)計(jì)[J].航空科學(xué)技術(shù)，2010（5）：36-38.

[2] 劉瑞瑞.基于遺傳模擬退火算法的三維離線裝箱優(yōu)化問題研究[D].長(zhǎng)春：吉林大學(xué)，2014.

[3] 張長(zhǎng)勇，翟一鳴.基于改進(jìn)遺傳算法的航空集裝箱裝載問題研究[J].北京航空航天大學(xué)學(xué)報(bào)，2021，47（7）：1345-1352.

[4] 王巖，潘衛(wèi)平，陳秋蓮，等．單一尺寸長(zhǎng)方體三維裝箱問題的一種求解算法[J].包裝工程，2015（11）：96-99.

[5] 薛蓮.同一規(guī)格貨物集裝箱裝載問題研究及其在物流行業(yè)的應(yīng)用[D].天津：天津大學(xué)，2008.

[6] 張德富，彭煜，張麗麗．求解三維裝箱問題的多層啟發(fā)式搜索算法[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（12）：2553-2561．

[7] 李偉，楊超宇，孟祥瑞.基于混合遺傳算法的多品種貨物裝箱問題研究[J].包裝與食品機(jī)械，2020，38（3）：51-56.

[8] FANSLAU T，BORTFELDT A． A tree search algorithm for solving the container loading problem[J]. Informs Journal on Computing，2010，22（2）：222-235．

[9] PARRE O F，ALVAREZ-VALDES Ｒ，OLIVEIRA J F，et al． Neighborhood structures for the container loading problem： a VNS implementation[J]． Journal of Heuristics，2010，16（1）：1-22．