陳意然，周正陽，吳思遠(yuǎn)，張燁鐘

（紹興文理學(xué)院，浙江 紹興 312000）

1 研究背景

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

2 問題重述

問題一：對訂單數(shù)據(jù)給出包裝方案。

問題二：優(yōu)化每種耗材尺寸。

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

3 模型假設(shè)

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

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

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

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

4 模型的建立與求解

4.1 問題一：對訂單數(shù)據(jù)給出包裝方案

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

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

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

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

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

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

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

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

綜上得到模型：

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

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

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

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

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

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

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

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

1.袋子約束：

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

對應(yīng)寫出數(shù)學(xué)約束：

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

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

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

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

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

由于袋子可塑性較強(qiáng)且比箱子更節(jié)省材料與空間，因此我們優(yōu)先考慮使用袋子，當(dāng)袋子裝不下時，再考慮使用箱子[3]進(jìn)行組裝：

構(gòu)造判斷函數(shù)：

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

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

目標(biāo)函數(shù)需要綜合考慮裝袋與裝箱部分：

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

4.2 問題二：優(yōu)化每種耗材尺寸

4.2.1 全部使用箱子時的耗材優(yōu)化

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

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

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

使用遺傳算法，根據(jù)每個箱子的既有尺寸在小范圍內(nèi)進(jìn)行修改，利用遺傳思路擴(kuò)大尺寸變化范圍，進(jìn)一步尋找最優(yōu)解。

4.2.2 全部使用袋子時的耗材優(yōu)化

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

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

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

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

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

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

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

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

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

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

在新條件約束下，

求解目標(biāo)函數(shù)：

利用遺傳算法求解優(yōu)化后的方案，設(shè)定目標(biāo)函數(shù)：

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

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

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

5 應(yīng)用前景

通過優(yōu)化裝箱方案，可以減少運(yùn)輸中的空間浪費(fèi)，縮減運(yùn)輸次數(shù)和運(yùn)輸成本，節(jié)約包裝材料的使用量，提高經(jīng)濟(jì)效益。

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