《倉(cāng)儲(chǔ)物流調(diào)度原理及算法綜述》5100字

倉(cāng)儲(chǔ)物流調(diào)度原理及算法綜述目錄TOC\o"1-2"\h\u5187倉(cāng)儲(chǔ)物流調(diào)度原理及算法綜述 195001.1路徑模型概述 1280141.2任務(wù)調(diào)度原理 2164681.2.1任務(wù)調(diào)度問(wèn)題分類(lèi) 2119681.2.2任務(wù)調(diào)度步驟 4117911.2.3基礎(chǔ)問(wèn)題描述 442531.3任務(wù)調(diào)度算法 518166（1）遺傳算法 519341（2）粒子群算法 716851（3）差分進(jìn)化算法 88722（4）蟻群算法 91.1路徑模型概述隨著導(dǎo)航定位技術(shù)的不斷更新?lián)Q代以及信息通訊技術(shù)的飛速發(fā)展，倉(cāng)儲(chǔ)物流機(jī)器人的導(dǎo)引方式越來(lái)越多樣化。如前所述，目前為止在實(shí)際應(yīng)用環(huán)境中主流的倉(cāng)儲(chǔ)物流機(jī)器人按照引導(dǎo)方式可分為地磁導(dǎo)引，通過(guò)在物流機(jī)器人運(yùn)行路徑上設(shè)置磁體引導(dǎo)機(jī)器人移動(dòng)；導(dǎo)軌導(dǎo)引，通過(guò)在物流機(jī)器人運(yùn)行路徑上設(shè)置導(dǎo)軌引導(dǎo)機(jī)器人移動(dòng)；激光導(dǎo)引，通過(guò)在物流機(jī)器人運(yùn)行路徑上設(shè)置激光制導(dǎo)裝置引導(dǎo)機(jī)器人移動(dòng)；慣性導(dǎo)引，利用慣性引導(dǎo)機(jī)器人移動(dòng)；地圖導(dǎo)引，在物流機(jī)器人管理系統(tǒng)中預(yù)先設(shè)置匹配的地圖引導(dǎo)機(jī)器人移動(dòng)。引導(dǎo)方式還可以從路徑是否固定大體分為固定路徑與非固定路徑。根據(jù)現(xiàn)有的倉(cāng)儲(chǔ)物流機(jī)器人通行規(guī)則和應(yīng)用環(huán)境等剛性需求，智能倉(cāng)儲(chǔ)物流系統(tǒng)中路徑模型主要可分為四種情形[43]:（1）在一個(gè)智能倉(cāng)儲(chǔ)物流系統(tǒng)中，任意時(shí)間段內(nèi)的任意一條通路只能允許一臺(tái)倉(cāng)儲(chǔ)物流機(jī)器人通過(guò)，在這條通路上，機(jī)器人也只能沿著一個(gè)固定的方向前進(jìn)，不能反向行駛，這種路徑模式被稱(chēng)為單通路單向路徑模型。在這種路徑模型下，所有的通路都不存在對(duì)向沖突，是一種較為簡(jiǎn)單的通路模型，但由于通路只能單項(xiàng)同行，前面的機(jī)器人在裝卸貨物時(shí)，后面的機(jī)器人只能等待，而路徑選擇方面也會(huì)受到非常大的限制，運(yùn)輸效率相對(duì)其他路徑模式而言非常低下。（2）單通路雙向模型；顧名思義，這種路徑模型與單通路單向路徑模型相似，同樣對(duì)于任意的通路只讓一臺(tái)倉(cāng)儲(chǔ)物流機(jī)器人通過(guò)，不同的是這種模型允許機(jī)器人反向行駛。這意味著可能出現(xiàn)兩臺(tái)機(jī)器人對(duì)向行駛的情況，這也是此類(lèi)路徑模型下調(diào)度系統(tǒng)需要考慮的問(wèn)題。由于機(jī)器人可以雙向行駛，在路徑選擇上更加自由，較單向通行的模型提升了運(yùn)輸效率，相對(duì)的也使得運(yùn)輸環(huán)境更加復(fù)雜，對(duì)調(diào)度系統(tǒng)的調(diào)度策略要求更高。（3）雙通路單向模型；現(xiàn)實(shí)生活中的道路交通基本使用的都是這種路徑模式，在該路徑模型中，每條道路都可以讓兩臺(tái)機(jī)器人同時(shí)通行，且通行的方向互為反向，如道路左側(cè)只允許向東，右側(cè)只允許向西。這樣的路徑模型較前兩種更加靈活，避免大部分的對(duì)向行駛沖突，運(yùn)輸效率也因此提升不少。需要考慮的是在路口處，由于雙通道且單向允許通行的規(guī)則，組合情況較多，對(duì)調(diào)度能力的要求也更高。（4）雙通路雙向模型；雙通路雙向模型是四種通路模型中最為靈活的一種。靈活性的提升主要原因在于每條通路的兩條路徑都允許兩種方向的機(jī)器人通行，這極大的提升了道路的通行效率，而代價(jià)則是對(duì)調(diào)度能力的要求也大幅度提升。這里的調(diào)度能力涉及到的關(guān)鍵部分是動(dòng)態(tài)調(diào)度部分，在處理多個(gè)執(zhí)行任務(wù)的機(jī)器人在同一通路發(fā)生對(duì)向沖突或是路口處的路徑選擇問(wèn)題上，需要考慮多種情況，這對(duì)采用該路徑模型的調(diào)度系統(tǒng)運(yùn)行效率來(lái)說(shuō)是巨大的考驗(yàn)。本文所使用的模型在通行方向上是雙向的，通路方向上則是單向的。1.2任務(wù)調(diào)度原理1.2.1任務(wù)調(diào)度問(wèn)題分類(lèi)根據(jù)倉(cāng)儲(chǔ)物流機(jī)器人在執(zhí)行任務(wù)期間獲取信息的情況，可將倉(cāng)儲(chǔ)物流機(jī)器人調(diào)度問(wèn)題分為倉(cāng)儲(chǔ)物流機(jī)器人靜態(tài)調(diào)度,倉(cāng)儲(chǔ)物流機(jī)器人動(dòng)態(tài)調(diào)度和倉(cāng)儲(chǔ)物流機(jī)器人資源聯(lián)合調(diào)度:圖1.1三種任務(wù)調(diào)度過(guò)程示意圖（1）倉(cāng)儲(chǔ)物流機(jī)器人靜態(tài)調(diào)度倉(cāng)儲(chǔ)物流機(jī)器人靜態(tài)調(diào)度是指在某一靜態(tài)時(shí)刻，通過(guò)對(duì)倉(cāng)儲(chǔ)物流機(jī)器人指派任務(wù)序列，解決倉(cāng)儲(chǔ)物流機(jī)器人調(diào)度問(wèn)題。靜態(tài)調(diào)度問(wèn)題常見(jiàn)于基礎(chǔ)算法或基本模型的研究，為了體現(xiàn)算法有效性，模型的準(zhǔn)確性，靜態(tài)調(diào)度可以直觀的反應(yīng)算法或模型變化帶來(lái)的性能指標(biāo)變化。其常見(jiàn)的優(yōu)化目標(biāo)包括:任務(wù)時(shí)間最短，倉(cāng)儲(chǔ)物流機(jī)器人利用率最高，倉(cāng)儲(chǔ)物流機(jī)器人數(shù)量最少，拖期延遲最小，物流成本最低等。其常見(jiàn)的約束則包括:倉(cāng)儲(chǔ)物流機(jī)器人容量約束，倉(cāng)儲(chǔ)物流機(jī)器人充電約束，任務(wù)順序約束，路徑方向約束等。（2）倉(cāng)儲(chǔ)物流機(jī)器人動(dòng)態(tài)調(diào)度倉(cāng)儲(chǔ)物流機(jī)器人動(dòng)態(tài)調(diào)度是指在考慮動(dòng)態(tài)擾動(dòng)，如任務(wù)變更、設(shè)備故障、沖突死鎖等問(wèn)題下，通過(guò)對(duì)倉(cāng)儲(chǔ)物流機(jī)器人進(jìn)行實(shí)時(shí)任務(wù)指派，解決倉(cāng)儲(chǔ)物流機(jī)器人調(diào)度問(wèn)題。動(dòng)態(tài)調(diào)度更接近實(shí)際生產(chǎn)中的情形，多適用于解決實(shí)際的問(wèn)題。其常見(jiàn)的優(yōu)化目標(biāo)包括:任務(wù)時(shí)間最短，倉(cāng)儲(chǔ)物流機(jī)器人數(shù)量最少，搬運(yùn)時(shí)間最短，倉(cāng)儲(chǔ)物流機(jī)器人利用率最大，倉(cāng)儲(chǔ)物流機(jī)器人負(fù)荷均衡，倉(cāng)儲(chǔ)物流機(jī)器人最小行走時(shí)間等。其常見(jiàn)約束則包括:倉(cāng)儲(chǔ)物流機(jī)器人容量約束，倉(cāng)儲(chǔ)物流機(jī)器人充電約束，任務(wù)順序約束，路徑方向約束等。（3）倉(cāng)儲(chǔ)物流機(jī)器人資源聯(lián)合調(diào)度倉(cāng)儲(chǔ)物流機(jī)器人資源聯(lián)合調(diào)度多出現(xiàn)于生產(chǎn)制造系統(tǒng)當(dāng)中一般為多目標(biāo)優(yōu)化問(wèn)題，資源聯(lián)合調(diào)度主要是指在倉(cāng)儲(chǔ)物流機(jī)器人調(diào)度過(guò)程中需要考慮其他生產(chǎn)工序的資源產(chǎn)出或使用情況，然后根據(jù)這些情況對(duì)倉(cāng)儲(chǔ)物流機(jī)器人實(shí)施任務(wù)指派，以達(dá)到任務(wù)調(diào)度期望達(dá)到的優(yōu)化目標(biāo)。調(diào)度問(wèn)題中最常見(jiàn)的幾類(lèi)優(yōu)化目標(biāo)包括：完成任務(wù)時(shí)間最短，消耗資源最少，資源利用率最大，懲罰成本最低，倉(cāng)儲(chǔ)物流機(jī)器人負(fù)荷均衡，每個(gè)工件在隊(duì)列中等待時(shí)間最少等。而常見(jiàn)的優(yōu)化目標(biāo)約束則包括:工件隊(duì)列中的緩沖量，工件工序約束，倉(cāng)儲(chǔ)物流機(jī)器人容量約束，倉(cāng)儲(chǔ)物流機(jī)器人充電約束，任務(wù)順序約束，路徑方向約束等。本文研究的倉(cāng)儲(chǔ)物流機(jī)器人任務(wù)調(diào)度問(wèn)題屬于倉(cāng)儲(chǔ)物流機(jī)器人靜態(tài)調(diào)度問(wèn)題，靜態(tài)調(diào)度問(wèn)題可以通過(guò)仿真模擬對(duì)比實(shí)驗(yàn)更準(zhǔn)確的反應(yīng)本文提出算法的有效性。1.2.2任務(wù)調(diào)度步驟倉(cāng)儲(chǔ)物流機(jī)器人任務(wù)調(diào)度系統(tǒng)主要工作步驟可分為三層:生成任務(wù)，分配任務(wù)，完成任務(wù)。其中，分配任務(wù)和完成任務(wù)稱(chēng)為資源分配，在系統(tǒng)生成的任務(wù)全部完成之前，智能倉(cāng)儲(chǔ)物流系統(tǒng)將會(huì)不間斷的進(jìn)行任務(wù)的分配并指導(dǎo)倉(cāng)儲(chǔ)物流機(jī)器人完成任務(wù)，直至系統(tǒng)不再生成新的任務(wù)。（1）生成任務(wù)。本文系統(tǒng)中由于不包含上位機(jī)系統(tǒng)，因此本文中所有實(shí)驗(yàn)的任務(wù)均為人工生成。（2）分配任務(wù)。系統(tǒng)在分配任務(wù)時(shí)需要對(duì)未完成任務(wù)的目標(biāo)地點(diǎn)和空閑的倉(cāng)儲(chǔ)物流機(jī)器人情況進(jìn)行實(shí)時(shí)的監(jiān)測(cè)，在系統(tǒng)生成新的任務(wù)后能夠立即根據(jù)目標(biāo)地點(diǎn)將任務(wù)分配給空閑且狀態(tài)正常的倉(cāng)儲(chǔ)物流機(jī)器人。分配任務(wù)的主要約束就是均衡性，在保證所有任務(wù)完成時(shí)間最短的前提下，實(shí)現(xiàn)任務(wù)的均衡分配。（3）完成任務(wù)。完成任務(wù)的過(guò)程為倉(cāng)儲(chǔ)物流機(jī)器人從起始地點(diǎn)到達(dá)任務(wù)的目的地，即為路徑規(guī)劃過(guò)程。為了高效有序的完成任務(wù)，需要對(duì)倉(cāng)儲(chǔ)物流機(jī)器人進(jìn)行路徑規(guī)劃，而路徑規(guī)劃的合理性也影響著任務(wù)的分配。系統(tǒng)需要根據(jù)任務(wù)的具體分配情況來(lái)對(duì)倉(cāng)儲(chǔ)物流機(jī)器人進(jìn)行路徑規(guī)劃，保證倉(cāng)儲(chǔ)物流機(jī)器人在無(wú)死鎖、無(wú)沖突的情況下完成任務(wù)，并也要根據(jù)任務(wù)的完成情況來(lái)對(duì)任務(wù)的分配進(jìn)行調(diào)整，力求倉(cāng)儲(chǔ)物流機(jī)器人完成任務(wù)時(shí)間最短。1.2.3基礎(chǔ)問(wèn)題描述普通的倉(cāng)儲(chǔ)物流布局由倉(cāng)儲(chǔ)物流機(jī)器人，貨物存放區(qū)，貨物裝卸區(qū)組成，整個(gè)環(huán)境布局圖如圖1.2所示，藍(lán)色膠囊為倉(cāng)儲(chǔ)物流機(jī)器人以及其起始區(qū)域，黃色方塊表示貨架，最下面是完成任務(wù)的卸貨區(qū)，兩個(gè)貨架之間的通道允許兩臺(tái)倉(cāng)儲(chǔ)物流機(jī)器人并排通過(guò)，中間通道可允許兩臺(tái)倉(cāng)儲(chǔ)物流機(jī)器人并排通過(guò)。圖1.2倉(cāng)儲(chǔ)物流布局圖為了方便求解，本文將整個(gè)環(huán)境轉(zhuǎn)化為節(jié)點(diǎn)圖形式，倉(cāng)儲(chǔ)物流機(jī)器人起始節(jié)點(diǎn)為一個(gè)節(jié)點(diǎn)。貨架每個(gè)貨物位置為一個(gè)節(jié)點(diǎn)，貨物裝卸區(qū)為一個(gè)節(jié)點(diǎn)，并且將倉(cāng)儲(chǔ)物流機(jī)器人起始位置設(shè)為1號(hào)節(jié)點(diǎn)，貨物按順序編號(hào)2到n節(jié)點(diǎn)，裝卸區(qū)為最后一個(gè)節(jié)點(diǎn)。為了保證倉(cāng)儲(chǔ)物流機(jī)器人調(diào)度系統(tǒng)的順暢運(yùn)行，本文對(duì)調(diào)度過(guò)程做如下合理假設(shè):（1）倉(cāng)儲(chǔ)物流機(jī)器人裝卸貨時(shí)間忽略不計(jì)；（2）倉(cāng)儲(chǔ)物流機(jī)器人勻速行駛，不考慮轉(zhuǎn)彎或其他情況造成的減速；（3）每臺(tái)倉(cāng)儲(chǔ)物流機(jī)器人可以搬運(yùn)多個(gè)貨物，但不能超出最大載重量；1.3任務(wù)調(diào)度算法智能優(yōu)化算法能解決其他方法難以求解的復(fù)雜組合優(yōu)化問(wèn)題，因而廣泛應(yīng)用于調(diào)度優(yōu)化方面，倉(cāng)儲(chǔ)物流機(jī)器人調(diào)度中用到的智能優(yōu)化方法包括粒子群算法(ParticleSwarmOptimization,PSO)、遺傳算法(GeneticAlgorithm,GA)、差分進(jìn)化算法(DifferentialEvolution,DE)、蟻群算法(AntColonyOptimization,ACO)等。（1）遺傳算法遺傳算法（GeneticAlgorithm，GA）的起源最早可以追溯到20世紀(jì)60年代初期，當(dāng)時(shí)由Holland教授的學(xué)生在其博士論文中首次提出，論文主要探討該算法在博弈中如何應(yīng)用，但這類(lèi)早期研究缺少指導(dǎo)性理論，也沒(méi)有計(jì)算工具作為支撐。直到1975年JohnHolland教授出版《自然系統(tǒng)和人工系統(tǒng)的適配》，于該書(shū)中對(duì)遺傳算法的算法原理，算法的基本方法及步驟進(jìn)行系統(tǒng)闡述，推動(dòng)遺傳算法的發(fā)展。遺傳算法本質(zhì)上是模仿生物的進(jìn)化過(guò)程而得出的計(jì)算模型[44]，達(dá)爾文在生物進(jìn)化論中提出自然選擇，而現(xiàn)代進(jìn)化論中提出基因突變的概念，這兩大概念促成了遺傳算法的誕生，遺傳算法也因此成為一種探索最優(yōu)化問(wèn)題的常用算法。遺傳算法流程如圖1.2所示。圖1.2遺傳算法流程圖通過(guò)流程圖可以看出，遺傳算法在求解問(wèn)題時(shí)先將問(wèn)題的解空間進(jìn)行染色體編碼，使解和求解用的染色體成一一對(duì)應(yīng)關(guān)系，然后隨機(jī)產(chǎn)生初始種群，在對(duì)當(dāng)前種群進(jìn)行交叉、變異操作后，就可以得到新一代的染色體，而后通過(guò)計(jì)算每條染色體的適應(yīng)度值（目標(biāo)函數(shù)的最優(yōu)值）來(lái)對(duì)新一代染色體做出評(píng)價(jià)，選出最優(yōu)質(zhì)的一部分子代成為下一代的父基因。為了防止以獲得的最優(yōu)解因?yàn)樘幵诟复蛑斜簧釛?，我們?huì)將父代基因中最優(yōu)的解和子代中所有基因相比較，取出其中最優(yōu)的一個(gè)基因，讓其必定可以遺傳到子代。這樣就得到歷史最優(yōu)解和子代基因的集合，只要對(duì)這個(gè)集合再進(jìn)行上述操作，重復(fù)足夠的次數(shù)后，就能將解無(wú)限接近全局最優(yōu)解。遺傳算法在解決任務(wù)調(diào)度問(wèn)題上具有一定優(yōu)勢(shì)，特別是對(duì)指派問(wèn)題的求解上，由于指派問(wèn)題的解空間一般是不連續(xù)的解空間，遺傳算法的基因序列可以很好的模擬指派任務(wù)的組別和序列，而通過(guò)遺傳算法與其他算法的結(jié)合，混合后的算法在擴(kuò)展性上有著明顯的優(yōu)勢(shì)，魯棒性也較好。遺傳算法求解任務(wù)調(diào)度問(wèn)題的不足主要在于遺傳算法的兩種算子較為復(fù)雜，交叉操作通過(guò)交換一對(duì)基因中部分基因?qū)崿F(xiàn)，交換后的兩個(gè)解和交換前的兩個(gè)解相比，在目標(biāo)函數(shù)上很難體現(xiàn)其迭代規(guī)律，因此遺傳算法在收斂速度上并不具備很大的優(yōu)勢(shì)。變異操作本質(zhì)是為了增加解的范圍，防止陷入局部最優(yōu)，但在遺傳算法中變異基因受變異概率影響，其作用效果有限?？偠灾z傳算法在求解中，初始參數(shù)對(duì)算法求解情況影響較大，較好的參數(shù)設(shè)定可能提升算法效率，反之亦然。（2）粒子群算法粒子群算法是對(duì)自然界中鳥(niǎo)群覓食的過(guò)程進(jìn)行模擬得出的智能算法，這種算法最早由J．Kennedy和R．C．Eberhart等人提出[45][47]。粒子群算法原理與大部分智能算法類(lèi)似，首先產(chǎn)生初始解集合，然后通過(guò)適應(yīng)度值對(duì)粒子群中粒子的位置、速度進(jìn)行改變，引導(dǎo)粒子向更優(yōu)區(qū)域飛行得到全局最優(yōu)解[46]。其算法流程圖如圖1.3所示。圖1.3粒子群算法流程圖在粒子群算法的迭代過(guò)程中，根據(jù)粒子群體中的不同個(gè)體得出的適應(yīng)度值，驅(qū)使粒子在解空間內(nèi)運(yùn)動(dòng)，所有的粒子都在朝極值位置移動(dòng)，直到得出全局最優(yōu)解。該算法的步驟與參數(shù)設(shè)計(jì)都較為簡(jiǎn)單，算法本身容易實(shí)現(xiàn)，能適用于大部分優(yōu)化求解問(wèn)題，且在求解過(guò)程中算法收斂速度較快。但缺點(diǎn)也很明顯，由于算法全局搜索性不強(qiáng)的特點(diǎn)，容易陷入局部最優(yōu)，在求解離散問(wèn)題時(shí)收斂速度過(guò)慢。（3）差分進(jìn)化算法差分進(jìn)化算法(DifferentialEvolution，DE)由Storn和Price于1995年首次提出[48-49]。主要用于求解實(shí)數(shù)優(yōu)化問(wèn)題。該算法是一類(lèi)基于群體的自適應(yīng)全局優(yōu)化算法，屬于演化算法的一種。該算法通過(guò)群體內(nèi)個(gè)體之間的相互合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能來(lái)指導(dǎo)優(yōu)化搜索的方向。該算法的基本思想是:從一個(gè)隨機(jī)產(chǎn)生的初始種群開(kāi)始，通過(guò)把種群中任意兩個(gè)個(gè)體的向量差與另外的個(gè)體求和，若得到的新個(gè)體適應(yīng)度更優(yōu)，就用新個(gè)體代替舊個(gè)體，否則依然使用舊個(gè)體繼續(xù)執(zhí)行進(jìn)化操作。以此方式不斷迭代，最終趨近全局最優(yōu)。圖1.4展示了差分進(jìn)化算法的流程。圖1.4差分進(jìn)化算法流程圖在基本的差分進(jìn)化算法中，參數(shù)設(shè)置對(duì)算法本身的影響非常大，特別是變異算子中的變異率，該值設(shè)置過(guò)小會(huì)導(dǎo)致種群的多樣性降低，以至于陷入局部最優(yōu)，該值設(shè)置過(guò)大算法就很難收斂。在特定情況下，差分進(jìn)化算法還可能出現(xiàn)算法停滯。（4）蟻群算法蟻群算法作為放生智能算法的一種，在20世紀(jì)90年代被提出。意大利學(xué)者M(jìn)arco．Dorigo等人發(fā)現(xiàn)自然界中蟻群覓食的方式可以作為啟發(fā)式規(guī)則用于算法的求解[50-51]。蟻群覓食主要通過(guò)每一只螞蟻在尋找