[發明專利]一種行包裝配方法

有效

• 申請號: 201810973498.8
• 申請日: 2018-08-24
• 公開（公告）號: CN109255372B
• 公開（公告）日: 2022-04-01
• 發明（設計）人: 張云翔;李厚恩;饒竹一;喻越;鐘曉雄;張盛
• 申請（專利權）人: 深圳供電局有限公司
• 主分類號: G06V10/774
• 分類號: G06V10/774;G06K9/62
• 代理公司: 深圳匯智容達專利商標事務所(普通合伙) 44238
• 代理人: 潘中毅;熊賢卿

1.一種行包裝配方法，其特征在于，包括如下步驟：

S1、根據行包特征以及裝配的總層數，采用SVM一對一算法對所述行包進行分層分類，獲得每一行包的分類層級；

S2、針對每一分類層級，對分入所述分類層級的行包進行編號，根據行包特征建立背包問題模型，所述背包問題模型以所有行包的配送利潤最大值為目標函數；

S3、求解所述目標函數，獲得行包的裝配方案；

所述采用SVM一對一算法對所述行包進行分層分類具體包括：

求解分類決策函數；

根據所述分類決策函數采用一對一分類法進行分類；

其中，求解分類決策函數具體包括：

構建行包特征和行包分類層級的數據集合：任意一個行包x_i的行包特征為x_i＝(l_i,d_i,h_i,v_i,m_i,γ_i)，其中l_i為行包的長度，d_i為行包的寬度，h_i為行包的高度，v_i為行包的體積，γ_i為行包的易碎度；該行包x_i的分類結果用y_i表示，y_i的取值為1或者-1；

根據數據集合和超平面方程獲得分類最優化問題：對于線性可分的數據集(x_i,y_i)，存在超平面w^Tx+b＝0對樣本集中的任一點(x_i,y_i)都滿足：

空間中的樣本點到分類超平面的距離為d＝|w^Tx_i+b|/||w||，當w^Tx_i+b＝±1時，超平面的分類間隔為2/||w||，最優化問題表示為：

s.t.y_i(w·x_i+b)-1≥0,

利用拉格朗日乘子法，求解該優化問題的對偶問題，并獲得其等價的對偶問題的最優化問題為：

α_i≥0

其中，i＝1,2,…,N；

采用序列最小最優化算法求解出α_i的最優解獲得w的最優解

2.根據權利要求1所述的裝配方法，其特征在于，所述行包的特征具體包括：

每個行包的長度、寬度、高度、體積、重量和易碎度。

3.根據權利要求1所述的裝配方法，其特征在于，所述步驟S2中建立背包問題模型具體包括：

對每一層級的行包進行編號，則背包問題模型表示為：

其中，x_ij表示第i層第j件行包，w_ij表示第i層第j件行包的重量，v_ij表示第i層第j件行包的體積，p_ij表示第i層第j件行包的利潤，S表示裝配運輸工具的底面積，V表示裝配運輸工具的體積，W表示裝配運輸工具的重量，m為裝配的總層數，n_i為每i層的行包總數。

4.根據權利要求3所述的裝配方法，其特征在于，所述步驟S3具體包括：

利用動態規劃算法獲得每一層級的動態規劃問題；

采用貪心算法求得行包的裝配方案。

5.根據權利要求4所述的裝配方法，其特征在于，所述利用動態規劃算法獲得每一層及的動態規劃問題具體為：

f(n_i,S,W_i)＝max{f(n_i-1,S,W_i),f(n_i-1,S-s_in,W_i-w_in)+p_in}

其中，f(n_i,S,W_i)表示第i層的最大效益，n_i表示分類為第i層的行包數量，W_i＝W-W_i-1-…-W₁為第i層所剩余的可裝配的最大重量；f(n,s,w)為第i層的第n個行包的利益，s_in是第i層第n個行包的底面積，w_in是第i層第n個行包的重量。