基于貪心法以及遺傳算法的工業裝箱優化

陳意然，周正陽，吳思遠，張燁鐘

（紹興文理學院，浙江 紹興 312000）

1 研究背景

目前我國快遞物流業已成為全球最大的快遞市場。由于包裹的基數很大，所以適當節省包裝材料就可以產生較大的經濟效益。因此，我們需優化耗材方案，在裝下包裹的同時節省材料與體積，并考慮貨物與耗材之間的柔性問題，做出進一步優化。

2 問題重述

問題一：對訂單數據給出包裝方案。

問題二：優化每種耗材尺寸。

問題三：若考慮到耗材是柔性物體（長寬高的延伸比例不超過5%），重新探究問題一和問題二。

3 模型假設

1.所有需要裝載的貨物沒有固定放置方向的要求。

2.待裝物件都是由包裝盒打包的規則長方體。

3.用袋子裝物品時袋子的形狀會因物件形狀變化，在裝如矩形物件后，袋子的邊角處會存在一個不能放入任何物件的角，忽略此部分的體積。

4.不考慮貨物與貨物之間的擠壓冗余，僅考慮耗材的形變。

4 模型的建立與求解

4.1 問題一：對訂單數據給出包裝方案

4.1.1 全部使用箱子作為耗材的方案

其中i=1，2，3，4，5。

訂單總數為Dn，令num(d,i)為訂單編號d 需要的i號箱的數量，目標函數可以表示為：

對于箱型選擇和貨物裝載兩個步驟，我們采用自適應隨機算法，算法思想如下：

1.對任意訂單d 輸入，首先規定物件在耗材中的擺放規則，在包裝箱的左后方為原點建立空間直角坐標系，優先填滿X 軸[一維過程，記為step1]，在X 軸達到最優后由X 軸向Y 軸延伸[二維過程，記為step2]，最后由XOY 平面向Z 軸頂端延伸[三維過程，記為step3]）。

2.隨機選擇箱型i，記Boxi（Li，Wi，Hi）為i 號箱子的長寬高，goods(lj,wj,hj，d)為訂單中第j 件貨物的長寬高。在訂單d 中隨機選擇首件貨物，若能放下則更新箱內空間，以及裝入后貨物離坐標原點的最遠距離點P（x,y,z），若不能則增大箱子型號，則結束，整體有約束：

3.計算剩余空間是否能減小箱子的尺寸型號，若能則減小，重新進行第二步；不能則繼續第四步。

4.根據重力式空間搜索策略[1]算法的擺放優先級選擇貨物最優尺寸，即在一維過程中需要在訂單d 中找到lj（wj 或hj），直至裝載完成。

綜上得到模型：

4.1.2 全部使用袋子作為耗材的方案

使用可變高度的袋子模型，配合貪心算法來解決問題[2]，首先用0-1 規劃選擇袋型：

對EXCEL 表格中的訂單進行處理，把同一訂單下的多種物品按照數量全部展開，akm表示第k 個訂單的第m 個物品，akmXi表示將第k 個訂單下的第m 個物品裝入第Xi號碼袋子，Vkm表示第k 個訂單的第m 個物品的體積，顯然有：Vkm=Ikm*Wkm*hkm。

Vi表示使用第i 個袋子的體積，顯然有：Vi=Ii*Wi*hi。

根據題目中所給hi高度為1，進一步構造可變高度的袋子模型，袋子的高度hi等于第一個裝入的物品高度且可實時更新，有：Vim=Ii*Wi*hkm。

用貪心法將所有訂單物品按底面積從大到小排列，并分別算出四個袋子的底面積，排除無法裝下的物品，在符合裝袋要求的物品中，優先將最大的物品裝入滿足底面積要求且剩余底面積最小的袋子，更新袋子剩余體積：Vi'=Vim-Vkm。

選擇滿足裝袋條件且次大的訂單物品，繼續進行裝載，同時比較hkm與hk1m1，倘若hkm>hk1m1則不必更新袋子體積，否則再次更新袋子體積：Vim1=Ii*Wi*hk1m1。

重復上述裝載操作，在整個裝載過程中，需同時滿足下列裝載條件：

1.袋子約束：

袋子長+袋子高≥物品長+物品高；袋子寬+袋子高≥物品寬+物品高

對應寫出數學約束：

其中hβikαβimα表示第β 次裝載時向第i 個袋子中放入第α次訂單物品后，更新的袋子高度。

2.方向約束。根據題意我們可以知道，袋子中的訂單物品長寬高可以任意互換，因此我們建立方向約束：

bIkm，bWkm，bhkm為第k 個訂單下的第m 個物品對應的邊豎直放置作為高度，0 表示可以放，1 則表示不能放。

3.設置雙目標函數。目標函數要滿足耗材總體積越小越好的條件，耗材數量少的條件，我們可以寫出：

4.1.3 箱子和袋子兩種耗材同時使用的方案

由于袋子可塑性較強且比箱子更節省材料與空間，因此我們優先考慮使用袋子，當袋子裝不下時，再考慮使用箱子[3]進行組裝：

構造判斷函數：

對于原來那些在上題情形超出1-4 號袋子底面積范圍的袋子，或者物品本身尺寸并不滿足袋子自身的約束條件，嘗試使用箱子進行裝載，比較物品體積與每個箱子的體積，用Vβω=Iβω*Wβω*hβω依次遍歷五個箱子，比較Vβω與Vkm=Ikm*Wkm*hkm的大小關系，找到滿足條件且體積最小的箱子，進行裝載，并更新箱子的剩余體積：Vi''=Vβω-Vkm

再用Vi''遍歷空箱子，若有多個訂單物品的體積滿足條件，則優先取體積最大的物品進行裝箱。

目標函數需要綜合考慮裝袋與裝箱部分：

在這一部分我們還要加上箱子體積約束：Vkm≤ aβVβω。

4.2 問題二：優化每種耗材尺寸

4.2.1 全部使用箱子時的耗材優化

采取遺傳算法，新變量I'βω表示更改后的第i 種箱子的長度，W'βω表示更改后的第i 種箱子的寬度，h'βω表示更改后的第i 種箱子的高度：

同時我們需要保持耗材部分總體積最小化：

著重考慮約束條件：裝箱方向保持約束條件不變。

使用遺傳算法，根據每個箱子的既有尺寸在小范圍內進行修改，利用遺傳思路擴大尺寸變化范圍，進一步尋找最優解。

4.2.2 全部使用袋子時的耗材優化

采取遺傳算法[4]，更新后袋子依舊是可塑性的，高度為1，I'βi表示更改后的第i 種袋子的長度，W'βi表示更改后的第i 種袋子的寬度，目標是更新后的每個袋子的體積減去每個物品裝袋后的剩余體積盡可能地小：

我們把假設的新袋裝尺寸代入剛才的約束條件：

首先是袋子約束依然滿足長寬條件：

其次是對于裝袋條件，如果尺寸過大且超出裝袋范圍則無法裝袋：I'βi ≤Ikm或者W'βi ≤Wkm，需在預處理時刪除數據。

最后是保持上述裝袋方向約束條件不變：

用遺傳算法[5]將新尺寸的裝載物品數量作為適應度函數的數值，同時減去箱子剩余空間的大小作為罰項。

同時使用箱子和袋子問題，基本思路同4.1.3，裝滿袋子后考慮箱子。

4.3 問題三：若考慮到耗材是柔性物體，重新探究問題一和問題二

全部使用箱子作為耗材時的方案。在裝載完成后，耗材長度上會有原長寬高1.05 倍的空間約束條件：

在裝載過程中，選取最佳貨物時也要滿足長度約束：

在新條件約束下，

求解目標函數：

利用遺傳算法求解優化后的方案，設定目標函數：

同時需保持耗材部分總體積最小化：

裝箱方向保持約束條件不變：

對于袋裝和混裝類型，只需要將參數做1.05 倍處理，其余做法與前例相同。

5 應用前景

通過優化裝箱方案，可以減少運輸中的空間浪費，縮減運輸次數和運輸成本，節約包裝材料的使用量，提高經濟效益。

在只用箱子包裝的情況下，本文使用的自適應隨機算法得到的方案準確度較高，但是收斂速度慢。在考慮只用袋裝時使用的貪心算法忽略了物體的三維特征，但是貪心算法在解決三維尺寸可變裝箱問題且待裝物件較少的時候，也能給出較為準確的結果，貪心算法的優勢在于運算時間短、效率高，但在運行時可能會陷入局部最優解，因而在某些情況下得到的解準確度較低。