小弟供職于某電商公司，公司有自己的加工中心，加工中心的重要職責之一就是根據收到的訂單，為客戶(hù)分揀打包好每個(gè)訂單中包含的產(chǎn)品。常規分揀流程：每天結單后，系統會(huì )統計好當天所有訂單中包含的所有產(chǎn)品，并分別放入分揀貨架，一個(gè)貨架放置一種產(chǎn)品。例--------------------------------------------------------------當天供有4個(gè)訂單：訂單1（包含產(chǎn)品,Ax1、Bx3、Cx2、Dx4）訂單2（包含產(chǎn)品,Bx2、Cx3、Dx2、Ex2）訂單3（包含產(chǎn)品,Cx2、Dx4、Ex2、Fx2）訂單4（包含產(chǎn)品,Ax1、Bx3、Cx2、Dx2）那么，系統會(huì )統計出：當天所有訂單共包含產(chǎn)品：Ax1、Bx8、Cx9、Dx12、Ex4、Fx2，轉運工會(huì )將這些產(chǎn)品按指定數量分別放置到6個(gè)貨架上分揀工每拿到一個(gè)訂單，分揀貨架上相應產(chǎn)品的貨架格子燈會(huì )亮起，分揀工根據亮燈情況將產(chǎn)品放入該訂單盒子，完成一次分揀---------------------------------------------------------------------------------目前的問(wèn)題來(lái)了，之前公司有100個(gè)分揀貨架。當天訂單產(chǎn)品種數之和小于100時(shí)，這套系統工作正常沒(méi)有問(wèn)題，但是隨著(zhù)公司業(yè)務(wù)量的不斷增大，每天的訂單產(chǎn)品種數總和一但大于100時(shí)，系統肯定無(wú)法工作了。最簡(jiǎn)單的辦法就是增加物理貨架的個(gè)數，但由于場(chǎng)地等其他原因，投入非常巨大，并且物流貨架也不可能無(wú)限制的增加，所以我們想通過(guò)軟件算法去解決這個(gè)問(wèn)題，我相信業(yè)內一定有同樣的處理辦法，思路如下：例：系統將每天的訂單分為多個(gè)批次，保證每個(gè)批次的訂單所包含產(chǎn)品種類(lèi)小于或等于100，且這批訂單中包含的種數小于或等于100種，這樣以后無(wú)論產(chǎn)品種數怎么提升無(wú)非就是訂單分解成幾批次的問(wèn)題了。但是目前困擾的就是這個(gè)最優(yōu)算法改怎么寫(xiě)？例：今天所有訂單產(chǎn)品類(lèi)目總和是170種，共100個(gè)訂單，每個(gè)訂單中包含的產(chǎn)品及數量是已知的，只有100個(gè)分揀貨架。求解：將這些訂單拆分成幾個(gè)批次（批次數越小越好，減少轉運次數），每個(gè)批次的訂單包含的產(chǎn)品種數小于或等于100，那么應該怎么分？每個(gè)批次應該具體是哪些訂單？求一個(gè)最優(yōu)解該算法已經(jīng)超出小弟知識范圍，請數學(xué)大牛支招----萬(wàn)分感謝！
我還沒(méi)能解決題主的問(wèn)題。說(shuō)一下我到目前為止的思路吧，權當拋磚引玉。我甚至都不保證我思考的方向是正確的。
首先，既然貨架的容量可以當作無(wú)限大（見(jiàn)原題評論），那么，每個(gè)訂單中每種產(chǎn)品的數量就不重要了，重要的只是有無(wú)。于是可以用一個(gè)0/1向量表示一個(gè)訂單，向量的長(cháng)度是所有產(chǎn)品的種類(lèi)數，向量中的1表示訂單中有這種產(chǎn)品，0表示沒(méi)有。所有訂單的向量可以排成矩陣，例如：
第一行表示1號訂單中有2、3、5號產(chǎn)品，以此類(lèi)推。
現在假設只有3個(gè)貨架（100太大了，畫(huà)不來(lái)……），那么上邊這批訂單可以這樣處理：
1) 先用3個(gè)貨架分別裝1、2、5號產(chǎn)品，搞定2、3號訂單；
2) 再用3個(gè)貨架分別裝2、3、5號產(chǎn)品，搞定1號訂單；
3) 最后用3個(gè)貨架分別裝3、4、5號產(chǎn)品，搞定4號訂單。
這樣總共需要3個(gè)批次。
把上面的矩陣的行列交換一下次序，讓新矩陣的每行分別對應原矩陣的第2、3、1、4行，每列分別對應原矩陣的第1、2、5、3、4列（即按照處理訂單和產(chǎn)品的順序排列），可以看得更清晰：
矩陣沿對角線(xiàn)形成三個(gè)塊（前兩行是一個(gè)塊，排版比較困難……），各塊之間沒(méi)有重疊的行，每個(gè)塊的寬度都是3（貨架數目），且從左向右排列。每個(gè)塊代表一個(gè)批次。
我對原問(wèn)題的建模就是：尋找一種交換訂單矩陣各行各列的方法，使得交換后的矩陣能夠劃分成盡可能少的塊。
然后我發(fā)現我不會(huì )解這個(gè)問(wèn)題……
==========================
然后題主又提出說(shuō)，可以把包含產(chǎn)品種類(lèi)比較多的訂單拆開(kāi)。
這樣的話(huà)，就又有一種思路：不是按行分批，而是按列分批，像這樣：
豎線(xiàn)左右分別是兩批，但是這樣有兩個(gè)訂單被拆了。
與之前的思路相比，這種思路要求解的問(wèn)題有兩點(diǎn)不同：
1) 只需要考慮交換各列，不需要考慮交換各行（雖然把矩陣排成對角的樣子思考更方便）；
2) 目標函數要綜合考慮批數和被拆開(kāi)的訂單數了。
很不幸，這個(gè)問(wèn)題我也不知道怎么解……
謝邀。
也感謝 @王赟 Maigo
寫(xiě)的答案，已經(jīng)建立了一個(gè)很好的模型?？戳藛?wèn)題評論，題主表示「拆單的問(wèn)題可以忽略不計」，所以接下來(lái)就只討論第一種模型。
這里我在王赟同學(xué)的模型基礎上，再把問(wèn)題重新描述一下：
設，用來(lái)表示所有的訂單，每一行表示一個(gè)訂單，一個(gè)訂單里需要的物品，就在相應的列上置1，否則就是0，比如（還是拿王赟同學(xué)的例子）
第一行表示1號訂單中有2、3、5號產(chǎn)品，以此類(lèi)推。按照題主的假設，沒(méi)有拆單，也就是說(shuō)D矩陣每一行的元素加起來(lái)，不會(huì )超過(guò)貨架個(gè)數（我們設為 k 吧）
現在我做一點(diǎn)操作，怎么操作呢，就是在某些元素的位置上加1。比如我在第2行最后一個(gè)元素位置上加1，于是第2行和第3行就變成一樣了：
這樣我們就可以看出來(lái)，第1行可以單獨成為一批，第2行和第3行可以合并為一批，第4行還是單獨一批。并且很容易看出，在某些位置加1的這個(gè)操作，對訂單分批來(lái)說(shuō)，是沒(méi)有影響的。
那么A矩陣為什么就可以分為這樣3批呢？因為A矩陣的秩（rank）是3，也就是說(shuō)，A矩陣的秩是多少，就可以分為多少批。
所以我們的目標就明確了：需要做一些操作，在原始矩陣的某些位置上加1，使得結果的矩陣的秩（rank）要越小越好，當然，A矩陣每一行的元素加起來(lái)不能超過(guò)貨架個(gè)數（也就是 k）
用數學(xué)式子表達出來(lái)，就是（對矩陣E的約束做了松弛）：
其中，
這就轉化為一個(gè)優(yōu)化問(wèn)題了，不過(guò)很遺憾，這個(gè)優(yōu)化問(wèn)題是不好求解的（我沒(méi)仔細證明過(guò)是不是NP，在E矩陣滿(mǎn)足原始約束的情況下應該是對的，松弛之后我不能確定，但至少是非凸的，這就不好求解了）
雖然嚴格求解不好解，但是我們可以求一個(gè)近似解。我們可以用核范數（nuclear norm）來(lái)近似秩（rank），也就是把優(yōu)化的目標函數變成：
這就變成一個(gè)凸優(yōu)化問(wèn)題了，就可以有很多有效的方法快速地進(jìn)行求解！
比如用 Boyd 教授開(kāi)發(fā)的 CVX 工具包（CVX: Matlab Software for Disciplined Convex Programming
?。?，幾行代碼就搞定了
這里 matA 就是最后的結果，把 matA 里重復的行去掉，每一行就是一個(gè)批次了！每一行里面的1就是要取的物品。
這雖然是松弛了目標函數之后得到的近似解，但是在實(shí)際應用中應該也足夠用了。
為什么要一個(gè)品種一個(gè)貨架呢？ 把一定量的訂單匯總后，把訂單內的所有品種揀在同一貨架或容器里，在分揀到對應的訂單中去
醫用試劑瓶如何分揀？人工分揀？耗時(shí)耗力！馬克拉伯機器視覺(jué)免費軟件SGVision輕松解決，采用的算法為形狀匹配與像素統計的調用。
下方鏈接進(jìn)入馬克拉伯學(xué)院馬克拉伯,一個(gè)機器視覺(jué)應用開(kāi)放社區
醫用試劑瓶分揀（原圖）
一、 檢測與實(shí)現功能
本案例通過(guò)調用相應算法實(shí)現不同試劑瓶的分揀。
二、 檢測系統需求分析
1.為了獲得最優(yōu)的打光效果，這里選用背光源從下往上打光；
2.為了達到檢測要求，這里選用500W黑白網(wǎng)口相機，工業(yè)高像素級25mm定焦鏡頭；
注意：這里背光源打光，所以不需要調整光源角度。我們所須要注意的是相機焦距和物距的調整以及相機參數的設置，將樣品盡量調整到清晰。
三、檢測具體步驟
1.調用形狀匹配算法，選擇樣品1進(jìn)行形狀匹配，選中你想測試的區域并設置模板待用。如下圖： 圖一
注意：這里調用形狀匹配主要是為了給樣品做一個(gè)位置配準，右邊參數要調整好，這樣才能準確找到樣品位置并做糾正。
2.調用像素統計算法，框選樣品1，并設置相應合格范圍。圖二
注意：匹配源一定要選擇我們設置的形狀匹配，合格標準一定要設置在樣品檢測結果范圍內。不然會(huì )顯示NG
3.點(diǎn)擊測試，區分出樣品1和樣品2： 圖三 OK圖，即樣品1圖四 ok圖 樣品1圖五 OK圖樣品1圖六NG圖樣品2圖七 NG圖 樣品2
所有算法設置完，點(diǎn)擊右下方的測試按鈕，檢測所有算法設置是否無(wú)錯誤，若無(wú)，點(diǎn)擊確定退回主界面，點(diǎn)擊主界面“檢測”按鈕即可開(kāi)始檢測產(chǎn)品。
