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

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

引

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

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

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

符號說明根據Yuan等[16]的研究，如表1所示，當庫存量約為平均需求量的四倍時，極少出現缺貨情況，又因為我們考慮倉庫初始狀態(tài)非空，我們需要最終倉庫中的庫存量為：其中每種商品的總需求量可以表示為：所以，可以計算出每種商品所需要的貨數Dp為：在此動態(tài)貨位分配問題中，考慮貨架原始狀態(tài)非空，根據訂單信息與庫存信息之間的差異可以得出可能存在的需要下架的滯銷商品集合α，以及需要上架的新品種商品集合β（存在于貨架上但并未出現在未來訂單中的商品種類屬于滯銷商品，存在于訂單中但貨架上并未存放的商品屬于新品種商品）。根據文獻對于商品關聯度的描述，我們定義商品之間的關聯度計算為，其中為同時包含商品和商品的訂單數量，為包含商品的訂單數量，為包含商品j的訂單數量[7]。1.3

非線性整數規(guī)劃模型決策變量：整數變量，商品在貨架上的分配數量。以最大化所有貨架中的商品關聯度為目標函數的非線性整數規(guī)劃模型如下。約束條件如下。其中，約束條件（1）表示分配到貨架上的商品數小于等于貨架上的空位數加上原有商品占用的貨位和滯銷商品下架產生的空貨位。約束條件（2）表示至少為每一種商品（滯銷商品除外）分配一個貨位。約束條件（3）表示當商品已經存放于貨架上時，不論存放數量是否已經達到該商品的貨架容量上限，都認為該商品分配至該貨架。約束條件（4）表示每個貨架上分配的商品種類數小于等于貨位數。約束條件（5）表示為商品分配的貨位數大于等于商品需要的貨位數。約束條件（6）和（7）規(guī)定了商品補充后的庫存量與需求量的關系：若貨架上已經存放了商品，但存放數量小于，根據約束條件（6），我們分配件該商品至該貨架，使得該貨架存放的該商品數量達到該商品的貨位容量上限；若分配商品到沒有存放該種商品的貨架時，分配件至該貨架，即使未分配滿時已經可以滿足需求仍然分配該貨位至滿容量，這樣就保證了最終存放商品的每一個貨位都存放了件商品。約束條件（8）和（9）約束了變量的取值。2

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

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

適應度函數本文將遺傳算法的適應度計算定義對每個染色體（貨位分配方案）遍歷每一行（每一個貨架），計算每一行中包含的每對商品之間的關聯度加總，再對單個個體的每一行的關聯度加總，得到該種分配方案下的總關聯度作為該個體的適應度值。2.3

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

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

傳統(tǒng)交叉?zhèn)鹘y(tǒng)遺傳算法所使用的交叉算子都是在兩個父代染色體之間進行基因交換來進行種群更新的，本文針對非空狀態(tài)的貨位分配問題的染色體設計的交叉算子運作流程如圖2所示。固定起始狀態(tài)商品位置的“1”元素以及滯銷商品列不參與交叉，計算其它位置的基因數量，隨機選擇其中一半的位置，交換兩個父代這些位置的基因。在進行上述規(guī)則的交叉后會影響子代染色體的基因規(guī)則，可能有出現子代染色體中的某些行（貨架）內出現超過貨位數L的“1”（商品），所以需要對交叉后的染色體進行修正后才能產生符合約束的子代染色體，這個修正過程將每一行的“1”的數量調整到貨位數量的同時，保證每一列的“1”符合商品所需要的貨位數量約束。2.4.2

單親交叉根據單親進化遺傳算法的思想，本文設計的單親交叉策略只在單個染色體內進行，不同于傳統(tǒng)交叉使用的先交叉再修正的思想，在單親交叉中為了提高搜索精度，本文直接按照染色體約束選擇合適的基因位置進行交叉，交叉操作流程如圖3所示。首先隨機選擇染色體中的兩行，遍歷這兩行中除滯銷商品列的位置尋找兩個可交叉位置，使得這兩行對應位置的元素分別相反，交換這兩行對應位置的元素，這樣既保證了每一個貨架存放的貨物種類數不會超過貨位數，又保證了每種商品被分配到所需要的貨位數量。2.4.3

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

變異操作根據上述染色體約束，本文采用成對基因突變變異算子進行變異操作，即隨機選擇染色體中的一行，將其中一個非滯銷商品列的“0”元素變成“1”，再將一個非起始狀態(tài)固定位置的“1”元素變成“0”，以此保證每行元素符合單個貨架的貨位數約束。然后根據每列（滯銷商品除外）是否符合每種商品所需貨位數約束進行修正，若變異后出現某一列（商品）的“1”元素的數量（為該種商品分配的貨位數）小于其所需貨位數，則在該列元素為“0”的位置隨機選擇一個變成“1”，再將產生變換的行中某種已分配的貨架數大于該種商品所需貨位數的商品的“1”變成“0”，若該行中所有商品都不符合上述變換條件，則選擇其他行的其他商品。如圖4所示，隨機選擇了第三行進行變異，假設第二種商品計算出所需要的貨位數為7個貨位，經過變異之后第二列只為該種商品分配了六個貨位，這時需要對染色體進行修正，隨機選擇了第二列第七行的“0”元素變?yōu)椤?”，再遍歷該行中所有的商品（起始固定位置商品除外）是否已經分配超過其所需貨位數的商品，我們搜索到第五種商品需要8個貨位，已經分配了10個貨位，所以該行將第五種商品的“1”變?yōu)椤?”。3

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