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

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

引

言近年來，隨著消費(fèi)者需求的多樣化轉(zhuǎn)變，電子商務(wù)呈現(xiàn)出高頻率、多品種、小批量的特點(diǎn)，對企業(yè)的倉儲(chǔ)、分揀、訂單處理等工作提出了更高的要求。作為一種新興的揀選處理模式，“貨到人”揀選系統(tǒng)（Roboticmobilefulfillmentsystems，RMFS）采用AGV（AutomatedGuidedVehicle）、AMR（AutonomousMobileRobot）、AGC（AutomatedGuidedCart）等設(shè)備[1]將儲(chǔ)存貨物的貨架、托盤等載體搬運(yùn)至人工揀選站實(shí)現(xiàn)“貨到人”的揀選。這種“貨到人”揀選模式最早于2012年由Amazon應(yīng)用于倉儲(chǔ)分揀系統(tǒng)中，目前國內(nèi)的“貨到人”揀選系統(tǒng)的實(shí)際運(yùn)用已經(jīng)有阿里菜鳥聯(lián)盟智能倉、京東天狼貨到人系統(tǒng)和快倉等。與傳統(tǒng)的“人到貨”揀選模式類似，“貨到人”系統(tǒng)也需要解決貨位分配、訂單分批、任務(wù)指派和路徑規(guī)劃等[2]問題。其中，作為揀選流程中的先決步驟，倉儲(chǔ)系統(tǒng)中的貨位分配工作無疑影響著后續(xù)工作的組織和效率。目前已經(jīng)有很多學(xué)者對“貨到人”揀選系統(tǒng)的貨位分配展開了大量研究，主要集中在問題模型的約束細(xì)化、優(yōu)化目標(biāo)的確定以及求解方法的改進(jìn)等方面[3]。在問題模型的約束細(xì)化方面，Mirzaei等[4]提出了規(guī)格相同的貨位對于不同種商品的容量上限不同，更加貼合于現(xiàn)實(shí)問題中的標(biāo)準(zhǔn)化貨位對應(yīng)不同規(guī)格的商品。李英德[5]考慮了SKU相關(guān)性的裝箱問題與貨位分配的協(xié)同優(yōu)化，設(shè)計(jì)了“SKUs對”相關(guān)性位置變換策略，并使用SAC算法和NFDP算法針對性地分別求解裝箱問題和貨位指派問題。楊雅婷等[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]考慮了倉庫非空狀態(tài)下一品多位的貨位分配問題，同時(shí)考慮滯銷商品的下架操作和商品的上架位置指派優(yōu)化，采用貪婪算法生成初始解，再采用粒子群優(yōu)化算法求解該問題。同時(shí)，由于不同行業(yè)對倉儲(chǔ)運(yùn)行的需求不盡相同，所以在進(jìn)行貨位分配決策時(shí)想要達(dá)到的目標(biāo)也比較多元，常見的貨位分配目標(biāo)有單位時(shí)間的吞吐量最大、批次訂單的揀選時(shí)間最短、單位貨架的穩(wěn)定性最高、貨架上商品關(guān)聯(lián)度最高等。Wang等[8]在考慮貨架承重約束以及高度約束的同時(shí)以貨架重心最低為目標(biāo)，采用層次遺傳算法求解貨位分配問題。袁瑞萍等[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)率，通過計(jì)算商品關(guān)聯(lián)性和相似性，采用基于拉普拉斯矩陣分解的SC算法中引入K-Means++算法對商品進(jìn)行聚類完成貨位分配決策。在求解方法的改進(jìn)方面，主要采用的方法有排隊(duì)網(wǎng)絡(luò)、啟發(fā)式聚類、啟發(fā)式算法以及一些仿真優(yōu)化等。Keung等[12]以改進(jìn)的A*算法計(jì)算揀選過程中所有貨架的總移動(dòng)距離，并以此衡量包括K-means聚類，高斯混合模型聚類，貝葉斯高斯混合模型聚類等在內(nèi)的9種貨位分配的聚類方法的優(yōu)化效果。胡祥培等[13]通過對商品關(guān)聯(lián)網(wǎng)絡(luò)的構(gòu)建、分析和聚類三個(gè)階段來解決一品多位的商品貨位分配問題。翟夢月等[14]同時(shí)考慮商品種類和數(shù)量的雙重關(guān)聯(lián)，以揀選批次訂單貨架移動(dòng)次數(shù)最小為目標(biāo)，設(shè)計(jì)了結(jié)合模擬退火思想的變鄰域搜索算法進(jìn)行求解。王征等[15]在已知未來訂單信息以及貨架上儲(chǔ)存的商品種類信息的情況下建立貨架熱度和貨架關(guān)聯(lián)度模型，設(shè)計(jì)了雙層鄰域變換的禁忌搜索啟發(fā)式算法來優(yōu)化貨架位置。對于“貨到人”系統(tǒng)中的商品分配到貨架的貨位分配問題，目前的研究大多都是針對倉庫起始狀態(tài)為空的歸零優(yōu)化，而在實(shí)際的倉儲(chǔ)條件下，系統(tǒng)中的補(bǔ)貨過程往往不是在倉庫全部為空的狀態(tài)下進(jìn)行的。針對某一特定時(shí)刻的貨位分配問題，本文考慮倉庫起始狀態(tài)非空，并根據(jù)訂單信息來確定特定商品是否需要進(jìn)行下架，以及某種商品實(shí)際所需要的貨位數(shù)量，在不對貨架進(jìn)行清空操作的情況下完成商品上架位置及數(shù)量的決策。同時(shí)，結(jié)合實(shí)際的貨位對于商品的容量上限以及商品的需求量，以最大化所有貨架上的商品關(guān)聯(lián)度為目標(biāo)構(gòu)建的整數(shù)非線性規(guī)劃模型，并設(shè)計(jì)了針對起始狀態(tài)非空的0-1矩陣編碼的遺傳算法進(jìn)行求解。由于染色體規(guī)模過大，為了保證搜索范圍與搜索精度，在交叉操作中設(shè)計(jì)了自適應(yīng)交叉策略。1

問題描述與分析“貨到人”揀選系統(tǒng)（RMFS）主要由可移動(dòng)式貨架、機(jī)器人、通道、揀選臺(tái)等構(gòu)成。RMFS的作業(yè)流程是：根據(jù)一定的分配策略將商品分配到各個(gè)貨架以及將貨架分配到倉庫中的相應(yīng)位置，收到訂單后，按照順序或者批次將訂單任務(wù)進(jìn)行排序或者分批，并將貨架搬運(yùn)任務(wù)分配給倉庫內(nèi)的機(jī)器人執(zhí)行，由機(jī)器人將貨架搬運(yùn)至揀選臺(tái)，再由人工完成揀選任務(wù)，機(jī)器人再按照相應(yīng)的策略將貨架重新搬運(yùn)至儲(chǔ)存區(qū)中的相應(yīng)位置[2]。在本文研究的動(dòng)態(tài)貨位分配問題中，考慮貨架初始狀態(tài)非空，即倉庫中的某些貨架的某些貨位中已經(jīng)存放有若干種商品，需要對原始倉儲(chǔ)狀態(tài)進(jìn)行分析來進(jìn)行貨位分配工作，其中可能包括滯銷商品的下架工作，非空但未滿的貨位的分配數(shù)量決策等。這樣的考慮更加符合當(dāng)前電子商務(wù)模式下消費(fèi)者高頻率、多品種、小批量的消費(fèi)需求?！柏浀饺恕睊x系統(tǒng)的動(dòng)態(tài)貨位分配問題描述如下：該系統(tǒng)中有N個(gè)可移動(dòng)貨架，每個(gè)貨架有L個(gè)貨位，每個(gè)貨位的規(guī)格相同，但是對于不同種類商品的容量限制LP不同[4]?，F(xiàn)存放有若干種（1，P）商品，且每個(gè)貨架上存放的商品種類及數(shù)量已知，其中存在某些商品可能不會(huì)出現(xiàn)在未來的訂單集合中，需要進(jìn)行下架操作，同時(shí)訂單中可能會(huì)出現(xiàn)一些新種類的商品需要上架。未來訂單包含的商品種類及數(shù)量已知，每種商品可以分散儲(chǔ)存在不同的貨架中（即“一品多位”策略），但是同一個(gè)貨架中的兩個(gè)貨位不能出現(xiàn)同種商品。1.1

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

符號說明根據(jù)Yuan等[16]的研究，如表1所示，當(dāng)庫存量約為平均需求量的四倍時(shí)，極少出現(xiàn)缺貨情況，又因?yàn)槲覀兛紤]倉庫初始狀態(tài)非空，我們需要最終倉庫中的庫存量為：其中每種商品的總需求量可以表示為：所以，可以計(jì)算出每種商品所需要的貨數(shù)Dp為：在此動(dòng)態(tài)貨位分配問題中，考慮貨架原始狀態(tài)非空，根據(jù)訂單信息與庫存信息之間的差異可以得出可能存在的需要下架的滯銷商品集合α，以及需要上架的新品種商品集合β（存在于貨架上但并未出現(xiàn)在未來訂單中的商品種類屬于滯銷商品，存在于訂單中但貨架上并未存放的商品屬于新品種商品）。根據(jù)文獻(xiàn)對于商品關(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ǔ)充后的庫存量與需求量的關(guān)系：若貨架上已經(jīng)存放了商品，但存放數(shù)量小于，根據(jù)約束條件（6），我們分配件該商品至該貨架，使得該貨架存放的該商品數(shù)量達(dá)到該商品的貨位容量上限；若分配商品到?jīng)]有存放該種商品的貨架時(shí)，分配件至該貨架，即使未分配滿時(shí)已經(jīng)可以滿足需求仍然分配該貨位至滿容量，這樣就保證了最終存放商品的每一個(gè)貨位都存放了件商品。約束條件（8）和（9）約束了變量的取值。2

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

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

適應(yīng)度函數(shù)本文將遺傳算法的適應(yīng)度計(jì)算定義對每個(gè)染色體（貨位分配方案）遍歷每一行（每一個(gè)貨架），計(jì)算每一行中包含的每對商品之間的關(guān)聯(lián)度加總，再對單個(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)，甚至無法達(dá)到收斂，基于這種情況我們引入精英保留策略，保留一定規(guī)模的適應(yīng)度最高的個(gè)體不參與交叉和變異操作直接進(jìn)入下一代種群，我們設(shè)定10%的概率保留精英個(gè)體。2.4

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

傳統(tǒng)交叉?zhèn)鹘y(tǒng)遺傳算法所使用的交叉算子都是在兩個(gè)父代染色體之間進(jìn)行基因交換來進(jìn)行種群更新的，本文針對非空狀態(tài)的貨位分配問題的染色體設(shè)計(jì)的交叉算子運(yùn)作流程如圖2所示。固定起始狀態(tài)商品位置的“1”元素以及滯銷商品列不參與交叉，計(jì)算其它位置的基因數(shù)量，隨機(jī)選擇其中一半的位置，交換兩個(gè)父代這些位置的基因。在進(jìn)行上述規(guī)則的交叉后會(huì)影響子代染色體的基因規(guī)則，可能有出現(xiàn)子代染色體中的某些行（貨架）內(nèi)出現(xiàn)超過貨位數(shù)L的“1”（商品），所以需要對交叉后的染色體進(jìn)行修正后才能產(chǎn)生符合約束的子代染色體，這個(gè)修正過程將每一行的“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è)可交叉位置，使得這兩行對應(yīng)位置的元素分別相反，交換這兩行對應(yīng)位置的元素，這樣既保證了每一個(gè)貨架存放的貨物種類數(shù)不會(huì)超過貨位數(shù)，又保證了每種商品被分配到所需要的貨位數(shù)量。2.4.3

自適應(yīng)交叉策略設(shè)計(jì)我們注意到傳統(tǒng)遺傳算法在收斂的過程中每一代的最優(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ù)上述染色體約束，本文采用成對基因突變變異算子進(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)過變異之后第二列只為該種商品分配了六個(gè)貨位，這時(shí)需要對染色體進(jìn)行修正，隨機(jī)選擇了第二列第七行的“0”元素變?yōu)椤?”，再遍歷該行中所有的商品（起始固定位置商品除外）是否已經(jīng)分配超過其所需貨位數(shù)的商品，我們搜索到第五種商品需要8個(gè)貨位，已經(jīng)分配了10個(gè)貨位，所以該行將第五種商品的“1”變?yōu)椤?”。3

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