一個三維裝箱問題的搜尋樹算法

三維裝箱問題的業務場景可以參考電商業務中的紙箱推薦問題. 文中考慮了如下問題.

輸入 : 長寬高為(L,W,H)(L, W, H)(L,W,H)的箱子和nnn個物品, 其長寬高為(li,wi,hi)(l_i, w_i, h_i)(li,wi,hi), i=1,2,…,ni=1,2,\ldots,ni=1,2,…,n. 假設物品是長方體, 長度不可變(沒有彈性). 裝箱時可以對商品進行90度旋轉, 但不能傾斜.

輸出 : 判斷所有物品是否能裝入箱子.

本文提供一個基于搜尋樹的精确算法. 基本思想是把三維裝箱問題歸約(Reduce)到一個有向無環圖(Directed Acyclic Graph)上的問題. 算法搜尋到一個符合限制條件的有向無環圖則傳回true, 否則傳回false.

物品的位置

如下圖所示, 考慮任意一個物品(或者箱子), 我們可以用aaa, bbb兩點的三維坐标描述其位置和大小. 設a=(xa,ya,za)a=(x_a,y_a,z_a)a=(xa,ya,za), 那麼b=(xa+L,ya+W,za+H)b=(x_a+L, y_a+W, z_a+H)b=(xa+L,ya+W,za+H), 其中L,W,HL, W, HL,W,H是物品的長寬高. 為了友善描述, 我們用aaa點的坐标表示物品的位置.

有向無環圖

假設所有物品能夠被裝入箱子中. 此時我們考慮一種可行的擺放方式. 對兩個物品i≠ji \neq ji=j, 分别考慮x,y,zx, y, zx,y,z軸方向物品之間的相對位置關系.

首先考慮xxx軸方向, iii和jjj隻有兩種位置關系

iii在jjj的左邊, 即xi≤xjx_i \leq x_jxi≤xj, 其中xi,xjx_i, x_jxi,xj為物品在xxx軸的坐标;
iii在jjj的右邊, 即xi>xjx_i > x_jxi>xj.

下面我們構造有向圖Dx=(V,ux,Ax)D_x = (V, u^x, A_x)Dx=(V,ux,Ax). 其中

V={1,2,…,n}V=\{1, 2, \ldots, n\}V={1,2,…,n}是所有物品的集合.
uxu^xux為頂點權重的集合, 即uix=liu^x_i=l_iuix=li, ∀i=1,2,…,n\forall i=1, 2, \ldots, n∀i=1,2,…,n.
AxA_xAx為弧(Arc)的集合. 如果iii在jjj的左邊, 則(i,j)∈Ax(i, j)\in A_x(i,j)∈Ax, 否則(j,i)∈Ax(j,i)\in A_x(j,i)∈Ax(如下圖所示).

注意: 如果(i,j),(j,k)∈Ax(i, j), (j,k) \in A_x(i,j),(j,k)∈Ax, 則(i,k)∈Ax(i,k)\in A_x(i,k)∈Ax. 換句話說, DxD_xDx無環.

令Sx,TxS_x, T_xSx,Tx分别代表DxD_xDx中入度(in-degree)為0和出度(out-degree)為0的點集. 以上圖為例, Sx={1,2}S_x = \{1, 2\}Sx={1,2}(藍色的點), Tx={4,6,7}T_x=\{4, 6, 7\}Tx={4,6,7}(紅色的點). 對任意的s∈Sxs\in S_xs∈Sx, t∈Txt\in T_xt∈Tx, 用Ps,txP^x_{s,t}Ps,tx代表從sss到ttt的路徑. 令u(Ps,tx)u(P^x_{s,t})u(Ps,tx)代表Ps,txP^x_{s,t}Ps,tx中頂點的總權重, 即

u(Ps,tx)=∑i∈Ps,txuix=∑i∈Ps,txli.u(P^x_{s, t}) = \sum_{i\in P^x_{s,t}}{u^x_i} = \sum_{i\in P^x_{s,t}}{l_i}.u(Ps,tx)=i∈Ps,tx∑uix=i∈Ps,tx∑li.

考慮到裝入箱子的物品總長度不能超過箱子的長, 我們要求max⁡s∈Sx,t∈Txu(Ps,tx)≤L\max_{s\in S_x, t\in T_x} u(P^x_{s, t}) \leq Lmaxs∈Sx,t∈Txu(Ps,tx)≤L.

用類似的方法考慮yyy軸和zzz軸方向并構造Dy=(V,uy,Ay)D_y=(V, u^y, A_y)Dy=(V,uy,Ay)和Dz=(V,uz,Az)D_z=(V,u^z, A_z)Dz=(V,uz,Az), 其中

uiy=wiu^y_i=w_iuiy=wi, uiz=hiu^z_i=h_iuiz=hi, i=1,2,…,ni=1, 2, \ldots, ni=1,2,…,n.
(i,j)∈Ay(i, j) \in A_y(i,j)∈Ay表示iii在jjj的後方(反之iii在jjj的前方).
(i,j)∈Az(i, j) \in A_z(i,j)∈Az表示iii在jjj的下方(反之iii在jjj的上方).

下面我們得到所有物品能裝入箱子的充要條件:

G=(V,E(Ax∪Ay∪Az))G=(V, E(A_x\cup A_y \cup A_z))G=(V,E(Ax∪Ay∪Az))是一個團(Clique), 其中記号E(A)E(A)E(A)代表有向邊集合AAA對應的無向邊集合.
max⁡s∈Sx,t∈Txu(Ps,tx)≤L\max_{s\in S_x, t\in T_x} u(P^x_{s, t}) \leq Lmaxs∈Sx,t∈Txu(Ps,tx)≤L.
max⁡s∈Sy,t∈Tyu(Ps,ty)≤W\max_{s\in S_y, t\in T_y} u(P^y_{s, t}) \leq Wmaxs∈Sy,t∈Tyu(Ps,ty)≤W.
max⁡s∈Sz,t∈Tzu(Ps,tz)≤H\max_{s\in S_z, t\in T_z} u(P^z_{s, t}) \leq Hmaxs∈Sz,t∈Tzu(Ps,tz)≤H.

搜尋政策

結合前文的讨論, 我們先總結分支的因素:

需要比較任意兩個物品之間的相對位置, 共有Cn2C_n^2Cn2種情況.
兩個物品之間共有6種相對位置關系: 左右, 後前, 下上.
每種物品最多有6種不同的擺放方式: (l,w,h),(l,h,w),(w,l,h),(w,h,l),(h,l,w),(h,w,l)(l, w, h), (l, h, w), (w, l, h), (w, h, l), (h, l, w), (h, w, l)(l,w,h),(l,h,w),(w,l,h),(w,h,l),(h,l,w),(h,w,l).

用Ik(1≤k≤n)I_k (1\leq k \leq n)Ik(1≤k≤n)表示一個裝箱問題的執行個體, 其中物品集合為{1,2,…,k}\{1, 2, \ldots, k\}{1,2,…,k}. 我們搜尋的政策是用深度優先的方式依次判斷I1,I2,…,InI_1, I_2, \ldots, I_nI1,I2,…,In的可行性. 設IkI_kIk可行. 考慮Ik+1I_{k+1}Ik+1時, 我們需要對比(1,k+1),(2,k+1),…,(k,k+1)(1, k+1), (2, k+1), \ldots, (k, k+1)(1,k+1),(2,k+1),…,(k,k+1). 此外, 對每個物品對(pair) (i,k+1)(i, k+1)(i,k+1), 1≤i≤k1\leq i\leq k1≤i≤k, 我們要考慮6×6=366\times 6 = 366×6=36種相對位置和排放方式. 是以, 對IkI_kIk的任意一搜尋節點, 它的分支數量是36k36k36k(示意圖如下).

說明 : 從根節點root開始搜尋. 第一層是判斷I1I_1I1是否可行, 由于I1I_1I1包含1個物品, 是以隻需要考慮6種擺放方式, 即(1)1,…,(1)6(1)^1, \ldots, (1)^6(1)1,…,(1)6; 第二層判斷I2I_2I2是否可行, 需要比較兩個物品(1,2)(1, 2)(1,2), 其中每個節點有36個分支, 對應6種相對位置關系和物品2的六種擺放方式的組合; 第三, 四層判斷I3I_3I3是否可行, 需要比較(1,3)(1,3)(1,3)和(2,3)(2,3)(2,3); 依次類推.

注意 : 分支前必須檢查兩個物品間是否已經有位置關系, 若有, 則目前節點不需要分支(確定無環). 例如, 如果物品1在物品2的左邊, 物品2在物品3的左邊, 那麼物品1一定在物品3的左邊, 是以無需比較物品3在物品1左邊的情況.

優化政策

物品的排序比較重要. 直覺的做法是把物品按照體積由大到小排序.
物品的擺放方式實際上是1-6種. 如果物品是立方體, 則隻需要考慮1種擺放方式. 在實際中應該額外考慮三邊相同和兩邊相同的情況.
判定I2I_2I2時可以考慮物品的對稱性, 是以相對位置隻要考慮左, 後, 下.
比較物品間的相對位置時按照"從外到内"的原則, 即右, 前, 上, 左, 後, 下.

可行性判定

考慮三維裝箱執行個體IkI_kIk, 1≤k≤n1\leq k\leq n1≤k≤n. 令Dxk,Dyk,DzkD^k_x, D^k_y, D^k_zDxk,Dyk,Dzk為x,y,zx,y,zx,y,z軸方向的有向無環圖. 令Dk=(Dxk,Dyk,Dzk)D^k=(D^k_x, D^k_y, D^k_z)Dk=(Dxk,Dyk,Dzk). 如上圖所示, 我們的搜尋過程需要判斷D1,D2,…,DnD^1, D^2, \ldots, D^nD1,D2,…,Dn的可行性. 考慮DkD^kDk: 頂點個數是3k3k3k, 邊的個數是O(k2)O(k^2)O(k2), 是以最長路(頂點權重之和最大) 的計算可以在O(k2)O(k^2)O(k2)的時間内完成. 具體來說, 以DxkD^k_xDxk為例, 我們可以維護每個頂點i(1≤i≤k)i(1\leq i\leq k)i(1≤i≤k)的最長路程. 當考慮Dxk+1D^{k+1}_xDxk+1時, 例如增加弧(i,k+1)(i, k+1)(i,k+1)或(k+1,i)(k+1, i)(k+1,i), 我們隻需要更新k+1k+1k+1所有子節點的最長路程即可.

時間複雜度

搜尋樹第kkk層(root是第0層)對應的節點數量是36k−136^{k-1}36k−1. 如上圖所示, 執行個體Ik(≥2)I_k(\geq 2)Ik(≥2)包含了k−1k-1k−1層. 是以, 從第二層到葉子節點一共有n(n−1)/2n(n-1)/2n(n−1)/2層. 是以, 搜尋樹的節點總數NNN為:

N=∑k=1n(n−1)/236k−1+7=O(6n2).N = \sum_{k=1}^{n(n-1)/2} 36^{k-1} + 7 = O(6^{n^2}).N=k=1∑n(n−1)/236k−1+7=O(6n2).

每個節點判斷可行性的時間為O(n2)O(n^2)O(n2). 是以算法的時間複雜度為O(6n2⋅n2)O(6^{n^2}\cdot n^2)O(6n2⋅n2).