基于模擬退火算法倉內(nèi)揀貨的優(yōu)化問題

馮愛芬， 聞博卉， 黃 宇

(河南科技大學(xué) 數(shù)學(xué)與應(yīng)用數(shù)學(xué)系， 河南 洛陽 47100)

隨著消費(fèi)模式的轉(zhuǎn)變，網(wǎng)絡(luò)購物成為當(dāng)今市場的一種重要消費(fèi)模式。人們使用網(wǎng)絡(luò)購物，不僅追求方便，也追求快捷[1]，物流運(yùn)輸?shù)男食蔀槿藗冴P(guān)注的內(nèi)容。倉庫作為商品出庫的起始點(diǎn)，對(duì)物流運(yùn)輸效率有重要的影響。針對(duì)沒有任何規(guī)劃的揀貨模式，需要對(duì)揀貨路線進(jìn)行規(guī)劃，以達(dá)到“效率高”的目的。本文對(duì)倉庫揀貨員接到訂單后揀貨過程的路線進(jìn)行最優(yōu)規(guī)劃。

1 數(shù)據(jù)來源

數(shù)據(jù)來自于2020年第十屆MathorCup高校數(shù)學(xué)建模挑戰(zhàn)賽C題：

倉庫有13個(gè)復(fù)核臺(tái)，4排貨架，每排25組，每組2個(gè)，共2000個(gè)貨架，每個(gè)貨架包含15個(gè)貨格如圖1所示。水平方向每組貨架之間的距離l1為1 500 mm，豎直方向相鄰兩排貨架縱向距離l2為2 000 mm，貨格長寬p1都是800 mm，復(fù)核臺(tái)長寬p2都是1 000 mm[2]。

圖1 倉庫平面示意圖

說明：

① 當(dāng)繞障礙物折線行走時(shí)橫向和豎向偏移都取d=750 mm；

② 復(fù)核臺(tái)之間距離簡化為兩復(fù)核臺(tái)坐標(biāo)差的絕對(duì)值之和；

③ 貨格與復(fù)核臺(tái)距離簡化為貨格中點(diǎn)到復(fù)核臺(tái)最近一條邊中點(diǎn)的距離。

2 問題的描述與模型

2.1 問題描述

本文主要研究在單層二維情況下，多個(gè)訂單的路線選擇以及多個(gè)揀貨員的訂單分配問題。該倉庫由多排平行的貨架組成，每個(gè)貨架包含相同個(gè)數(shù)的貨格用來存放貨物，復(fù)核臺(tái)負(fù)責(zé)發(fā)放訂單以及對(duì)揀貨完成的訂單進(jìn)行打包。揀貨員在開放的復(fù)核臺(tái)領(lǐng)取訂單，根據(jù)訂單需求在對(duì)應(yīng)的貨格上取走貨物，在開放的復(fù)核臺(tái)進(jìn)行貨物打包。

2.2 數(shù)學(xué)模型

2.2.1 距離函數(shù)的建立

在求解過程中求得任意兩個(gè)貨格之間、任意一個(gè)貨格與任意一個(gè)復(fù)核臺(tái)之間、任意兩個(gè)復(fù)核臺(tái)之間的距離。構(gòu)建以穿過下側(cè)復(fù)核臺(tái)中點(diǎn)的直線為x軸，以穿過左側(cè)復(fù)核臺(tái)中點(diǎn)的直線為y軸形成的坐標(biāo)系，貨格坐標(biāo)由所給距離依次可得。

(1)貨格與貨格之間的距離

由于貨格間的位置關(guān)系不同，距離D的計(jì)算方法有所不同，分為4種情況(為方便敘述，“任意兩個(gè)貨格”分別稱為“貨格1”與“貨格2”,貨格1的坐標(biāo)為(x1,y1)，貨格2的坐標(biāo)為(x2,y2))：

① 貨格1與貨格2屬于同一個(gè)貨架組。當(dāng)二者屬于同一個(gè)貨架組，二者的距離為他們各自到達(dá)過道的距離加上兩個(gè)貨格的距離以及為避開障礙物所需要的偏移距離。

D=|x1-x2|+|y1-y2|+2d

(1)

② 貨格1與貨格2位于同一過道的兩側(cè)。當(dāng)二者位于同一過道的兩側(cè)，二者的距離可分解為豎向相距距離與橫向相距距離，偏移距離在該種情況下不需要計(jì)算。

D=|x1-x2|+|y1-y2|

(2)

③ 貨格1位于所在貨格組的左側(cè)(右側(cè))，貨格2位于所在貨格組的右側(cè)(左側(cè))。二者的距離可分解為偏移距離，貨架組的寬度以及二者各自到同一過道的距離。

D=|x1-x2|+|y1-y2|+2l1+2min[x1,x2,|15-x1|,|15-x2|]p1

(3)

④ 貨格1與貨格2位于所在貨架組的同側(cè)(同在左側(cè)或右側(cè))。二者的距離可分解為偏移距離貨架組的寬度以及二者各自到同一過道的距離。

D=|x1-x2|+|y1-y2|+3l1+2min[x1,x2,|15-x1|,|15-x2|]p1

(4)

(2)貨格與復(fù)核臺(tái)的距離

貨格與復(fù)核臺(tái)距離簡化為貨格中點(diǎn)到復(fù)核臺(tái)最近一條邊中點(diǎn)的距離，附件所給坐標(biāo)簡化為中點(diǎn)坐標(biāo)。由于復(fù)核臺(tái)與貨格位置關(guān)系不同，會(huì)導(dǎo)致二者距離的計(jì)算方法也有所變化，仍將其距離分情況進(jìn)行計(jì)算(為敘述方便，將任意復(fù)核臺(tái)的坐標(biāo)記為(x1,y1)，任意貨格的坐標(biāo)為(x2,y2))。

① 復(fù)核臺(tái)位于左側(cè)(x1=0)

(a)貨格在復(fù)核臺(tái)對(duì)面。該種情況類似于貨格位于同一過道的兩側(cè)，此時(shí)二者的距離分解為豎向相距距離以及橫向相距距離：

D=|x1-x2|+|y1-y2|

(5)

(b)貨格位于所在貨架組的右側(cè)。二者的距離分解為一個(gè)偏移距離，橫向相距距離以及 二者到最近同一過道的距離：

D=|x1-x2|+|y1-y2|+d+2l1

(6)

(c)貨格位于所在貨架組的左側(cè)時(shí)。二者的距離分解為橫向相距距離、二者到最近同一過道的距離：

D=|x1-x2|+|y1-y2|+d

(7)

② 復(fù)核臺(tái)位于下側(cè)(y1=0)

(a)貨格位于所在貨架組的左側(cè) 。二者的距離分解為橫向相距距離、豎向相距距離以及偏移距離：

D=|x1-x2|+|y1-y2|+d

(8)

(b)貨格位于所在貨架組的右側(cè)。二者的距離分解為橫向相距距離、豎向相距距離：

D=|x1-x2|+|y1-y2|

(9)

(c)貨格位于復(fù)核臺(tái)右側(cè)

① 貨格位于所在貨架組的左側(cè)。二者的距離分解為橫向相距距離、豎向相距距離:

D=|x1-x2|+|y1-y2|

(10)

② 貨格位于所在貨架組的右側(cè) 。二者的距離分解為橫向相距距離、豎向相距距離以及偏移距離：

D=|x1-x2|+|y1-y2|+d

(11)

(3)復(fù)核臺(tái)與復(fù)核臺(tái)的距離

兩復(fù)核臺(tái)的坐標(biāo)記為(x1,y1)和(x2,y2)，二者的距離與貨格位于同一過道兩側(cè)的情況相同，求解方法也相同：

D=|x1-x2|+|y1-y2|

(12)

2.2.2 揀貨員對(duì)一個(gè)貨單進(jìn)行揀貨時(shí)最短路線的模型

設(shè)訂單中有y件位于不同貨格的商品需要進(jìn)行取件，第i件商品與第j件商品所處貨格之間的距離為xij,d1和d2分別表示第一個(gè)貨格與其距離最近復(fù)核臺(tái)之間的距離和最后一個(gè)貨格與其距離最近的復(fù)核臺(tái)之間的距離。則該問題的數(shù)學(xué)模型為：

(13)

s. t.

xi,i+1≥0(i=1,2,…,y)

(14)

di≥0(i=1,2)

(15)

其中，xi,i+1(i=1,2,…,y)表示在確定的一條行駛路線中第i個(gè)貨格與第i+1個(gè)貨格之間的距離。

2.2.3 多個(gè)揀貨員對(duì)多個(gè)貨單進(jìn)行揀貨時(shí)最短路線的模型

(1)模型假設(shè)

假設(shè)共有z個(gè)訂單和x個(gè)揀貨員進(jìn)行揀貨。每個(gè)揀貨員每次只能執(zhí)行一個(gè)訂單的揀貨任務(wù)，多個(gè)揀貨員在同一個(gè)貨格揀貨時(shí)不需要等待，若多個(gè)揀貨員同時(shí)在同一復(fù)核臺(tái)進(jìn)行打包時(shí)需要考慮等待時(shí)間。

(2)符號(hào)說明

表1 符號(hào)說明

(3)模型建立

求解揀貨員的訂單分配問題以及每個(gè)訂單的揀貨路線，使多個(gè)揀貨員同時(shí)揀貨的總時(shí)間達(dá)到最小，故有：

(16)

s.t.

Di=D(yi，S1i,S2i)

(17)

Di≥0,(i=1,2,…,z)

(18)

Wi≥0，(i=1,2,…,z)

(19)

2.3 模擬退火算法求倉內(nèi)揀貨優(yōu)化問題

2.3.1 揀貨員對(duì)一個(gè)貨單進(jìn)行揀貨時(shí)最短路線問題的算法設(shè)計(jì)

到達(dá)貨格的順序可以自由選擇，返回的復(fù)核臺(tái)也是自由選擇的。采取模擬退火算法進(jìn)行最優(yōu)路線的選擇，通過結(jié)合概率的突跳特性在所有路線中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在從局部最優(yōu)解中概率性地跳出并最終趨于全局最優(yōu)，有效避免陷入局部極小[3]。進(jìn)行多次迭代擾動(dòng)，使其更快得到最優(yōu)解。

步驟1：根據(jù)任務(wù)單i,找到任務(wù)單對(duì)應(yīng)的所有貨格的坐標(biāo)，存儲(chǔ)起來；

步驟2：設(shè)定初始溫度temperature0=1 000*yi，初始迭代次數(shù)t=0[4]；

步驟3：輸入貨格坐標(biāo)，計(jì)算初始路線下的行走距離距離d；

步驟4：使用蒙特卡洛方法中的多次迭代擾動(dòng)，求出任意交換兩個(gè)貨格的行走順序后的新路線的行走距離d′；

步驟5：比較新老路線的差值Δ=d-d′;

步驟7：令temperature=temperature*0.99，t=t+1;

步驟8：由已求得的最優(yōu)路線，通過for循環(huán)找到與其第一個(gè)貨格與最后一個(gè)貨格最近的復(fù)核臺(tái)，計(jì)算距離，求出總距離。根據(jù)商品的下架速度和揀貨員的行走速率求所有任務(wù)復(fù)核打包完成所花費(fèi)的時(shí)間。

2.3.2 多個(gè)揀貨員對(duì)多個(gè)貨單進(jìn)行揀貨時(shí)最短路線問題的算法設(shè)計(jì)

假設(shè)n個(gè)復(fù)核臺(tái)正常工作，m個(gè)任務(wù)單等待揀貨，一共有r個(gè)揀貨員負(fù)責(zé)揀貨?？赡軙?huì)出現(xiàn)揀貨員完成揀貨，在復(fù)核臺(tái)排隊(duì)等候的問題。具體步驟如下。

步驟1：分別計(jì)算出完成每個(gè)任務(wù)單所需要的時(shí)間，令第i個(gè)任務(wù)單的完成時(shí)間為ti(i=1,2,…,m)[6]。

步驟2：根據(jù)排隊(duì)理論安排領(lǐng)取順序，將任務(wù)單所需時(shí)間按從小到大的順序進(jìn)行排列，令r個(gè)揀貨員按照新的貨單順序依次領(lǐng)取任務(wù)單。

步驟3：按照揀貨員對(duì)一個(gè)貨單進(jìn)行揀貨時(shí)最短路線問題的計(jì)算方法計(jì)算每個(gè)揀貨員完成自己的任務(wù)單所需的時(shí)間Tj(j=1,2,…,r)，此時(shí)Tj(j=1,2,…,r)不包括不同揀貨員在復(fù)核臺(tái)等待的時(shí)間。

3 算例及結(jié)果分析

先假設(shè)有4個(gè)復(fù)核臺(tái)(FH01、FH03、FH10、FH12)正常工作，40個(gè)任務(wù)單(T0001～T0040)等待揀貨，一共有9 個(gè)揀貨員(P1～P9)負(fù)責(zé)揀貨。利用模擬退火算法得到的行走路線與按訂單原始路線進(jìn)行對(duì)比如表2所示。

表2 模擬退火算法的計(jì)算結(jié)果與訂單順序行走路線計(jì)算結(jié)果的對(duì)比

由表2看出，利用模擬退火算法得到的路線進(jìn)行揀貨，揀貨員的揀貨時(shí)間與按照訂單順序進(jìn)行揀貨所需時(shí)間明顯減少，復(fù)核臺(tái)的利用效率得到了大幅度提升。

4 結(jié) 語

運(yùn)用模擬退火算法，提供一種解決多個(gè)揀貨員面對(duì)大量訂單時(shí)的路線規(guī)劃和訂單分配的解決方法。結(jié)論表明：多個(gè)揀貨員及揀貨臺(tái)的情況下，合理的分配訂單并選擇路線可以大幅度提升揀貨效率，證明模擬退火算法對(duì)倉內(nèi)揀貨的訂單分派及路線規(guī)劃有指導(dǎo)意義，對(duì)物流運(yùn)輸行業(yè)也有一定的指導(dǎo)意義。