訂單揀選優(yōu)化之訂單揀選概述

項目一人工智能算法在智慧倉內(nèi)的應(yīng)用《物流人工智能技術(shù)》任務(wù)五訂單揀選優(yōu)化之訂單揀選概述2目錄/CONTENTS301訂單分批02揀選路徑優(yōu)化03揀選任務(wù)分配4【知識目標(biāo)】1.了解機器人路徑規(guī)劃的幾種常見算法及各自優(yōu)缺點；2.了解不同訂單分配和算法下的揀貨路徑優(yōu)化組合。【情感目標(biāo)】1.具有工匠精神、服務(wù)意識、環(huán)保意識、質(zhì)量意識、安全意識；2.培養(yǎng)獨立獲取信息和自學(xué)能力；3.堅定擁護中國共產(chǎn)黨領(lǐng)導(dǎo)和我國社會主義制度?！窘虒W(xué)目標(biāo)】1.訂單分批問題解決訂單分批問題的啟發(fā)式算法主要有種子法和節(jié)約法兩種思路。節(jié)約法是由ClarkeandWright提出的，它是指將短路徑的訂單合并到長路徑的訂單中，從而達到揀選路徑最短的優(yōu)化方法。節(jié)約法在確定所有訂單的分批揀選次數(shù)n后，選擇出n個特殊的訂單作為種子，并將它們分配到不同的批次中，然后再插入剩余的訂單，從而達到高速有效分批的方法。種子法一、訂單分批選擇種子訂單可以從以下幾方面考慮：隨機產(chǎn)生的訂單1具有最長揀選路線的訂單3包含有特殊位置貨物的訂單5涉及了最多的存儲貨位的訂單2包含有特殊位置貨物的訂單4包含的貨物位置含有最大的通道跨度的訂單6一、訂單分批2.訂單分批策略根據(jù)不同行業(yè)、企業(yè)訂單到達具有的不同特點，訂單分批主要有以下幾種不同的方式：合計量分批、固定訂單量分批、時窗分批、智慧型分批。時窗分批智慧型分批是指開啟一定時間長度的窗口，將該時間段內(nèi)所到達的訂單匯總成一批，然后，待該時間窗口結(jié)束后立即開始揀貨作業(yè)。訂單經(jīng)過匯集后，經(jīng)過較復(fù)雜的電腦計算程式，將揀取路線相近的訂單集中處理，可大量縮短揀選行走距離。一、訂單分批3.訂單分批模型與算法對訂單的分批，往往以揀選距離最短或揀選時間最短來建立數(shù)學(xué)模型，目的都是提高揀選效率。研究人員分別釆用不同的算法求解訂單分批模型主要有：聚類算法訂單包絡(luò)算法遺傳算法模擬退火算法蟻群算法一、訂單分批1.揀選路徑規(guī)劃問題揀選路徑規(guī)劃問題是指對每個訂單，如何合理確定揀貨員或揀貨機器人對貨物揀選的順序，以實現(xiàn)揀選時行走距離短或者損耗的時間最少。揀選貨物的時間是由行走時間、取貨時間和等待時間組成的。二、揀選路徑優(yōu)化2.路徑策略訂單揀選的順序與路徑，與倉庫的貨架布局及揀選設(shè)施有關(guān)。在揀選的過程中，有S型揀選策略、返回型策略、中點型策略、最大間隔策略、組合策略等。不同的路徑策略，針對不同的倉庫布局和訂單的到達特性、訂單數(shù)量的多少不同，其優(yōu)化的效果也不同。二、揀選路徑優(yōu)化3.路徑優(yōu)化的模型與算法在對路徑優(yōu)化的過程中，大多以揀選路徑最短為目標(biāo)，或者以揀選時間最短為目標(biāo)建立數(shù)學(xué)模型。在以往的研究中，更多的研究選擇，是用遺傳算法及改進的遺傳算，來對路徑優(yōu)化問題進行求解。遺傳算法具有很高的并行性和魯棒性，可以同時搜索解空間的多個區(qū)域搜索信息，沿多種路線進行平行搜索，從而降低算法陷入局部最優(yōu)解的可能性，具有良好的可操作性。二、揀選路徑優(yōu)化4.Kiva機器人路徑規(guī)劃算法分析與選擇（1）機器人路徑規(guī)劃算法分析根據(jù)系統(tǒng)環(huán)境的不同，智能機器人的路徑有不同的方案，每一種方案又有多種算法進行解決，目前常用的有：傳統(tǒng)的A*算法遺傳算法蟻群算法粒子群算法二、揀選路徑優(yōu)化（2）機器人路徑規(guī)劃算法比較與選擇1）路徑規(guī)劃問題描述對單個Kiva機器人而言，環(huán)境中障礙物包含貨架和其它機器人，在考慮它的規(guī)劃方案時，貨架的位置信息是已知的，適合應(yīng)用全局規(guī)劃方案；其它機器人的位置是實時變化的，其位置信息需要不斷更新，適合應(yīng)用局部規(guī)劃方案。因此，針對這種障礙物位置信息既有時變乂有不變的環(huán)境情況，綜合考慮兩種方案的優(yōu)缺點，選擇混合路徑規(guī)劃方案在保障機器人與障礙物（包括固定障礙物和其他移動機器人）安全距離的前提下，找出到達目標(biāo)點的最短路線可通過數(shù)學(xué)模型描述為：在式3.1成立的條件下，找出式3.2中dr的最小值其中（xr，k,yr，k）為第r個機器人k時刻的坐標(biāo)，（xri,yr）為第ⅰ個機器人或障礙物k時刻的坐標(biāo)，dm為最小安全距離，dr為第r個機器人到達目標(biāo)點行走的距離。（式3.1）（式3.2）二、揀選路徑優(yōu)化2）算法比較與選擇算法優(yōu)點缺點傳統(tǒng)A*算法計算最短路徑最快的一種方法，具有高時效性。空間需求太大，它的共空間增長是指數(shù)級別的。人工勢場法躲避障礙的能力強，路徑軌跡相對比較平滑，有利于平穩(wěn)運行。容易陷入局部最優(yōu)解，出現(xiàn)卡死狀態(tài)，甚至不能抵達目的地。遺傳算法全局搜索性能好，能有效的避免陷入局部最優(yōu)的情況，容錯能力相對較好。算法對群體的反復(fù)選擇等遺傳操作較多，進化次數(shù)較多，容易導(dǎo)致進化效果不明顯。蟻群算法是一種基于種群的進化算法，具有較好的搜索能力，易于并行實現(xiàn)。計算量較大，求解所需時間較長，算法的收斂較慢，容易陷入局部最優(yōu)。粒子群算法逼近最優(yōu)解的速度較快，其個體可以充分利用自身經(jīng)驗和群體經(jīng)驗進行自我調(diào)整。局部搜索能力不強，容易產(chǎn)生過早收斂現(xiàn)象。表3-8多種算法的優(yōu)缺點對比二、揀選路徑優(yōu)化1.任務(wù)分配策略目前，電商的配送中心廣泛采用分區(qū)揀選的模式，而對于不同的設(shè)備，通常也是按照分區(qū)對任務(wù)進行分配。在分區(qū)揀貨的模式下，有串行揀選策略和并行揀選策略。對于一個批次其完成時間較長。減少揀選的時間，因此在實際應(yīng)用中大多選用并行的方式。串行揀選并行揀選三、揀選任務(wù)分配2.任務(wù)分配模型與算法Jane提出了幾種不同的智能啟發(fā)式算法，平衡多個揀貨員之間的工作量并且調(diào)整揀貨區(qū)的大小。Gregor設(shè)計了基于相似系數(shù)的動態(tài)聚類算法，根據(jù)訂單的相似度進行分區(qū)分配任務(wù)。雷斌等按照訂單品項在各分區(qū)的分布情況，建立了人員動態(tài)分配模型，并運用啟發(fā)式算法對模型進行求解。德國馬格德堡大學(xué)的Henn先后研究了迭代局部搜索算法和基于屬性的爬山算法求解任務(wù)分配問題的效果，并成功將二者集成，形成混合算法。三、揀選任務(wù)分配17訂單揀選優(yōu)化之訂單揀選概述訂單分批1.訂單分批問題2.訂單分批策略3.訂單分批模型與算法揀選路徑優(yōu)化1.揀選路徑規(guī)劃問題2.路徑策略3.路徑優(yōu)化的模型與算法4.Kiva機器人路徑規(guī)劃算法分析與選擇揀選任務(wù)分配1.任務(wù)分配策略2.任務(wù)分配模型與算法【課后小結(jié)】18問題：1.（判斷）訂單分批，是對客戶下達的多個訂單進行匯總、分類，然后再將訂單按照一定的分類