文/陳增坤 余蕾 王旭

1.1問題的提出

1.1.1 問題背景

B電商智能物流中心24小時不間斷接收客戶訂單，并且所有訂單都要求次日達(dá)，為了提高多品種、小批量商品的分揀效率和效益，就要首先對商品訂單進(jìn)行分類處理。同時B電商物流中心采用“貨到人”的自動化揀選系統(tǒng)，即通過智能搬運(yùn)機(jī)器人實(shí)現(xiàn)“無人化”搬運(yùn)作業(yè)模式，在方便快捷的同時也帶來了前所未有的挑戰(zhàn)，即要合理調(diào)度AGV才能以最低成本實(shí)現(xiàn)最大效益，而調(diào)度的原則便是基于客戶的訂單信息。因此，智能物流中心的訂單處理是提高揀選效率，降低運(yùn)營成本，實(shí)現(xiàn)規(guī)模效益的關(guān)鍵環(huán)節(jié)。

1.1.2 問題分析

在B智能物流中心“貨到人”的作業(yè)模式下當(dāng)已知目前的訂單情況，則其在倉庫中的貨位倉儲信息已知，因此只需要調(diào)度AGV小車將訂單品項所在貨架全部搬運(yùn)到揀選臺即可完成所有的搬運(yùn)任務(wù)。在物流中心目前的運(yùn)營中按照客戶下單訂單的先后順序劃分訂單波次，發(fā)現(xiàn)這種分波模式下，經(jīng)常造成AGV小車重復(fù)搬運(yùn)貨架，并且由于不同訂單分布的移動貨架距離較遠(yuǎn)，使得AGV小車搬運(yùn)時間較長，且造成運(yùn)力浪費(fèi)。為解決上述問題，需要改變當(dāng)前的訂單處理模式，需要基于訂單相似性來劃分訂單波次，即訂單品項所在統(tǒng)一個貨架的訂單分為一個波次，從而可以減少AGV小車搬運(yùn)次數(shù)，提高揀選效率，降低運(yùn)營成本。

2.1基于總搬運(yùn)次數(shù)優(yōu)化的訂單分波模型

2.1.1 訂單分波目標(biāo)函數(shù)

對訂單進(jìn)行分波是為了提高揀選的效率，更有效地完成揀選作業(yè)，為了達(dá)到這個目的，通常將訂單分波的目標(biāo)設(shè)置為總的揀選距離最短或者總的揀選時間最短，這兩個目標(biāo)都為定量并且是容易實(shí)現(xiàn)的。在運(yùn)行的過程中，揀選時間除了與揀選的距離有關(guān)外，搬運(yùn)行走的速度，尋找儲位的時間以及設(shè)備的自動化程度等因素有關(guān)，這些因素往往與整個系統(tǒng)的硬件以及人員設(shè)備有關(guān)，不受人力的控制，因此通常情況下，訂單分波的目標(biāo)可通過減少總的搬運(yùn)距離來實(shí)現(xiàn)。

以揀選距離最短為目標(biāo)建立數(shù)學(xué)模型，首先要為AGV小車設(shè)置一定的路徑策略，本文采用穿越式策略，這種方式的特點(diǎn)是AGV揀貨小車從通道的一段進(jìn)入，同時從揀選通道兩側(cè)尋找分配的貨架，抬起后從通道另一端離開，由于行走的路徑看上去像是一個“Z”形狀，所以又稱為“Z”形路徑式。

2.1.2 建立模型前的準(zhǔn)備

假設(shè)AGV揀貨小車從貨架到揀選臺的行駛距離為si，貨架i被搬運(yùn)的次數(shù)為ti，AGV揀貨小車從貨架i到貨架i+1之間行駛的距離為di，從起始點(diǎn)到第一個貨架行駛的距離為d0，從最后一個貨架回到起始點(diǎn)行駛的距離為dn，那么一臺AGV揀貨小車總的搬運(yùn)

由于AGV搬運(yùn)小車每次只能搬運(yùn)一個貨架，因此訂單在分波前與分波后AGV揀貨小車在貨架之間的搬運(yùn)距離和AGV揀貨小車從初始位置到第一個貨架的距離以及從最后一個貨架返回初始位置的行走距離都是必不可少的，這一點(diǎn)也是與“人到貨”的揀選方式最大的不同，另外，考慮AGV揀貨小車的作業(yè)成本，AGV揀貨小車在貨架之間移動時為空車運(yùn)行，在貨架與揀選臺之間為承載貨架運(yùn)行，其成本較高，因此認(rèn)為AGV揀貨小車在貨架與揀選臺之間的搬運(yùn)距離重要性更高，影響更大。

對AGV揀貨小車的搬運(yùn)路徑進(jìn)行分析，綜合考慮以上因素，認(rèn)為AGV揀貨小車總的搬運(yùn)距離可以簡化為以下公式：

在不考慮AGV揀貨小車在哪一個揀選臺處揀選的情況下，即假設(shè)AGC揀貨小車到各個揀選臺的搬運(yùn)距離相同，由于貨架與揀選臺的位置固定，那么AGV揀貨小車搬運(yùn)貨架到揀選臺的距離則為固定，因此AGV揀貨小車的搬運(yùn)距離只與AGV揀貨小車搬運(yùn)貨架的次數(shù)有關(guān)，當(dāng)AGV揀貨小車搬運(yùn)貨架的總次數(shù)最少時，AGV揀貨小車的搬運(yùn)距離也達(dá)到最小。

根據(jù)以上分析，同時系統(tǒng)中存在多臺AGV揀貨小車，假設(shè)所有小車搬運(yùn)的總貨架數(shù)為N，則本文在對訂單分波的過程中，以所有AGV揀貨小車搬運(yùn)貨架的總次數(shù)最少為目標(biāo)函數(shù)建立數(shù)學(xué)模型，即目標(biāo)函數(shù)為：

以AGV揀貨小車的搬運(yùn)次數(shù)最少為目標(biāo)函數(shù)建立數(shù)學(xué)模型，可以為訂單分波作指導(dǎo)，使得分波有所依據(jù)。另外以此目標(biāo)建立的模型一方面不需要事先確定AGV揀貨小車搬運(yùn)的路徑策略，同時在對模型的求解時，大大減少了計算量，方便了問題的求解。

2.1.3 訂單分波模型設(shè)定

為了建模的方便，本文對系統(tǒng)做了如下假設(shè)：

（1）一個訂單包含的品項數(shù)至少為1。

（2）一個訂單只能被分在一個波次中，不允許分割。

（3）一個貨架在同一個波次中只能被搬運(yùn)一次。

（4）不存在缺貨的情況。

（5）訂單信息已知，并且訂單品項在貨架中的儲位已知。

（6）AGV小車的搬運(yùn)路線策略已知。

同時在模型的建立中，設(shè)置了如下參數(shù)，對其進(jìn)行了定義。

表1 訂單分波模型所用參數(shù)符號及含義

2.1.4 訂單分波模型的建立

根據(jù)以上的模型假設(shè)及其參數(shù)設(shè)置，可以將本文研究系統(tǒng)的訂單分波問題描述為：假設(shè)有M個訂單需要揀選，共包含W個品項，所有的品項共分布在N個貨架上?，F(xiàn)在對這M個訂單進(jìn)行分波，最終使得AGV揀貨小車搬運(yùn)貨架的總次數(shù)最少。因此，本文中所研究系統(tǒng)的訂單分波問題的數(shù)學(xué)模型如下：

其中為目標(biāo)函數(shù)，表示所有貨架被搬運(yùn)到次數(shù)之和最小。通過每一個波次中每個貨架的搬運(yùn)次數(shù)，即可求得總的搬運(yùn)次數(shù)。約束條件公式表示每個訂單只能被分配到一個波次；公式表示一個貨架在一個波次中只能被搬運(yùn)1次或者0次；表示一個波次的訂單總數(shù)不能超過周轉(zhuǎn)貨架總的儲位數(shù)D·C。

3.1基于節(jié)約算法的訂單分波模型求解

訂單分波問題屬于NP～hard問題，而且其隨著訂單數(shù)量的增多，其計算量呈指數(shù)增長，因此對其求精確解相當(dāng)困難，在研究中通常選擇啟發(fā)式算法對其進(jìn)行求解。目前對訂單分波問題求解的啟發(fā)式算法有多種，可以歸結(jié)為種子算法和節(jié)約算法兩類。本文應(yīng)用節(jié)約算法來對該系統(tǒng)的訂單分波進(jìn)行求解，找出優(yōu)化的分波結(jié)果。

節(jié)約算法的提出是為了解決運(yùn)輸問題，在配送的過程中，通常需要完成多個客戶的配送作業(yè)，根據(jù)客戶的地理位置以及客戶和客戶之間的距離，通過將兩個或兩個以上的客戶合并為一起同時配送，來計算節(jié)約的運(yùn)輸里程，從而找出節(jié)約里程最多的客戶合并方式。本文將節(jié)約算法應(yīng)用在配送中心內(nèi)部AGV揀貨小車的搬運(yùn)過程，通過計算AGV揀貨小車節(jié)約的搬運(yùn)貨架總次數(shù)來對訂單進(jìn)行分波。

3.2節(jié)約算法設(shè)計

本文應(yīng)用C++語言對算法進(jìn)行編譯求解，節(jié)約算法在求解以上訂單分波問題時的計算步驟如下：

（1）在系統(tǒng)中輸入當(dāng)前所有的訂單信息，以及周轉(zhuǎn)貨架的儲位數(shù)。每一個訂單存放在一個儲位上，周轉(zhuǎn)貨架的儲位數(shù)則代表可以存放的訂單數(shù)。

（2）將所有的訂單兩兩組對，計算其組對后的搬運(yùn)次數(shù)的節(jié)約量。假設(shè)訂單1分布在3個貨架上，訂單2分布在5個貨架上，其中訂單1和訂單2分布的貨架有兩個為重復(fù)。若按訂單別來揀選，那么訂單1需要搬運(yùn)3次，搬運(yùn)訂單2需要5次；而將訂單1和訂單2劃分為一波后，其重復(fù)的貨架只需搬運(yùn)一次即可，那么兩個訂單總的搬運(yùn)次數(shù)變?yōu)?次，則訂單分波后節(jié)約的搬運(yùn)次數(shù)就為2次。

（3）將所有的節(jié)約次數(shù)按由大到小降序排列。

（4）選擇節(jié)約次數(shù)最大的兩個訂單組合作為初始訂單波量。

（5）首先以這兩個初始訂單組合為基準(zhǔn)，找出與這兩個訂單同時位于同一貨架上的訂單，加入到該波次中來：其次再分別以這兩個訂單為基準(zhǔn)，比較其與其他訂單的節(jié)約量，按節(jié)約量由大到小的順序降序排列，選擇節(jié)約量最大的訂單劃入該波次。

（6）重復(fù)步驟（5），直到該波次的訂單數(shù)不滿足周轉(zhuǎn)貨架所包含的儲位數(shù)，那么已完成該波次的分波作業(yè)。

（7）不斷的重復(fù)步驟（4）～（6），直到所有的訂單都完成分波。

在本文的研究中，通過C++語言對算法進(jìn)行實(shí)現(xiàn)。在實(shí)際的應(yīng)用中，將配送中心收到的顧客訂單進(jìn)行處理，獲取訂單的貨架信息，將訂單及其貨架信息輸入算法中來，通過運(yùn)行最終將返回訂單的分波結(jié)果。由于在實(shí)際的電商配送中心中，訂單量巨大，為了對所用的算法做出更加清晰地解釋，故對實(shí)際的配送中心進(jìn)行了一定的假設(shè)并隨機(jī)產(chǎn)生少量的訂單來證明算法的有效性。

4.1訂單分波模型效果分析

B電商智能物流中心的分揀作業(yè)均在揀選站臺完成，揀選站臺按照波次訂單進(jìn)行揀選作業(yè)，由于不同訂單調(diào)度AGV小車搬運(yùn)的移動貨架不同，而不同移動貨架到各個揀選臺的位置不同，因此將客戶訂單依據(jù)AGV小車總搬運(yùn)距離最短的原則劃分波次，將同一波次訂單分配到同一個揀選站臺，可以有效減少重復(fù)搬運(yùn)、均衡搬運(yùn)作業(yè)，縮短搬運(yùn)時間，從而降低智能搬運(yùn)機(jī)器人能量損耗、提高揀選作業(yè)效率。

5.1結(jié)論

在電商智能物流中心的實(shí)際運(yùn)營中，改變傳統(tǒng)的根據(jù)時間先后劃分訂單波次的方式，根據(jù)訂單相似性，采用基于總搬運(yùn)距離最短的訂單分波模型，對客戶訂單進(jìn)行波次分配，可有效解決物流中心存在的智能搬運(yùn)機(jī)器人重復(fù)搬運(yùn)、搬運(yùn)作業(yè)不均衡等問題，實(shí)現(xiàn)提高揀選效率，降低運(yùn)營成本的運(yùn)營目標(biāo)，促進(jìn)物流中心的持續(xù)發(fā)展。