左先旺，榮先釗

基于二叉樹(shù)算法的三維裝箱求解

左先旺，榮先釗

（三峽大學(xué) 電氣與新能源學(xué)院，湖北 宜昌 443002）

近年來(lái)，經(jīng)濟(jì)的發(fā)展使得物流行業(yè)急劇擴(kuò)張，集裝箱進(jìn)出口貨物以及快遞運(yùn)輸包裹均在急劇增加?；诖藢?duì)于如何高效、快速地裝載不同尺寸的貨物，并且能夠相對(duì)較好地利用容器箱的裝載空間顯得尤為重要。采用生成優(yōu)選條及優(yōu)選層的方法將三維裝箱問(wèn)題簡(jiǎn)化為二維裝箱問(wèn)題求解，極大地簡(jiǎn)化了三維空間不確定性對(duì)三維問(wèn)題帶來(lái)的復(fù)雜度問(wèn)題，并且采用二叉樹(shù)搜索算法對(duì)裝載問(wèn)題進(jìn)行求解，使得求解更加簡(jiǎn)單、準(zhǔn)確，對(duì)于三維裝箱問(wèn)題求解水平有顯著提高。

優(yōu)選條；優(yōu)選層；三維裝箱；二叉樹(shù)搜索算法

1 背景及意義

隨著經(jīng)濟(jì)的發(fā)展，貨物運(yùn)輸需求逐漸增多。目前，集裝箱內(nèi)貨物的裝載大多依靠人工的技能和經(jīng)驗(yàn)，對(duì)于大規(guī)模以及大尺寸的貨物裝載運(yùn)輸會(huì)存在極大的空間浪費(fèi)問(wèn)題。而三維裝箱問(wèn)題即是將一組三維長(zhǎng)方體放置在三維空間內(nèi)，以使得空間的填充率最大或者利用率最高。

本文主要研究單容器裝箱問(wèn)題，其形式化的定義如下：給定一個(gè)容器（其長(zhǎng)為，寬為，高為，體積為）和一系列待轉(zhuǎn)載的箱子（其長(zhǎng)為i，寬為i，高為i，體積為i），給定的容器和箱子都為長(zhǎng)方體，目標(biāo)為確定一個(gè)可行的箱子裝載方案，使得在滿足給定的裝載約束條件下，使容器中所裝箱子總體積或者箱子的填充率/盡可能的大。需要滿足的約束條件主要有以下兩個(gè)：①裝載的箱子平行放置，不能與其他箱子之間有重疊，且箱子外形不能被破壞；②裝載的箱子的長(zhǎng)寬高不能超出容器箱子的長(zhǎng)寬高。

除此之外，在結(jié)合不同實(shí)際情況下，還會(huì)考慮以下約束條件：①質(zhì)量約束。裝載貨物的總質(zhì)量必須小于或者等于容器的最大承載質(zhì)量。②方向性約束。在實(shí)際應(yīng)用中，對(duì)箱子的裝載具有方向性約束，比如有的箱子不能倒置，因此，部分箱子只能有其中的一條或者兩條邊作為高。③穩(wěn)定性約束。在實(shí)際的應(yīng)用中，為了裝載貨物的安全性，通常會(huì)對(duì)裝載貨物進(jìn)行穩(wěn)定性約束。即要求每個(gè)裝載貨物的箱子必須得到容器底或其他已經(jīng)裝載貨物箱子的支撐。即上一層貨物的長(zhǎng)、寬不能超過(guò)下一層裝載貨物的長(zhǎng)、寬。

2 模型建立

本文主要針對(duì)集裝箱對(duì)目標(biāo)箱子的裝載情況進(jìn)行研究，因此，對(duì)一些其他因素進(jìn)行了假設(shè)，對(duì)問(wèn)題進(jìn)行了簡(jiǎn)化。現(xiàn)對(duì)模型做出以下假設(shè)：①假設(shè)貨物在裝載箱子內(nèi)質(zhì)量分布均勻；②貨物能夠進(jìn)行疊加，不會(huì)被壓壞；③不考慮中途的貨物增加或卸載。

2.1 目標(biāo)函數(shù)

目標(biāo)函數(shù)為容器裝箱體積利用率最高：

式（1）中：為容器箱體積利用率；為貨物的序號(hào)，=1，2，3，…，；i為第件貨物的體積；為容器箱的體積。

2.2 約束條件

約束條件一，裝載貨物長(zhǎng)、寬、高約束為：

式（2）中：i，i，i為裝載貨物的位置參考坐標(biāo)；i，i，i為第件裝載貨物的長(zhǎng)、寬、高；，，為容器箱的長(zhǎng)、寬、高。

約束條件二，裝載貨物總質(zhì)量約束為：

式（3）中：i第件貨物的質(zhì)量；為容器箱所允許的最大裝載質(zhì)量。

約束條件三，裝載貨物總體積約束為：

式（4）中：i第件貨物的體積；為容器箱的體積。

約束條件四，裝載貨物方向性約束為i，i，i。

3 問(wèn)題求解

該模型求解基于二叉樹(shù)算法，首先生成優(yōu)選條，組成優(yōu)選條集合，再生成優(yōu)選層，生成優(yōu)選層集合，最終選擇容器箱體積利用率最高的方案為最優(yōu)方案。

3.1 生成優(yōu)選條

從長(zhǎng)方體裝載貨物箱子中選擇生成一個(gè)子集，子集中的箱子滿足方向性約束，優(yōu)選條沿著軸豎直地堆疊成一摞，形成長(zhǎng)方條，長(zhǎng)方條在軸方向上滿足容器箱的高度c約束限制。在長(zhǎng)寬方向上，jl為此長(zhǎng)方條在軸上的長(zhǎng)度，jw為此長(zhǎng)方條在軸上的寬度。則此長(zhǎng)方條的填充率為Sj=/（jl×jw×c）。

其中填充率最高的長(zhǎng)方條的子集形成的長(zhǎng)方條定義為優(yōu)選條mj。

多個(gè)優(yōu)選條mj組成集合，即產(chǎn)生了優(yōu)選條集合{m1，m2，…，mn}。

3.2 生成優(yōu)選層

從優(yōu)選條集合{m1，m2，…，mn}中選擇一個(gè)子集，中的優(yōu)選條沿著軸或者軸的方向排成一排，形成豎直層j，若是沿著軸排列的，則在軸上長(zhǎng)度不超過(guò)容器箱長(zhǎng)度m的限制，其在軸方向上的寬度為jw。如果是沿著軸排列的，則在軸上長(zhǎng)度不超過(guò)容器箱長(zhǎng)度m的限制，其在軸方向上的寬度為jl。

則豎直層的j的填充率為：

優(yōu)選條沿軸方向排列時(shí)，填充率Lj最高時(shí)豎直層的子集，形成的豎直層定義為沿軸方向的優(yōu)選層x；優(yōu)選條沿軸方向排列時(shí)，填充率Lj最高時(shí)豎直層的子集，形成的豎直層定義為沿軸方向的優(yōu)選層y。

3.3 算法求解

本算法先將所有待裝載箱子組合成多個(gè)沿著容器箱子方向上擺放的優(yōu)選條mj，這樣便將三維裝箱問(wèn)題降低維度到裝載優(yōu)選條的二維裝箱問(wèn)題。通過(guò)構(gòu)建二叉樹(shù)，對(duì)應(yīng)不同的裝載方案，如圖1所示。二叉樹(shù)上每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)了一個(gè)裝載方案，下一層節(jié)點(diǎn)是在上一層節(jié)點(diǎn)裝載方案的基礎(chǔ)上繼續(xù)裝載新的優(yōu)選條形成的，根節(jié)點(diǎn)為空載容器箱。

在根節(jié)點(diǎn)的基礎(chǔ)上產(chǎn)生優(yōu)選條集合，隨機(jī)選擇不同的優(yōu)選條裝入容器箱中，形成不同的節(jié)點(diǎn)裝載方案；在上一節(jié)點(diǎn)裝載方案的基礎(chǔ)上，繼續(xù)生成裝載新的優(yōu)選條，子節(jié)點(diǎn)是在母節(jié)點(diǎn)的基礎(chǔ)上繼續(xù)裝載而成的；不斷更新容器箱子剩余空間的體積，生成新的優(yōu)選條，產(chǎn)生新的裝載方案。直到剩余空間無(wú)法再裝載下任何優(yōu)選條，包括只包含任意箱子的最小優(yōu)選條在內(nèi)。證明該種裝載方案最終完成。比較所有裝載方案的填充率大小。其中，填充率最大的即為最優(yōu)裝載方案。

圖1 三維裝載的二叉樹(shù)算法示意圖

4 總結(jié)

本文采用生成優(yōu)選條及優(yōu)選層的方法將三維裝箱問(wèn)題簡(jiǎn)化為二維裝箱問(wèn)題求解，極大地簡(jiǎn)化了三維空間不確定性對(duì)三維問(wèn)題帶來(lái)的復(fù)雜度，并且采用二叉樹(shù)搜索算法對(duì)裝載問(wèn)題進(jìn)行求解，使得求解更加簡(jiǎn)單準(zhǔn)確，對(duì)于三維裝箱問(wèn)題求解水平有顯著提高。

［1］那日薩，崔雪蓮，韓琪瑋.基于實(shí)際約束的三維裝箱問(wèn)題優(yōu)化算法［J］.工業(yè)工程與管理，2017，22（4）：10-16.

［2］雷洋.動(dòng)態(tài)多目標(biāo)三維裝箱問(wèn)題的研究及其應(yīng)用［D］.吉林：東北電力大學(xué)，2017.

［3］劉明明，童小嬌，戴彧虹.裝箱問(wèn)題的算法及最新進(jìn)展［J］.計(jì)算數(shù)學(xué)，2016，38（3）：257-280.

［4］金潔.二維矩形裝箱問(wèn)題及其算法設(shè)計(jì)［D］.昆明：云南大學(xué)，2015.

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

［6］魏麗軍.求解裝箱問(wèn)題的啟發(fā)式算法研究［D］.廈門：廈門大學(xué)，2008.

［7］劉艷娟.二維裝箱問(wèn)題的啟發(fā)式算法研究［D］.廈門：廈門大學(xué)，2007.

［8］韓運(yùn)實(shí).裝箱問(wèn)題方法研究及其集成應(yīng)用［D］.青島：中國(guó)海洋大學(xué)，2004.

TM63

A

10.15913/j.cnki.kjycx.2019.14.063

2095－6835（2019）14－0138－02

左先旺（1997—），男，三峽大學(xué)2016級(jí)本科生，研究方向?yàn)橹悄茈娋W(wǎng)信息工程。榮先釗（1998—），男，三峽大學(xué)2016級(jí)本科生，研究方向?yàn)閃eb應(yīng)用程序設(shè)計(jì)。

〔編輯：張思楠〕