馮愛芬， 聞博卉， 黃 宇

(河南科技大學 數學與應用數學系， 河南 洛陽 47100)

隨著消費模式的轉變，網絡購物成為當今市場的一種重要消費模式。人們使用網絡購物，不僅追求方便，也追求快捷[1]，物流運輸的效率成為人們關注的內容。倉庫作為商品出庫的起始點，對物流運輸效率有重要的影響。針對沒有任何規(guī)劃的揀貨模式，需要對揀貨路線進行規(guī)劃，以達到“效率高”的目的。本文對倉庫揀貨員接到訂單后揀貨過程的路線進行最優(yōu)規(guī)劃。

1 數據來源

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

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

圖1 倉庫平面示意圖

說明：

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

② 復核臺之間距離簡化為兩復核臺坐標差的絕對值之和；

③ 貨格與復核臺距離簡化為貨格中點到復核臺最近一條邊中點的距離。

2 問題的描述與模型

2.1 問題描述

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

2.2 數學模型

2.2.1 距離函數的建立

在求解過程中求得任意兩個貨格之間、任意一個貨格與任意一個復核臺之間、任意兩個復核臺之間的距離。構建以穿過下側復核臺中點的直線為x軸，以穿過左側復核臺中點的直線為y軸形成的坐標系，貨格坐標由所給距離依次可得。

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

(2)貨格與復核臺的距離

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

① 復核臺位于左側(x1=0)

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

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

(5)

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

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

(6)

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

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

(7)

② 復核臺位于下側(y1=0)

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

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

(8)

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

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

(9)

(c)貨格位于復核臺右側

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

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

(10)

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

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

(11)

(3)復核臺與復核臺的距離

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

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

(12)

2.2.2 揀貨員對一個貨單進行揀貨時最短路線的模型

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

(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個貨格與第i+1個貨格之間的距離。

2.2.3 多個揀貨員對多個貨單進行揀貨時最短路線的模型

(1)模型假設

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

(2)符號說明

表1 符號說明

(3)模型建立

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

(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 模擬退火算法求倉內揀貨優(yōu)化問題

2.3.1 揀貨員對一個貨單進行揀貨時最短路線問題的算法設計

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

步驟1：根據任務單i,找到任務單對應的所有貨格的坐標，存儲起來；

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

步驟3：輸入貨格坐標，計算初始路線下的行走距離距離d；

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

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

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

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

2.3.2 多個揀貨員對多個貨單進行揀貨時最短路線問題的算法設計

假設n個復核臺正常工作，m個任務單等待揀貨，一共有r個揀貨員負責揀貨。可能會出現揀貨員完成揀貨，在復核臺排隊等候的問題。具體步驟如下。

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

步驟2：根據排隊理論安排領取順序，將任務單所需時間按從小到大的順序進行排列，令r個揀貨員按照新的貨單順序依次領取任務單。

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

3 算例及結果分析

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

表2 模擬退火算法的計算結果與訂單順序行走路線計算結果的對比

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

4 結 語

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