[發明專利]一種用基于動態規劃的多車廂物料車貨位優化方法

在審

• 申請號: 202011604140.1
• 申請日: 2020-12-29
• 公開（公告）號: CN112581032A
• 公開（公告）日: 2021-03-30
• 發明（設計）人: 蔡敏;沈瓊瑋
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/08;G06F30/20;G06F30/15
• 代理公司: 浙江千克知識產權代理有限公司 33246
• 代理人: 周希良

1.一種用基于動態規劃的多車廂物料車貨位優化方法，其特征在于，包括步驟：

S1.確定與多車廂物料車貨位相關的參數；

S2.基于確定的參數，建立多車廂物料車貨位優化模型；

S3.采用動態規劃算法求解建立的多車廂物料車貨位優化模型，輸出貨位指派方案。

2.根據權利要求1所述的一種用基于動態規劃的多車廂物料車貨位優化方法，其特征在于，所述步驟S1中確定的參數包括物料盒的數量與重量、多車廂物料車車廂數、貨架層數、貨架高度。

3.根據權利要求2所述的一種用基于動態規劃的多車廂物料車貨位優化方法，其特征在于，所述步驟S2中建立多車廂物料車貨位優化模型，表示為：

其中，MinE_p(x)表示以最小化總裝在所需能量為目標函數，建立多車廂物料車貨位優化模型；δ(k,l)表示工人將物料盒k放到貨架l上所需的能量；

s.t.

其中，公式(1)為目標函數；公式(2)為決策變量；公式(3)為每個物料盒會被指派到一個物料架上；公式(4)為兩個目的工位相同的物料盒會被安排在同一節車廂；公式(5)為每層貨架不會超載。

4.根據權利要求3所述的一種用基于動態規劃的多車廂物料車貨位優化方法，其特征在于，所述步驟S3具體為：

S31.根據工位需求量求解可行的工位劃分方案；

S32.對可行解進行優化并最終求得可行解。

5.根據權利要求4所述的一種用基于動態規劃的多車廂物料車貨位優化方法，其特征在于，所述步驟S31具體為：

根據物料車的車廂總數，將動態規劃程序劃分成W+1個階段其中，用符號r＝0,…,W表示；每個階段都包含狀態Γ，表示需求物料盒已經被安排到車廂上的工位的集合。

6.根據權利要求5所述的一種用基于動態規劃的多車廂物料車貨位優化方法，其特征在于，所述步驟S31還包括：動態規劃進入下一個階段r+1應滿足以下三個規則：

a.λ中包含的工位的物料盒總需求量不能超過一節車廂的最大負載量，即∑_i∈λ|B_i|≤m_r·μ；

b.尚未被指派的工位的物料盒總需求量不能超過剩余車廂的最大總負載量，要有足夠的空間來存放未被指派的工位需求的物料盒，即

c.僅當min{i∈λ}＜min{i∈S(λ∪Γ)}成立時，才將λ加入Γ。

7.根據權利要求4所述的一種用基于動態規劃的多車廂物料車貨位優化方法，其特征在于，所述步驟S32具體為：

S321.采用匈牙利算法對問題進行求解；

S322.對于每一個可行解執行以下步驟：

S3221.計算將Λ＝{λ₁,……,λ_W}中每個子集中的工位對應的物料盒分配到某節車廂上可以達到的最小裝卸能耗，并記錄此時的物料盒與各貨架上物料盒位的對應關系；

S3222.將所有子集可達到的最小能量消耗相加，從而得到該可行解可達到的最小裝卸能耗。

S3223.挑選出可達到的最小能量消耗最小的可行物料盒劃分方案，對應的貨位指派方案即為最優解。

8.根據權利要求7所述的一種用基于動態規劃的多車廂物料車貨位優化方法，其特征在于，所述步驟S321中采用匈牙利算法對問題進行求解，表示為：

s.t.

其中，公式(6)是最小化裝卸這些物料盒會造成的能量消耗。約束(7)和(8)保證了每個物料盒會且僅會被安排到一個位置，每個位置也會且僅會放置一個物料盒；約束(9)表示決策變量z_tk是一個只能在{0,1}中取值的二元變量。

9.根據權利要求7所述的一種用基于動態規劃的多車廂物料車貨位優化方法，其特征在于，所述步驟S3223中還包括：令V(Γ)為轉移到狀態Γ前的狀態集合，目標函數值E(Γ,r)的計算方法如下：

E(Γ,r)＝min_{Γ′∈V(Γ)}{E(Γ′,r-1)+g^*(∪_i∈Γ\Γ′K_i,r)} (10)

其中，初始狀態下g^*是通過匈牙利算法求得的將一批既定的物料盒∪_i∈Γ\Γ′K_i裝載車廂r上所需的最小能量；在到達最終狀態Γ＝S時的E(S,W)即為目標函數值，對應的指派方案即為最優解。