[發(fā)明專利]一種結(jié)合相似度算法和遺傳算法求取包裹最優(yōu)組合算法

在審

• 申請?zhí)枺?/td>: 201811215619.9
• 申請日: 2018-10-18
• 公開（公告）號: CN109583624A
• 公開（公告）日: 2019-04-05
• 發(fā)明（設(shè)計(jì)）人: 李志軍;徐侃
• 申請（專利權(quán)）人: 心怡科技股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種結(jié)合相似度算法和遺傳算法求取包裹最優(yōu)組合算法，其特征在于：包括以下算法步驟：

步驟一：根據(jù)庫存預(yù)占后的包裹屬性，對包裹進(jìn)行劃分；

步驟二：對當(dāng)前是否為緊急時(shí)刻進(jìn)行檢測，緊急時(shí)刻為當(dāng)前時(shí)間與最近截單點(diǎn)時(shí)間差值超過一定的閾值，即deadline-curtime＜Threshold，并且?guī)齑骖A(yù)占池中的包裹數(shù)量以及揀貨在途的包裹數(shù)量超過一定的閾值；

步驟三：利用包裹中商品的位置，并采用相似度公式，得到包裹之間的相似度，相似度公式為：其中|position_iIposition_j|為包裹i和包裹j之間重合的位置數(shù)量，|position_iUposition_j|為包裹i和包裹j合并后的位置數(shù)量的和；

步驟四：利用包裹之間的相似度，對包裹進(jìn)行組合，完成一個(gè)波次組合，則執(zhí)行步驟三；

步驟五：利用遺傳算法對所有完成的波次組合進(jìn)行全局調(diào)優(yōu)。

2.根據(jù)權(quán)利要求1所述的一種結(jié)合相似度算法和遺傳算法求取包裹最優(yōu)組合算法，其特征在于：所述步驟一中，包裹屬性包含包裹計(jì)劃出庫時(shí)間、揀選分區(qū)以及箱型。

3.根據(jù)權(quán)利要求1所述的一種結(jié)合相似度算法和遺傳算法求取包裹最優(yōu)組合算法，其特征在于：所述步驟四中，將兩個(gè)相似度最高的包裹進(jìn)行組合后，不斷尋找與這兩個(gè)位置重合度最高的包裹合成的大包裹最相似的包裹，直到滿足波次上限包裹數(shù)為止。

4.根據(jù)權(quán)利要求1所述的一種結(jié)合相似度算法和遺傳算法求取包裹最優(yōu)組合算法，其特征在于：所述步驟五中，將組完的波次采用遺傳算法進(jìn)行包裹之間的交換，適應(yīng)度函數(shù)為平均波次商品種類。

5.根據(jù)權(quán)利要求1-4任意一項(xiàng)所述的一種結(jié)合相似度算法和遺傳算法求取包裹最優(yōu)組合算法的實(shí)現(xiàn)方法，其特征在于：具體實(shí)現(xiàn)步驟如下：

步驟一：訂單流入，根據(jù)包裹的箱型、揀貨區(qū)域、計(jì)劃出庫時(shí)間，對包裹進(jìn)行劃分，保證同一類型的包裹屬性一致，箱型為1#-7#，揀貨區(qū)域?yàn)锳、B、C區(qū)，計(jì)劃出庫時(shí)間為12點(diǎn)、21點(diǎn)、23點(diǎn)30分、次日1點(diǎn)；

步驟二：算法初始參數(shù)設(shè)置，根據(jù)相似度公式：|position_iIposition_j|對于A區(qū)表示訂單i和訂單j間相同的揀選通道數(shù)量，對于B區(qū)表示訂單i和訂單j間相同的揀選貨架數(shù)量，對于C區(qū)表示訂單i和訂單j間相同的揀選貨位數(shù)量；|position_iUposition_j|對于A區(qū)表示訂單i和訂單j合并后總的揀選通道數(shù)量，對于B區(qū)表示訂單i和訂單j合并后總的揀選貨架數(shù)量，對于C區(qū)表示訂單i和訂單j合并后總的揀選貨位數(shù)量；

步驟三：根據(jù)包裹屬性進(jìn)行劃分，根據(jù)步驟一中得到的包裹屬性，判斷包裹是否為特殊包裹，即不是根據(jù)相似度組合的單獨(dú)包裹，當(dāng)是特殊包裹時(shí)，則進(jìn)行單獨(dú)處理，當(dāng)不是特殊包裹時(shí)，進(jìn)行下一步操作；

步驟四：相似度算法進(jìn)行波次組合，利用包裹之間的相似度，對包裹進(jìn)行組合，完成一個(gè)波次組合，并得到一個(gè)波次結(jié)果；

步驟五：遺傳算法對結(jié)果進(jìn)行修正，將步驟四中相似度算法得到的波次結(jié)果作為遺傳算法的輸入，一個(gè)波次看成一個(gè)個(gè)體，適應(yīng)度函數(shù)為平均波次商品種類，選擇算子采用輪盤賭，其基本思想為各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比，交叉操作采用多點(diǎn)交叉，即在每個(gè)波次中隨機(jī)選擇多個(gè)包裹，進(jìn)行波次之間包裹的交換；

步驟六：波次結(jié)果輸出，將步驟五中利用遺傳算法修正后的波次結(jié)果輸出。