[發明專利]一種優化倉儲堆垛機揀選策略的改進多目標局部搜索算法

在審

• 申請號: 202210554779.6
• 申請日: 2022-05-20
• 公開（公告）號: CN114896889A
• 公開（公告）日: 2022-08-12
• 發明（設計）人: 劉青松;孫浩;魏立新;趙明達;呼子宇
• 申請（專利權）人: 燕山大學
• 主分類號: G06F30/27
• 分類號: G06F30/27;G06Q10/08;G06N3/00;B66F9/07;G06F111/06
• 代理公司: 西安匯恩知識產權代理事務所(普通合伙) 61244
• 代理人: 彭瓊

本發明提出了一種優化倉儲堆垛機揀選策略的改進多目標局部搜索算法，該算法包括：堆垛機揀選參數初始化，生成堆垛機揀選序列的初始化種群，然后進行優化，獲得較高質量的堆垛機揀選序列初始解，然后計算堆垛機揀選路徑總距離和收集貨物總利潤值兩個目標值，獲得非支配解，存儲精英池中，再繼續優化精英池中解的質量，若滿足終止條件，則結束，否則繼續執行增強擾動策略或者一般擾動策略獲取候選解，并對候選解進行埃普西隆約束的局部搜索策略，獲得最優解更新精英池，跳回迭代搜索。本發明避免大量無效解的產生，綜合提高算法的求解效率，較之傳統的迭代局部搜索具有更好的性能和穩定性。

技術領域

本發明屬于搜索算法技術領域，具體涉及一種優化倉儲堆垛機揀選策略的改進多目標局部搜索算法。

背景技術

在生產制造領域，倉儲運行管理作為提高生產效率的重要環節，其中倉儲管理系統發揮了高效的作用。據統計，訂單揀選流程通常需要占用倉庫運行成本的55％，因此訂單揀選或為智能倉庫中的關鍵問題之一。當多個訂單下達時，堆垛機將需要揀選的貨物按照優化后的序列逐個取出，放置于分揀區，再根據訂單的緊急程度進行揀選。訂單揀選的效率受倉庫貨架布局、貨位擺放位置、堆垛機揀選路徑以及訂單的分批處理等因素。堆垛機的揀選時間占用貨物進出庫的大部分時間，一個訂單批次分為多次作業。堆垛機在高位存儲貨架處可以同時進行水平和垂直方向移動，相比較一般倉庫，能充分利用倉庫空間環境，屬于高級揀選系統。在當今多品種、小批量的生產和消費模式下，應用于倉儲堆垛機揀選的獎品收集車輛路徑問題(Prize Collecting Vehicle Route Problem,PCVRP)模型，是CVRP的一種變體，屬于典型NP-Hard問題。

在大多數現實情況下，不同訂單對決策者的重要性不同，因為不同的訂單能夠提供不同的利潤，此外，由于不同訂單的緊急程度不同，導致揀選序列末尾貨物不再設置利潤值，且部分原材料出庫后也有貨物加工順序的約束。由此，建立倉儲堆垛機出庫揀選策略優化的多目標數學模型：以揀選路徑值和收集利潤值總和分別建立目標模型。

倉儲出庫時堆垛機揀選策略優化研究中，若使用較大規模貨位節點的問題進行求解時，若采用分支定界法、整數規劃法、割平面法等精確算法進行求解，需要消耗大量的計算時間，而使用元啟發式則可以在合理的時間內求得較好的解。迭代局部搜索(IterativeLocal Search，ILS)算法是解決組合優化問題的一種簡單有效的元啟發式方法，已經在堆垛機揀選策略問題上廣泛應用。迭代局部搜索ILS算法基于局部搜索和擾動兩個階段的優化策略，以迭代的方式應用這兩個階段，直到滿足預設的終止條件。近年來，對倉儲堆垛機的出庫揀選策略問題的研究取得了極大的進展，帕累托解的質量也在不斷改進。但是在現有的求解策略中，仍存在當前解容易陷入局部最優，收斂性較差；局部搜索階段易產生大量無效解，導致不能快速有效的求得全局最優解。針對目前存在的缺陷，設計改進的迭代局部搜索算法，以提高算法求解性能，提升堆垛機揀選運行效率。

發明內容

本發明所要解決的技術問題在于針對上述現有技術的不足，提供了一種優化倉儲堆垛機揀選策略的改進多目標局部搜索算法，該算法提高提升堆垛機揀選運行效率。

為解決上述技術問題，本發明采用的技術方案是：一種優化倉儲堆垛機揀選策略的改進多目標局部搜索算法，其特征在于，該算法包括：

S1、堆垛機揀選參數初始化：輸入訂單中貨物的節點坐標、體積和利潤值等信息，設置最大迭代次數N、種群大小設置為pop_size、判斷陷入深度局部最優的迭代次數λ；

S2、初始化種群：采用自然數編碼的染色體形式，生成初始種群，所述初始種群內包含堆垛機的多個揀選序列；

S3、使用2-opt算法對所述初始種群進行優化，獲得較高質量的初始解；

S4、對優化后的初始種群中的所有個體進行目標值計算，所述目標值包括堆垛機揀選路徑總距離F₁和收集貨物總利潤值F₂；所述個體指堆垛機的某一個揀選序列；