李珍萍，付紅葉，卜曉奇，張國維，吳凌云

(1.北京物資學(xué)院 信息學(xué)院,北京 101149; 2.中國科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)研究院,應(yīng)用數(shù)學(xué)研究所,管理、決策與信息系統(tǒng)重點實驗室，國家數(shù)學(xué)與交叉科學(xué)中心,北京 100190; 3.中國科學(xué)院大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,北京 100190)

0 引言

隨著電子商務(wù)的迅速發(fā)展，電商每天要處理的訂單數(shù)量日益增長，在訂單處理過程中，超過50%的時間耗費在訂單揀選作業(yè)上[1]。因此，縮短訂單揀選時間是提高物流效率、降低物流成本的有效途徑。傳統(tǒng)配送中心采取揀選人員在貨架中來回穿梭的人到貨揀選模式，勞動強度大、耗時長，且揀選過程容易出現(xiàn)差錯。近年來出現(xiàn)的基于自動引導(dǎo)小車(AGV)的智能倉庫中，揀選人員站立在固定的工作臺前，由倉儲機器人把貨架搬運到揀選人員面前，完成訂單揀選工作。這種新型的貨到人揀選作業(yè)模式，將揀選人員從繁重的工作中解放出來，大大提高了揀選工作效率[2]。無論是在傳統(tǒng)的人到貨揀選倉儲系統(tǒng)還是最新的貨到人智能倉儲系統(tǒng)中，單個訂單中包含的物品種類和數(shù)量都不多, 為了提高訂單揀選效率，配送中心通常將多個訂單合并成一個揀選單進(jìn)行揀選。訂單分批問題就是將訂單池中的眾多訂單按照一定的規(guī)則劃分成若干個批次, 每一批次的訂單構(gòu)成一張揀貨單并在一次作業(yè)中完成揀選[3]。在基于AGV的智能倉庫中，采取合理的訂單分批策略可以大大減少工作人員的揀選操作次數(shù)和倉庫機器人搬運貨架的次數(shù)，降低揀選成本、提高揀選效率。

針對傳統(tǒng)人到貨揀選模式下的訂單分批揀選問題的研究成果已經(jīng)非常豐富[4～11]。由于基于AGV的貨到人揀選倉庫系統(tǒng)的工作流程與傳統(tǒng)的人到貨揀選倉庫系統(tǒng)的工作流程不同，已有的針對人到貨揀選系統(tǒng)中訂單分批問題的研究成果不能直接用于解決貨到人智能倉庫系統(tǒng)中的訂單分批揀選問題。近年來，部分學(xué)者針對貨到人智能倉庫系統(tǒng)中的訂單分批揀選相關(guān)問題開展了研究工作。張彩霞等綜合考慮訂單分批、路徑、任務(wù)分配等三個過程，研究了基于AGV的“貨到人”揀選模式的優(yōu)化方法和模型[1]。王艷艷等以并行自動分揀系統(tǒng)為研究對象，運用迭代優(yōu)化、聚類分析等工具，研究了智能倉庫中訂單揀選拆分優(yōu)化、系統(tǒng)調(diào)度優(yōu)化及補貨緩存優(yōu)化問題, 建立優(yōu)化模型并設(shè)計了啟發(fā)式自適應(yīng)遺傳算法[12]。王善超以訂單是否拆分為準(zhǔn)則，建立基于通道相似度的訂單不可拆分模型和基于車輛路徑問題的訂單可拆分模型，分別設(shè)計了求解兩種模型的算法，并比較了在兩種獨立分揀模式下不同訂單分批方法的工作效率[13]。Lenoble Nicolas等人在具有多個垂直升降模塊的自動化倉庫中進(jìn)行實驗，以完成訂單揀選時間最短為目標(biāo)建立優(yōu)化模型，并設(shè)計了求解模型的元啟發(fā)式方法[14]。王旭坪等人研究了基于相似度聚類的訂單分批策略，利用相同通道數(shù)系數(shù)作為衡量訂單間相似度的指標(biāo)[15]。Xi Xiang等人研究了Kiva系統(tǒng)中的儲位分配和訂單分批問題，以最小化貨架的訪問次數(shù)作為訂單分批的目標(biāo)。通過最大化順序關(guān)聯(lián)或最小化順序異化獲得初始可行解，并采用變鄰域搜索算法對可行解進(jìn)行改進(jìn)[16]。

針對訂單分批問題的研究大部分都是根據(jù)訂單相似度進(jìn)行聚類。在傳統(tǒng)人到貨倉儲系統(tǒng)中，揀選人員穿越通道的數(shù)量是影響揀選效率的主要因素，因此訂單相似度主要根據(jù)訂單中物品所在的通道是否相同進(jìn)行定義。基于AGV的智能倉庫系統(tǒng)中，機器人搬運貨架的次數(shù)和揀選人員從貨架上揀取物品的次數(shù)是影響訂單揀選效率的兩個主要因素，現(xiàn)有文獻(xiàn)大都基于其中一個因素定義訂單相似度，尚未發(fā)現(xiàn)同時考慮兩種因素的研究成果。

本文將研究基于AGV的智能倉庫系統(tǒng)訂單分批揀選問題，在給定倉庫布局、貨位分配信息的前提下，同時考慮訂單中包含的商品信息和訂單中商品所在的貨架信息，構(gòu)建加權(quán)訂單相似度指標(biāo)，并基于該指標(biāo)研究訂單分批策略。建立訂單分批問題的數(shù)學(xué)模型并設(shè)計求解模型的算法，同時兼顧工作人員從貨架上揀取商品成本和AGV搬運貨架成本，使智能倉庫系統(tǒng)完成訂單揀選的總成本達(dá)到最小。

1 問題描述與分析

基于AGV的智能倉庫訂單分批問題可以描述為:已知倉庫中有S個貨架，每一個貨架上有h個貨位，每個貨位最多存放一種商品，倉儲中共存放著M種商品，且每種商品的貨位已知。假設(shè)該倉庫某時刻的訂單池中有N張訂單需要揀選，已知每張訂單上包含的商品品項信息、工作人員從貨架上揀取一種商品的成本、AGV搬運一次貨架的成本。問如何將N張訂單進(jìn)行分批才能使訂單揀選的總成本最低？

為了簡化問題，假設(shè)每張訂單中的商品均不缺貨；每種商品在貨架上的貨位固定，每個貨架在倉庫中的位置固定；揀選每個批次的訂單時都需要AGV把包含該批次訂單商品的貨架搬運至揀選臺，等待工作人員從貨架上取下待揀選商品后，再將貨架搬回倉庫中原來的位置；揀選下一個批次訂單時需要重新搬運貨架，即不同批次訂單中的同種商品不能合并揀選。

在以上假設(shè)下，影響每個批次訂單揀選效率和揀選成本的主要因素包括兩個方面，一個是工作人員從貨架上揀選商品的次數(shù)；另一個是AGV將貨架搬運至揀選工作臺的次數(shù)和來回行走距離。由于每個貨架在倉庫中的位置是確定的，為了簡化問題，計算訂單揀選成本時可以不考慮貨架搬運距離，只考慮貨架搬運次數(shù)。

基于以上假設(shè)，為了提高訂單揀選效率、降低揀選總成本，在對訂單進(jìn)行分批的時候，應(yīng)該重點考慮減少工作人員從貨架上揀取商品的次數(shù)、和減少AGV搬運貨架的次數(shù)。如果兩個訂單中包含的商品品項相同，若將它們合并揀選可以使工作人員從貨架上揀取商品的次數(shù)減少一半；如果兩個訂單中包含的商品存放在同一個貨架上，若將它們合并揀選，可以使AGV搬運貨架的次數(shù)減少一半。因此在進(jìn)行訂單分批的時候，應(yīng)該綜合考慮訂單中包含的商品品項信息和訂單中包含的商品所在貨架信息。

2 訂單分批問題的整數(shù)規(guī)劃模型

為了建立訂單分批問題的數(shù)學(xué)模型，定義如下符號。

索引：

i,j：訂單索引，i,j=1,2,…,N；

k：批次索引，k=1,2,…,K；

s：貨架索引，s=1,2,…,S；

t：商品索引，t=1,2,…,M。

參數(shù)：

q：每個批次允許的最大訂單數(shù)量；

c1：從貨架上揀取一種商品的成本；

c2：搬運一次貨架的成本。

決策變量：

基于以上符號，訂單分批問題可以表示成如下0-1規(guī)劃模型:

(1)

(8)

目標(biāo)函數(shù)(1)表示極小化訂單揀選的總成本，其中第一項表示從貨架上揀取商品的成本，第二項表示貨架搬運的成本；約束條件(2)表示每個訂單恰好被分配到一個批次中；約束條件(3)表示分配到每個批次的訂單數(shù)量不超過規(guī)定的最大數(shù)量；約束條件(4)表示如果批次k中有任意一個訂單包含商品t，則該批次就包含商品t；約束條件(5)表示如果批次k包含商品t，則揀選該批次時需要搬運包含商品t的貨架；約束條件(6)～(8)表示決策變量取值約束。

定理1智能倉庫系統(tǒng)訂單分批問題屬于NP-hard問題。

由于訂單分批問題屬于NP-hard問題，對于小規(guī)模問題，可以直接利用商業(yè)求解器如Lingo、Cplex等求解整數(shù)規(guī)劃模型得到最優(yōu)解，對于大規(guī)模問題，需要設(shè)計快速有效的近似求解算法。

3 訂單加權(quán)相似度

從訂單分批問題數(shù)學(xué)模型的目標(biāo)函數(shù)和約束條件可以看出，影響訂單揀選成本的主要因素是各個批次中包含的商品品項數(shù)量和滿足各個批次揀選需求的貨架數(shù)量。因此，合并包含相同商品品項或需要相同貨架的訂單，就可以有效降低訂單揀選的總成本?；谝陨纤枷?，本節(jié)先分別按照訂單中包含的商品品項是否相同、訂單中包含的商品所在的貨架是否相同定義兩種描述訂單相似度的指標(biāo)：基于商品品項的訂單相似度和基于貨架的訂單相似度，進(jìn)一步定義加權(quán)相似度作為訂單分批的依據(jù)。

3.1 基于商品品項的訂單相似度

基于商品品項的訂單相似度是根據(jù)兩個訂單中包含的相同商品品項數(shù)量與兩個訂單中的總商品品項數(shù)量之比定義的。

假設(shè)訂單i和訂單j中包含的商品品項集合分別為Ii,Ij，則基于商品品項的訂單相似度rij可以定義為:

(9)

3.2 基于貨架的訂單相似度

基于貨架的訂單相似度定義為兩個訂單中的商品對應(yīng)的相同貨架數(shù)量與兩個訂單中商品對應(yīng)的總貨架數(shù)量之比。

假設(shè)訂單i和訂單j中商品所在的貨架集合分別為Si和Sj，則基于貨架的訂單相似度lij定義為:

(10)

表1 倉庫中3個貨架的各個貨位存放的商品信息

3.3 加權(quán)相似度

基于商品品項的訂單相似度反映了訂單中包含的相同商品的比例，將商品品項相似度大的訂單合并揀選，可以減少從貨架上揀取商品的次數(shù)；基于貨架的訂單相似度反映了訂單中商品所在的相同貨架所占的比例，將貨架相似度較大的訂單合并揀選，可以減少貨架搬運的次數(shù)。由于從貨架上揀取商品的次數(shù)和貨架搬運的次數(shù)均是影響揀選效率和揀選成本的主要因素，因此，本文綜合考慮兩方面因素，分別賦予兩種相似度權(quán)系數(shù)λ和1-λ(其中 0≤λ≤1)，定義訂單i和訂單j之間的加權(quán)相似度如下:

(11)

對于某個批次k,若其中包含p個訂單p≥2，不妨設(shè)批次k對應(yīng)的訂單集合為:Batch(k)={Ok1,Ok2,…,Okp},則批次Batch(k)中包含的訂單之間的平均加權(quán)相似度Z(Batch(k))為

(12)

加權(quán)相似度綜合考慮了商品揀選的成本(次數(shù))和貨架搬運的成本(次數(shù))。根據(jù)加權(quán)相似度進(jìn)行分批，使同一批次內(nèi)訂單的平均加權(quán)相似度極大化等價于使商品揀選的次數(shù)和貨架搬運次數(shù)的加權(quán)和極小化，因此根據(jù)加權(quán)相似度進(jìn)行分批可以使訂單揀選的總成本達(dá)到最小。

4 求解訂單分批問題的貪婪算法

由于實際問題中涉及到的訂單數(shù)量、商品品項及貨架數(shù)量都很多，其對應(yīng)的訂單分批問題規(guī)模很大，無法在短時間內(nèi)通過直接求解整數(shù)規(guī)劃模型得到精確解，因此需要設(shè)計快速有效的近似求解算法來得到近似最優(yōu)解。本節(jié)基于訂單之間的加權(quán)相似度設(shè)計求解訂單分批問題的貪婪算法。

算法的基本思想：首先根據(jù)待揀選訂單中包含的商品品項及各種商品所在貨架信息計算訂單之間的加權(quán)相似度；先將每個訂單單獨作為一個批次；再分別計算任意兩個批次合并以后，平均加權(quán)相似度的增加量，依次選擇合并后滿足批次內(nèi)訂單總數(shù)容量約束并且平均加權(quán)相似度增量達(dá)到最大的批次進(jìn)行合并，直到平均加權(quán)相似度不再增加或者不存在合并后滿足容量約束的訂單批次為止。

基于加權(quán)相似度的訂單分批問題貪婪算法基本步驟如下：

輸入：待揀選訂單中包含的商品品項信息及各個貨架上存放的商品品項信息，加權(quán)系數(shù)λ。

Step1計算任意兩個訂單之間的加權(quán)相似度Tij，得到加權(quán)相似度矩陣

Step2將每個訂單單獨作為一個批次，記錄各個批次中的訂單數(shù)量，初始化每個批次內(nèi)部訂單之間的平均加權(quán)相似度為0(此時每個批次包含的訂單數(shù)量均為1)

Step3對于任意兩個批次u,v(u≠v)，按照公式(13)計算將批次u,v合并為一個批次Batch(u)∪Batch(v)以后，平均加權(quán)相似度之和的增加量Δuv以及兩個批次合并以后總訂單數(shù)量Nuv

Δuv=Z(Batch(u)∪Batch(v))-

Z(Batch(u))-Z(Batch(v))

(13)

Step4在滿足容量約束Nuv≤q的批次中找出Δuv的最大值maxΔ及對應(yīng)的批次u*,v*。

Step5若maxΔ>0，將批次Batch(u*),Batch(v*)合并為一個批次，轉(zhuǎn)Step 3;若maxΔ≤0，或者不存在滿足Nuv≤q的訂單批次，則結(jié)束計算。

輸出：各個批次對應(yīng)的訂單集合。

定理2對于N個訂單，S個貨架，M種商品，需要將訂單劃分為K個批次的問題，用貪婪算法求解的時間復(fù)雜度為O(N2M+N3)。

5 模擬計算與分析

5.1 算例描述

某電商企業(yè)采用基于AGV的智能倉庫系統(tǒng)，該企業(yè)經(jīng)銷的100種商品(商品編碼為1～100)存放在20個貨架上(貨架編碼為1～20)，每一個貨架上有5個貨位，每個貨架上的5個貨位擺放的商品品項信息如表2所示。

該公司在某段時間內(nèi)收到100個訂單，每個訂單中包含的商品品項信息如表3所示。假設(shè)工作人員從貨架上揀取一件商品的成本為0.6元，AGV搬運一次貨架的成本為0.4元，問如何對100個訂單進(jìn)行分批才能使總揀選成本最低？

表2 貨架-商品關(guān)系表

表3 訂單-商品關(guān)系表

5.2 訂單分批結(jié)果與分析

本例中工作人員揀選一種商品的成本c1=0.6元，AGV搬運一個貨架的成本為c2=0.4元，為了利用貪婪算法求解整數(shù)規(guī)劃模型，首先要分析貪婪算法中參數(shù)λ的取值與整數(shù)規(guī)劃模型中目標(biāo)函數(shù)系數(shù)c1,c2取值的關(guān)系。不妨讓參數(shù)λ分別取[0,1]之間的不同值，計算加權(quán)相似度。利用MATLAB編寫的貪婪算法實現(xiàn)程序，按照不同參數(shù)下的加權(quán)相似度運行貪婪算法程序，得到各種參數(shù)對應(yīng)的訂單分批結(jié)果，并計算分批結(jié)果對應(yīng)的各個批次中包含的不同商品品項n1(即揀選各個批次訂單時，工作人員從貨架上揀取商品的總次數(shù))、各個批次中的商品對應(yīng)的不同貨架數(shù)量n2(即揀選各個批次訂單時，AGV需要搬運貨架的總次數(shù))，以及揀選訂單的總成本f(即整數(shù)規(guī)劃模型的目標(biāo)函數(shù)值)，其中揀選訂單總成本計算公式為f=c1·n1+c2·n2，具體計算結(jié)果見表4。

表4 不同參數(shù)下的訂單分批結(jié)果及對應(yīng)的揀選成本指標(biāo)

由表4可以看出，參數(shù)λ的變化直接影響訂單分批結(jié)果。參數(shù)λ表示在加權(quán)相似度指標(biāo)中基于商品品項的訂單相似度所占的比重，當(dāng)λ取最小值0時，基于商品品項的相似度所占比重為0，此時訂單分批主要根據(jù)基于貨架的相似度，分批結(jié)果對應(yīng)的工作人員揀選商品的總次數(shù)最多，AGV搬運貨架的總次數(shù)最少；當(dāng)λ由小到大變化時，基于商品品項的相似度所占比重越來越大，基于貨架的相似度所占比重越來越小，因此分批結(jié)果對應(yīng)的工作人員揀選商品的總次數(shù)呈現(xiàn)遞減趨勢，AGV搬運貨架的總次數(shù)呈現(xiàn)遞增趨勢；當(dāng)λ取最大值1時，基于商品品項的相似度所占比重達(dá)到最大值1，基于貨架的相似度所占比重為0，此時的分批結(jié)果對應(yīng)的工作人員揀選商品的總次數(shù)達(dá)到最少，AGV搬運貨架的總次數(shù)達(dá)到最多。因此，λ的取值很好的體現(xiàn)了訂單揀選過程中工作人員的揀選成本和AGV搬運貨架的成本所占的比重。由于訂單分批問題整數(shù)規(guī)劃模型的目標(biāo)函數(shù)是極小化訂單揀選總成本，為了分析最優(yōu)的訂單分批結(jié)果與參數(shù)λ取值的關(guān)系，本文直接取c1=0.6，c2=0.4計算各種分批結(jié)果對應(yīng)的訂單揀選總成本(見表4最后一列)，從總成本的變化情況可以看出，當(dāng)λ=0.6時的分批結(jié)果對應(yīng)的揀選總成本達(dá)到最小。此時的參數(shù)λ與c1、c2的取值恰好滿足下面的關(guān)系式(14)。

(14)

本例中當(dāng)λ*=0.6時，利用貪婪算法得到的訂單分批結(jié)果為：將100個訂單分為25個批次，各個批次中包含的訂單序號見表5，其對應(yīng)的訂單揀選總成本(整數(shù)規(guī)劃目標(biāo)函數(shù)值)210.6達(dá)到最小。

表5 λ=0.6時的訂單分批結(jié)果

5.3 貪婪算法的計算時間和計算效果分析

為了分析貪婪算法的運算時間和計算效果，本節(jié)模擬產(chǎn)生了一批不同參數(shù)下的小規(guī)模算例，分別利用Lingo軟件編程求解整數(shù)規(guī)劃模型得到精確最優(yōu)解，然后利用貪婪算法求出近似最優(yōu)解，并將精確最優(yōu)解和近似最優(yōu)解對比，分析各種參數(shù)發(fā)生變化時貪婪算法的計算時間和近似比的變化規(guī)律。

(1)參數(shù)λ發(fā)生變化時的求解效果分析

為了分析參數(shù)λ發(fā)生變化對貪婪算法求解效果的影響，模擬生成20個訂單、20種商品、5個貨架的小規(guī)模算例。首先取不同參數(shù)c1,c2(c1+c2=1)利用Lingo軟件編程直接求解本文的整數(shù)規(guī)劃模型得到精確最優(yōu)解，然后令參數(shù)λ=c1利用貪婪算法求出近似最優(yōu)解，并將各種參數(shù)下貪婪算法得到的近似最優(yōu)解與精確最優(yōu)解進(jìn)行對比。分析兩種算法的運算時間和得到的最優(yōu)解對應(yīng)的總揀選成本。具體計算結(jié)果見表6。

表6 參數(shù)λ發(fā)生變化時貪婪算法和Lingo精確求解的計算時間和計算效果對比

通過分析發(fā)現(xiàn)，對于包含20個訂單的小規(guī)模算例(5個貨架，20種商品)，在不同參數(shù)下，用Lingo直接求解整數(shù)規(guī)劃模型的計算時間差別較大, 當(dāng)c1取0或1的時候計算時間較短，c1取其它值時，計算時間均超過了20分鐘，最長的時間超過了1小時。而貪婪算法在各種參數(shù)下的最長計算時間不足0.1秒。比較兩種方法得到的目標(biāo)函數(shù)值可以看出，對于包含20個訂單的小規(guī)模算例，貪婪算法得到的近似最優(yōu)解在最壞情況下對應(yīng)的近似比不超過1.35。

(2)訂單總數(shù)發(fā)生變化時的求解效果分析

為了分析訂單總數(shù)變化對求解效果的影響，對于20種商品、5個貨架的算例，固定c1=c2=λ=0.5，選取不同的訂單數(shù)目生成算例，分別進(jìn)行求解，結(jié)果見表7。

從表7可以看出，當(dāng)訂單數(shù)從5增加到25時，貪婪算法的求解時間變化不大，均未超過1秒鐘，但Lingo軟件的求解時間增長迅速，當(dāng)訂單總數(shù)為20和25時，Lingo軟件求解整數(shù)規(guī)劃模型需要的時間均達(dá)到1小時。隨著訂單數(shù)量的增加，貪婪算法的近似比會有小幅度的波動，最壞情況下的近似比不超過1.31。

表7 訂單數(shù)發(fā)生變化時貪婪算法和Lingo精確求解的計算時間和計算效果對比

(3)物品總數(shù)發(fā)生變化時的求解效果分析

為了分析物品總數(shù)變化對求解效果的影響，固定20個訂單、5個貨架，固定c1=c2=λ=0.5，選取不同的物品總數(shù)并按照每個貨架上存放的商品數(shù)量相同的原則生成算例，分別進(jìn)行求解，結(jié)果見表8。

表8 物品數(shù)發(fā)生變化時貪婪算法求解和Lingo軟件精確求解的計算時間和計算效果對比

從表8可以看出，隨著物品總數(shù)的增加精確求解的計算時間增長迅速，當(dāng)物品總數(shù)為20種時，精確求解的計算時間已經(jīng)超過2小時，當(dāng)物品總數(shù)為25種時，精確求解需要的時間超過5個小時，由于運算時間太長，我們記錄了Lingo軟件運行2小時得到的局部最優(yōu)解與貪婪算法的求解結(jié)果進(jìn)行對比，發(fā)現(xiàn)貪婪算法得到的近似最優(yōu)解優(yōu)于Lingo軟件運行2小時得到的局部最優(yōu)解。

(4)貨架總數(shù)發(fā)生變化時的求解效果分析

為了分析貨架總數(shù)變化對求解效果的影響，固定20個訂單、20種商品，固定c1=c2=λ=0.5，選取不同的貨架總數(shù)并按照每個貨架上存放的商品數(shù)量盡量相等的原則生成算例，分別進(jìn)行求解，結(jié)果見表9。

由表9可以看出，當(dāng)貨架總數(shù)為5時，用Lingo軟件精確求解的運算時間已經(jīng)超過2小時，對于貨架總數(shù)超過5的算例，表9中記錄了Lingo軟件運行2小時得到的局部最優(yōu)解，可以看出，貪婪算法在不足1秒的時間內(nèi)得到的近似最優(yōu)解優(yōu)于Lingo軟件運行2小時得到的局部最優(yōu)解。

表9 貨架數(shù)量發(fā)生變化時貪婪算法和Lingo精確求解的計算時間和計算效果對比

由表7～ 9中的計算結(jié)果可以看出， Lingo軟件求解整數(shù)規(guī)劃模型需要的運算時間隨著物品總數(shù)、訂單總數(shù)、貨架總數(shù)的增加呈指數(shù)增長，而貪婪算法在求解小規(guī)模問題時運算時間均未超過1秒鐘，且貪婪算法得到的近似比均未超過1.31。

對于前一節(jié)中的100個訂單、100種商品的算例，我們也嘗試用Lingo軟件編程直接求解整數(shù)規(guī)劃模型，結(jié)果發(fā)現(xiàn)Lingo程序運行24小時仍然沒有得到最終結(jié)果，而用貪婪算法運行時間不足5秒就可以得到近似最優(yōu)解，這說明貪婪算法適合求解大規(guī)模訂單分批問題。由于實際中的訂單分批問題都是大規(guī)模的在線問題，必須在短時間內(nèi)得到近似最優(yōu)結(jié)果，因此本文設(shè)計的貪婪算法是求解這類問題的有效方法。

6 結(jié)論

本文研究了基于AGV的智能倉庫系統(tǒng)訂單分批揀選問題，分析了智能倉庫中影響訂單揀選效率和揀選成本的兩種主要因素分別是工作人員從貨架上揀取商品的次數(shù)和AGV搬運貨架次數(shù)，以訂單揀選總成本極小化為目標(biāo)建立了訂單分批問題的整數(shù)規(guī)劃模型，進(jìn)一步根據(jù)訂單中包含的商品信息和商品對應(yīng)的貨架信息構(gòu)建了訂單相似度指標(biāo)，并設(shè)計了基于訂單之間的加權(quán)相似度貪婪算法。最后利用具體算例進(jìn)行了模擬計算，分析了加權(quán)系數(shù)λ的變化對訂單分批結(jié)果的影響，以及加權(quán)系數(shù)λ的取值與工作人員揀取一件商品的成本c1和AGV搬運一次貨架的成本c2之間的關(guān)系，得到了貪婪算法中加權(quán)系數(shù)λ的確定方法。進(jìn)一步分析了物品總數(shù)、訂單總數(shù)、貨架總數(shù)等發(fā)生變化時，貪婪算法的計算時間和計算效果。結(jié)果顯示，本文設(shè)計的貪婪算法具有較高的求解效率，由于本文的模型和算法同時考慮了商品揀取成本和貨架搬運成本，通過適當(dāng)選取加權(quán)系數(shù)，利用貪婪算法可以得到總揀選成本最低的訂單分批結(jié)果。

本文結(jié)合我國電商企業(yè)智能物流系統(tǒng)的實際業(yè)務(wù)場景開展研究，目前，京東、菜鳥等大型電商平臺已經(jīng)實現(xiàn)了分揀作業(yè)中心無人化，物流系統(tǒng)根據(jù)訂單發(fā)布任務(wù)，就近調(diào)配機器人；機器人搬運貨架至揀選臺，機器人可以自由旋轉(zhuǎn)保證貨架上的商品直接調(diào)配到揀選員面前；完成揀選任務(wù)后，系統(tǒng)可以根據(jù)實時訂單信息變化動態(tài)調(diào)整貨架的存放位置。本文給出的訂單分批方法為設(shè)計智能物流系統(tǒng)后臺控制系統(tǒng)提供了理論依據(jù)，本文的方法不僅適用于解決基于AGV的智能倉庫系統(tǒng)訂單分批問題，對于解決其他類型的無人倉系統(tǒng)(如基于旋轉(zhuǎn)貨架和傳送帶的無人倉系統(tǒng))中的訂單分批問題，同樣具有參考價值。

本文在研究訂單分批問題時做了一些必要的簡化假設(shè)，如沒有考慮商品缺貨、大訂單拆分、緊急訂單插單等實際情況，實際中訂單揀選過程中可能遇到某些暢銷商品缺貨的情況；由于每個貨位上的商品數(shù)量有限，有些訂購商品數(shù)量較多的訂單可能需要拆分多個揀選單；而且不同訂單的優(yōu)先級不同，遇到優(yōu)先級高的訂單往往需要加急處理等情況。以上情況在本文研究的問題中均未考慮，后續(xù)研究中可以進(jìn)一步考慮這些因素，擴(kuò)展本文的模型和算法。另外，本文設(shè)計的貪婪算法還有很大的改進(jìn)空間，后續(xù)研究中可以針對模型的特點，改進(jìn)貪婪算法或設(shè)計近似度更高的智能算法。