[發明專利]一種結合相似度算法和遺傳算法求取包裹最優組合算法

在審

• 申請號: 201811215619.9
• 申請日: 2018-10-18
• 公開（公告）號: CN109583624A
• 公開（公告）日: 2019-04-05
• 發明（設計）人: 李志軍;徐侃
• 申請（專利權）人: 心怡科技股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了一種結合相似度算法和遺傳算法求取包裹最優組合算法，包括以下算法步驟：步驟一：根據庫存預占后的包裹屬性，對包裹進行劃分，步驟二：對當前是否為緊急時刻進行檢測；步驟三：利用包裹中商品的位置得到包裹之間的相似度；步驟四：利用包裹之間的相似度，對包裹進行組合；步驟五：利用遺傳算法對所有完成的波次組合進行全局調優。本發明結合相似度算法和遺傳算法求取包裹最優組合算法，通過可以得到局部最優解的相似度算法以及全局最優解的遺傳算法來得到最終的解，大大彌補了兩種獨立算法各自的不足，相似度算法得到的局部最優解作為遺傳算法的初始父本，提升了遺傳算法的效率，從而使訂單揀選效率和精準度都大大提高。

技術領域

本發明涉及物流倉儲技術領域，特別涉及一種結合相似度算法和遺傳算法求取包裹最優組合算法。

背景技術

隨著近年來電子商務的迅猛發展，電子商務正逐漸滲透到人們生活的各個方面。其中，訂單揀選是電子商務物流中倉儲作業最重要的環節之一，依據客戶的訂單信息，從倉庫中相應的位置揀出相應商品的過程；

在實際操作中，訂單揀選可分為訂單到人和貨到人兩類，訂單到人是由訂單車載有一定數量的買家訂單到固定站點等待揀貨。貨到人是由agv拖有裝載有多種商品的貨架到相應的站點；

在倉儲操作中，訂單揀選是最耗費時間和勞力的一項工作，一個倉庫日訂單量動輒5-6W，由于客戶的訂單具有小批量、高頻次等特征，使得訂單車和agv搬運次數增多，揀貨員工的工作量也變大。電商商務環境下顧客對快遞到達時間更為敏感，因此對訂單揀選效率提出了更高的要求。

相似度算法(Similarity Algorithm)，在數據分析和數據挖掘的過程中，需要知道個體間差異的大小，進而評價個體的相似性和類別；

遺傳算法(Genetic Algorithm)是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。根據問題域中個體的適應度大小選擇個體，并借助與自然遺傳學的遺傳算子進行組合交叉和變異，產生出代表新的解集的種群；

相似度算法和遺傳算法都是求取包裹最優組合的常用算法。由于相似度算法是一種貪心算法，只能得到一個局部最優解。遺傳算法雖然可以得到全局最優解，但由于遺傳算法的父本是隨機生成的，由隨機的父本進行不斷迭代得到最優子代所需要的時間較長。而精確算法雖然可以求得全局解，但由于算法本身計算復雜度高，導致時間成本高。結合相似度算法和遺傳算法求取包裹最優組合算法大大彌補了兩種獨立算法各自的不足，相似度算法得到的局部最優解作為遺傳算法的初始父本，提升了遺傳算法的效率。

因此，發明一種結合相似度算法和遺傳算法求取包裹最優組合算法來解決上述問題很有必要。

發明內容

本發明的目的在于提供一種結合相似度算法和遺傳算法求取包裹最優組合算法，通過結合相似度算法和遺傳算法求取包裹最優組合算法，通過可以得到局部最優解的相似度算法以及全局最優解的遺傳算法來得到最終的解，大大彌補了兩種獨立算法各自的不足，相似度算法得到的局部最優解作為遺傳算法的初始父本，提升了遺傳算法的效率，從而使訂單揀選效率和精準度都大大提高，以解決上述背景技術中提出的問題。

為實現上述目的，本發明提供如下技術方案：一種結合相似度算法和遺傳算法求取包裹最優組合算法，包括以下算法步驟：

步驟一：根據庫存預占后的包裹屬性，對包裹進行劃分；

步驟二：對當前是否為緊急時刻進行檢測，緊急時刻為當前時間與最近截單點時間差值超過一定的閾值，即deadline-curtime＜Threshold，并且庫存預占池中的包裹數量以及揀貨在途的包裹數量超過一定的閾值；