文/陳增坤 余蕾 王旭
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.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。
訂單分波問題屬于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)行分波。
本文應(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)生少量的訂單來證明算法的有效性。
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è)效率。
在電商智能物流中心的實(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ā)展。