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

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