徐 銓，何利力

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

0 引言

隨著物聯(lián)網(wǎng)技術的發(fā)展，智能物流運用物聯(lián)網(wǎng)、互聯(lián)網(wǎng)、自動化、人工智能等技術實現(xiàn)了物流的智能化、自動化，包括智能倉儲、運輸管理、物流管理等［1］。自動導航車（Automated Guided Vehicle，AGV）作為智能倉儲貨架搬運方式［2］，能實現(xiàn)運輸路線的數(shù)字化管理及智能路線規(guī)劃。

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

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

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

1 模型構(gòu)建

1.1 智能物流倉庫

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

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

Fig.1 Warehouse layout圖1 倉庫布局

1.2 基本條件假設

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

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

（2）倉庫內(nèi)貨架尺寸、貨位相同，長a。

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

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

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

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

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

1.3 貨位分配模型

1.3.1 貨架穩(wěn)定性原則

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

約束條件為：

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

1.3.2 出入庫效率原則

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

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

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

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

約束條件為：

1.3.3 貨物相關性原則

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

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

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

約束條件為：

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

1.3.4 多目標分配模型

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

約束條件為：

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

約束條件為：

2 遺傳算法

已經(jīng)根據(jù)3 個原則建立多目標數(shù)學模型，并利用權(quán)重法轉(zhuǎn)換成單目標函數(shù)。本文將基于改進的遺傳算法求解該模型。

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

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

2.1 染色體編碼

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

若i、j、k都小于10，則基因可以用三位數(shù)表示。當有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 初始化種群

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

2.3 適應度函數(shù)

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

2.4 選擇算子

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

2.5 交叉算子

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

2.6 變異算子

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

2.7 結(jié)束標志

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

3 實驗與分析

3.1 實驗數(shù)據(jù)與算法參數(shù)

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

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

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

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

3.2 實驗方案與結(jié)果分析

本文選擇10 件貨物作為仿真數(shù)據(jù)，分別用改進遺傳算法和傳統(tǒng)遺傳算法進行貨位分配。貨物信息（質(zhì)量、周轉(zhuǎn)率）及貨位分配仿真結(jié)果如表3 所示。表3 中編號6 和編號13 貨物為一組相關貨物組。

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

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

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

4 結(jié)語

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