智能物流下貨到人模式的貨位分配優化

徐 銓，何利力

（浙江理工大學信息學院，浙江杭州 310018）

0 引言

隨著物聯網技術的發展，智能物流運用物聯網、互聯網、自動化、人工智能等技術實現了物流的智能化、自動化，包括智能倉儲、運輸管理、物流管理等［1］。自動導航車（Automated Guided Vehicle，AGV）作為智能倉儲貨架搬運方式［2］，能實現運輸路線的數字化管理及智能路線規劃。

貨位分配策略是智能物流倉儲的重要決策問題，幾乎影響著所有關鍵的倉儲作業過程，包括揀貨、生產效率、貨物定位和裝箱打包等。它決定貨物的存儲位置，影響貨物庫存盤點和跟蹤，直接決定貨物出入庫效率。貨位分配原則主要有：周轉率原則、貨物相關性原則、穩定性原則等［3］。貨物貨位分配策略主要有隨機分配、固定分配、分類分配、共享分配策略［4］。Housman 等［5］研究了隨機存儲、就近存儲以及基于周轉率分類策略對自動倉儲操作性能的影響；文獻［6-8］分別從庫存周轉率、分類隨機策略、COI 指數策略研究貨位分配優化。

針對倉庫貨位分配優化研究，段悅等［9］提出一種基于入侵雜草算法的貨位分配方法；錢同惠等［10］提出用等效標號法優化分配策略；張貴軍等［11］提出一種基于精英多策略差分進化算法的貨位分配方法；趙陽［12］提出一種雙種群遺傳算法并將其應用于立體倉庫貨位分配；李珍萍等［13］設計一種貪婪算法并驗證算法的有效性；彭小利等［14］研究制造物聯技術環境下智能倉庫貨位優化；寧方華等［15］研究一種針對貨到人模式下的魚骨型布局的禁忌搜索算法，縮短了揀選路程；徐偉華等［16］利用遺傳算法對密集型自動化立體倉庫貨位進行優化；陳月婷等［17］提出基于Pareto 的粒子群優化算法解決貨位分配問題；Li 等［18］提出一種基于改進遺傳算法的貨位分配優化算法。

現有研究有的只考慮單個原則，有的研究目標是靜止的立體化自動倉庫，有的多目標求解優化算法存在收斂速度慢等問題。本文擬對智能物流下貨到人模式的貨位分配問題進行研究，以穩定性、周轉率、相關性為目標建立智能物流倉庫的多目標貨位分配模型，并提出一種改進的遺傳算法對模型進行求解，算法通過改進初始化方式、選擇算子、交叉算子、變異算子提高收斂速度，避免陷入局部最優解。

1 模型構建

1.1 智能物流倉庫

智能物流倉庫是智能物流過程的重要環節，應用物聯網技術，構建智能倉庫，實現倉庫狀態實時感知。借助射頻識別技術（RFID）、二維碼、傳感器及互聯網將倉庫里的貨架、貨物、貨位、托盤、AGV 等物理實體智能化，使其成為具有自身信息反饋功能的智能對象［19］。智能倉庫主要采用自動立體化倉庫或基于AGV 的移動式貨架倉庫，本文研究對象為基于AGV 的移動式貨架倉庫。

假設智能倉庫只有一個出入庫位置，貨架位置呈正方形，一個位置放置一個貨架，貨架和位置存在一對一的對應關系（圖1 中一個正方形上可以放置一個貨架）。出入庫點、貨架位置用（x，y）表示，出入庫點位置為（0，0）。倉庫布局如圖1 所示。

Fig.1 Warehouse layout圖1 倉庫布局

1.2 基本條件假設

為方便數學建模及問題求解，本文作出以下假設：

（1）兩排貨架之間有一道巷道，每條巷道寬為w，布局如圖1 所示。

（2）倉庫內貨架尺寸、貨位相同，長a。

（3）貨架上的每層貨位最多只能放置一種貨物。

（4）每個貨架放置于倉庫的位置固定，即貨架每次被AGV 小車搬運后仍回到原來位置。

（5）AGV 小車在行駛過程是勻速運動，速度恒定為v。

（6）AGV 小車搬運貨架出入庫按照最短路徑搬運。

（7）不考慮多AGV 小車協同工作情況。

1.3 貨位分配模型

1.3.1 貨架穩定性原則

為保證貨架穩定性及AGV 小車運輸過程平穩，要求貨架重心盡量低，即重的貨物放于靠近地面的低層貨位，輕的貨物放于遠離地面的高層貨位。貨架重心評價指數可用貨物質量與當前所在層數的乘積表示，乘積越小表示重心越低。由此建立的數學模型如式（1）所示。

約束條件為：

其中，A為倉庫貨架總排數，B為倉庫貨架總列數，C為貨架總層數；Mijk第i排第j列貨架上第k層貨物的質量。

1.3.2 出入庫效率原則

智能物流貨到人模式中，AGV 搬運速度是恒定的，搬運貨物的效率與搬運距離有關。同時，為了提高貨物出入庫效率，采用基于周轉率的貨位分配策略，將周轉率高的貨物放在靠近出入庫點的貨架上。周轉率為一段時間內貨物出入庫數量和該貨物總量的比值。由此建立的數學模型如式（2）所示。

其中，tij表示AGV 小車將第i排第j列的貨架運到出入庫點所需時間，dij表示第i排第j列貨架到出入庫點的運輸距離，fijk第i排第j列貨架的第k層上貨物的周轉率。

倉庫布局近似看作直角坐標系，出入庫位置為原點(0,0)，貨架位置為(i,j)，從而得到AGV 小車運輸貨架到出入庫點的最短距離如式（3）所示。

將式（3）代入式（2）得到最終函數如式（4）所示。

約束條件為：

1.3.3 貨物相關性原則

實際環境下當一種貨物出庫，往往相關的貨物也需要一起出庫。因此相關性大的物品進行入庫貨位分配時，應靠近存放，即兩貨物所在貨架之間距離應當較小。貨物相關性用相關度進行衡量，兩種貨物相關度越高表示越相關。貨物相關度計算如式（5）所示。

其中，Pij表示貨物i、j之間的相關度，Oi表示包含貨物i的訂單數量，Oj表示包含貨物j的訂單數量，Oij表示包含貨物i和j的訂單數量。設定一個閾值，當小于閾值則兩個貨物相關組成一個相關組。

假設兩貨物分別放置在(i1,j1,k1)和(i2,j2,k2)，則目標函數如式（6）：

約束條件為：

其中，c表述相關物品的組序號，m表示相關貨物的組數。當i1=i2表示兩個貨物在同一貨架上。

1.3.4 多目標分配模型

當對貨物貨位進行分配時，需考慮上述幾個原則，即滿足式（1）、式（4）、式（6）3 個方程。

約束條件為：

根據式（1）、式（4）、式（6）對貨位優化問題進行求解，該問題求解是多目標函數求極值，本文用權重法為3 個函數分別分配θ1、θ2、θ33 個權重因子，將多目標函數轉為單目標函數進行求極值。單目標函數如式（6）所示。

約束條件為：

2 遺傳算法

已經根據3 個原則建立多目標數學模型，并利用權重法轉換成單目標函數。本文將基于改進的遺傳算法求解該模型。

遺傳算法（Genetic Algorithm，GA）是一種模擬生物種群進化的搜索算法，由美國大學教授Holland［20］提出。遺傳算法的基本原理是：首先初始化設置一定數量個體（染色體）組成的生物種群，每個個體代表一個潛在的解；每個個體通過適應度評價進行優勝劣汰，選擇較優個體經過交叉算子、變異算子操作形成下一代種群，經過種群多次進化，種群會逐漸向最優個體進化；當進化結束，得到最優個體。算法流程如圖2 所示。

Fig.2 Genetic algorithm process圖2 遺傳算法流程

2.1 染色體編碼

遺傳算法的模擬過程都是基于染色體編碼的操作。因此編碼方式對算法性能有較大影響。相比二進制的編碼方式，用自然數編碼表達更加直觀。本文采用自然數編碼方式，染色體編碼方式：x1x2x3...xn...xm,1 ≤n ≤m，其中n為待入庫貨物數量，m為空閑貨位數量。每條染色體表示一種貨位分配結果，每條染色體可以分為多個基因x，基因表示一個貨架貨位的位置(i,j,k)，以坐標形式表示倉庫內貨架的空閑貨位位置，i、j、k3 個整數分別表示貨位在i排第j列貨架的第k層。

若i、j、k都小于10，則基因可以用三位數表示。當有3個貨物待入庫和4 個空閑貨位時，第一個貨物放在(1,1,1)，表示貨物放在第1 排第1 列貨架第1 層；第二個貨物放在(1,1,2)，表示貨物放在第1 排第1 列貨架第2 層；第二個貨物放在(1,1,3)，表示貨物放在第1 排第1 列貨架第3 層，剩下的貨位(2,1,1) 未分配貨物。此時，染色體編碼為“111112113211”，表示一種貨位分配解。

2.2 初始化種群

初始化種群的基本內容是隨機生成一定數量的個體作為遺傳算法的初始種群。初始種群對算法收斂效率和最優解的優劣有較大影響，選擇合適的初始種群很有必要。本文采用先獲取空閑貨位的坐標數據，周轉率高的貨物分配到靠近出入庫點的貨位，生成初始染色體，然后隨機選擇兩個貨位進行交換，重復操作得到新染色體，不斷循環初始化第一代種群。在種群規模選擇上，同時兼顧計算效率和種群多樣性，本文取種群規模100 左右。

2.3 適應度函數

適應度函數是判斷個體優劣程度的重要評價標準。根據適應度大小對個體進行優勝劣汰，適應度越大的個體遺傳到下一代的概率更大，適應度越小的個體遺傳到下一代的概率更小。本文用式（6）表示適應度函數。

2.4 選擇算子

選擇算子是模擬大自然生物進化的淘汰過程。通過適應度函數計算當代所有個體適應度，選擇優質個體進入下一代種群。本文選擇精英選擇策略，選擇適應度最優的個體直接進入下一代；種群剩余個體從經過交叉、變異的個體中產生。

2.5 交叉算子

遺傳算法使用交叉算子模仿生物產生后代過程。設定交叉概率Pc，選擇兩個染色體個體計算交叉概率，若交叉概率小于設定概率則按照某種方案交換部分基因，生成子代個體；否則重新選擇兩個個體并進行判定。單純使用個體交叉會造成數據錯亂，因此本文選擇模擬細胞分裂方式以產生子代：根據交叉概率判斷個體是否需要分裂復制；若個體進行分裂復制，會將所有基因復制到子代并發生基因重組（交換部分基因）從而產生子代個體。

2.6 變異算子

變異算子基本操作是根據變異概率確定是否改變種群個體染色體的部分基因，從而提高種群多樣性，防止算法早熟收斂陷入局部最優解。本文采用交換貨位位置的方式進行變異操作，首先計算生成當前個體變異概率Pi，將個體變異概率與設定的變異概率Pm進行比較，若Pi

2.7 結束標志

若種群進化的迭代次數達到初始設定的迭代次數，則終止循環；否則開始選擇算子并進入下一輪循環。

3 實驗與分析

3.1 實驗數據與算法參數

實驗仿真數據：倉庫、貨架及AGV 小車基本信息如表1 所示，空閑貨位信息如表2 所示。

Table 1 Basic information of shelves and AGV表1 貨架與AGV 基本信息

遺傳算法的參數設定：初始種群規模設為100 個，迭代代數為500 代，初始交叉概率Pc為0.8，初始變異概率Pm為0.2。實驗中貨物出入庫效率、貨架穩定性、相關貨物靠近存放3 個權重視為同等重要，因此式（6）中的權重因子θ1、θ2、θ3分別設為0.33、0.33、0.33。

Table 2 Free cargo bay location information表2 空閑貨位位置信息

3.2 實驗方案與結果分析

本文選擇10 件貨物作為仿真數據，分別用改進遺傳算法和傳統遺傳算法進行貨位分配。貨物信息（質量、周轉率）及貨位分配仿真結果如表3 所示。表3 中編號6 和編號13 貨物為一組相關貨物組。

Table 3 Inbound cargo information and distribution results表3 入庫貨物信息及分配結果

圖3 為實驗中遺傳算法和改進優化的遺傳算法適應度變化曲線。由圖3 可以看出，對于初始種群的適應度，由于使用近貨位優先分配給周轉率高貨物的策略，改進的遺傳算法在初始階段就遠低于標準遺傳算法；在此后迭代過程中，兩個算法都快速收斂，但是改進遺傳算法的收斂速度更快；當迭代代數至120 代左右，算法已經收斂，可以得到較好的穩定解。

Fig.3 Fitness curve圖3 適應度變化曲線

4 結語

針對智能物流環境下人到貨模式的貨位分配問題，在考慮貨架穩定性、出入庫效率、相關貨物靠近存放的基礎上，建立貨位分配模型，提出一種改進的遺傳算法。該算法通過優化初始種群的產生方式及細胞分裂方式進行交叉運算、變異概率階段遞減等，避免了傳統遺傳算法收斂速度慢等問題。實驗結果表明，改進的遺傳算法提高了算法收斂速度，減少了搜索時間。該方法雖然提高了效率，但仍然存在不足，需要預先設定權重因子，不同情況下需重新設定，因此如何確定權重因子值還有待研究。