求解三維裝箱問題的啟發式搜索算法

梅志虎，唐志波

（浙江海洋大學，浙江 舟山 316022）

1 引言

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

圖1 近五年進出口總額統計

2 三維裝箱問題的數學模型

2.1 裝箱問題描述

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

圖2 裝箱示意圖

2.2 模型假設

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

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

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

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

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

（5）穩定性約束：在實際應用中，裝載必須保證每個裝載的貨物必須有集裝箱底部或其他貨物的支撐，以防止貨物被懸掛。

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

2.3 模型建立

在實際裝箱中，由于訂單貨物和貨運車輛的多種多樣，對于公司來說，集裝箱的空間利用率是他們最關心的問題，因此，基于以上分析的內容，建立目標函數和裝箱約束的數學模型如下。

2.3.1 目標函數為集裝箱體積利用率最優

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

2.3.2 貨物重量約束

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

2.3.3 貨物體積約束

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

2.3.4 貨物裝載三維尺寸約束

其中，xi,yi,zi為第i種貨物在集裝箱內部的位置坐標，li,wi,hi為第i 種貨物的長寬高，L,W,H 為集裝箱的長寬高。

2.3.5 方向約束

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

3 啟發式搜索算法

本文所研究的啟發式搜索算法具體流程如圖3所示。通過兩個啟發式算法來獲取當前剩余空間的可行性塊，為后續尋優過程提供較為良好的初始解；隨后采用帶有深度限制的深度優先搜索算法和貪心算法對裝載方案進行尋優。

圖3 啟發式搜索算法

3.1 啟發式算法

3.1.1 簡單塊

簡單塊是由同一朝向的同種類型的箱子堆疊而成的，箱子和箱子之間沒有空隙，堆疊的結果形成一個長方體[3]。將所有排列組合生成并滿足約束條件的簡單塊，按照體積降序排序存儲到塊表中，用于迅速生成指定剩余空間的可行塊列表。如圖4所示，nx,ny,nz 分別表示在對應坐標軸上的箱子數。

圖4 簡單塊

3.1.2 空間分割

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

圖5 剩余空間切割和轉移

3.2 帶深度限制的深度優先搜索算法

首先進行帶深度限制的深度優先搜索算法制定當前的預裝載方案，從一個部分方案出發，遞歸計算可行塊的評估值，當達到深度限制的葉子節點時，調用貪心函數算出當前的方案，進而選擇最優解。如圖6所示，方框中的節點表示用貪心算法計算出的節點，而黑色節點表示最終選擇的最優節點。

圖6 深度優先搜索（深度為3，分支數為2）

4 實驗方案

采用JAVA 編程語言實現本文所研究的集裝箱裝載算法，利用MATLAB 編程語言進行仿真實驗以及實例驗證，并根據某外貿公司的實際訂單貨物，得到三維裝箱圖以及目標函數值。

4.1 實例驗證

為了驗證本文算法的可行性和適用性，以40HQ 外貿集裝箱進行裝箱為例。從寧波某進出口有限公司獲取某個訂單進行驗證，該訂單產品箱數為893 箱，產品種類為67 種。

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

圖7 40HQ 集裝箱

5 結論

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

當然，本文算法仍然存在一定的缺陷，例如，箱子種類越多，產生的可行塊就會越多，搜索樹就會越復雜，計算時間也會越長。