多批次的訂單分揀系統貨架分配演算法是怎麼樣的？

01-21

小弟供職於某電商公司，公司有自己的加工中心，加工中心的重要職責之一就是根據收到的訂單，為客戶分揀打包好每個訂單中包含的產品。
常規分揀流程：每天結單後，系統會統計好當天所有訂單中包含的所有產品，並分別放入分揀貨架，一個貨架放置一種產品。
例--------------------------------------------------------------
當天供有4個訂單：
訂單1（包含產品,Ax1、Bx3、Cx2、Dx4）

訂單2（包含產品,Bx2、Cx3、Dx2、Ex2）
訂單3（包含產品,Cx2、Dx4、Ex2、Fx2）
訂單4（包含產品,Ax1、Bx3、Cx2、Dx2）
那麼，系統會統計出：
當天所有訂單共包含產品：Ax1、Bx8、Cx9、Dx12、Ex4、Fx2，
轉運工會將這些產品按指定數量分別放置到6個貨架上
分揀工每拿到一個訂單，分揀貨架上相應產品的貨架格子燈會亮起，分揀工根據亮燈情況將產品放入該訂單盒子，完成一次分揀
---------------------------------------------------------------------------------
目前的問題來了，之前公司有100個分揀貨架。當天訂單產品種數之和小於100時，這套系統工作正常沒有問題，但是隨著公司業務量的不斷增大，每天的訂單產品種數總和一但大於100時，系統肯定無法工作了。最簡單的辦法就是增加物理貨架的個數，但由於場地等其他原因，投入非常巨大，並且物流貨架也不可能無限制的增加，所以我們想通過軟體演算法去解決這個問題，我相信業內一定有同樣的處理辦法，思路如下：
例：

系統將每天的訂單分為多個批次，保證每個批次的訂單所包含產品種類小於或等於100，且這批訂單中包含的種數小於或等於100種，這樣以後無論產品種數怎麼提升無非就是訂單分解成幾批次的問題了。但是目前困擾的就是這個最優演算法改怎麼寫？
例：今天所有訂單產品類目總和是170種，共100個訂單，每個訂單中包含的產品及數量是已知的，只有100個分揀貨架。
求解：將這些訂單拆分成幾個批次（批次數越小越好，減少轉運次數），每個批次的訂單包含的產品種數小於或等於100，那麼應該怎麼分？每個批次應該具體是哪些訂單？求一個最優解
該演算法已經超出小弟知識範圍，請數學大牛支招----萬分感謝！

謝邀。

也感謝 @王贇 Maigo 寫的答案，已經建立了一個很好的模型。看了問題評論，題主表示「拆單的問題可以忽略不計」，所以接下來就只討論第一種模型。

這裡我在王贇同學的模型基礎上，再把問題重新描述一下：

設 $Din{0,1}^{m imes n}$ ，用來表示所有的訂單，每一行表示一個訂單，一個訂單里需要的物品，就在相應的列上置1，否則就是0，比如（還是拿王贇同學的例子）

$D=left[egin{array}{ccccc}01101\11000\11001\00111end{array} ight]$

第一行表示1號訂單中有2、3、5號產品，以此類推。按照題主的假設，沒有拆單，也就是說D矩陣每一行的元素加起來，不會超過貨架個數（我們設為 k 吧）

現在我做一點操作，怎麼操作呢，就是在某些元素的位置上加1。比如我在第2行最後一個元素位置上加1，於是第2行和第3行就變成一樣了：

$D+E=left[egin{array}{ccccc}01101\11000\11001\00111end{array} ight]+left[egin{array}{ccccc}00000\00001\00000\00000end{array} ight]=left[egin{array}{ccccc}01101\11001\11001\00111end{array} ight]=A$

這樣我們就可以看出來，第1行可以單獨成為一批，第2行和第3行可以合併為一批，第4行還是單獨一批。並且很容易看出，在某些位置加1的這個操作，對訂單分批來說，是沒有影響的。

那麼A矩陣為什麼就可以分為這樣3批呢？因為A矩陣的秩（rank）是3，也就是說，A矩陣的秩是多少，就可以分為多少批。

所以我們的目標就明確了：需要做一些操作，在原始矩陣的某些位置上加1，使得結果的矩陣的秩（rank）要越小越好，當然，A矩陣每一行的元素加起來不能超過貨架個數（也就是 k）

用數學式子表達出來，就是（對矩陣E的約束做了鬆弛）：

$egin{array}{cl}minmbox{rank}(A)\[.2em]mbox{s.t.}A=D+E\[.2em]0le Ele 1\[.2em]Acdotmathbf{e}le kend{array}$

其中， $mathbf{e}=[1,1,dots,1]^T$

這就轉化為一個優化問題了，不過很遺憾，這個優化問題是不好求解的（我沒仔細證明過是不是NP，在E矩陣滿足原始約束的情況下應該是對的，鬆弛之後我不能確定，但至少是非凸的，這就不好求解了）

雖然嚴格求解不好解，但是我們可以求一個近似解。我們可以用核範數（nuclear norm）來近似秩（rank），也就是把優化的目標函數變成：

$minquad|A|_*$

這就變成一個凸優化問題了，就可以有很多有效的方法快速地進行求解！

比如用 Boyd 教授開發的 CVX 工具包（CVX: Matlab Software for Disciplined Convex Programming），幾行代碼就搞定了

cvx_clear; cvx_begin variables matE(m,n) matA(m,n); minimize(norm_nuc(matA)); subject to 0 &<= matE &<= 1; matA == matD + matE; matA*vecE &<= k; cvx_end

這裡 matA 就是最後的結果，把 matA 里重複的行去掉，每一行就是一個批次了！每一行裡面的1就是要取的物品。

這雖然是鬆弛了目標函數之後得到的近似解，但是在實際應用中應該也足夠用了。

我還沒能解決題主的問題。說一下我到目前為止的思路吧，權當拋磚引玉。我甚至都不保證我思考的方向是正確的。

首先，既然貨架的容量可以當作無限大（見原題評論），那麼，每個訂單中每種產品的數量就不重要了，重要的只是有無。於是可以用一個0/1向量表示一個訂單，向量的長度是所有產品的種類數，向量中的1表示訂單中有這種產品，0表示沒有。所有訂單的向量可以排成矩陣，例如：

$left[ egin{matrix} 0 1 1 0 1 \ 1 1 0 0 0 \ 1 1 0 0 1 \ 0 0 1 1 1 end{matrix} ight]$

第一行表示1號訂單中有2、3、5號產品，以此類推。

現在假設只有3個貨架（100太大了，畫不來……），那麼上邊這批訂單可以這樣處理：

1) 先用3個貨架分別裝1、2、5號產品，搞定2、3號訂單；

2) 再用3個貨架分別裝2、3、5號產品，搞定1號訂單；

3) 最後用3個貨架分別裝3、4、5號產品，搞定4號訂單。

這樣總共需要3個批次。

把上面的矩陣的行列交換一下次序，讓新矩陣的每行分別對應原矩陣的第2、3、1、4行，每列分別對應原矩陣的第1、2、5、3、4列（即按照處理訂單和產品的順序排列），可以看得更清晰：

$left[ egin{matrix} [1 1 0] 0 0 \ [1 1 1] 0 0 \ 0 [1 1 1] 0 \ 0 0 [1 1 1] end{matrix} ight]$

矩陣沿對角線形成三個塊（前兩行是一個塊，排版比較困難……），各塊之間沒有重疊的行，每個塊的寬度都是3（貨架數目），且從左向右排列。每個塊代表一個批次。

我對原問題的建模就是：尋找一種交換訂單矩陣各行各列的方法，使得交換後的矩陣能夠劃分成儘可能少的塊。

然後我發現我不會解這個問題……

==========================

然後題主又提出說，可以把包含產品種類比較多的訂單拆開。

這樣的話，就又有一種思路：不是按行分批，而是按列分批，像這樣：

$left[ egin{matrix} 1 1 | 0 0 0 \ 1 1 | 1 0 0 \ 0 1 | 1 1 0 \ 0 0 | 1 1 1 end{matrix} ight]$

豎線左右分別是兩批，但是這樣有兩個訂單被拆了。

與之前的思路相比，這種思路要求解的問題有兩點不同：

1) 只需要考慮交換各列，不需要考慮交換各行（雖然把矩陣排成對角的樣子思考更方便）；

2) 目標函數要綜合考慮批數和被拆開的訂單數了。

很不幸，這個問題我也不知道怎麼解……