智能物流下貨到人模式的貨位分配優(yōu)化

徐 銓，何利力

（浙江理工大學(xué)信息學(xué)院，浙江杭州 310018）

0 引言

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

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

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

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

1 模型構(gòu)建

1.1 智能物流倉庫

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

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

Fig.1 Warehouse layout圖1 倉庫布局

1.2 基本條件假設(shè)

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

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

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

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

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

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

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

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

1.3 貨位分配模型

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

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

約束條件為：

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

1.3.2 出入庫效率原則

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

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

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

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

約束條件為：

1.3.3 貨物相關(guān)性原則

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

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

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

約束條件為：

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

1.3.4 多目標(biāo)分配模型

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

約束條件為：

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

約束條件為：

2 遺傳算法

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

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

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

2.1 染色體編碼

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

若i、j、k都小于10，則基因可以用三位數(shù)表示。當(dāng)有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)容是隨機(jī)生成一定數(shù)量的個體作為遺傳算法的初始種群。初始種群對算法收斂效率和最優(yōu)解的優(yōu)劣有較大影響，選擇合適的初始種群很有必要。本文采用先獲取空閑貨位的坐標(biāo)數(shù)據(jù)，周轉(zhuǎn)率高的貨物分配到靠近出入庫點(diǎn)的貨位，生成初始染色體，然后隨機(jī)選擇兩個貨位進(jìn)行交換，重復(fù)操作得到新染色體，不斷循環(huán)初始化第一代種群。在種群規(guī)模選擇上，同時兼顧計(jì)算效率和種群多樣性，本文取種群規(guī)模100 左右。

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

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

2.4 選擇算子

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

2.5 交叉算子

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

2.6 變異算子

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

2.7 結(jié)束標(biāo)志

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與算法參數(shù)

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

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

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

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

3.2 實(shí)驗(yàn)方案與結(jié)果分析

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

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

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

Fig.3 Fitness curve圖3 適應(yīng)度變化曲線

4 結(jié)語

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