基于模擬退火蟻群算法的揀貨路徑規劃

胡治鋒，陳冬方，李慶奎，恒慶海

（1.北京信息科技大學，北京 100192；2.北京天地瑪珂電液控制系統有限公司，北京 100020）

倉庫集存儲、輸送、分發、管理于一體，在倉儲物流中是非常重要的一部分。提高倉庫管理效率，一方面可以優化倉位設置，另一方面可以在貨物分批、貨物揀選路徑規劃等方面進行優化。

文獻[1]為提高魚骨型倉庫布局下的訂單揀選效率,基于揀貨路徑距離計算模型和以最小化揀貨路徑總距離為優化目標的揀選路徑優化模型,提出一種混沌模擬退火粒子群優化算法，引入混沌理論使粒子更高效地遍歷搜尋空間，同時結合了模擬退火算法的概率突跳特點使算法在迭代后期仍具有較好的全局尋優能力，為魚骨型倉庫布局下揀選路徑規劃問題提供了新的解決思路。現在很多大中企業建設了自動化倉庫，結合很多優化算法利用機器人進行揀選。文獻[2]研究了基于柵格圖法的移動物流機器人全局路徑規劃方法，針對傳統方法無法有效解決物流機器人一次訪問若干個節點的全局路徑規劃問題，通過柵格圖法構造容易被移動物流機器人理解的倉儲環境，效率得到了顯著提高。文獻[3]介紹了物流機器人路徑規劃研究現狀，近幾年物流機器人的應用已經成為物流企業市場競爭的重要手段，如何得到最優路徑成為研究的關鍵。雖然利用物流機器人進行貨物揀選或搬運有效地提高了倉儲效率，但是根據不同的研究可以看出目前的路徑規劃研究還存在部分問題。文獻[4]針對物流領域降低配送成本、提升配送效率的需求,對物流路徑的優化方法進行了研究，通過數學建模的方式，將物流路徑優化問題轉化為數學研究領域經典的旅行商問題(TSP)，對傳統的粒子群算法加以改進，引入了遺傳算法的交叉操作與遺傳因子。在路徑規劃方面，文獻[5]基于A*算法和改進模擬退火算法提出了一種新型的航跡規劃方法，解決了在復雜約束條件下完成多目標任務的問題。文獻[6]總結了相關路徑規劃算法，同時也對未來路徑規劃算法進行了展望。文獻[7]利用改進遺傳算法對包裝廢棄物的回收車輛進行了路徑規劃，通過與傳統算法比較，改進遺傳算法取得了更好的效果。文獻[8]研究了基于模擬退火蟻群算法的機器人路徑規劃方法，優化變電站巡檢機器人巡檢路線，節省巡檢時間，加入了偏離度參數，但計算量略大。

1 問題提出

從目前的研究來看，國內外的相關研究相對集中于自動化揀選倉庫的庫位和倉庫貨位的優化等方面。但對于很多小型企業，倉庫的運營管理依靠人工進行操作，很多企業貨物揀選順序依賴人的主觀判斷，導致揀貨效率偏低[9]。

該文在已有研究基礎上將揀選路線問題抽象成旅行商售貨（TSP）問題，借鑒機器人路徑規劃的方法，忽略揀選人的可揀選數量以及貨物的體積，應用了一種以路徑最短為目標的優化數學模型，并將兩種算法結合之后的算法進行仿真比較，經分析得出新算法較原先單一的算法取得了更好的效果。

2 貨物揀選路徑規劃的數學建模

在各種倉儲活動中，有各種各樣的貨架，文中以倉庫中的最常規的多層貨架為基礎建立數學模型。

在貨架b中有O個貨位的貨物，可以記作o=(1,2,…,O-1,O)，待揀選的貨物位置可表示為l=1,2,…,i,j,L-1,L。兩個貨位i、j之間的距離可表示為：

基于這些，文中給出了一些參數：

o∈O表示所有待揀選的貨物合集；

i、j∈L表示待揀選貨物的位置；

dij表示兩個貨位之間的距離；

表示b貨架是否先揀選i后揀選j；

表示揀選人員總是能一次揀選完所有位置；

表示從貨架b的i位置揀選貨物。

該模型忽略揀選人員的揀選容量以及貨物的重量體積，將揀選最短距離作為目標函數[10]。目標函數為：

限制條件如下：

目標函數（2）最小化揀選完所有貨物經過的路徑距離，式（3）確保每個貨位只經過一次，式（4）保證所有位置能一次揀選完，式（5）確保只揀選需要的貨物的位置，式（6）（7）聲明每個位置只經過一次，且只有一個前任和后繼，式（8）確保訪問了所有位置，避免出現子行程，式（9）指出決策變量是二進制的[11]。

在分析模型目的和特征的基礎上，對模型進行描述與假設：

①在對一批貨物進行揀選時，僅由一個人完成揀貨。

②揀貨時，揀選完所有貨物時的重量和體積不會超過揀選人的最大容量。

③倉庫中所有的貨架全部是上下結構且水平排列的，倉位之間距離固定。

3 算法描述

模擬退火算法用于優化問題是因為物理中固體物質的退火過程和一般組合優化問題之間存在相似性。雖然它有大范圍全局搜索的能力，但是模擬退火算法沒有有效的正反饋機制，當求解到一定程度后，往往作一些沒有用處的迭代，因此求解精度值偏低[12]。而蟻群算法的原理本質上是一種正反饋機制，但是在初期的迭代過程中產生的信息素十分有限，由于反饋的信息有限，因此需要漫長的過程，求解速度較慢[13]，不能滿足要求。文中將模擬退火算法與蟻群算法混合來解決貨架揀貨路徑規劃問題，采用模擬退火算法快速生成一個解，將信息素分布在這個解上，利用蟻群算法的正反饋機制求精確解，取長補短，期望獲得優化效果和快速求解的雙贏[14]。

混合算法的思路是首先由模擬退火算法快速產生較優的解，較優的路徑留下信息素；然后讓螞蟻按照蟻群算法，利用留下的信息素完成一次遍歷后，采用模擬退火的方法在鄰域內找另外一個解，這個解有可能不是更好的解，這個時候接受準則采用模擬退火的思想[15]，允許目標函數有限范圍內變壞，為簡化計算量并不按概率取舍，若路徑長度差ΔE＜e接受，e為按允許目標函數變壞范圍。

每只螞蟻走過的路徑會留下信息素，與此同時原本路徑的信息素會揮發一部分，所以信息素的更新分為局部信息素更新和全局信息素更新[16]。局部信息素的更新是對于已選的邊對于后來的螞蟻有較小的影響力，從而使得螞蟻對于沒被選中的邊具有較強的影響力，當螞蟻從位置i移動到位置j之后，邊(i,j)上的信息素按下式更新，其中τo為常數，η為可調參數。

當所有螞蟻均完成一次搜索后，對全局最優解進行全局信息素更新。這時只對最優路徑進行信息素加強，因此增大了最優路徑和最差路徑間信息素的差異，從而讓螞蟻更快集中到最優路徑附近，加快全局收斂[17]。

3.1 流程圖

算法流程如圖1 所示。

圖1 算法流程圖

3.2 模擬退火蟻群算法步驟

1）模擬退火算法產生初始解；

2）較優路徑留下信息素；

3）蟻群算法完成一次遍歷，產生一個解；

4）模擬退火算法在蟻群算法產生的解的鄰域內找出一個新解；

5）判斷ΔT是否小于0，若是則蟻群更新信息素，否則回到步驟2）；

6）判斷蟻群算法是否達到最大迭代次數，如果是則輸出最優解，否則回到步驟2），繼續循環。

4 模型仿真分析

4.1 仿真環境

文中利用Matlab R2016b 編寫算法實現程序，并進行算例求解，所有的工作均在一臺計算機上完成。

4.2 模擬退火蟻群算法效果分析

為了驗證融合的模擬退火蟻群算法是否對貨物揀選路徑規劃有效，應用某小型倉庫貨架的某一段時間的某一次揀貨進行優化處理。實驗時選取了16個貨位，設置螞蟻個數m=50，信息素蒸發系數r=0.1，信息素啟發算子α=1，期望啟發算子β=5。退火參數設置初始溫度Tmax=100，終止溫度Tmin=0。

該文僅展示了蟻群算法和模擬退火蟻群算法的路線規劃圖。如圖2 所示，蟻群算法雖然也規劃了行程，但是卻陷入了局部最優解，得到的不是全局最優解，而圖3 所示的模擬退火蟻群算法較好地規劃了揀選貨物時的路徑。因此模擬退火蟻群算法為路徑規劃縮短了行程，節省了時間，提高了工作效率。

圖2 蟻群算法

圖3 模擬退火蟻群算法

經過多次實驗求取平均值，規劃最短路徑時間為Tmin，輸出最優解迭代次數D，最短路徑為Zmin，得出結果如表1 所示。

表1 3種算法比較

4.3 大規模貨架路徑規劃實驗

實際上有的立體貨架規模較大，貨位數量可能達到上百個，故該文以路徑最短為目標，分別用模擬退火算法、蟻群算法以及模擬退火蟻群算法對貨位數為100 的立體貨架進行仿真實驗，分別求解得到的迭代曲線，如圖4 所示。可以看出，模擬退火蟻群算法能夠得出更優的解，新算法較傳統的模擬退火算法，得出最優解需要的時間降低10.7%，較蟻群算法迭代次數減少28.4%，有效提高了人工揀選的效率。

圖4 各算法迭代曲線圖

5 結論

為了改善倉儲活動中人力揀選貨物時沒有路徑規劃的情況，提高倉庫的運行效率。該文分析了立體貨架揀貨時的特點，結合旅行商（TSP）問題中的兩種常用算法——模擬退火算法和蟻群算法對立體貨架的貨物揀選路徑進行規劃。經過仿真實驗，該算法有效解決了模擬退火算法無法有效利用系統中的反饋信息，使得求解到一定精度后往往作一系列無用的迭代，導致無法求精確解以及效率低的問題，同時解決了蟻群算法求解速度慢的問題，有效提高了全局搜索能力并減少了迭代次數，縮短了路徑規劃的時間。

總的來說，該文所研究的只是倉儲活動中單一的揀貨路徑問題，對有關要素進行了適當的簡化處理，而事實上倉儲活動是一系列工作的集合，以后的研究應該著眼于整個倉儲活動。