求解三維裝箱問(wèn)題的啟發(fā)式搜索算法

梅志虎，唐志波

（浙江海洋大學(xué)，浙江 舟山 316022）

1 引言

據(jù)中國(guó)海關(guān)統(tǒng)計(jì)，2021年度我國(guó)外貿(mào)進(jìn)出口總值到達(dá)27.8 萬(wàn)億元人民幣，同比增長(zhǎng)14.2%，出口值15.3萬(wàn)億元人民幣，同比增長(zhǎng)10.8%，進(jìn)口值12.5 萬(wàn)億元人民幣，同比增長(zhǎng)18.7%，如圖1所示。在我國(guó)，九成以上的外貿(mào)貨物均通過(guò)港口進(jìn)出[1]。隨著港口貨物運(yùn)輸量呈現(xiàn)螺旋式上升的趨勢(shì)，越來(lái)越多的外貿(mào)公司加速發(fā)展信息化管理，提高公司的效率，增加企業(yè)及行業(yè)的經(jīng)濟(jì)效益。研究三維集裝箱裝箱問(wèn)題對(duì)于提高運(yùn)輸效率、降低運(yùn)輸成本、提高企業(yè)盈利能力、減少污染物排放等方面具有十分積極的現(xiàn)實(shí)意義。

圖1 近五年進(jìn)出口總額統(tǒng)計(jì)

2 三維裝箱問(wèn)題的數(shù)學(xué)模型

2.1 裝箱問(wèn)題描述

裝箱問(wèn)題是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，屬于經(jīng)典的NP-hard 問(wèn)題，有著廣泛的應(yīng)用，在日常生活中也屢見(jiàn)不鮮。通常定義為：給定i 種長(zhǎng)寬高為L(zhǎng)i、Wi、Hi 的集裝箱和j 種長(zhǎng)寬高為lj、wj、hj，重量為mj 的貨物[2]，然后將所有物品都裝入箱子中，要求裝入箱子中所有物品的總體積不能超過(guò)箱子的容積，并且使集裝箱的利用率達(dá)到最高。裝箱問(wèn)題的示意圖如圖2所示。

圖2 裝箱示意圖

2.2 模型假設(shè)

本文主要研究單個(gè)集裝箱裝載問(wèn)題，考慮以下約束條件：

（1）體積約束：貨物的總體積不超過(guò)集裝箱的最大容積；

（2）載重量約束：貨物的總重量不超過(guò)集裝箱的最大承載能力；

（3）不重疊約束：貨物之間不允許重疊放置；

（4）正交放置約束：擺放過(guò)程中貨物邊緣與集裝箱邊緣平行或者垂直。

（5）穩(wěn)定性約束：在實(shí)際應(yīng)用中，裝載必須保證每個(gè)裝載的貨物必須有集裝箱底部或其他貨物的支撐，以防止貨物被懸掛。

（6）方向約束：一些特定類(lèi)型的貨物在確定裝載順序時(shí)，還需考慮擺放方向。

2.3 模型建立

在實(shí)際裝箱中，由于訂單貨物和貨運(yùn)車(chē)輛的多種多樣，對(duì)于公司來(lái)說(shuō)，集裝箱的空間利用率是他們最關(guān)心的問(wèn)題，因此，基于以上分析的內(nèi)容，建立目標(biāo)函數(shù)和裝箱約束的數(shù)學(xué)模型如下。

2.3.1 目標(biāo)函數(shù)為集裝箱體積利用率最優(yōu)

其中，i 為貨物的序號(hào)，i=1,2,…,N，ai為第i 種貨物在集裝箱里面的裝載數(shù)量，vi為第i 種貨物的體積，Z 為集裝箱的體積利用率，V 為集裝箱的容積。

2.3.2 貨物重量約束

其中，mi為第i 種貨物的重量，M 為集裝箱的最大載重量。

2.3.3 貨物體積約束

其中，vi為第i 種貨物的體積，V 為集裝箱的容積。

2.3.4 貨物裝載三維尺寸約束

其中，xi,yi,zi為第i種貨物在集裝箱內(nèi)部的位置坐標(biāo)，li,wi,hi為第i 種貨物的長(zhǎng)寬高，L,W,H 為集裝箱的長(zhǎng)寬高。

2.3.5 方向約束

其中，bli,bwi,bhi為第i 種貨物對(duì)應(yīng)的邊豎直放置作為高度，0 表示不可以，1 表示可以。

3 啟發(fā)式搜索算法

本文所研究的啟發(fā)式搜索算法具體流程如圖3所示。通過(guò)兩個(gè)啟發(fā)式算法來(lái)獲取當(dāng)前剩余空間的可行性塊，為后續(xù)尋優(yōu)過(guò)程提供較為良好的初始解；隨后采用帶有深度限制的深度優(yōu)先搜索算法和貪心算法對(duì)裝載方案進(jìn)行尋優(yōu)。

圖3 啟發(fā)式搜索算法

3.1 啟發(fā)式算法

3.1.1 簡(jiǎn)單塊

簡(jiǎn)單塊是由同一朝向的同種類(lèi)型的箱子堆疊而成的，箱子和箱子之間沒(méi)有空隙，堆疊的結(jié)果形成一個(gè)長(zhǎng)方體[3]。將所有排列組合生成并滿(mǎn)足約束條件的簡(jiǎn)單塊，按照體積降序排序存儲(chǔ)到塊表中，用于迅速生成指定剩余空間的可行塊列表。如圖4所示，nx,ny,nz 分別表示在對(duì)應(yīng)坐標(biāo)軸上的箱子數(shù)。

圖4 簡(jiǎn)單塊

3.1.2 空間分割

如圖5所示，將一個(gè)長(zhǎng)為l，寬為w，高為h 的可行塊裝入到這個(gè)剩余空間中[4]，此時(shí)該剩余空間除去該可行塊所占有的體積外，將該空間劃分成前(Front)、右(Right)、上(Up)三個(gè)空間，但是在分割前(Front)、右(Right)兩個(gè)空間時(shí)，可以有如圖5（a）和圖5（b）兩種分割方式，圖5（c）箭頭所示的空間便是圖5（a）和圖5（b）的可轉(zhuǎn)移空間，隨著裝箱的需要，可轉(zhuǎn)移空間可以被轉(zhuǎn)移給另一個(gè)剩余空間重新利用。

圖5 剩余空間切割和轉(zhuǎn)移

3.2 帶深度限制的深度優(yōu)先搜索算法

首先進(jìn)行帶深度限制的深度優(yōu)先搜索算法制定當(dāng)前的預(yù)裝載方案，從一個(gè)部分方案出發(fā)，遞歸計(jì)算可行塊的評(píng)估值，當(dāng)達(dá)到深度限制的葉子節(jié)點(diǎn)時(shí)，調(diào)用貪心函數(shù)算出當(dāng)前的方案，進(jìn)而選擇最優(yōu)解。如圖6所示，方框中的節(jié)點(diǎn)表示用貪心算法計(jì)算出的節(jié)點(diǎn)，而黑色節(jié)點(diǎn)表示最終選擇的最優(yōu)節(jié)點(diǎn)。

圖6 深度優(yōu)先搜索（深度為3，分支數(shù)為2）

4 實(shí)驗(yàn)方案

采用JAVA 編程語(yǔ)言實(shí)現(xiàn)本文所研究的集裝箱裝載算法，利用MATLAB 編程語(yǔ)言進(jìn)行仿真實(shí)驗(yàn)以及實(shí)例驗(yàn)證，并根據(jù)某外貿(mào)公司的實(shí)際訂單貨物，得到三維裝箱圖以及目標(biāo)函數(shù)值。

4.1 實(shí)例驗(yàn)證

為了驗(yàn)證本文算法的可行性和適用性，以40HQ 外貿(mào)集裝箱進(jìn)行裝箱為例。從寧波某進(jìn)出口有限公司獲取某個(gè)訂單進(jìn)行驗(yàn)證，該訂單產(chǎn)品箱數(shù)為893 箱，產(chǎn)品種類(lèi)為67 種。

通過(guò)該訂單的實(shí)例驗(yàn)證可以看出，在滿(mǎn)足實(shí)際裝載約束的同時(shí)，40HQ 的集裝箱的體積利用率達(dá)到了91.66%，降低了運(yùn)輸成本。如圖7所示40HQ 外貿(mào)集裝箱的裝載效果，不同顏色表示不同的貨物。

圖7 40HQ 集裝箱

5 結(jié)論

通過(guò)對(duì)寧波某進(jìn)出口有限公司實(shí)例驗(yàn)證，表明所提算法能夠較好地解決大規(guī)模貨物的裝載問(wèn)題，進(jìn)行了上百個(gè)訂單測(cè)試，集裝箱平均體積利用率均高于89%，取得了理想的裝箱效果，證明了算法的有效性和可行性。

當(dāng)然，本文算法仍然存在一定的缺陷，例如，箱子種類(lèi)越多，產(chǎn)生的可行塊就會(huì)越多，搜索樹(shù)就會(huì)越復(fù)雜，計(jì)算時(shí)間也會(huì)越長(zhǎng)。