B2C電商解決方案
隨著電子商務的快速發展，其對倉儲業提出了更高的要求。中國物資儲運協會會長姜浩峰指出，電商對倉儲業的需求主要體現在倉儲和配送兩個方面，要求倉儲實現快速響應，準確地入倉、完成貨位管理，快速準確分揀[1]。作為智能倉儲的重要組成部分，物流機器人主要完成倉儲包裹分揀、傳輸等工作。路徑規劃是物流機器人導航過程中的一個重要環節，而物流機器人屬于移動機器人中的一種，移動機器人的路徑規劃是指機器人基于環境信息規劃出一條從起點到終點的無碰、安全的可行路徑，并盡可能地優化路徑[2]。機器人路徑規劃的常用方法有可視圖法、人工勢場法、A*算法、人工智能算法等。智能倉儲環境下的物流機器人路徑規劃方法主要有A*算法[3]、遺傳算法[4]、蟻群算法[5,6]、強化學習算法[7]及算法融合[8,9,10]。其中，文獻[4]分別基于人工魚群算法、遺傳算法、A*算法解決倉儲系統中多機器人小車路徑規劃問題，結果表明，在多機器人倉儲系統路徑規劃中，改進A*算法完成所有任務的時間最短，總的路徑步數也最少。
A*算法是Dijikstra算法的一個擴展，它利用等代價搜索和啟發式搜索來有效地計算最佳優先搜索，使用的時間更少[11]。文獻[12]針對倉儲物流中移動機器人的多任務調度問題，提出復雜對角線距離算法，改進A*算法的啟發函數，實現調度系統中移動機器人的總任務完工時間最短，但規劃之后的路徑仍存在冗余節點。針對A*算法規劃出的移動機器人路徑存在折線多、轉折次數多、累計轉折角度大等問題，研究者們主要提出了平滑路徑的解決方案。例如，文獻[13]在A*算法的初始路徑規劃的基礎上，遍歷路徑中的所有節點，刪除冗余節點，建立平滑A*模型，以極低的計算時間損失有效地降低移動機器人規劃路徑的長度、轉折次數和轉折角度,適用于復雜環境的路徑規劃。而文獻[14]在A*算法的初始路徑的基礎上，通過劃分路徑步長、刪除冗余路徑節點的方法，有效地減小路徑長度和轉折角度，適合多任務點、高障礙率環境下的移動機器人路徑規劃。但智能倉儲環境與一般機器人的工作環境大不相同，倉儲環境中布滿貨架，物流機器人的可行空間有限，障礙物形狀規則，因此，智能倉儲環境下的物流機器人的路徑規劃有別于一般移動機器人。對于智能倉儲物流機器人而言，不僅要求規劃的路徑最短，同時，也要求轉折角度小，轉折次數少，從而便于物流機器人的運行控制和安全作業。文獻[15]在A*算法的基礎上進行改進，在代價函數中加入轉向代價和路徑沖突代價，實現多物流機器人的路徑規劃，但具體的代價值比較難確定。
綜上，針對A*算法規劃的路徑存在轉折點和冗余點過多的問題，現有的研究主要采用刪除冗余節點的路徑平滑方法，較少考慮智能倉儲環境的特殊性。因此，本文首先探索了A*算法中不同啟發式距離函數對智能倉儲環境下路徑規劃的適用性；其次，針對A*算法在路徑規劃中存在較多轉折的問題，提出一種適用于智能倉儲環境路徑規劃的L型路徑趨勢的改進A*算法。
智能倉儲系統一般由揀選工作臺、貨架、物流機器人等組成，對于物流機器人而言，揀選工作臺、貨架、其他物流機器人等都是障礙物。
為便于研究且不失一般性，本文在智能倉儲系統的環境建模時做出以下合理假設：
(1)揀選工作臺、貨柜等障礙物邊界是在實際邊界的基礎上加一個物流機器人安全距離；
(2)把物流機器人看做是一個質點，暫不考慮其高度，且物流機器人可以在任意方向移動；
(3)在路徑規劃過程中，倉儲環境信息不變。
常用的環境建模方法有幾何法、可視圖法和柵格法等。柵格法是將環境分割成大小相等的方格單元的一種建模方法，被廣泛用于描述二維信息，具有簡單有效的特點，因此，本文采用柵格法進行智能倉儲環境的建模，同時以經典物流系統———KIVA系統中的倉儲布局模式為參考，建立了一個51×16的柵格化智能倉儲環境（如圖1所示，在實際應用中，可以根據實際需要設定智能倉儲環境的規模和貨架布局）。其中，紫色矩形為揀選工作臺，黑色矩形為貨架，青色小方格為障礙物（其他物流機器人等），紅色為起始位置，藍色為目標位置（目標貨架），白色為通道。
本文設計基于改進A*算法求解智能倉儲環境下，物流機器人從起始位置到目標位置的無碰撞最優路徑。
A*算法由Dijkstra算法演變而來，是一種啟發式算法。A*算法通過估價函數引導和決定路徑的搜索方向。從起點開始搜索當前位置相鄰的8個周圍節點，由估價函數表示每個節點的價值，選擇價值最低的節點作為下一個擴展節點，循環這一過程直到到達終點停止搜索，從而獲得最終的路徑規劃結果。因為每次搜索都選擇價值最低的節點作為擴展節點，因此，最終獲得的路徑代價是最低的。
A*算法的估價函數f(n)表示如式（1):
其中:f(n)表示從起始位置經過節點n到達終點的估價函數；g(n)表示從起始位置到節點n的實際代價函數；h(n)表示從節點n到終點的估計代價函數。
通常，估計代價函數h(n)可以使用歐幾里得距離或曼哈頓距離作為啟發函數，因為曼哈頓距離只涉及加、減法，和歐式距離相比較，節約算法的運行時間，提高算法效率。相比于一般移動機器人的工作環境，智能倉儲環境中布滿貨架，曼哈頓距離顯然更適用。因此，本文采用曼哈頓距離作為節點間的啟發函數，即
其中：（xd,yd）為目標位置的坐標；（xn,yn）是節點n的坐標。
A*算法在搜索路徑過程中，需要不斷更新兩個列表，一個是開啟列表，另一個是關閉列表。開啟列表存儲所有周圍的節點。A*算法從開啟列表中選擇估價值最小的節點作為下一個擴展節點。關閉列表存儲所有經過的節點和環境中的障礙物所在節點。
通過A*算法計算，得到智能倉儲物流機器人的初始路徑規劃。
傳統A*算法計算的路徑類似“鋸齒形”路徑，存在轉折過多，轉彎過多的問題。智能倉儲環境不同于一般的移動機器人所處的環境，智能倉儲環境中障礙物主要是貨架、揀選工作臺、隨機障礙物等，這些障礙物都是規則、有序且相對固定，輪廓近似矩形。與此同時，智能倉儲環境中的通道規則且狹窄，可行空間相對有限，因此，“鋸齒形”路徑主要出現在揀選工作臺附近的局部區域。從起始位置S到目標位置T形成的最終路徑可以近似看做是L趨勢，當各部分路徑都和該L趨勢一致時，則該路徑的轉彎節點最少。
本文根據起始位置S與目標位置T的幾何關系，構造4種L型路徑趨勢的標識，分別為L1（實線）、L2（實線）、L3（實線）和L4（實線）。
路徑趨勢標識的構建方法。以L1型路徑趨勢標識為例，起始位置S在目標位置T的左下方，延長S、T所在直線構成直角（D），構建L1型路徑趨勢標識。同樣地，S在T左上方時，構建L2型路徑趨勢標識；S在T右上方時，構建L3型路徑趨勢標識；S在T右下方時，構建L4型路徑趨勢標識。
路徑趨勢標識的使用方法。在A*算法規劃出初始路徑之后，依據“盡可能使局部路徑與S、T構成的路徑趨勢一致”的原則，通過路徑趨勢標識進行優化。具體規則如下：局部路徑中，鄰近的3個節點（k-1、k、k+1）構成L型鏈路時，判斷其與當前L型路徑趨勢標識是否匹配（依據：局部鏈路的L型與S、T構成的路徑趨勢標識L剛好組成一個回路）；如果匹配，判斷局部鏈路中間節點k的對角節點D（組成回路的對角）是否為障礙物，如果不是障礙物，則將對角節點D替換該節點k。
以L1型路徑趨勢標識的優化為例。當前，S與T構成L1型路徑趨勢，初始路徑中局部路徑k-1、k、k+1三個節點構成的鏈路（綠色點劃線所示），呈現出L型形狀，（從S、k-1、k、k+1、T路徑出現了鋸齒形狀，存在3個轉彎），因此需要進行優化。現判斷D節點是否為障礙物（揀選工作臺、貨架、其他障礙物等），如果是，則不處理；如果否，則節點k替換成節點D。此時，鏈路變成S、k-1、D、k+1、T，該鏈路中，只有1個轉彎，從而，減少了轉彎的節點，使路徑變得平滑。其他L型路徑趨勢標識的優化方法以此類推。
基于A*算法的智能倉儲物流機器人的L型路徑優化流程如圖3。
本文通過MATLAB2015軟件（Math Works公司）對所提出的基于改進A*算法的智能倉儲物流機器人的路徑規劃進行仿真驗證。首先設置智能倉儲環境，包括倉儲邊界、貨架、揀選工作臺、物流機器人初始位置和目標位置、隨機障礙物位置等信息。其中，起始位置S的柵格坐標為（5,6），目標位置的柵格坐標為（25,11）。其次，設計A*算法求解從起始位置到目標位置的初始規劃路徑。
為探索曼哈頓距離與文獻[12]提出的復雜對角線距離對智能倉儲環境路徑規劃的適應性，本文分別求解基于以上兩種距離公式的A*算法初始路徑。結果如圖4～5所示。
圖中灰色表示已訪問的柵格，灰白色代表在訪問列表中。圖4中點實線表示基于文獻[12]提出的復雜對角線距離公式獲得的A*算法初始路徑，圖5中點實線表示基于曼哈頓距離公式獲得的A*算法初始路徑。觀察發現，兩種距離公式最終規劃出的路徑一致，均成功避免了與貨架等障礙物相碰，并且找到了從起始位置到目標位置的規劃路徑。
表1的數據說明，基于文獻[12]中的復雜對角線距離公式獲得的A*算法初始路徑與基于曼哈頓距離獲得的A*算法初始路徑總長度一致，都是25單位長度，但前者算法運行時間為7.46 s，后者運行時間為7.23 s。這個結果表明，對于智能倉儲環境，曼哈頓距離在算法運行時間上更有優勢。因此，本文在改進A*算法時采用曼哈頓距離公式。
進一步觀察以上兩條初始路徑，可以發現，A*算法求解的初始路徑中有5個轉折，路徑不夠平滑。
在實驗中，分別用平滑A*算法和本文提出的L型路徑趨勢標識對A*算法獲得的初始路徑進行優化。首先參考文獻[13]的平滑A*算法，在A*算法初始規劃路徑的基礎上，遍歷所有節點，若某一節點的前一節點與后一節點連線未經過障礙物，則剔除本中間節點，從而減少轉折節點和轉彎過多的問題。結果如圖6所示。
其中o-實線表示采用平滑A*算法獲得的從起始位置S到目標貨架T的優化路徑。
其次，采用本文構造的L型路徑趨勢標識對A*算法初始路徑中的局部路徑進行優化，結果如圖7所示。
其中*線表示采用L型路徑趨勢標識優化后的從起始位置S到目標貨架T的優化路徑。
A*算法改進前后智能倉儲物流機器人的路徑規劃結果比較見表2。
與A*算法規劃的初始路徑比較可以發現，平滑A*算法中，路徑長度較初始路徑減少8.7%；轉折節點減少2個，減少率為40%；累計轉彎角度減少225°，減少率為50%，即在一定程度上達到了減少路徑總長度、轉折節點數和累計轉彎角度的效果。與A*算法初始路徑比較，L型路徑趨勢改進A*算法，其路徑總長度沒有減少，但轉折節點減少3個，減少率為60%；累計轉彎角度減少270°，減少率為60%。L型路徑趨勢改進A*算法減少轉彎節點率較平滑A*算法高20%,L型路徑趨勢改進A*算法減少轉彎角度率較平滑A*算法高10%，對于布滿貨架、可行空間有限的智能倉儲系統環境而言，相較于路徑總長度的減少，對減少轉彎次數和轉彎角度的需求更迫切，一方面便于控制物流機器人的轉向，另一方面，更有利于作業安全。與此同時，L型路徑趨勢改進A*算法的運行時間較平滑A*算法運行時間短，在大規模智能倉儲環境的路徑規劃中，算法運行時間短顯然更有優勢。
本文建立了柵格化的智能倉儲環境。采用A*算法求解智能倉儲物流機器人的路徑規劃，獲得了一條從起始位置到終點位置的無碰撞安全路徑。仿真實驗結果表明，與文獻[12]提出的復雜對角線距離比較，曼哈頓距離更適用于智能倉儲環境的路徑規劃。針對A*算法求解最優路徑時存在轉折點過多和轉彎角度過大的問題，提出了一種基于起始位置與目標位置構建的L型路徑趨勢方法對A*算法規劃的初始路徑進行局部優化。仿真實驗表明，L型路徑趨勢局部優化方法能夠以微小的算法運行時間為代價有效地減少A*算法規劃路徑中的轉折次數和累計轉彎角度，使物流機器人的路徑趨向于總體路徑方向，路徑更加平滑，有效提高倉儲的作業安全和效率。本文研究的是智能倉儲環境中物流機器人的全局路徑規劃問題，將來，可以在此基礎上考慮動態障礙物及避碰策略，更加有效地對物流機器人進行協同調度和路徑規劃。
上一篇： 關于云計算技術物聯網倉儲管理系統設計
下一篇： 需求信息更新時單一倉儲中心動態選擇策略
134-7270-5338
上海市嘉定區南翔嘉美路428號（靠近滬宜公路）
