基于模擬退火對貨倉揀貨的優(yōu)化

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

摘 要 隨著信息技術(shù)及移動互聯(lián)網(wǎng)的迅速發(fā)展，電子商務(wù)也迅速崛起，作為一種新型的商業(yè)運作模式，正逐漸影響著人們的生活方式，倉庫作為物流系統(tǒng)的一個重要結(jié)點，減少工作人員揀貨作業(yè)的耗時對提高倉庫運作效率有著至關(guān)重要的影響。

關(guān)鍵詞 最短路徑 模擬退火 TSP MATLAB

中圖分類號：F540 文獻標(biāo)識碼：A 文章編號：1007-0745（2020）02-0038-07

1 問題重述

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

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

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

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

說明：

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

（2）復(fù)核臺之間距離簡化為兩復(fù)核臺坐標(biāo)差的絕對值之和，如復(fù)核臺A，復(fù)核臺B，則兩復(fù)核臺的距離為;

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

根據(jù)已知條件和要求，請完成以下問題：

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

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

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

問題4：假如4個復(fù)核臺（FH01，F(xiàn)H03，F(xiàn)H10，F(xiàn)H12）正常工作，49個任務(wù)單（T0001-T0049）等待揀貨，9個揀貨員（P1-P9負責(zé)揀貨，請給每個揀貨員分配任務(wù)單、起始揀貨復(fù)核臺，并分別規(guī)劃理想的揀貨路線，使得49個任務(wù)單盡快完成出庫，并計算完成出庫需要花費的時間和每個復(fù)核臺利用率。

問題5：在問題4中，有4個復(fù)核臺（FH01，F(xiàn)H03，F(xiàn)H10， FH12）正常工作，請評估增加一個正常工作的復(fù)核臺對出庫時間的影響。

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

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

2 模型假設(shè)

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

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

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

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

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

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

（6）領(lǐng)揀貨車和任務(wù)單與復(fù)核臺對訂單復(fù)核可以同時進行;

3 符號說明

4 問題一的分析和解答

4.1 問題的分析

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

4.2 模型的建立與求解

4.2.1 曼哈頓距離簡介

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

5 問題二的分析與解答

5.1 問題的分析

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

5.2 旅行商問題的背景

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

5.3 模型的建立與求解

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

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

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

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

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

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

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

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

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

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

復(fù)核臺每個訂單復(fù)核和打包花費30秒，任務(wù)單T0001總共包含10個訂單，復(fù)核臺所需時間：

綜上所述，任務(wù)單T0001出庫花費的時間為t：

6 問題三的分析與求解

6.1 問題三的分析

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

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

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

6.2 問題三的建模與求解

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

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

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

揀貨員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在行走過程中需要下架貨物，在任務(wù)單T0002-T0006中任意貨格中需要下架三件及三件以上的貨格共26個，其中26個貨格所包含的商品數(shù)量共78件，三件以下的貨格共93個，其中93個貨格所包含的商品數(shù)量有112件，故可算出揀貨員p下架任務(wù)單T0001所有商品所需時間：;

復(fù)核臺每個訂單復(fù)核和打包花費30秒，任務(wù)單T0002- T006總共包含65個訂單，復(fù)核臺所需時間：

綜上所述，任務(wù)單T0001出庫花費的時間為t：

若一個復(fù)核臺完成該復(fù)核臺所有任務(wù)單的復(fù)核和打包，沒有新任務(wù)前，該復(fù)核臺將處于空閑狀態(tài)。從 0 時刻到 TOTAL_TIME 時刻，若一個復(fù)核臺總空閑時間為 IDLE_TIME，則該復(fù)核臺利用率=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;

復(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 問題四的分析與求解

7.1 問題的分析

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

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

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

7.2 問題四的建模與求解

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

每個揀貨員規(guī)劃理想的揀貨路線如表7-1所示：

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

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

若一個復(fù)核臺完成該復(fù)核臺所有任務(wù)單的復(fù)核和打包，沒有新任務(wù)前，該復(fù)核臺將處于空閑狀態(tài)。從 0 時刻到 TOTAL_TIME 時刻，若一個復(fù)核臺總空閑時間為 IDLE_TIME，則該復(fù)核臺利用率=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問題五的分析與解答

8.1 問題的分析

問題5是在問題4的基礎(chǔ)上進一步拓展，現(xiàn)有4個復(fù)核臺（FH01，F(xiàn)H03，F(xiàn)H10，F(xiàn)H12）正常工作，評估增加一個正常工作的復(fù)核臺對出庫時間的影響。在題中有9個復(fù)核臺未工作，所以再增加一個正常工作的復(fù)核臺有9種可能，故我們要分別對這9個復(fù)核臺分析，用MATLAB編程，分別計算出這增加9個復(fù)核臺其中的一個對出庫時間的影響。

8.2 模型的建立與求解

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

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

9 問題六的建議

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

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

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

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

10.1 模型的評價

10.1.1 模型優(yōu)點

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

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

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

10.1.2 模型缺點

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

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

10.2 模型算法的改進及推廣

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

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

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

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

參考文獻：

[1] 曼哈頓距離_百度百科https：//baike.baidu.com，2020-5-22.

[2] TSP問題_百度百科https：//baike.baidu.com，2020-5-23.

[3] 模擬退火算法_百度百科https：//baike.baidu.com，2020-5-23.

[4] 苗卉，楊韜，旅行商問題（TSP）的改進模擬退火算法[J].《微計算機信息》，2008，23（33）：241-242.

1.西華大學(xué) 理學(xué)院，四川 成都

2.西華大學(xué) 電氣與電子信息學(xué)院，四川 成都