倉(cāng)內(nèi)揀貨路徑優(yōu)化模型概述

韓同卓 許佳樂(lè) 王貞 李俊麗 任杰

摘 要 倉(cāng)庫(kù)的揀貨順序與貨物的擺放順序?qū)Τ鰩?kù)效率有著重要的影響。本文參考查閱大量相關(guān)資料，利用圖論加權(quán)圖表示出貨格與貨格、貨格與復(fù)核臺(tái)兩兩之間的距離關(guān)系，再使用蟻群算法建立揀貨路徑模型，從而求得理想的揀貨路徑。

關(guān)鍵詞 蟻群算法;多目標(biāo)規(guī)劃;圖論;逐層優(yōu)化

1問(wèn)題重述

電商訂單下達(dá)倉(cāng)庫(kù)后，商品下架出庫(kù)，該過(guò)程主要包括定位、組單、揀貨、復(fù)核和打包。該倉(cāng)庫(kù)有13個(gè)復(fù)核臺(tái)，200個(gè)貨架共3000個(gè)貨格，每個(gè)貨格最多擺放一種商品。訂單下達(dá)倉(cāng)庫(kù)后，進(jìn)行定位操作確定商品下架的貨格和所需下架的商品數(shù)量。揀貨員在某個(gè)復(fù)核臺(tái)領(lǐng)取任務(wù)單后，依次訪問(wèn)任務(wù)單中商品所在貨格并下架商品，下架完畢后揀貨員返回到某個(gè)復(fù)核臺(tái)[1]。

基于以上條件，需解決以下問(wèn)題：

在所有復(fù)核臺(tái)正常工作的前提下，給揀貨員P規(guī)劃從復(fù)核臺(tái)FH10領(lǐng)取任務(wù)單T0001 進(jìn)行揀貨的理想揀貨路線[2]

2問(wèn)題二的建模與求解

2.1 數(shù)據(jù)預(yù)處理

任務(wù)單中每個(gè)訂單所在貨格與所有復(fù)核臺(tái)抽象成圖論問(wèn)題，并對(duì)該模型進(jìn)行如下分析：已知賦權(quán)圖，其中為貨格與復(fù)核臺(tái)的集合;

為集合C中各貨格與復(fù)核臺(tái)兩兩連接的集合;每一條邊都存在與之對(duì)應(yīng)的權(quán)值，本題中表示L集合兩元素之間的距離并滿足

若本題中揀貨員P的揀貨路線為，滿足函數(shù)f（L）的值最小，則路徑S就是所求的最優(yōu)路徑。

其中：

2.2 基于蟻群算法的模型

初始化信息， 設(shè)信息素啟發(fā)式因子，表示路徑的相對(duì)重要性;期望值啟發(fā)式因子表示能見(jiàn)度的相對(duì)重要性;信息素?fù)]發(fā)系數(shù);信息素強(qiáng)度，表示螞蟻攜帶信息素的量;每?jī)蓚€(gè)城市之間的距;信息素表示路徑上的信息素強(qiáng)度;啟發(fā)式信息，反映螞蟻對(duì)下一個(gè)城市的能見(jiàn)度，通常取值;城市規(guī)模;螞蟻數(shù)量。

在初始時(shí)刻各條路徑上的信息素兩相等，即[3]。

設(shè)為t時(shí)段位于城市i的螞蟻數(shù)目，為t時(shí)段路徑上的信息素，有：

通過(guò)迭代尋找最佳路徑，螞蟻k不能重復(fù)經(jīng)過(guò)同一個(gè)城市，因此需要建立一個(gè)禁忌表來(lái)記錄螞蟻k走過(guò)的城市，并隨著時(shí)間做動(dòng)態(tài)調(diào)整。每一次迭代后對(duì)信息素進(jìn)行更新。

螞蟻k由城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率：

一次循環(huán)結(jié)束后對(duì)殘留信息進(jìn)行更新處理如下：

每一次循環(huán)結(jié)束后對(duì)所有路徑上信息素進(jìn)行更新：

表示第k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度[4]。

2.3 模型求解

（1）理想揀貨路徑求解

由蟻群算法模型求解流程，編寫MATLAB程序。輸入各個(gè)參數(shù)并對(duì)主要參數(shù)進(jìn)行初始化：時(shí)間，最大循環(huán)次數(shù)為100，螞蟻所攜帶的信息素量，初始時(shí)刻，螞蟻數(shù)量，節(jié)點(diǎn)數(shù)，信息啟發(fā)式因子，期望啟發(fā)式因子，信息素?fù)]發(fā)系數(shù)

根據(jù)題目要求，起始點(diǎn)為復(fù)核臺(tái)FH10，終點(diǎn)為全部13個(gè)復(fù)核臺(tái)之一，在MATLAB程序中考慮由起點(diǎn)坐標(biāo)和所以貨格組成節(jié)點(diǎn)，采用蟻群算法遍歷所有節(jié)點(diǎn)，并在每一次迭代中，計(jì)算終點(diǎn)節(jié)點(diǎn)與每個(gè)復(fù)核臺(tái)的距離，將最短的一個(gè)距離加入到蟻群算法的目標(biāo)函數(shù)之中，并記錄獲得最短距離的復(fù)核臺(tái)[5]。

（2）出庫(kù)花費(fèi)時(shí)間求解

根據(jù)題目知 出庫(kù)時(shí)間=揀貨員行走時(shí)間+商品下架時(shí)間+訂單復(fù)核和打包時(shí)間，即

其中為第個(gè)訂單號(hào)的商品件數(shù)，，根據(jù)（1）中求得的最短揀貨路徑，得出相應(yīng)出費(fèi)時(shí)間為1123.1s。

參考文獻(xiàn)

[1] 卓雪雪，苑紅星，朱蒼璐，等.蟻群遺傳混合算法在求解旅行商問(wèn)題上的應(yīng)用[J].價(jià)值工程，2020，39（2）：188-193.

[2] 張帥，彭玉青，趙鎮(zhèn)，等.螞蟻算法在公交查詢最短路徑求法中的應(yīng)用[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2003（S1）：313-315.

[3] 劉建勝，熊峰，陳景坤，等.基于蟻群算法的雙分區(qū)倉(cāng)庫(kù)揀貨路徑的優(yōu)化[J].高技術(shù)通訊，2017（1）：72-78.

[4] 劉愛(ài)軍，楊育，李斐，等.混沌模擬退火粒子群優(yōu)化算法研究及應(yīng)用[J].浙江大學(xué)學(xué)報(bào)（工學(xué)版），2013（10）：1722-1730.

[5] 樊明，郭藝，贠超，等.基于自適應(yīng)混合算法的智能存取系統(tǒng)動(dòng)態(tài)路徑規(guī)劃[J].系統(tǒng)仿真學(xué)報(bào)，2013（7）：1543-1548.