B電商智能物流中心訂單分波（處理）優(yōu)化設(shè)計(jì)

文/陳增坤 余蕾 王旭

1.1問題的提出

1.1.1 問題背景

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

1.1.2 問題分析

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

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

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

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

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

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

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

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

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

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

根據(jù)以上分析，同時(shí)系統(tǒng)中存在多臺(tái)AGV揀貨小車，假設(shè)所有小車搬運(yùn)的總貨架數(shù)為N，則本文在對(duì)訂單分波的過程中，以所有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)的路徑策略，同時(shí)在對(duì)模型的求解時(shí)，大大減少了計(jì)算量，方便了問題的求解。

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

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

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

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

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

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

（5）訂單信息已知，并且訂單品項(xiàng)在貨架中的儲(chǔ)位已知。

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

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

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

2.1.4 訂單分波模型的建立

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1訂單分波模型效果分析

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

5.1結(jié)論

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