陳博文 李雨塵 李雪蓮 袁芏楷

（1.西華大學(xué) 理學(xué)院，四川 成都 610039；2.西華大學(xué) 電氣與電子信息學(xué)院，四川 成都 610039）

1 問(wèn)題重述

某電商公司客戶(hù)訂單下達(dá)倉(cāng)庫(kù)后,商品開(kāi)始下架出庫(kù),出庫(kù)主要包含5 個(gè)流程如下所示：

定位-->組單-->揀貨-->復(fù)核-->打包

現(xiàn)有一個(gè)倉(cāng)庫(kù),倉(cāng)庫(kù)數(shù)據(jù)見(jiàn)附件1,包括4 個(gè)表格,前3個(gè)表格為倉(cāng)庫(kù)信息,包括貨架、貨格、復(fù)核臺(tái)的位置及大小,貨格和貨架的關(guān)系。第4 個(gè)表格為任務(wù)單信息,一個(gè)任務(wù)單包含多個(gè)訂單,一個(gè)訂單商品包含多個(gè)貨格,一個(gè)貨格需要揀多件商品。

根據(jù)倉(cāng)庫(kù)數(shù)據(jù)附件1 和附件2,倉(cāng)庫(kù)有13 個(gè)復(fù)核臺(tái),4排貨架,其中每排25 組貨架,每組2 個(gè)貨架,共50 個(gè)貨架,每個(gè)貨架包含15 個(gè)貨格。水平方向每組貨架之間的距離為1500 毫米,豎直方向相鄰兩排貨架縱向距離為2000 毫米,貨格長(zhǎng)寬都是800 毫米,復(fù)核臺(tái)長(zhǎng)寬都為1000 毫米。備注：貨架和復(fù)核臺(tái)為障礙物,不可通行,其余位置均可通行。不用考慮揀貨車(chē)尺寸,貨架和復(fù)核臺(tái)高度。

說(shuō)明：

（1）當(dāng)繞障礙物折線(xiàn)行走時(shí)橫向和豎向偏移都取d=750mm;

（2）復(fù)核臺(tái)之間距離簡(jiǎn)化為兩復(fù)核臺(tái)坐標(biāo)差的絕對(duì)值之和,如復(fù)核臺(tái),復(fù)核臺(tái),則兩復(fù)核臺(tái)的距離為；

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

根據(jù)已知條件和要求,請(qǐng)完成以下問(wèn)題：

問(wèn)題1：當(dāng)揀貨員在倉(cāng)庫(kù)中揀貨時(shí),需要在貨格之間、貨格與復(fù)核臺(tái)之間、復(fù)核臺(tái)與復(fù)核臺(tái)之間行走。由于這些行走通常要繞過(guò)障礙物,不能直接采用坐標(biāo)計(jì)算歐幾里得距離。請(qǐng)你按照?qǐng)D中距離標(biāo)示,設(shè)計(jì)一種計(jì)算3000 個(gè)貨格和13 個(gè)復(fù)核臺(tái),總共3013 個(gè)元素之間距離的方法,并將3013個(gè)元素之間的最短距離矩陣填入表單 Ques1。

問(wèn)題2：假設(shè)所有復(fù)核臺(tái)正常工作,任務(wù)單 T0001 等待揀貨,揀貨員P 在復(fù)核臺(tái) FH10 領(lǐng)取了任務(wù)單 T0001。請(qǐng)給P 規(guī)劃理想的揀貨路線(xiàn),包括貨格訪問(wèn)順序、返回的復(fù)核臺(tái),計(jì)算完成出庫(kù)花費(fèi)的時(shí)間（揀貨員揀貨開(kāi)始到所有任務(wù)復(fù)核打包完成花費(fèi)的時(shí)間）。

問(wèn)題3：假設(shè)2 個(gè)復(fù)核臺(tái) (FH03,FH11) 正常工作,5 個(gè)任務(wù)單（T0002-T0006）等待揀貨,繼續(xù)由揀貨員P 負(fù)責(zé)揀貨,P初始位置為 FH03。通過(guò)建模和優(yōu)化,請(qǐng)給P 指定任務(wù)領(lǐng)取順序,規(guī)劃理想的揀貨路線(xiàn),使得這些任務(wù)盡快出庫(kù)。請(qǐng)計(jì)算完成出庫(kù)需要花費(fèi)的時(shí)間和每個(gè)復(fù)核臺(tái)利用率。

問(wèn)題4：假如4 個(gè)復(fù)核臺(tái)（FH01,FH03,FH10,FH12）正常工作,49 個(gè)任務(wù)單（T0001-T0049）等待揀貨,9 個(gè)揀貨員（P1-P9 負(fù)責(zé)揀貨,請(qǐng)給每個(gè)揀貨員分配任務(wù)單、起始揀貨復(fù)核臺(tái),并分別規(guī)劃理想的揀貨路線(xiàn),使得49 個(gè)任務(wù)單盡快完成出庫(kù),并計(jì)算完成出庫(kù)需要花費(fèi)的時(shí)間和每個(gè)復(fù)核臺(tái)利用率。

問(wèn)題5：在問(wèn)題4 中,有4 個(gè)復(fù)核臺(tái)（FH01,FH03,FH10,FH12）正常工作,請(qǐng)?jiān)u估增加一個(gè)正常工作的復(fù)核臺(tái)對(duì)出庫(kù)時(shí)間的影響。

問(wèn)題6：商品在貨架中的擺放位置,會(huì)影響揀貨效率。若將暢銷(xiāo)品放置在離復(fù)核臺(tái)較近的位置,揀貨員行走距離相應(yīng)減少,但暢銷(xiāo)品所在貨架可能擁擠,反而降低揀貨效率。對(duì)于倉(cāng)內(nèi)商品擺放問(wèn)題,你有什么建議？

注：在問(wèn)題 3,4,5 中,當(dāng)一個(gè)人有多個(gè)任務(wù)時(shí),只能一個(gè)一個(gè)任務(wù)完成,不能在完成一個(gè)任務(wù)過(guò)程中揀另一個(gè)任務(wù)的貨。

2 模型假設(shè)

為了本題的的研究需要,做以下假設(shè)：

（1）不存在缺貨與緊急插入新訂單的情況;

（2）揀貨人員或車(chē)輛移動(dòng)速度保持不變;

（3）每個(gè)訂單的訂貨重量不超過(guò)揀貨車(chē)的容量;

（4）揀選單上物品的存儲(chǔ)貨位是已知的;

（5）揀選人員或揀選設(shè)備數(shù)量充足;

（6）領(lǐng)揀貨車(chē)和任務(wù)單與復(fù)核臺(tái)對(duì)訂單復(fù)核可以同時(shí)進(jìn)行;

3 符號(hào)說(shuō)明

4 問(wèn)題一的分析和解答

4.1 問(wèn)題的分析

由于當(dāng)揀貨員在倉(cāng)庫(kù)中揀貨時(shí),需要在貨格之間、貨格與復(fù)核臺(tái)之間、復(fù)核臺(tái)與復(fù)核臺(tái)之間行走。由于這些行走通常要繞過(guò)障礙物,所以不能直接采用坐標(biāo)計(jì)算歐幾里得距離。倉(cāng)庫(kù)一共四排,每排25 組貨架,每組2 個(gè)貨架,共50個(gè)貨架,每個(gè)貨架包含15 個(gè)貨格,由于貨架數(shù)量過(guò)多,為了方便計(jì)算,故考慮將一組貨架看成兩個(gè)貨架,每排的貨架從左到右開(kāi)始排序,將每排的貨架分為奇數(shù)列和偶數(shù)列,分析在貨格之間、貨格與復(fù)核臺(tái)之間、復(fù)核臺(tái)與復(fù)核臺(tái)之間的距離關(guān)系,由距離關(guān)系和曼哈頓距離得到相應(yīng)的距離表達(dá)式,然后用MATLAB 計(jì)算表達(dá)式,從而得到3000 個(gè)貨格和13 個(gè)復(fù)核臺(tái),總共3013 個(gè)元素之間的距離。

4.2 模型的建立與求解

4.2.1 曼哈頓距離簡(jiǎn)介

曼哈頓距離（Manhattan Distance）是由十九世紀(jì)的赫爾曼·閔可夫斯基所創(chuàng)詞匯,是種使用在幾何度量空間的幾何學(xué)用語(yǔ),用以標(biāo)明兩個(gè)點(diǎn)在標(biāo)準(zhǔn)坐標(biāo)系上的絕對(duì)軸距總和。[1]

（1）二維平面兩點(diǎn)a(x1,y1)與b(x2,y2)間的曼哈頓距離：

(2)兩個(gè)n 維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的曼哈頓距離

由于本題都是在二維平面進(jìn)行討論,故只參考曼哈頓距離（1）的關(guān)系式。

4.2.2 貨格與貨格之間的距離

（1）如果貨格不在同一排貨架,分以下2 種情況討論貨格與貨格之間的距離D：

當(dāng)貨格所在列同為偶數(shù)或奇數(shù)時(shí)：

當(dāng)貨格所在列為一奇一偶或者一偶一奇時(shí)：

（2）如果貨格在同一排貨架,對(duì)x,y 的值分以下4 種情況討論貨格與貨格之間的距離D：

將上述中的表達(dá)式,用MATLAB 編程,得出貨格與貨格之間的距離矩陣。（相關(guān)數(shù)據(jù)在Ques1 的表單中）

4.2.3 貨格與復(fù)刻臺(tái)之間的距離

（1）如果不在同一排貨架時(shí),分以下幾種情況討論：

當(dāng)貨架所在列為奇數(shù)時(shí):

當(dāng)貨架所在列為偶數(shù)時(shí):

（2）如果在同一排貨架時(shí),對(duì)x,y 的值分以下4 種情況討論：

將上述中的表達(dá)式求解,得出貨格與復(fù)刻臺(tái)之間的距離矩陣。（相關(guān)數(shù)據(jù)在Ques1 的表單中）4.2.4 復(fù)刻臺(tái)與復(fù)刻臺(tái)之間的距離

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

將上述中的表達(dá)式求解,得出復(fù)刻臺(tái)與復(fù)刻臺(tái)之間的距離矩陣。（相關(guān)數(shù)據(jù)在Ques1 的表單中）

5 問(wèn)題二的分析與解答

5.1 問(wèn)題的分析

在問(wèn)題2 中規(guī)劃揀貨員 P 在復(fù)核臺(tái)FH10 領(lǐng)取了任務(wù)單 T0001 理想的揀貨路線(xiàn),揀貨員p 在倉(cāng)庫(kù)內(nèi)的移動(dòng),可以將其移動(dòng)看做TSP 問(wèn)題,但由于障礙物的作用和終點(diǎn)與起點(diǎn)不在同一處,故不能用一般的TSP 計(jì)算。由問(wèn)題1 計(jì)算出的最短距離矩陣為基礎(chǔ),將揀貨員p 的路線(xiàn)拆分為復(fù)核臺(tái)FH10 →任務(wù)單T0001 所有貨格為最優(yōu)路徑1 和最優(yōu)路徑1的最后一個(gè)貨格→復(fù)刻臺(tái)為最優(yōu)路徑2。我們?yōu)榱吮ＷC結(jié)果的精確度,沒(méi)有采用基于2-OPT 的普通模擬退火算法,而是對(duì)模擬退火算法進(jìn)行改進(jìn),這種改進(jìn)的模擬退火算法的改進(jìn)之處在于引入多種算子 (如:移位,交換,倒置等等)來(lái)產(chǎn)生新解空間,并且以一定的概率來(lái)決定運(yùn)用哪種算子來(lái)產(chǎn)生新的解空間。用改進(jìn)后的模擬退火算法分別計(jì)算出路徑1 和路徑2 的最優(yōu)路徑,再將兩條最優(yōu)路徑合并得到揀貨員p 的最佳路徑,然后在最佳路徑的基礎(chǔ)上計(jì)算出庫(kù)花費(fèi)的時(shí)間。

5.2 旅行商問(wèn)題的背景

旅行商問(wèn)題(TravelingSalesmanProblem,TSP)是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題。經(jīng)典的TSP 可以描述為：一個(gè)商品推銷(xiāo)員要去若干個(gè)城市推銷(xiāo)商品,該推銷(xiāo)員從一個(gè)城市出發(fā),需要經(jīng)過(guò)所有城市后,回到出發(fā)地。應(yīng)如何選擇行進(jìn)路線(xiàn),以使總的行程最短。從圖論的角度來(lái)看,該問(wèn)題實(shí)質(zhì)是在一個(gè)帶權(quán)完全無(wú)向圖中,找一個(gè)權(quán)值最小的Hamilton 回路。由于該問(wèn)題的可行解是所有頂點(diǎn)的全排列,隨著頂點(diǎn)數(shù)的增加,會(huì)產(chǎn)生組合爆炸,它是一個(gè)NP 完全問(wèn)題。由于其在交通運(yùn)輸、電路板線(xiàn)路設(shè)計(jì)以及物流配送等領(lǐng)域內(nèi)有著廣泛的應(yīng)用,國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行了大量的研究。早期的研究者使用精確算法求解該問(wèn)題,常用的方法包括：分枝定界法、線(xiàn)性規(guī)劃法、動(dòng)態(tài)規(guī)劃法等。但是,隨著問(wèn)題規(guī)模的增大,精確算法將變得無(wú)能為力,因此,在后來(lái)的研究中,國(guó)內(nèi)外學(xué)者重點(diǎn)使用近似算法或啟發(fā)式算法,主要有遺傳算法、模擬退火法、蟻群算法、禁忌搜索算法、貪婪算法和神經(jīng)網(wǎng)絡(luò)等。[2]

5.3 模型的建立與求解

對(duì)于模擬退火算法,它是一種通用概率算法,用來(lái)在一定時(shí)間內(nèi)尋求在一個(gè)大的搜尋空間內(nèi)找到的最優(yōu)解.

模擬退火算法來(lái)源于固體退火原理,將固體加溫至充分高,再讓其徐徐冷卻,加溫時(shí)固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀,內(nèi)能增大,而徐徐冷卻時(shí)粒子漸趨有序,在每個(gè)溫度都達(dá)到平衡態(tài),最后在常溫時(shí)達(dá)到基態(tài),內(nèi)能減為最小。根據(jù)Metropolis 準(zhǔn)則,粒子在溫度T 時(shí)趨于平衡的概率為,其中E 為溫度T 時(shí)的內(nèi)能,ΔE 為其改變量,k 為Boltzmann 常數(shù)。用固體退火模擬組合優(yōu)化問(wèn)題,將內(nèi)能E模擬為目標(biāo)函數(shù)值f,溫度T 演化成控制參數(shù)t,即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i 和控制參數(shù)初值t開(kāi)始,對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代,并逐步衰減t 值,算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解,這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程,退火過(guò)程由冷卻進(jìn)度表(Cooling Schedule)控制,包括控制參數(shù)的初值T0及其衰減因子、每個(gè)T 值時(shí)的迭代次數(shù)L 和停止條件S。[3]算法的步驟如下：

（1）給定一個(gè)初始溫度0T，并隨機(jī)生成一個(gè)初始路徑x0，并計(jì)算相應(yīng)目標(biāo)函數(shù)值f(x0)；

（2）令當(dāng)前溫度T 等于冷卻進(jìn)度表中的下一個(gè)值iT；（第一次迭代時(shí)T0T）；

（3）在當(dāng)前路徑ix的附近隨機(jī)產(chǎn)生一個(gè)新路徑ix，計(jì)算新解的目標(biāo)函數(shù)值f(xj)（隨機(jī)產(chǎn)生產(chǎn)華部格方法有的換法、移位法、例法）；

（4）如果f(xj)f(xi)，則接受新路徑xj；如果則計(jì)算；ff(xj)f(xi)，并計(jì)算，然后隨機(jī)生成一個(gè)在區(qū)間[0,1]上服從均勻分布的隨機(jī)數(shù)r，如果r

（5）在溫度T 下、將步驟（3）和（4）重復(fù)iL次；

（6）判斷是否滿(mǎn)足退出條件，如果滿(mǎn)足則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。（終止條件通常取為連續(xù)若干個(gè)新解都設(shè)有被接受時(shí)終止算法）；

（7）iT逐漸減少，且0iT，然后轉(zhuǎn)第二步?？刂茀?shù)的確定：

在使用普通的模擬退火算法解決 TSP 時(shí),一般采用 2-opt 算法來(lái)產(chǎn)生新的解空間,導(dǎo)致算法效率低下,為了增進(jìn)模擬退火算法解決 TSP 問(wèn)題的效率。故引入多種算子(如:移位,交換,倒置等等)來(lái)產(chǎn)生新解空間。改進(jìn)后的模擬退火算法效率明顯提高,在收斂性和運(yùn)算結(jié)果上都有較大的進(jìn)步,這種改進(jìn)的模擬退火算法的改進(jìn)之處在于引入多種算子(如:移位,交換,倒置等等)來(lái)產(chǎn)生新解空間,產(chǎn)生新解的方法如下。并且以一定的概率來(lái)決定運(yùn)用哪種算子來(lái)產(chǎn)生新的解空間,改進(jìn)后的算法在運(yùn)算效率,收斂性和運(yùn)算時(shí)間上都優(yōu)于2-OPT的模擬退火算法,從而求得問(wèn)題的最優(yōu)解。在改進(jìn)的算法中,以 50%的概率選擇位移,25%的概率選擇置換和25%的概率選擇倒置來(lái)產(chǎn)生新解空間可以使算法的效果比較好。[4]

新解產(chǎn)生的三種方法：

（1）交換法：隨機(jī)選擇兩個(gè)點(diǎn)，交換這兩個(gè)點(diǎn)的位置。

（2）移位法：隨機(jī)選擇三個(gè)點(diǎn)，將前三個(gè)點(diǎn)之間的點(diǎn)移位到第三個(gè)點(diǎn)后。

（3）倒置法：隨機(jī)選擇兩個(gè)點(diǎn)，將這兩個(gè)點(diǎn)之間的順序完全顛倒。

我們以問(wèn)題一的距離矩陣為基礎(chǔ),用模擬退火算法建模和MATLAB 編程求得最優(yōu)路徑和最優(yōu)路徑的距離(具體程序見(jiàn)附錄2),揀貨員 P 在復(fù)核臺(tái)FH10 領(lǐng)取了任務(wù)單 T0001理想的揀貨路線(xiàn)如表5-3 所示：

表5-3 最優(yōu)揀貨路線(xiàn)

由MATLAB 計(jì)算的最優(yōu)路徑的最短距離為238460mm,由題目可得到揀貨員p 的行走速度為 1.5m/s,在商品下架過(guò)中程,對(duì)任意一個(gè)貨格,若下架商品數(shù)量小于 3 件,每件完成下架花費(fèi)5 秒,否則每件花費(fèi)4 秒,當(dāng)復(fù)核臺(tái)正常工作時(shí),才可以進(jìn)行復(fù)核打包操作,每個(gè)訂單復(fù)核和打包花費(fèi)30 秒,從上述信息可計(jì)算任務(wù)單T0001 出庫(kù)花費(fèi)的時(shí)間：

揀貨員p 在行走過(guò)程中需要下架貨物,在任務(wù)單T0001中任意貨格中需要下架三件及三件以上的貨格共六個(gè),其中六個(gè)貨格所包含的商品數(shù)量共18 件,三件以下的貨格共17 個(gè),其中17 個(gè)貨格所包含的商品數(shù)量有21 件,故可算出揀貨員p 下架任務(wù)單T0001 所有商品所需時(shí)間

復(fù)核臺(tái)每個(gè)訂單復(fù)核和打包花費(fèi)30 秒,任務(wù)單T0001總共包含10 個(gè)訂單,復(fù)核臺(tái)所需時(shí)間:

綜上所述,任務(wù)單T0001 出庫(kù)花費(fèi)的時(shí)間為t：

6 問(wèn)題三的分析與求解

6.1 問(wèn)題三的分析

問(wèn)題三在問(wèn)題二的基礎(chǔ)上,增加到五個(gè)任務(wù)單（T0002-T0006）,并限制復(fù)核臺(tái)正常工作的數(shù)量為兩臺(tái)（分別為FH03,FH11）,由揀貨員 P 負(fù)責(zé)揀貨,P 初始位置為 FH03.該問(wèn)題與問(wèn)題2 相似,也是終點(diǎn)和起點(diǎn)不在同一點(diǎn),有障礙物的TSP 問(wèn)題,故也可采用問(wèn)題二中改進(jìn)后的模擬退火方法來(lái)進(jìn)行問(wèn)題三的運(yùn)算。

首先,因?yàn)閱?wèn)題三需要找到揀貨員p 完成五個(gè)訂單的最優(yōu)路徑,根據(jù)附件中所對(duì)應(yīng)的資料,我們考慮整體直接求出任務(wù)單T0002-T0006 的理想路徑比較困難,所以我們將這五個(gè)訂單的整體最優(yōu)路徑拆分為完成每個(gè)訂單的理想路徑,記為理想路徑1-5,計(jì)算完畢后再合并從而得到任務(wù)單T0002-T0006 的整體最優(yōu)路徑。我們先用改進(jìn)后的模擬退火模型作為建模方法,然后用MATLAB 編程分別計(jì)算這五個(gè)任務(wù)單內(nèi)貨格與貨格之間的最優(yōu)路徑,經(jīng)過(guò)計(jì)算可得到五條最優(yōu)路徑,然后從這五條最優(yōu)路徑中分別找出路徑兩端的端點(diǎn)（貨格）,這五條最優(yōu)路徑可找出十個(gè)端點(diǎn),從題目中P 初始位置為 FH03,基于問(wèn)題一的最短路徑矩陣,將FH03到十個(gè)端點(diǎn)的距離做比較,與FH03 距離最小的點(diǎn)所對(duì)應(yīng)的訂單為揀貨員p 處理的第一個(gè)訂單,復(fù)核臺(tái)首先進(jìn)入該端點(diǎn)所對(duì)應(yīng)的貨格,該訂單的另一個(gè)端點(diǎn)作為最后經(jīng)過(guò)的貨格,然后找第一個(gè)訂單最后經(jīng)過(guò)的貨格與復(fù)核臺(tái)FH03,FH11 的最短距離,最小距離所對(duì)應(yīng)的復(fù)刻臺(tái)為理想路徑1 的終點(diǎn)。此時(shí)第一個(gè)訂單揀貨完成,到達(dá)復(fù)核臺(tái)后揀貨員無(wú)需等待,繼續(xù)領(lǐng)取揀貨車(chē)和任務(wù)單,開(kāi)始下一個(gè)任務(wù)單揀貨流程,理想路徑1 所到達(dá)的最終復(fù)核臺(tái)作為理想路徑2 的起點(diǎn),將該起點(diǎn)與剩余的八個(gè)端點(diǎn)的距離作比較,距離最小的端點(diǎn)所對(duì)應(yīng)的訂單為揀貨員p 處理的第二個(gè)訂單,復(fù)核臺(tái)首先進(jìn)入該端點(diǎn)所對(duì)應(yīng)的貨格,該訂單的另一個(gè)端點(diǎn)作為最后經(jīng)過(guò)的貨格,然后找第二個(gè)訂單最后經(jīng)過(guò)的貨格與復(fù)核臺(tái)FH03,FH11的最短距離,最短距離最小所對(duì)應(yīng)的復(fù)刻臺(tái)為理想路徑2 的終點(diǎn),此時(shí)第二個(gè)訂單揀貨完成。然后不斷重復(fù)上述過(guò)程,下個(gè)理想路徑的起始復(fù)核臺(tái)與任務(wù)端的兩端端點(diǎn)比較,端點(diǎn)數(shù)量將會(huì)變?yōu)?、4、2,在這個(gè)過(guò)程中,可找到理想路徑3、4、5,最后根據(jù)上述的數(shù)據(jù),將理想路徑1-5 進(jìn)行合并,可得到揀貨員p 完成任務(wù)單T0002-T0006 的完整理想路徑。

根據(jù)揀貨員p 完成任務(wù)單T0002-T0006 的完整理想路徑先計(jì)算距離,然后分類(lèi)計(jì)算完成出庫(kù)需要花費(fèi)的時(shí)間,最后根據(jù)時(shí)間計(jì)算每個(gè)復(fù)核臺(tái)利用率。

6.2 問(wèn)題三的建模與求解

問(wèn)題三用的模型是問(wèn)題二改進(jìn)后的模擬退火模型,該模型在問(wèn)題二中已經(jīng)詳細(xì)介紹過(guò)了,在這里就不繼續(xù)介紹。根據(jù)6.1 中做出的分析,先用改進(jìn)后的模擬退火模型作為建模方法用MATLAB 編程分別計(jì)算T0001-T0006 任務(wù)單內(nèi)貨格與貨格之間的最優(yōu)路徑,經(jīng)過(guò)計(jì)算可得到五條最優(yōu)路徑,然后繼續(xù)以改進(jìn)后的模擬退火模型作為建模方法用MATLAB編程得到每個(gè)訂單的理想路徑1-5,計(jì)算完畢后再將其合并從而得到任務(wù)單T0002-T0006 的整體最優(yōu)路徑：FH03 →T 0005→FH03→T0004→FH11→T0003→FH11→T0006→FH03→T0002→FH11。(詳細(xì)路徑在Ques3)

根據(jù)揀貨員p 完成任務(wù)單T0002-T0006 的完整理想路徑先計(jì)算復(fù)核臺(tái)到任務(wù)單的第一個(gè)訂單距離和任務(wù)單的最后一個(gè)訂單到復(fù)核臺(tái)的距離和任務(wù)單內(nèi)的距離。（詳細(xì)距離見(jiàn)表6-1）

表6-1

由題目可得到揀貨員p 的行走速度為 1.5m/s,在商品下架過(guò)中程,對(duì)任意一個(gè)貨格,若下架商品數(shù)量小于 3 件,每件完成下架花費(fèi)5 秒,否則每件花費(fèi)4 秒,當(dāng)復(fù)核臺(tái)正常工作時(shí),才可以進(jìn)行復(fù)核打包操作,每個(gè)訂單復(fù)核和打包花費(fèi)30 秒,從上述信息可計(jì)算任務(wù)單T0002-T0006 出庫(kù)花費(fèi)的時(shí)間：

揀貨員p 完成任務(wù)單T0002-T0006 的完整理想路徑行走距離：8400+227990+10900+18700+283390+55200+40400+295250+45000+57200+215490+5900+70700+263960+71400=1669880(mm)=1669.88(m)

揀貨員p 在行走過(guò)程中需要下架貨物,在任務(wù)單T0002-T0006 中任意貨格中需要下架三件及三件以上的貨格共26 個(gè),其中26 個(gè)貨格所包含的商品數(shù)量共78 件,三件以下的貨格共93 個(gè),其中93 個(gè)貨格所包含的商品數(shù)量有112 件,故可算出揀貨員p 下架任務(wù)單T0001 所有商品所需時(shí)間

復(fù)核臺(tái)每個(gè)訂單復(fù)核和打包花費(fèi)30 秒,任務(wù)單T0002-T006 總共包含65 個(gè)訂單,復(fù)核臺(tái)所需時(shí)間

綜上所述,任務(wù)單T0001 出庫(kù)花費(fèi)的時(shí)間為t：

若一個(gè)復(fù)核臺(tái)完成該復(fù)核臺(tái)所有任務(wù)單的復(fù)核和打包,沒(méi)有新任務(wù)前,該復(fù)核臺(tái)將處于空閑狀態(tài)。從 0 時(shí)刻到 TOTAL_TIME 時(shí)刻,若一個(gè)復(fù)核臺(tái)總空閑時(shí)間為 IDLE_TIME,則該復(fù)核臺(tái)利用率=1-IDLE_TIME/TOTAL_TIME。

由以上信息可推出IDLE_TIME=TOTAL_TIME-work_TIME,TOTAL_TIME=3935.25s；

對(duì)于FH03:work_TIME=840s;對(duì)于FH04:work_TIME=1110s;

對(duì)于FH03：IDLE_TIME=3935.25-840=3095.25s;

對(duì)于FH11：IDLE_TIME=3935.25-1110=2825.25s;

復(fù)核器利用率：FH03:1-IDLE_TIME/TOTAL_TIME=1-3095.25/3935.25 ≈21.35%;

FH11:1-IDLE_TIME/TOTAL_TIME=1-2825.25/3935.25 ≈28.21%;

7 問(wèn)題四的分析與求解

7.1 問(wèn)題的分析

問(wèn)題四在問(wèn)題三的基礎(chǔ)上,進(jìn)一步擴(kuò)展,任務(wù)單、人數(shù)、復(fù)核臺(tái)的數(shù)量都增加了,使問(wèn)題更加復(fù)雜,需要考慮到給9 個(gè)揀貨員（P1-P9）分配訂單的問(wèn)題.在題中4 個(gè)復(fù)核臺(tái)（FH01,FH03,FH10,FH12）正常工作,49 個(gè)任務(wù)單（T0001-T0049）等待揀貨,9 個(gè)揀貨員（P1-P9）負(fù)責(zé)揀貨,還是繼續(xù)采用問(wèn)題二中改進(jìn)后的模擬退火方法,以問(wèn)題三的計(jì)算思路作為基本思路來(lái)進(jìn)行問(wèn)題四的運(yùn)算。

首先,因?yàn)閱?wèn)題四需要找到完成任務(wù)單T0001-T0049 的整體理想路徑,根據(jù)附件中所對(duì)應(yīng)的資料,我們考慮整體直接求出任務(wù)單T0001-T0049 的理想路徑比較困難,所以我們將這49 個(gè)訂單的整體最優(yōu)路徑拆分為完成每個(gè)訂單的理想路徑（記為理想路徑1-49）,計(jì)算完畢后再合并從而得到任務(wù)單T0001-T0049 的整體最優(yōu)路徑。我們先用改進(jìn)后的模擬退火模型作為建模方法,然后用MATLAB 編程分別計(jì)算這49 個(gè)任務(wù)單內(nèi)貨格與貨格之間的最優(yōu)路徑,經(jīng)過(guò)計(jì)算可得到49 條最優(yōu)路徑,然后從這49 條最優(yōu)路徑中分別找出路徑兩端的端點(diǎn)（貨格）,這49 條最優(yōu)路徑可找出98 個(gè)端點(diǎn)。由于本題的初始出發(fā)位置未知,基于問(wèn)題一的最短路徑矩陣,將4 個(gè)復(fù)核臺(tái)到98 個(gè)端點(diǎn)的距離做比較,找出距離最小所對(duì)應(yīng)的訂單和復(fù)核臺(tái)為揀貨員處理的第一個(gè)訂單和理想路徑起點(diǎn),復(fù)核臺(tái)首先進(jìn)入該端點(diǎn)所對(duì)應(yīng)的貨格,該訂單的另一個(gè)端點(diǎn)作為最后經(jīng)過(guò)的貨格,然后找第一個(gè)任務(wù)單訂單最后經(jīng)過(guò)的貨格與4 個(gè)復(fù)核臺(tái)的最短距離,距離最小所對(duì)應(yīng)的復(fù)刻臺(tái)為理想路徑1的終點(diǎn)。此時(shí)第一個(gè)訂單揀貨完成,到達(dá)復(fù)核臺(tái)后揀貨員無(wú)需等待,繼續(xù)領(lǐng)取揀貨車(chē)和任務(wù)單,開(kāi)始下一個(gè)任務(wù)單揀貨流程,理想路徑1 所到達(dá)的最終復(fù)核臺(tái)作為理想路徑2 的起點(diǎn),將該起點(diǎn)與剩余的96 個(gè)端點(diǎn)的距離作比較,距離最小的端點(diǎn)所對(duì)應(yīng)的訂單為揀貨員處理的第二個(gè)訂單,復(fù)核臺(tái)首先進(jìn)入該端點(diǎn)所對(duì)應(yīng)的貨格,該訂單的另一個(gè)端點(diǎn)作為最后經(jīng)過(guò)的貨格,然后找第二個(gè)任務(wù)單最后經(jīng)過(guò)的貨格與4 個(gè)復(fù)核臺(tái)的最短距離,最短距離最小所對(duì)應(yīng)的復(fù)刻臺(tái)為理想路徑2的終點(diǎn),此時(shí)第二個(gè)訂單揀貨完成。然后不斷重復(fù)上述過(guò)程,下個(gè)理想路徑的起始復(fù)核臺(tái)與任務(wù)端的兩端端點(diǎn)比較,端點(diǎn)數(shù)量將會(huì)變?yōu)?6、94、92…,直到端點(diǎn)數(shù)量變?yōu)?,在這個(gè)過(guò)程中,可找到理想路徑3-49,最后根據(jù)上述的數(shù)據(jù),將理想路徑1-49 進(jìn)行合并,可得到完成任務(wù)單T0001-T0049 的完整理想路徑。最后用MATLAB 編程求得任務(wù)單T0001-T0049 的完整理想路徑,先計(jì)算完整理想路徑的距離然后計(jì)算完成所有任務(wù)單出庫(kù)需要花費(fèi)的時(shí)間,最后根據(jù)時(shí)間計(jì)算每個(gè)復(fù)核臺(tái)利用率。

表8-1

在對(duì)任務(wù)單進(jìn)行合理分配問(wèn)題上,將按照任務(wù)單T0001-T0049 的完整理想路徑進(jìn)行分配,完整理想路徑的第一個(gè)任務(wù)單是完成揀貨時(shí)間最短的,將第一個(gè)任務(wù)單分配給揀貨員1,按照理想路徑順序依次給揀貨員P2-P9 分配任務(wù)單,因?yàn)閽泦TP1 的揀貨時(shí)間比另外8 個(gè)揀貨員的時(shí)間都短,故揀貨員P1 最快完成所分配任務(wù)單的揀貨,然后按照理想路徑順序再次給揀貨員P1 分配任務(wù)單,揀貨員P2 的揀貨時(shí)間比另外6 個(gè)揀貨員(不包含揀貨員P1)的時(shí)間都短,故揀貨員2 第二快完成所分配任務(wù)單的揀貨,然后按照整體理想路徑順序再次給揀貨員P2 分配任務(wù)單,按照上面的規(guī)律,分配剩余的任務(wù)單,直至49 個(gè)任務(wù)單全部被完成。

7.2 問(wèn)題四的建模與求解

問(wèn)題四用的模型是問(wèn)題二改進(jìn)后的模擬退火模型,其思路在問(wèn)題三的思路上再做進(jìn)一步改進(jìn)。根據(jù)7.1 中做出的分析,先用改進(jìn)后的模擬退火模型作為建模方法用MATLAB編程分別計(jì)算T0001-T00049 任務(wù)單內(nèi)貨格與貨格之間的最優(yōu)路徑,經(jīng)過(guò)計(jì)算可得到49 條最優(yōu)路徑,然后繼續(xù)以改進(jìn)后的模擬退火模型作為建模方法用MATLAB 編程得到每個(gè)訂單的理想路徑1-5,計(jì)算完畢后再將其合并從而得到任務(wù)單T0001-T0049 的整體理想路徑,再按照任務(wù)單T0001-T0049 的完整理想路徑進(jìn)行分配揀貨員。（整體理想路徑在表單Ques3）

每個(gè)揀貨員規(guī)劃理想的揀貨路線(xiàn)如表7-1 所示:

從題目中可得到揀貨員的行走速度為 1.5m/s,在商品下架過(guò)中程,對(duì)任意一個(gè)貨格,若下架商品數(shù)量小于3 件,每件完成下架花費(fèi)5 秒,否則每件花費(fèi)4 秒,當(dāng)復(fù)核臺(tái)正常工作時(shí),才可以進(jìn)行復(fù)核打包操作,每個(gè)訂單復(fù)核和打包花費(fèi)30 秒,從上述信息可計(jì)算任務(wù)單T0001-T0049 出庫(kù)花費(fèi)的時(shí)間。

揀貨員（P1-P9）完成任務(wù)單T0001-T0049 的完整理想路徑行走距離：3657m;任務(wù)單T0001-T0049 出庫(kù)花費(fèi)的時(shí)間為t=29169s。

若一個(gè)復(fù)核臺(tái)完成該復(fù)核臺(tái)所有任務(wù)單的復(fù)核和打包,沒(méi)有新任務(wù)前,該復(fù)核臺(tái)將處于空閑狀態(tài)。從 0 時(shí)刻到 TOTAL_TIME 時(shí)刻,若一個(gè)復(fù)核臺(tái)總空閑時(shí)間為 IDLE_TIME,則該復(fù)核臺(tái)利用率=1-IDLE_TIME/TOTAL_TIME。

TOTAL_TIME=29169s ;

復(fù)核器利用率：FH01:1-IDLE_TIME/TOTAL_TIME=10.59%;

FH03:1-IDLE_TIME/TOTAL_TIME=14.25%;

FH10:1-IDLE_TIME/TOTAL_TIME=26.55%;

FH12:1-IDLE_TIME/TOTAL_TIME=16.25%;

8 問(wèn)題五的分析與解答

8.1 問(wèn)題的分析

問(wèn)題5 是在問(wèn)題4 的基礎(chǔ)上進(jìn)一步拓展,現(xiàn)有4 個(gè)復(fù)核臺(tái)（FH01,FH03,FH10,FH12）正常工作,評(píng)估增加一個(gè)正常工作的復(fù)核臺(tái)對(duì)出庫(kù)時(shí)間的影響。在題中有9 個(gè)復(fù)核臺(tái)未工作,所以再增加一個(gè)正常工作的復(fù)核臺(tái)有9 種可能,故我們要分別對(duì)這9 個(gè)復(fù)核臺(tái)分析,用MATLAB 編程,分別計(jì)算出這增加9 個(gè)復(fù)核臺(tái)其中的一個(gè)對(duì)出庫(kù)時(shí)間的影響。

8.2 模型的建立與求解

通過(guò)MATLAB 編程,求得增加9 個(gè)復(fù)核臺(tái)其中的一個(gè)對(duì)出庫(kù)時(shí)間的影響,結(jié)果如表8-1：

在沒(méi)有增加復(fù)核臺(tái)時(shí),倉(cāng)庫(kù)花費(fèi)的時(shí)間為26169s。無(wú)論增加哪個(gè)復(fù)核臺(tái),都能夠減少花費(fèi)時(shí)間,有效增加倉(cāng)庫(kù)完成揀貨的效率,其中增加復(fù)核臺(tái)FH04 倉(cāng)庫(kù)完成揀貨花費(fèi)的時(shí)間最短。

9 問(wèn)題六的建議

隨著信息技術(shù)及移動(dòng)互聯(lián)網(wǎng)的迅速發(fā)展,人們對(duì)于網(wǎng)上購(gòu)物需求越來(lái)越大,不管是在網(wǎng)上購(gòu)物還是在實(shí)體店購(gòu)物,倉(cāng)庫(kù)都起著至關(guān)重要的作用,可以用來(lái)存儲(chǔ)商品,也是物流系統(tǒng)中的重要節(jié)點(diǎn)。每位顧客在購(gòu)買(mǎi)商品時(shí),都希望能盡快拿到貨,拿到貨的時(shí)間越短,顧客的滿(mǎn)意度越高,商品能否盡快從倉(cāng)庫(kù)出貨是顧客能否在短時(shí)間內(nèi)拿到貨的重要因素,在一定時(shí)間內(nèi),某種商品數(shù)量出庫(kù)最多可稱(chēng)為暢銷(xiāo)品。商品在貨架中的擺放位置,會(huì)影響商品出庫(kù)的效率,若將暢銷(xiāo)品放置在離復(fù)核臺(tái)較近的位置,揀貨員行走距離相應(yīng)減少,但暢銷(xiāo)品所在貨架能擁擠,反而降低揀貨效率。減少揀貨員在揀貨過(guò)程中的耗時(shí)對(duì)提高倉(cāng)庫(kù)運(yùn)作效率有著至關(guān)重要的影響。

在問(wèn)題三、四中對(duì)復(fù)核臺(tái)利用率計(jì)算時(shí),發(fā)現(xiàn)這些復(fù)核臺(tái)的利用率都小于30%,復(fù)核臺(tái)的利用率較小,可能是由于商品在倉(cāng)庫(kù)中的擺放位置比較隨意導(dǎo)致倉(cāng)庫(kù)運(yùn)作效率較低,為了提高倉(cāng)庫(kù)運(yùn)用效率,我們提出如下建議：

將商品按照銷(xiāo)售數(shù)量分等級(jí),可分為一等品,二等品,三等品…（一等品出庫(kù)數(shù)量最高,二等品出庫(kù)數(shù)量比一等品少）,然后根據(jù)倉(cāng)庫(kù)內(nèi)的貨架離復(fù)核臺(tái)的距離分成幾個(gè)區(qū)域,離復(fù)核臺(tái)距離越近的區(qū)域放一等品,離復(fù)核臺(tái)距離較近的區(qū)域放二等品,直至所有等級(jí)的商品被放完。每個(gè)等級(jí)存在很多種類(lèi)的商品,商品的擺放可以考慮商品之間的相關(guān)性,其相關(guān)性越強(qiáng),商品之間的擺放距離就越近,同種種類(lèi)的暢銷(xiāo)品,可以分散開(kāi)放置在該暢銷(xiāo)品所對(duì)應(yīng)區(qū)域的多個(gè)貨架中,由此可以解決暢銷(xiāo)品所在貨架擁擠的問(wèn)題。

10 模型的評(píng)價(jià)、改進(jìn)與推廣

10.1 模型的評(píng)價(jià)

10.1.1 模型優(yōu)點(diǎn)

（1）本文的特色體現(xiàn)在引入多種算子改進(jìn)后的模擬退火算法,相比于傳統(tǒng)的采用2-opt 算法的模擬退火效率明顯提高,在收斂性和運(yùn)算結(jié)果上都有較大的進(jìn)步,增加了解題的精確度,將改進(jìn)后的模擬退火算法與TSP 理論相結(jié)合給出問(wèn)題的最優(yōu)解。

（2）模擬退火算法不僅能處理連續(xù)優(yōu)化問(wèn)題,還能很方便的處理組合優(yōu)化問(wèn)題,且編程簡(jiǎn)單易于實(shí)現(xiàn),目標(biāo)函數(shù)的收斂速度較快。在本題相關(guān)條件的約束下,通過(guò)此模型可以較容易求得問(wèn)題的最優(yōu)解。

（3）通過(guò)該模型求解的最佳路徑,可以有效提高倉(cāng)庫(kù)的揀選效率,縮短揀選時(shí)間和減少工人在倉(cāng)庫(kù)的行走距離。

10.1.2 模型缺點(diǎn)

（1）模擬退火算法參數(shù)的選擇至關(guān)重要,初始參數(shù)的合理選取是保證算法的全局收斂性和效率的關(guān)鍵,選擇不當(dāng)?shù)玫降慕Y(jié)果可能會(huì)很差。

（2）在本題的解答過(guò)程中,因?yàn)閷?duì)題的分類(lèi)情況較多,所以可能有部分因素沒(méi)考慮進(jìn)來(lái),從而影響結(jié)果的正確性。

10.2 模型算法的改進(jìn)及推廣

（1）可以引入粒子算法等優(yōu)化算法對(duì)改進(jìn)后的模擬退火模型再次優(yōu)化,增加模型的精確度。

（2）對(duì)問(wèn)題進(jìn)行細(xì)分,將各種可能影響問(wèn)題的因素,帶入題中分析,以此來(lái)保證結(jié)果的正確性。

（3）在倉(cāng)庫(kù)管理的問(wèn)題中,可以考慮將訂單用總合計(jì)量,時(shí)窗,固定量訂單分批等方法,可以進(jìn)一步有效提高倉(cāng)庫(kù)的揀選效率和擴(kuò)大使用范圍。

該模型可以推廣于中小型倉(cāng)庫(kù),可以有效提高倉(cāng)庫(kù)的揀選效率,縮短揀選時(shí)間和減少工人在倉(cāng)庫(kù)的行走距離。