[發明專利]一種基于變鄰域NSGA-Ⅱ算法的多目標貨位優化方法

有效

• 申請號: 201911247460.3
• 申請日: 2019-12-09
• 公開（公告）號: CN110991754B
• 公開（公告）日: 2021-03-16
• 發明（設計）人: 張劍;羅煥;鄧停銘;閆富強;付建林;江海凡
• 申請（專利權）人: 西南交通大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/12
• 代理公司: 成都信博專利代理有限責任公司 51200
• 代理人: 舒啟龍

1.一種基于變鄰域NSGA-Ⅱ算法的多目標貨位優化方法，其特征在于，包括：

步驟1：貨物和倉庫參數確定：設定倉庫貨物屬性，確定貨架、堆垛機和傳送帶參數；設出入庫口位置坐標為(0,0,0)；則(x,y,z)表示貨物放置在第x排y列z層的貨位上；

步驟2：建立貨位分配多目標優化的數學模型：以出入庫效率、貨架整體重心、同類貨物間距離、巷道堆垛機工作量分別建立目標模型；

2.1出入庫效率模型

式中，x表示倉庫第x排貨架，x＝{1,2,3...,X}；y表示倉庫第y列貨架，y＝{1,2,3...,Y}；z表示倉庫第z層貨架，z＝{1,2,3...,Z}；p_ji表示第i類貨物中第j個貨物的出入庫頻率；(x_ji,y_ji,z_ji)表示第i類貨物中第j個貨物的貨位坐標；t(x_ji,y_ji,z_ji)表示第i類貨物中第j個貨物從倉庫出口到貨位的時間，其計算公式如下：

式中，v_x表示傳送帶沿水平方向的平均速度；v_y表示堆垛機沿巷道方向的平均速度；v_z表示堆垛機沿豎直方向的平均速度；L₀代表巷道寬度；L代表貨位寬度；

2.2貨架整體重心模型

式中，m_ji代表第i類貨物中第j個貨物的重量；

2.3同類貨物間距離模型

用同類貨物到該類貨物位置中心的距離差之和作為同類貨物間的距離，其計算公式如下：

式中，A_i代表第i類貨物的中心坐標的橫坐標，B_i代表第i類貨物的中心坐標的縱坐標，C_i代表第i類貨物的中心坐標的豎坐標，其計算公式如下：

式中，J代表第i類貨物的總數；

2.4巷道堆垛機工作量均衡模型

巷道堆垛機工作量均衡用巷道兩側貨架上堆放貨物總數來反映該巷道堆垛機的工作量，為了使各條巷道堆垛機工作量均衡將同類貨物均勻分布到各條巷道兩側的貨架上，由此可以使得各巷道堆垛機工作量均衡且貨物的分布也更加均勻，其公式如下：

式中：h代表巷道序號；H代表巷道總數；h(x_ji,y_ji,z_ji)表示第i類貨物中第j個貨物在不在巷道h中，如果i類貨物中第j個貨物在巷道h中則h(x_ji,y_ji,z_ji)＝1，否則h(x_ji,y_ji,z_ji)＝0；

2.5將上述目標模型函數集合成多目標優化函數，具體如下：

min[f₁(x,y,z),f₂(x,y,z),f₃(x,y,z),f₄(x,y,z)] (7)

式中：f₁(x,y,z)表示出入庫效率；f₂(x,y,z)貨架整體重心；f₃(x,y,z)同類貨物間距離；f₄(x,y,z)巷道堆垛機工作量；約束條件為：

1≤h≤H且h為正整數 (9)

式中：G_(x)max代表第x排貨架的最大承重；式(8)表示倉庫貨架的行數、列數、層數不能超過其最大值；式(9)表示倉庫巷道數不能超過最大巷道數H；式(10)表示貨架x的存放貨物的總重量不能超過貨架最大承重；

步驟3：變鄰域NSGA-II算法優化求解模型，得出最優貨位分配方案：變鄰域NSGA-Ⅱ算法步驟如下：

3.1初始化參數：設置種群大小為PopSize，交叉概率為Pc，變異概率為Pm，最大迭代次數為Gmax，最優前端個體系數P_F，鄰域初始種群大小VNSize，變鄰域最大循環次數VNS_Gmax；

3.2初始化種群：采用實數編碼隨機生成初始種群Initial_Pop；

3.3目標函數值的計算：根據公式(1)、(3)、(4)、(6)計算四個目標函數值f₁、f₂、f₃、f₄；

3.4非支配排序和擁擠度計算：

3.4.1非支配排序：根據目標函數值進行個體序值的計算；

3.4.2擁擠距離計算：對四個目標分別計算相應的擁擠距離，再將四個目標函數的擁擠距離相加得到最后的擁擠距離；

3.5遺傳操作：

3.5.1選擇操作：錦標賽選擇，根據序值和擁擠度進行選擇操作，對于種群中的兩個隨機個體，當序值不同時，序值小的個體將被選中；當序值相同時，擁擠距離大的個體將被選中；

3.5.2交叉：單點交叉，并運用同位基因的思想進行交叉前的處理；

3.5.3變異：為避免在前兩個操作中優秀基因的丟失，選擇隨機性更大的對調基因位的變異方式；

3.6變領域操作：從變異后種群中隨機選部分個體進行變鄰域操作，變鄰域操作流程如下：

3.6.1對初始鄰域種群進行鄰域操作；

3.6.2將變鄰域產生的種群與初始鄰域種群進行合并；

3.6.3對合并后的種群進行選擇得到新一代鄰域種群；

3.6.4判斷是否滿足鄰域終止條件，滿足則結束變鄰域操作得到變鄰域解集，不滿足則返回3.6.1繼續執行變鄰域操作直到滿足鄰域終止條件；

3.7種群合并：將變領域搜索產生的個體與變異之后未進行變鄰域操作的個體合并再與初始父種群合并；

3.8生成新種群：根據父代種群規模對合并后的種群進行修剪生成新的父代種群；

3.9判斷是否達到終止條件，若滿足則結束，否則，轉去執行步驟3.5。