基于模擬退火對貨倉揀貨的優化

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

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

1 問題重述

某電商公司客戶訂單下達倉庫后,商品開始下架出庫,出庫主要包含5 個流程如下所示：

定位-->組單-->揀貨-->復核-->打包

現有一個倉庫,倉庫數據見附件1,包括4 個表格,前3個表格為倉庫信息,包括貨架、貨格、復核臺的位置及大小,貨格和貨架的關系。第4 個表格為任務單信息,一個任務單包含多個訂單,一個訂單商品包含多個貨格,一個貨格需要揀多件商品。

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

說明：

（1）當繞障礙物折線行走時橫向和豎向偏移都取d=750mm;

（2）復核臺之間距離簡化為兩復核臺坐標差的絕對值之和,如復核臺,復核臺,則兩復核臺的距離為；

（3）貨格與復核臺距離簡化為貨格中點到復核臺最近一條邊中點的距離;

根據已知條件和要求,請完成以下問題：

問題1：當揀貨員在倉庫中揀貨時,需要在貨格之間、貨格與復核臺之間、復核臺與復核臺之間行走。由于這些行走通常要繞過障礙物,不能直接采用坐標計算歐幾里得距離。請你按照圖中距離標示,設計一種計算3000 個貨格和13 個復核臺,總共3013 個元素之間距離的方法,并將3013個元素之間的最短距離矩陣填入表單 Ques1。

問題2：假設所有復核臺正常工作,任務單 T0001 等待揀貨,揀貨員P 在復核臺 FH10 領取了任務單 T0001。請給P 規劃理想的揀貨路線,包括貨格訪問順序、返回的復核臺,計算完成出庫花費的時間（揀貨員揀貨開始到所有任務復核打包完成花費的時間）。

問題3：假設2 個復核臺 (FH03,FH11) 正常工作,5 個任務單（T0002-T0006）等待揀貨,繼續由揀貨員P 負責揀貨,P初始位置為 FH03。通過建模和優化,請給P 指定任務領取順序,規劃理想的揀貨路線,使得這些任務盡快出庫。請計算完成出庫需要花費的時間和每個復核臺利用率。

問題4：假如4 個復核臺（FH01,FH03,FH10,FH12）正常工作,49 個任務單（T0001-T0049）等待揀貨,9 個揀貨員（P1-P9 負責揀貨,請給每個揀貨員分配任務單、起始揀貨復核臺,并分別規劃理想的揀貨路線,使得49 個任務單盡快完成出庫,并計算完成出庫需要花費的時間和每個復核臺利用率。

問題5：在問題4 中,有4 個復核臺（FH01,FH03,FH10,FH12）正常工作,請評估增加一個正常工作的復核臺對出庫時間的影響。

問題6：商品在貨架中的擺放位置,會影響揀貨效率。若將暢銷品放置在離復核臺較近的位置,揀貨員行走距離相應減少,但暢銷品所在貨架可能擁擠,反而降低揀貨效率。對于倉內商品擺放問題,你有什么建議？

注：在問題 3,4,5 中,當一個人有多個任務時,只能一個一個任務完成,不能在完成一個任務過程中揀另一個任務的貨。

2 模型假設

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

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

（2）揀貨人員或車輛移動速度保持不變;

（3）每個訂單的訂貨重量不超過揀貨車的容量;

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

（5）揀選人員或揀選設備數量充足;

（6）領揀貨車和任務單與復核臺對訂單復核可以同時進行;

3 符號說明

4 問題一的分析和解答

4.1 問題的分析

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

4.2 模型的建立與求解

4.2.1 曼哈頓距離簡介

曼哈頓距離（Manhattan Distance）是由十九世紀的赫爾曼·閔可夫斯基所創詞匯,是種使用在幾何度量空間的幾何學用語,用以標明兩個點在標準坐標系上的絕對軸距總和。[1]

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

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

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

4.2.2 貨格與貨格之間的距離

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

當貨格所在列同為偶數或奇數時：

當貨格所在列為一奇一偶或者一偶一奇時：

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

將上述中的表達式,用MATLAB 編程,得出貨格與貨格之間的距離矩陣。（相關數據在Ques1 的表單中）

4.2.3 貨格與復刻臺之間的距離

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

當貨架所在列為奇數時:

當貨架所在列為偶數時:

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

將上述中的表達式求解,得出貨格與復刻臺之間的距離矩陣。（相關數據在Ques1 的表單中）4.2.4 復刻臺與復刻臺之間的距離

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

將上述中的表達式求解,得出復刻臺與復刻臺之間的距離矩陣。（相關數據在Ques1 的表單中）

5 問題二的分析與解答

5.1 問題的分析

在問題2 中規劃揀貨員 P 在復核臺FH10 領取了任務單 T0001 理想的揀貨路線,揀貨員p 在倉庫內的移動,可以將其移動看做TSP 問題,但由于障礙物的作用和終點與起點不在同一處,故不能用一般的TSP 計算。由問題1 計算出的最短距離矩陣為基礎,將揀貨員p 的路線拆分為復核臺FH10 →任務單T0001 所有貨格為最優路徑1 和最優路徑1的最后一個貨格→復刻臺為最優路徑2。我們為了保證結果的精確度,沒有采用基于2-OPT 的普通模擬退火算法,而是對模擬退火算法進行改進,這種改進的模擬退火算法的改進之處在于引入多種算子 (如:移位,交換,倒置等等)來產生新解空間,并且以一定的概率來決定運用哪種算子來產生新的解空間。用改進后的模擬退火算法分別計算出路徑1 和路徑2 的最優路徑,再將兩條最優路徑合并得到揀貨員p 的最佳路徑,然后在最佳路徑的基礎上計算出庫花費的時間。

5.2 旅行商問題的背景

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

5.3 模型的建立與求解

對于模擬退火算法,它是一種通用概率算法,用來在一定時間內尋求在一個大的搜尋空間內找到的最優解.

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

（1）給定一個初始溫度0T，并隨機生成一個初始路徑x0，并計算相應目標函數值f(x0)；

（2）令當前溫度T 等于冷卻進度表中的下一個值iT；（第一次迭代時T0T）；

（3）在當前路徑ix的附近隨機產生一個新路徑ix，計算新解的目標函數值f(xj)（隨機產生產華部格方法有的換法、移位法、例法）；

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

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

（6）判斷是否滿足退出條件，如果滿足則輸出當前解作為最優解，結束程序。（終止條件通常取為連續若干個新解都設有被接受時終止算法）；

（7）iT逐漸減少，且0iT，然后轉第二步?？刂茀档拇_定：

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

新解產生的三種方法：

（1）交換法：隨機選擇兩個點，交換這兩個點的位置。

（2）移位法：隨機選擇三個點，將前三個點之間的點移位到第三個點后。

（3）倒置法：隨機選擇兩個點，將這兩個點之間的順序完全顛倒。

我們以問題一的距離矩陣為基礎,用模擬退火算法建模和MATLAB 編程求得最優路徑和最優路徑的距離(具體程序見附錄2),揀貨員 P 在復核臺FH10 領取了任務單 T0001理想的揀貨路線如表5-3 所示：

表5-3 最優揀貨路線

由MATLAB 計算的最優路徑的最短距離為238460mm,由題目可得到揀貨員p 的行走速度為 1.5m/s,在商品下架過中程,對任意一個貨格,若下架商品數量小于 3 件,每件完成下架花費5 秒,否則每件花費4 秒,當復核臺正常工作時,才可以進行復核打包操作,每個訂單復核和打包花費30 秒,從上述信息可計算任務單T0001 出庫花費的時間：

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

復核臺每個訂單復核和打包花費30 秒,任務單T0001總共包含10 個訂單,復核臺所需時間:

綜上所述,任務單T0001 出庫花費的時間為t：

6 問題三的分析與求解

6.1 問題三的分析

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

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

根據揀貨員p 完成任務單T0002-T0006 的完整理想路徑先計算距離,然后分類計算完成出庫需要花費的時間,最后根據時間計算每個復核臺利用率。

6.2 問題三的建模與求解

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

根據揀貨員p 完成任務單T0002-T0006 的完整理想路徑先計算復核臺到任務單的第一個訂單距離和任務單的最后一個訂單到復核臺的距離和任務單內的距離。（詳細距離見表6-1）

表6-1

由題目可得到揀貨員p 的行走速度為 1.5m/s,在商品下架過中程,對任意一個貨格,若下架商品數量小于 3 件,每件完成下架花費5 秒,否則每件花費4 秒,當復核臺正常工作時,才可以進行復核打包操作,每個訂單復核和打包花費30 秒,從上述信息可計算任務單T0002-T0006 出庫花費的時間：

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

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

復核臺每個訂單復核和打包花費30 秒,任務單T0002-T006 總共包含65 個訂單,復核臺所需時間

綜上所述,任務單T0001 出庫花費的時間為t：

若一個復核臺完成該復核臺所有任務單的復核和打包,沒有新任務前,該復核臺將處于空閑狀態。從 0 時刻到 TOTAL_TIME 時刻,若一個復核臺總空閑時間為 IDLE_TIME,則該復核臺利用率=1-IDLE_TIME/TOTAL_TIME。

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

對于FH03:work_TIME=840s;對于FH04:work_TIME=1110s;

對于FH03：IDLE_TIME=3935.25-840=3095.25s;

對于FH11：IDLE_TIME=3935.25-1110=2825.25s;

復核器利用率：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 問題四的分析與求解

7.1 問題的分析

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

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

表8-1

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

7.2 問題四的建模與求解

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

每個揀貨員規劃理想的揀貨路線如表7-1 所示:

從題目中可得到揀貨員的行走速度為 1.5m/s,在商品下架過中程,對任意一個貨格,若下架商品數量小于3 件,每件完成下架花費5 秒,否則每件花費4 秒,當復核臺正常工作時,才可以進行復核打包操作,每個訂單復核和打包花費30 秒,從上述信息可計算任務單T0001-T0049 出庫花費的時間。

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

若一個復核臺完成該復核臺所有任務單的復核和打包,沒有新任務前,該復核臺將處于空閑狀態。從 0 時刻到 TOTAL_TIME 時刻,若一個復核臺總空閑時間為 IDLE_TIME,則該復核臺利用率=1-IDLE_TIME/TOTAL_TIME。

TOTAL_TIME=29169s ;

復核器利用率：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 問題五的分析與解答

8.1 問題的分析

問題5 是在問題4 的基礎上進一步拓展,現有4 個復核臺（FH01,FH03,FH10,FH12）正常工作,評估增加一個正常工作的復核臺對出庫時間的影響。在題中有9 個復核臺未工作,所以再增加一個正常工作的復核臺有9 種可能,故我們要分別對這9 個復核臺分析,用MATLAB 編程,分別計算出這增加9 個復核臺其中的一個對出庫時間的影響。

8.2 模型的建立與求解

通過MATLAB 編程,求得增加9 個復核臺其中的一個對出庫時間的影響,結果如表8-1：

在沒有增加復核臺時,倉庫花費的時間為26169s。無論增加哪個復核臺,都能夠減少花費時間,有效增加倉庫完成揀貨的效率,其中增加復核臺FH04 倉庫完成揀貨花費的時間最短。

9 問題六的建議

隨著信息技術及移動互聯網的迅速發展,人們對于網上購物需求越來越大,不管是在網上購物還是在實體店購物,倉庫都起著至關重要的作用,可以用來存儲商品,也是物流系統中的重要節點。每位顧客在購買商品時,都希望能盡快拿到貨,拿到貨的時間越短,顧客的滿意度越高,商品能否盡快從倉庫出貨是顧客能否在短時間內拿到貨的重要因素,在一定時間內,某種商品數量出庫最多可稱為暢銷品。商品在貨架中的擺放位置,會影響商品出庫的效率,若將暢銷品放置在離復核臺較近的位置,揀貨員行走距離相應減少,但暢銷品所在貨架能擁擠,反而降低揀貨效率。減少揀貨員在揀貨過程中的耗時對提高倉庫運作效率有著至關重要的影響。

在問題三、四中對復核臺利用率計算時,發現這些復核臺的利用率都小于30%,復核臺的利用率較小,可能是由于商品在倉庫中的擺放位置比較隨意導致倉庫運作效率較低,為了提高倉庫運用效率,我們提出如下建議：

將商品按照銷售數量分等級,可分為一等品,二等品,三等品…（一等品出庫數量最高,二等品出庫數量比一等品少）,然后根據倉庫內的貨架離復核臺的距離分成幾個區域,離復核臺距離越近的區域放一等品,離復核臺距離較近的區域放二等品,直至所有等級的商品被放完。每個等級存在很多種類的商品,商品的擺放可以考慮商品之間的相關性,其相關性越強,商品之間的擺放距離就越近,同種種類的暢銷品,可以分散開放置在該暢銷品所對應區域的多個貨架中,由此可以解決暢銷品所在貨架擁擠的問題。

10 模型的評價、改進與推廣

10.1 模型的評價

10.1.1 模型優點

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

（2）模擬退火算法不僅能處理連續優化問題,還能很方便的處理組合優化問題,且編程簡單易于實現,目標函數的收斂速度較快。在本題相關條件的約束下,通過此模型可以較容易求得問題的最優解。

（3）通過該模型求解的最佳路徑,可以有效提高倉庫的揀選效率,縮短揀選時間和減少工人在倉庫的行走距離。

10.1.2 模型缺點

（1）模擬退火算法參數的選擇至關重要,初始參數的合理選取是保證算法的全局收斂性和效率的關鍵,選擇不當得到的結果可能會很差。

（2）在本題的解答過程中,因為對題的分類情況較多,所以可能有部分因素沒考慮進來,從而影響結果的正確性。

10.2 模型算法的改進及推廣

（1）可以引入粒子算法等優化算法對改進后的模擬退火模型再次優化,增加模型的精確度。

（2）對問題進行細分,將各種可能影響問題的因素,帶入題中分析,以此來保證結果的正確性。

（3）在倉庫管理的問題中,可以考慮將訂單用總合計量,時窗,固定量訂單分批等方法,可以進一步有效提高倉庫的揀選效率和擴大使用范圍。

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