基于自適應(yīng)交叉策略遺傳算法的非空貨位分配方案優(yōu)化研究

何金濤 楊中華

摘 要：針對(duì)“貨到人”揀選系統(tǒng)的補(bǔ)貨環(huán)節(jié)，考慮倉(cāng)庫(kù)起始狀態(tài)非空條件下的貨位分配問(wèn)題，將貨架現(xiàn)存商品種類及數(shù)量信息與訂單包含的商品種類及數(shù)量信息進(jìn)行比對(duì)，做出商品分配位置以及上架數(shù)量決策，以所有貨架上的商品相似度總和最大化為目標(biāo)，構(gòu)建了整數(shù)非線性規(guī)劃模型，并設(shè)計(jì)了自適應(yīng)交叉策略的遺傳算法進(jìn)行求解，以問(wèn)題實(shí)際約束對(duì)染色體生成、交叉和變異操作進(jìn)行設(shè)計(jì)。通過(guò)隨機(jī)算例來(lái)對(duì)算法進(jìn)行測(cè)試，結(jié)果表明文章設(shè)計(jì)的算法能夠有效解決其實(shí)狀態(tài)非空的貨位分配問(wèn)題。

關(guān)鍵詞：“貨到人”揀選；貨位分配；遺傳算法

中圖分類號(hào)：F252；TP18 文獻(xiàn)標(biāo)志碼：A DOI：10.13714/j.cnki.1002-3100.2024.10.003

Abstract： In view of the replenishment process of the "goods to people" picking system，considering the space allocation problem under the condition that the initial state of the warehouse is not empty，the type and quantity information of the existing goods on the shelf is compared with the type and quantity information of the goods contained in the order to make the decision of the distribution location and the number of goods on the shelf. An integer nonlinear programming model was constructed with the goal of maximizing the sum of similarity of goods on all shelves，and an adaptive crossover strategy genetic algorithm was designed to solve the problem. The chromosome generation，crossover and mutation operations were designed according to the practical constraints of the problem. The algorithm is tested by a random example，and the results show that the algorithm designed in this paper can effectively solve the problem of non-empty space allocation.

Key words： "goods to people" picking; space allocation; genetic algorithm

0? ? 引? ? 言

近年來(lái)，隨著消費(fèi)者需求的多樣化轉(zhuǎn)變，電子商務(wù)呈現(xiàn)出高頻率、多品種、小批量的特點(diǎn)，對(duì)企業(yè)的倉(cāng)儲(chǔ)、分揀、訂單處理等工作提出了更高的要求。作為一種新興的揀選處理模式，“貨到人”揀選系統(tǒng)（Robotic mobile fulfillment systems，RMFS）采用AGV（Automated Guided Vehicle）、AMR（Autonomous Mobile Robot）、AGC（Automated Guided Cart）等設(shè)備[1]將儲(chǔ)存貨物的貨架、托盤(pán)等載體搬運(yùn)至人工揀選站實(shí)現(xiàn)“貨到人”的揀選。這種“貨到人”揀選模式最早于2012年由Amazon應(yīng)用于倉(cāng)儲(chǔ)分揀系統(tǒng)中，目前國(guó)內(nèi)的“貨到人”揀選系統(tǒng)的實(shí)際運(yùn)用已經(jīng)有阿里菜鳥(niǎo)聯(lián)盟智能倉(cāng)、京東天狼貨到人系統(tǒng)和快倉(cāng)等。與傳統(tǒng)的“人到貨”揀選模式類似，“貨到人”系統(tǒng)也需要解決貨位分配、訂單分批、任務(wù)指派和路徑規(guī)劃等[2]問(wèn)題。其中，作為揀選流程中的先決步驟，倉(cāng)儲(chǔ)系統(tǒng)中的貨位分配工作無(wú)疑影響著后續(xù)工作的組織和效率。目前已經(jīng)有很多學(xué)者對(duì)“貨到人”揀選系統(tǒng)的貨位分配展開(kāi)了大量研究，主要集中在問(wèn)題模型的約束細(xì)化、優(yōu)化目標(biāo)的確定以及求解方法的改進(jìn)等方面[3]。

在問(wèn)題模型的約束細(xì)化方面，Mirzaei 等[4]提出了規(guī)格相同的貨位對(duì)于不同種商品的容量上限不同，更加貼合于現(xiàn)實(shí)問(wèn)題中的標(biāo)準(zhǔn)化貨位對(duì)應(yīng)不同規(guī)格的商品。李英德[5]考慮了SKU相關(guān)性的裝箱問(wèn)題與貨位分配的協(xié)同優(yōu)化，設(shè)計(jì)了“SKUs對(duì)”相關(guān)性位置變換策略，并使用SAC算法和NFDP算法針對(duì)性地分別求解裝箱問(wèn)題和貨位指派問(wèn)題。楊雅婷等[6]在交叉存取揀選模式下考慮動(dòng)態(tài)時(shí)間閾值和動(dòng)態(tài)距離閾值，以揀選任務(wù)為主，在閾值約束下考慮是否執(zhí)行存放任務(wù)并判斷貨物存放位置，同時(shí)優(yōu)化了訂單揀選順序及貨物上架位置的決策，實(shí)現(xiàn)了“貨到人”揀選系統(tǒng)中的動(dòng)態(tài)揀選與貨位分配任務(wù)同時(shí)進(jìn)行。張雪等[7]考慮了倉(cāng)庫(kù)非空狀態(tài)下一品多位的貨位分配問(wèn)題，同時(shí)考慮滯銷商品的下架操作和商品的上架位置指派優(yōu)化，采用貪婪算法生成初始解，再采用粒子群優(yōu)化算法求解該問(wèn)題。

同時(shí)，由于不同行業(yè)對(duì)倉(cāng)儲(chǔ)運(yùn)行的需求不盡相同，所以在進(jìn)行貨位分配決策時(shí)想要達(dá)到的目標(biāo)也比較多元，常見(jiàn)的貨位分配目標(biāo)有單位時(shí)間的吞吐量最大、批次訂單的揀選時(shí)間最短、單位貨架的穩(wěn)定性最高、貨架上商品關(guān)聯(lián)度最高等。Wang等[8]在考慮貨架承重約束以及高度約束的同時(shí)以貨架重心最低為目標(biāo)，采用層次遺傳算法求解貨位分配問(wèn)題。袁瑞萍等[9]以最小化貨架搬運(yùn)次數(shù)以及最小化機(jī)器人總揀選路程為目標(biāo)，并結(jié)合商品分配到貨架以及貨架位置的兩階段決策思想，設(shè)計(jì)兩階段啟發(fā)式算法進(jìn)行求解。包菊芳等[10]以同一貨架上SKU的總關(guān)聯(lián)度最大為目標(biāo)，采用FP-Growth算法以及聚類方法進(jìn)行求解。周亞云等[11]綜合考慮了商品需求關(guān)聯(lián)度與周轉(zhuǎn)率，通過(guò)計(jì)算商品關(guān)聯(lián)性和相似性，采用基于拉普拉斯矩陣分解的SC算法中引入K-Means++算法對(duì)商品進(jìn)行聚類完成貨位分配決策。

在求解方法的改進(jìn)方面，主要采用的方法有排隊(duì)網(wǎng)絡(luò)、啟發(fā)式聚類、啟發(fā)式算法以及一些仿真優(yōu)化等。Keung等[12]以改進(jìn)的A*算法計(jì)算揀選過(guò)程中所有貨架的總移動(dòng)距離，并以此衡量包括K-means聚類，高斯混合模型聚類，貝葉斯高斯混合模型聚類等在內(nèi)的9種貨位分配的聚類方法的優(yōu)化效果。胡祥培等[13]通過(guò)對(duì)商品關(guān)聯(lián)網(wǎng)絡(luò)的構(gòu)建、分析和聚類三個(gè)階段來(lái)解決一品多位的商品貨位分配問(wèn)題。翟夢(mèng)月等[14]同時(shí)考慮商品種類和數(shù)量的雙重關(guān)聯(lián)，以揀選批次訂單貨架移動(dòng)次數(shù)最小為目標(biāo)，設(shè)計(jì)了結(jié)合模擬退火思想的變鄰域搜索算法進(jìn)行求解。王征等[15]在已知未來(lái)訂單信息以及貨架上儲(chǔ)存的商品種類信息的情況下建立貨架熱度和貨架關(guān)聯(lián)度模型，設(shè)計(jì)了雙層鄰域變換的禁忌搜索啟發(fā)式算法來(lái)優(yōu)化貨架位置。

對(duì)于“貨到人”系統(tǒng)中的商品分配到貨架的貨位分配問(wèn)題，目前的研究大多都是針對(duì)倉(cāng)庫(kù)起始狀態(tài)為空的歸零優(yōu)化，而在實(shí)際的倉(cāng)儲(chǔ)條件下，系統(tǒng)中的補(bǔ)貨過(guò)程往往不是在倉(cāng)庫(kù)全部為空的狀態(tài)下進(jìn)行的。針對(duì)某一特定時(shí)刻的貨位分配問(wèn)題，本文考慮倉(cāng)庫(kù)起始狀態(tài)非空，并根據(jù)訂單信息來(lái)確定特定商品是否需要進(jìn)行下架，以及某種商品實(shí)際所需要的貨位數(shù)量，在不對(duì)貨架進(jìn)行清空操作的情況下完成商品上架位置及數(shù)量的決策。同時(shí)，結(jié)合實(shí)際的貨位對(duì)于商品的容量上限以及商品的需求量，以最大化所有貨架上的商品關(guān)聯(lián)度為目標(biāo)構(gòu)建的整數(shù)非線性規(guī)劃模型，并設(shè)計(jì)了針對(duì)起始狀態(tài)非空的0-1矩陣編碼的遺傳算法進(jìn)行求解。由于染色體規(guī)模過(guò)大，為了保證搜索范圍與搜索精度，在交叉操作中設(shè)計(jì)了自適應(yīng)交叉策略。

1? ? 問(wèn)題描述與分析

“貨到人”揀選系統(tǒng)（RMFS）主要由可移動(dòng)式貨架、機(jī)器人、通道、揀選臺(tái)等構(gòu)成。RMFS的作業(yè)流程是：根據(jù)一定的分配策略將商品分配到各個(gè)貨架以及將貨架分配到倉(cāng)庫(kù)中的相應(yīng)位置，收到訂單后，按照順序或者批次將訂單任務(wù)進(jìn)行排序或者分批，并將貨架搬運(yùn)任務(wù)分配給倉(cāng)庫(kù)內(nèi)的機(jī)器人執(zhí)行，由機(jī)器人將貨架搬運(yùn)至揀選臺(tái)，再由人工完成揀選任務(wù)，機(jī)器人再按照相應(yīng)的策略將貨架重新搬運(yùn)至儲(chǔ)存區(qū)中的相應(yīng)位置[2]。在本文研究的動(dòng)態(tài)貨位分配問(wèn)題中，考慮貨架初始狀態(tài)非空，即倉(cāng)庫(kù)中的某些貨架的某些貨位中已經(jīng)存放有若干種商品，需要對(duì)原始倉(cāng)儲(chǔ)狀態(tài)進(jìn)行分析來(lái)進(jìn)行貨位分配工作，其中可能包括滯銷商品的下架工作，非空但未滿的貨位的分配數(shù)量決策等。這樣的考慮更加符合當(dāng)前電子商務(wù)模式下消費(fèi)者高頻率、多品種、小批量的消費(fèi)需求。

“貨到人”揀選系統(tǒng)的動(dòng)態(tài)貨位分配問(wèn)題描述如下：該系統(tǒng)中有N個(gè)可移動(dòng)貨架，每個(gè)貨架有L個(gè)貨位，每個(gè)貨位的規(guī)格相同，但是對(duì)于不同種類商品的容量限制LP不同[4]?，F(xiàn)存放有若干種（1，P）商品，且每個(gè)貨架上存放的商品種類及數(shù)量已知，其中存在某些商品可能不會(huì)出現(xiàn)在未來(lái)的訂單集合中，需要進(jìn)行下架操作，同時(shí)訂單中可能會(huì)出現(xiàn)一些新種類的商品需要上架。未來(lái)訂單包含的商品種類及數(shù)量已知，每種商品可以分散儲(chǔ)存在不同的貨架中（即“一品多位”策略），但是同一個(gè)貨架中的兩個(gè)貨位不能出現(xiàn)同種商品。

1.1? ? 模型假設(shè)

未來(lái)時(shí)段的訂單信息包含所需商品種類及數(shù)量，其中每個(gè)訂單包含一種及以上種商品；倉(cāng)庫(kù)貨架原始狀態(tài)不全為空；每個(gè)貨架規(guī)格相同，但是對(duì)于不同種類商品的容量不同[4]；每種商品的貨位容量限制能夠滿足訂單對(duì)于該種商品的需求，即不存在某個(gè)訂單需要搬運(yùn)兩個(gè)貨架來(lái)滿足其中一種商品的需求；每種商品可以分配到多個(gè)貨架上，一個(gè)貨位只能存放一種商品；訂單不可拆分；每個(gè)貨架在倉(cāng)庫(kù)中的位置固定，即貨架完成揀選后仍返回原來(lái)的位置；訂單上出現(xiàn)的商品至少存放在一個(gè)貨架的某個(gè)儲(chǔ)位上。

1.2? ? 符號(hào)說(shuō)明

根據(jù)Yuan等[16]的研究，如表1所示，當(dāng)庫(kù)存量約為平均需求量的四倍時(shí)，極少出現(xiàn)缺貨情況，又因?yàn)槲覀兛紤]倉(cāng)庫(kù)初始狀態(tài)非空，我們需要最終倉(cāng)庫(kù)中的庫(kù)存量為：

其中每種商品的總需求量可以表示為：

所以，可以計(jì)算出每種商品所需要的貨數(shù)Dp為：

在此動(dòng)態(tài)貨位分配問(wèn)題中，考慮貨架原始狀態(tài)非空，根據(jù)訂單信息與庫(kù)存信息之間的差異可以得出可能存在的需要下架的滯銷商品集合α，以及需要上架的新品種商品集合β（存在于貨架上但并未出現(xiàn)在未來(lái)訂單中的商品種類屬于滯銷商品，存在于訂單中但貨架上并未存放的商品屬于新品種商品）。

根據(jù)文獻(xiàn)對(duì)于商品關(guān)聯(lián)度的描述，我們定義商品之間的關(guān)聯(lián)度計(jì)算為，其中為同時(shí)包含商品和商品的訂單數(shù)量，為包含商品的訂單數(shù)量，為包含商品j的訂單數(shù)量[7]。

1.3? ? 非線性整數(shù)規(guī)劃模型

決策變量：

整數(shù)變量，商品在貨架上的分配數(shù)量。

以最大化所有貨架中的商品關(guān)聯(lián)度為目標(biāo)函數(shù)的非線性整數(shù)規(guī)劃模型如下。

約束條件如下。

其中，約束條件（1）表示分配到貨架上的商品數(shù)小于等于貨架上的空位數(shù)加上原有商品占用的貨位和滯銷商品下架產(chǎn)生的空貨位。約束條件（2）表示至少為每一種商品（滯銷商品除外）分配一個(gè)貨位。約束條件（3）表示當(dāng)商品已經(jīng)存放于貨架上時(shí)，不論存放數(shù)量是否已經(jīng)達(dá)到該商品的貨架容量上限，都認(rèn)為該商品分配至該貨架。約束條件（4）表示每個(gè)貨架上分配的商品種類數(shù)小于等于貨位數(shù)。約束條件（5）表示為商品分配的貨位數(shù)大于等于商品需要的貨位數(shù)。約束條件（6）和（7）規(guī)定了商品補(bǔ)充后的庫(kù)存量與需求量的關(guān)系：若貨架上已經(jīng)存放了商品，但存放數(shù)量小于，根據(jù)約束條件（6），我們分配件該商品至該貨架，使得該貨架存放的該商品數(shù)量達(dá)到該商品的貨位容量上限；若分配商品到?jīng)]有存放該種商品的貨架時(shí)，分配件至該貨架，即使未分配滿時(shí)已經(jīng)可以滿足需求仍然分配該貨位至滿容量，這樣就保證了最終存放商品的每一個(gè)貨位都存放了件商品。約束條件（8）和（9）約束了變量的取值。

2? ? 基于自適應(yīng)交叉策略的遺傳算法設(shè)計(jì)

貨位分配問(wèn)題屬于“一品多位”的指派問(wèn)題，“一品多位”的貨位分配問(wèn)題已經(jīng)被證明屬于NP-hard問(wèn)題[13]。本文研究的貨位分配問(wèn)題由于貨架初始狀態(tài)非空，商品的上架位置決策受到約束更多，所以，針對(duì)上述的初始狀態(tài)非空的貨位分配問(wèn)題需要設(shè)計(jì)求解算法。按照問(wèn)題描述，我們需要獲取起始狀態(tài)下每個(gè)貨架存放的商品種類及數(shù)量，根據(jù)訂單信息確認(rèn)滯銷商品種類以及計(jì)算商品之間的關(guān)聯(lián)度、每種商品的需求量、所需要的貨位數(shù)量。根據(jù)所需的變量的數(shù)據(jù)類型，本文設(shè)計(jì)了針對(duì)該問(wèn)題的基于自適應(yīng)交叉策略的遺傳算法。

2.1? ? 染色體編碼

根據(jù)貨位分配問(wèn)題的特點(diǎn)，本文采用0-1矩陣編碼來(lái)構(gòu)造貨位分配方案染色體：每一個(gè)的染色體代表一種貨位分配方案，其中每一行代表一個(gè)貨架，每一列代表一種商品。由于倉(cāng)庫(kù)起始狀態(tài)下的商品位置固定，且滯銷商品需要下架，染色體的生成需要根據(jù)倉(cāng)庫(kù)起始狀態(tài)來(lái)確定。從倉(cāng)庫(kù)起始狀態(tài)生成染色體的過(guò)程（5種商品、10個(gè)貨架）如圖1所示。

圖1中左圖表示倉(cāng)庫(kù)起始狀態(tài)下有編號(hào)為1、2、4的三種商品存放于貨架中，又根據(jù)訂單信息得到了新品種商品3和5，并且商品1未出現(xiàn)在未來(lái)訂單中，屬于需要下架的滯銷商品。根據(jù)這些信息，生成染色體時(shí)先將滯銷商品列全部變?yōu)?，然后在固定初始庫(kù)存中非滯銷商品位置的情況下隨機(jī)填充每一行（每一個(gè)貨架）存放的商品至貨架中的貨位數(shù)上限L（上例假設(shè)為3），并且針對(duì)上一章提出的每一種商品需要的貨位數(shù)Dp，我們還定義了每個(gè)商品列（滯銷商品除外）包含元素“1”的數(shù)量大于等于其Dp值。最后我們就得到了一個(gè)可行的貨位分配方案染色體，其中每一個(gè)位置的元素對(duì)應(yīng)著非線性整數(shù)規(guī)劃模型中的決策變量。

2.2? ? 適應(yīng)度函數(shù)

本文將遺傳算法的適應(yīng)度計(jì)算定義對(duì)每個(gè)染色體（貨位分配方案）遍歷每一行（每一個(gè)貨架），計(jì)算每一行中包含的每對(duì)商品之間的關(guān)聯(lián)度加總，再對(duì)單個(gè)個(gè)體的每一行的關(guān)聯(lián)度加總，得到該種分配方案下的總關(guān)聯(lián)度作為該個(gè)體的適應(yīng)度值。

2.3? ? 精英保留策略

在基于傳統(tǒng)交叉算子的遺傳算法中，在迭代后期每一代的最優(yōu)適應(yīng)度值會(huì)出現(xiàn)較大波動(dòng)，甚至無(wú)法達(dá)到收斂，基于這種情況我們引入精英保留策略，保留一定規(guī)模的適應(yīng)度最高的個(gè)體不參與交叉和變異操作直接進(jìn)入下一代種群，我們?cè)O(shè)定10%的概率保留精英個(gè)體。

2.4? ? 自適應(yīng)交叉策略

針對(duì)前文所述的染色體需要滿足的約束條件，本文設(shè)計(jì)了一種自適應(yīng)交叉策略，包含兩種交叉算子，分別是傳統(tǒng)遺傳算法所使用的兩個(gè)父代染色體交換部分基因的雙親交叉算子（下文簡(jiǎn)述為“傳統(tǒng)交叉”），以及在單個(gè)染色體內(nèi)進(jìn)行交叉操作的單親進(jìn)化交叉算子[17]（下文簡(jiǎn)述為“單親交叉”）。

2.4.1? ? 傳統(tǒng)交叉

傳統(tǒng)遺傳算法所使用的交叉算子都是在兩個(gè)父代染色體之間進(jìn)行基因交換來(lái)進(jìn)行種群更新的，本文針對(duì)非空狀態(tài)的貨位分配問(wèn)題的染色體設(shè)計(jì)的交叉算子運(yùn)作流程如圖2所示。

固定起始狀態(tài)商品位置的“1”元素以及滯銷商品列不參與交叉，計(jì)算其它位置的基因數(shù)量，隨機(jī)選擇其中一半的位置，交換兩個(gè)父代這些位置的基因。在進(jìn)行上述規(guī)則的交叉后會(huì)影響子代染色體的基因規(guī)則，可能有出現(xiàn)子代染色體中的某些行（貨架）內(nèi)出現(xiàn)超過(guò)貨位數(shù)L的“1”（商品），所以需要對(duì)交叉后的染色體進(jìn)行修正后才能產(chǎn)生符合約束的子代染色體，這個(gè)修正過(guò)程將每一行的“1”的數(shù)量調(diào)整到貨位數(shù)量的同時(shí)，保證每一列的“1”符合商品所需要的貨位數(shù)量約束。

2.4.2? ? 單親交叉

根據(jù)單親進(jìn)化遺傳算法的思想，本文設(shè)計(jì)的單親交叉策略只在單個(gè)染色體內(nèi)進(jìn)行，不同于傳統(tǒng)交叉使用的先交叉再修正的思想，在單親交叉中為了提高搜索精度，本文直接按照染色體約束選擇合適的基因位置進(jìn)行交叉，交叉操作流程如圖3所示。

首先隨機(jī)選擇染色體中的兩行，遍歷這兩行中除滯銷商品列的位置尋找兩個(gè)可交叉位置，使得這兩行對(duì)應(yīng)位置的元素分別相反，交換這兩行對(duì)應(yīng)位置的元素，這樣既保證了每一個(gè)貨架存放的貨物種類數(shù)不會(huì)超過(guò)貨位數(shù)，又保證了每種商品被分配到所需要的貨位數(shù)量。

2.4.3? ? 自適應(yīng)交叉策略設(shè)計(jì)

我們注意到傳統(tǒng)遺傳算法在收斂的過(guò)程中每一代的最優(yōu)值變動(dòng)較大，雖然在迭代前期收斂速度較快，但是在收斂后期，最優(yōu)適應(yīng)度值時(shí)不時(shí)會(huì)發(fā)生不規(guī)則波動(dòng)，導(dǎo)致每一代的種群更新速度較慢，這是由于傳統(tǒng)交叉算子所選擇的交叉范圍比較大的緣故?；诖耍疚脑O(shè)計(jì)了一種自適應(yīng)交叉策略，在迭代初期更多地選擇傳統(tǒng)交叉策略以擴(kuò)大搜索范圍加快迭代速度，在迭代后期更多地選擇單親交叉策略增加搜索精度。具體而言，根據(jù)迭代進(jìn)程以線性遞減的概率選擇傳統(tǒng)交叉策略，每一代選擇傳統(tǒng)交叉策略的概率Ptro表示如下。

其中，表示最大迭代次數(shù)，表示當(dāng)前迭代次數(shù)。

2.5? ? 變異操作

根據(jù)上述染色體約束，本文采用成對(duì)基因突變變異算子進(jìn)行變異操作，即隨機(jī)選擇染色體中的一行，將其中一個(gè)非滯銷商品列的“0”元素變成“1”，再將一個(gè)非起始狀態(tài)固定位置的“1”元素變成“0”，以此保證每行元素符合單個(gè)貨架的貨位數(shù)約束。然后根據(jù)每列（滯銷商品除外）是否符合每種商品所需貨位數(shù)約束進(jìn)行修正，若變異后出現(xiàn)某一列（商品）的“1”元素的數(shù)量（為該種商品分配的貨位數(shù)）小于其所需貨位數(shù)，則在該列元素為“0”的位置隨機(jī)選擇一個(gè)變成“1”，再將產(chǎn)生變換的行中某種已分配的貨架數(shù)大于該種商品所需貨位數(shù)的商品的“1”變成“0”，若該行中所有商品都不符合上述變換條件，則選擇其他行的其他商品。

如圖4所示，隨機(jī)選擇了第三行進(jìn)行變異，假設(shè)第二種商品計(jì)算出所需要的貨位數(shù)為7個(gè)貨位，經(jīng)過(guò)變異之后第二列只為該種商品分配了六個(gè)貨位，這時(shí)需要對(duì)染色體進(jìn)行修正，隨機(jī)選擇了第二列第七行的“0”元素變?yōu)椤?”，再遍歷該行中所有的商品（起始固定位置商品除外）是否已經(jīng)分配超過(guò)其所需貨位數(shù)的商品，我們搜索到第五種商品需要8個(gè)貨位，已經(jīng)分配了10個(gè)貨位，所以該行將第五種商品的“1”變?yōu)椤?”。

3? ? 隨機(jī)算例仿真

以一個(gè)小規(guī)模算例為例，首先對(duì)100個(gè)容量為5的貨架（500個(gè)貨位）按照0.8的概率隨機(jī)生成空位，并針對(duì)每種商品生成商品的貨位容量上限為10～25的隨機(jī)數(shù)，對(duì)于存放商品的位置隨機(jī)選擇非新品種商品，并設(shè)置現(xiàn)存數(shù)量為5到該種商品容量上限的隨機(jī)數(shù)，得到起始狀態(tài)下的倉(cāng)儲(chǔ)狀態(tài)如表2所示，其中每個(gè)貨位第一位表示存放的商品種類，第二位表示該種商品的存放數(shù)量；*表示滯銷商品（不出現(xiàn)在訂單中），#表示新品種商品（不出現(xiàn)在起始倉(cāng)儲(chǔ)狀態(tài)中）。然后按照訂單數(shù)量生成隨機(jī)訂單，其中每個(gè)訂單包含1～9（一種滯銷商品除外）種商品，每種商品的訂購(gòu)數(shù)量為1～5之間的隨機(jī)數(shù)，生成的每種商品的貨位容量上限以及訂單信息如表3所示。

對(duì)該算例采用自適應(yīng)遺傳算法進(jìn)行求解，實(shí)驗(yàn)參數(shù)設(shè)置為：種群規(guī)模Ps=100、最大迭代次數(shù)Gmax=1 000、交叉概率Pc=0.8、變異概率Pm=0.1、精英保留概率Pe=0.1。進(jìn)行十次求解的相似度平均值為473.711 02，輸出的分配矩陣如表4所示，可以觀察出算法求出的解同樣符合約束條件。對(duì)該算例的每一次迭代的效果如表5所示，其中Gap（最優(yōu)解）表示算法解與Gurobi求解出的全局最優(yōu)解的差距，Gap（隨機(jī)策略）表示算法求解的分配方案與隨機(jī)存儲(chǔ)策略的相似度值差距?？梢钥闯鲈谠撍憷斜疚奶岢龅乃惴ㄝ^之于隨機(jī)存儲(chǔ)策略優(yōu)化效果達(dá)到51.21%，與全局最優(yōu)方案差距保持在0.1%左右，有著較好的收斂效果，算法的收斂曲線如圖5所示。

4? ? 總結(jié)與展望

本文針對(duì)起始狀態(tài)非空的“貨到人”系統(tǒng)的貨位分配問(wèn)題，考慮的商品的滯銷下架、貨位對(duì)于商品的容量約束以及從訂單中得出具體的貨位分配數(shù)量，以所有貨架上的相似度總和最大化為目標(biāo)，設(shè)計(jì)了0-1矩陣編碼的自適應(yīng)交叉策略遺傳算法進(jìn)行求解，并在算法中為了貼合該問(wèn)題的實(shí)際約束重新設(shè)計(jì)了染色體生成、交叉和變異規(guī)則，在交叉部分設(shè)計(jì)了針對(duì)0-1矩陣編碼的染色體的傳統(tǒng)交叉與單親交叉混合的交叉策略，有助于在收斂前期擴(kuò)大搜索范圍，在收斂后期增加搜索精度。實(shí)驗(yàn)結(jié)果表明，本文設(shè)計(jì)的自適應(yīng)交叉策略的遺傳算法能夠有效解決起始狀態(tài)非空的貨位分配問(wèn)題。

但是，本文僅考慮了大批訂單下的貨架商品相似度，并未考慮到在不同分批策略下的貨位分配目標(biāo)是否需要改進(jìn)，對(duì)于后續(xù)的研究，可以在此基礎(chǔ)上考慮揀選任務(wù)與補(bǔ)貨任務(wù)同時(shí)進(jìn)行的交叉存取規(guī)則下的貨位分配問(wèn)題，以及實(shí)時(shí)狀態(tài)監(jiān)控與更新，實(shí)現(xiàn)更加動(dòng)態(tài)的貨位分配決策優(yōu)化。

參考文獻(xiàn)：

[1] DA COSTA BARROS T R，NASCIMENTO T P．Robotic Mobile Fulfillment Systems：A survey on recent developments and?? ? ?research opportunities [J/OL]．Robotics and Autonomous Systems，2021，137．[2023-07-23].https：//doi.org/10.1016/j.robot.2021.103729.

[2] 徐翔斌，馬中強(qiáng)．基于移動(dòng)機(jī)器人的揀貨系統(tǒng)研究進(jìn)展[J]．自動(dòng)化學(xué)報(bào)，2022，48（1）：1-20．

[3] 雷斌，王菀瑩，趙佳欣．貨位分配優(yōu)化研究綜述[J]．計(jì)算機(jī)工程與應(yīng)用，2021，57（1）：48-55．

[4] MIRZAEI M，ZAERPOUR N，DE KOSTER R B M．How to benefit from order data：Correlated dispersed storage assignment?? ?in robotic warehouses [J]．International Journal of Production Research，2022，60（2）：549- 568．

[5] 李英德．波次分區(qū)揀貨時(shí)裝箱與貨位指派問(wèn)題協(xié)同優(yōu)化的模型與算法[J]．系統(tǒng)工程理論與實(shí)踐，2013，33（5）：1269-1276．

[6] 楊雅婷，許瑞，陸曉芬，等．動(dòng)態(tài)閾值下的交叉存取優(yōu)化問(wèn)題研究[J]．工業(yè)工程與管理，2023，28（3）：83-95．

[7] 張雪，周麗，路雪鵬，等．基于“貨到人”揀選系統(tǒng)的動(dòng)態(tài)貨位分配研究[J]．包裝工程，2022，43（15）：247-257．

[8] WANG Xuelian，Xu Man，XIAO Jing，et al．Optimization of goods locations assignment of automated warehouse on hierarchic?? ? ? genetic algorithm[J]．Applied Mechanics and Materials，2014，510：265-270．

[9] 袁瑞萍，王慧玲，李俊韜，等．基于移動(dòng)機(jī)器人的訂單揀選系統(tǒng)貨位優(yōu)化模型和算法研究[J].系統(tǒng)科學(xué)與數(shù)學(xué)，2020，40（6）：1050-1060.

[10] 包菊芳，王麗．基于SKU關(guān)聯(lián)度的儲(chǔ)位優(yōu)化問(wèn)題研究[J]．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2021，51（14）：31-40．

[11] 周亞云，項(xiàng)前，余崇貴，等．考慮物料需求關(guān)聯(lián)與周轉(zhuǎn)率的倉(cāng)儲(chǔ)貨位優(yōu)化方法[J]．東華大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，46（3）：414-420.

[12] KEUNG K L，LEE C K M，JI P．Data-driven order correlation pattern and storage location assignment in robotic mobile fulfillment and?? ? ?process automation system[J/OL]．Advanced Engineering Informatics，2021，50．[2023-08-01]．https：//doi.org/10.1016/j.aei.2021.101369.

[13] 胡祥培，丁天蓉，張?jiān)磩P，等.基于關(guān)聯(lián)網(wǎng)絡(luò)的機(jī)器人移動(dòng)貨架系統(tǒng)貨位分配方法[J].工程管理科技前沿，2022，41（1）：56-64.

[14] 翟夢(mèng)月，王征，李延通，等．可移動(dòng)貨架倉(cāng)儲(chǔ)系統(tǒng)中商品儲(chǔ)位分配問(wèn)題研究[J]．中國(guó)管理科學(xué)，2023，31（3）：167-176．

[15] 王征，魯鵬，胡祥．可移動(dòng)貨架倉(cāng)儲(chǔ)系統(tǒng)中的貨架位置優(yōu)化方法[J/OL].中國(guó)管理科學(xué)：1-12.[2023-08-09]．http：//kns.cnki．? ?net/kcms/detail/11.2835.G3.20210908.1726.002.html．

[16] YUAN Rong，CEZIK T，GRAVES S C．Stowage decisions in multi-zone storage systems [J]．International Journal of Production Research，2018，56（1-2）：333-343．

[17] 李珍萍，范欣然，吳凌云．基于“貨到人”揀選模式的儲(chǔ)位分配問(wèn)題研究[J]．運(yùn)籌與管理，2020，29（2）：1-11．