藺一帥 , 李青山 , 陸鵬浩 , 孫雨楠 , 王 亮 , 王穎芝

1(西安電子科技大學 計算機科學與技術(shù)學院,陜西 西安 710071)

2(蘇州明逸智庫信息技術(shù)有限公司,江蘇 昆山 215300)

智能倉儲系統(tǒng)是由立體貨架、有軌巷道堆垛機、出入庫輸送系統(tǒng)、信息識別系統(tǒng)、自動控制系統(tǒng)、計算機監(jiān)控系統(tǒng)、計算機管理系統(tǒng)等其他輔助設備組成的智能化系統(tǒng).智能倉儲的高度信息化、自動化,使得控制優(yōu)化算法成為了智能倉儲的靈魂所在[1].目前,智能倉儲優(yōu)化算法主要集中在貨架優(yōu)化和AGV 車路徑規(guī)劃這兩部分,且關于這兩部分的研究都是各自獨立的.貨架優(yōu)化是針對貨物與貨架兩者的關系,對貨物擺放位置的優(yōu)化,其重點關注于總體出貨代價、貨架穩(wěn)定性等因素[2].而路徑優(yōu)化主要針對于自動化運載車輛的路徑規(guī)劃的優(yōu)化,要關注的重點在于完成任務的時間開銷最小、避免車輛之間發(fā)生碰撞等.然而,基于對實際倉儲的運維數(shù)據(jù)分析,我們發(fā)現(xiàn)傳統(tǒng)的獨立的智能倉儲優(yōu)化策略,即研究貨架優(yōu)化時只專注于貨架擺放最優(yōu)結(jié)果,研究路徑規(guī)劃時只關注于算法的執(zhí)行效率和優(yōu)化成果,完全忽視了貨架規(guī)劃和路徑規(guī)劃兩者間的耦合關系,嚴重影響了智能倉儲的出貨效率最大化[3-5].因此,本文提出了基于遺傳算法的貨位規(guī)劃與AGV 路徑規(guī)劃協(xié)同優(yōu)化算法(以下簡稱貨位路徑協(xié)同優(yōu)化算法).該協(xié)同優(yōu)化算法改進了經(jīng)典遺傳算法,其創(chuàng)新點在于將貨位規(guī)劃和路徑規(guī)劃協(xié)同考慮后,構(gòu)造的適應性函數(shù)能夠?qū)⑾嗨贫雀叩呢浖芊稚⒎胖?將高頻出庫貨物放置在易于出貨的位置上,從而實現(xiàn)在大量同時出庫任務到來時AGV 調(diào)度不堵塞,從整體上提高倉庫出貨效率.

本文主要創(chuàng)新貢獻如下:

(1) 本文通過對智能倉儲環(huán)節(jié)中各部分的關系進行耦合分析,進而提出貨位和AGV 路徑協(xié)同優(yōu)化的數(shù)學模型.該模型與傳統(tǒng)智能倉儲優(yōu)化算法的區(qū)別在于:將貨架優(yōu)化和路徑規(guī)劃歸為一個整體,并用數(shù)學公式表達兩者間的關系;

(2) 提出了智能倉儲協(xié)同優(yōu)化的求解算法,其中包括有貨品相似度求解算法、改進的路徑規(guī)劃算法.在以上兩種算法的基礎上,使用改進適應性函數(shù)的遺傳算法,實現(xiàn)了貨位路徑協(xié)同優(yōu)化.同時,通過實驗驗證了該協(xié)同優(yōu)化算法在不同場景下的表現(xiàn)情況.

1 國內(nèi)外研究現(xiàn)狀

本文研究的智能倉儲貨位與路徑協(xié)同優(yōu)化算法相關的公開文獻資料很少,大多都是以貨架優(yōu)化和AGV 路徑規(guī)劃獨立研究為主.本文將分別就這兩類問題分析國內(nèi)外研究現(xiàn)狀以及存在的相關問題.除此之外,對本文提出的協(xié)同優(yōu)化算法的協(xié)同優(yōu)化思想起源以及應用實例給予簡要介紹.

1.1 智能倉儲貨架優(yōu)化研究現(xiàn)狀

貨架(貨位)優(yōu)化研究是智能倉儲領域的重要研究方向.貨架優(yōu)化就是計算貨物擺放位置的算法,貨架優(yōu)化的目標是在保證倉儲環(huán)境穩(wěn)定的條件下提高倉庫的出入庫效率,同時優(yōu)化貨架空間,使倉儲放入貨品的數(shù)量最大化.

由Cai 等人[6]針對倉儲策略部分提出了基于存儲的出入庫頻率和負載平衡的絕對的主通道存儲策略與平均和最大值相關的控制策略,提升了庫位使用率.Wang 等人[7]對傳統(tǒng)的遺傳算法進行改進,研究出基于遺傳算法的庫位分配方法.該方法以貨品位置坐標為基因,使用權(quán)重和的方式來統(tǒng)一多目標函數(shù)為一個函數(shù),使其成為適應性函數(shù).通過基因遺傳運算,得出優(yōu)化后的庫位擺放方案.劉峰等人[8]使用模糊化這一理念形成模糊算法,對貨品的出貨率、重量進行模糊化.但該優(yōu)化算法每次只計算單個貨品的位置擺放,對于一次性全部入庫的運算會變得十分復雜.同時,模糊化方式存在使用精確度來換取計算時間的弊端.楊瑋等人[9]基于混合粒子群算法,采用多色集合概念對貨位進行分區(qū),對不同對象使用相同形式的數(shù)學模型進行仿真.該算法的優(yōu)點在于沒有交叉變異,需要調(diào)整的參數(shù)較少.其缺點在于因缺乏動態(tài)調(diào)節(jié),存在陷入局部最優(yōu)的可能.

Tinelli 等人[10]使用多標準工具來優(yōu)化智能倉儲貨位分配,應用層次分析法,以目標按照一定方式分成不同的標準,標準間相互組合形成不同的解,即對不同的目標函數(shù)進行求解并組合.Arnaout 等人[11]用蠕蟲優(yōu)化來解決多層倉庫庫位布局問題.蠕蟲類似于群體智能算法,使用連接圖的方式來表現(xiàn),通過迭代、限界來搜尋最優(yōu)解.在Arnaout 等人描繪的特定倉儲算例中,與基本遺傳算法相比,基于蠕蟲算法的倉儲布局算法計算時間較短.

基于對上述國內(nèi)外研究現(xiàn)狀的分析,可以看出,庫位優(yōu)化問題是一個NP 難問題,目標函數(shù)較多,目前解決方法主要是來自于自啟發(fā)算法的各類變種算法,這也是解決NP 難問題的常規(guī)方式.但是,多數(shù)方法的優(yōu)化思路都集中在根據(jù)物品和貨架的關系來進行貨位優(yōu)化,忽略了出貨路徑對貨位擺放優(yōu)化的影響.

1.2 自動導引車路徑規(guī)劃研究現(xiàn)狀

AGV(automated guided vehicle,自動導引車)是智能倉儲的重要組成部分,在倉儲系統(tǒng)中,主要扮演智能物流搬運的角色,配合任務分配和調(diào)度系統(tǒng)實現(xiàn)物品的智能配送、周轉(zhuǎn)、出入庫等操作[12].現(xiàn)階段,針對AGV 的優(yōu)化算法主要分為兩個方面:一方面是對路徑進行優(yōu)化,另一方面是針對AGV 的任務調(diào)度進行優(yōu)化.雖然側(cè)重點不同,但其目標都在于提高AGV 的使用效率.

Zhang 等人[13]在A*算法的基礎上加入AGV 轉(zhuǎn)彎次數(shù)影響因素,通過減少AGV 的轉(zhuǎn)彎次數(shù),降低AGV 轉(zhuǎn)彎的時間消耗,有效地提高了AGV 的使用效率.但算法忽略了AGV 的沖突問題.姜康等人[14]研究了改進的遺傳算法,在基因片段里,以三元為一組,整個任務序列為全部任務.對此基因段進行交叉、變異,通過適應度函數(shù)進行篩選.由于該算法每次都會計算全部的任務序列,頻繁的新任務添加會大大增加此算法的計算次數(shù).同時,該方法也忽略了小車的碰撞以及充電對調(diào)度帶來的影響.張素云等人[15]在解決AGV 沖突方面展開研究,提出了通過加減速控制AGV 的碰撞避免方法.該方法先預估哪些節(jié)點會產(chǎn)生碰撞,在該節(jié)點部分使用加減速控制,以此來避免沖撞.在實際運行中,該算法需進一步考慮AGV 承重、重心高低等因素對加減速幅度的影響.

Bilge 等人[16]使用時間窗法解決行駛沖突,對所有AGV 的行動進行預估,可以預知所有車輛在不同時段所占用的不同路段,以此避免AGV 車輛的碰撞.Mousavi 等人[17]采用混合遺傳算法和粒子群算法優(yōu)化多目標AGV調(diào)度.該算法在初期選用粒子群算法,在粒子進行移動后,更新粒子位置找到最佳粒子位置,再使用遺傳算法對粒子的位置進行再優(yōu)化,而后再回到粒子群算法中進行下一次粒子移動計算,直到收斂.此算法在收斂速度方面與遺傳算法相近,最終結(jié)果優(yōu)于單獨使用遺傳算法或粒子群算法.其缺點在于混合算法計算耗時較長.

上述國內(nèi)外研究現(xiàn)狀為本文的研究提供了很多值得借鑒的思路,比如遺傳算法中的編碼方式、A*算法中關于AGV 轉(zhuǎn)彎會影響效率的提示、時間窗法通過靜態(tài)規(guī)劃路徑來避免沖突等.同時,分析當前國內(nèi)外的研究現(xiàn)狀不難發(fā)現(xiàn):現(xiàn)有AGV 的優(yōu)化算法中,對沖突問題的時間代價沒有充分考慮.更重要的是,缺少將貨架優(yōu)化和路徑規(guī)劃聯(lián)系起來進行統(tǒng)一優(yōu)化的方法.這種忽略貨架和路徑的內(nèi)在聯(lián)系、兩者分開優(yōu)化、僅將兩部分各自的最優(yōu)解的串行組合的方式,很難找到一個全局最優(yōu)解.

1.3 協(xié)同進化算法研究現(xiàn)狀

協(xié)同進化算法框架的形成較早,是Hillis 從自然界捕食、競爭以及共生關系得到啟發(fā),于1990 年將這種協(xié)同的思想引入到進化算法中[18].Potter 將協(xié)同進化算法進行了進一步的研究,提出了合作式協(xié)同進化算法[19].此算法主要提出了一個算法框架,將完整的系統(tǒng)根據(jù)一定規(guī)則分為子系統(tǒng),以“分而治之”的思想對子系統(tǒng)分別求解,將求解結(jié)果與其他子系統(tǒng)互動,達到協(xié)同進化的目的.

目前,協(xié)同算法在國內(nèi)主要運用于空間布置,如Wang 等人[20]、Huo 等人[21]在衛(wèi)星艙的布局問題上使用協(xié)同進化的思想,配合相對應的算法,較好地解決了空間布局問題.Wang 等人在協(xié)同進化的基礎上加入散射搜索法,更加貼合衛(wèi)星艙的特點.而Huo 等人則通過使用協(xié)同進化遺傳算法,取得較好的布局優(yōu)化結(jié)果.梁靜等人[22]則通過協(xié)同進化的思想,提出使用粒子群算法來解決高維度問題.

比起具體的解決方案,協(xié)同進化更多的是一種解決問題的思想.上述的研究者在此思想上,結(jié)合適合的算法用來解決不同種類的問題,都取得一定成果.因此,結(jié)合智能倉儲的特點,我們研究團隊嘗試將該思想引入倉儲領域,運用協(xié)同進化的思想來對貨架優(yōu)化和路徑規(guī)劃進行集成研究[23].

綜合分析上述國內(nèi)外研究現(xiàn)狀,可以看出:關于貨架優(yōu)化和AGV 路徑規(guī)劃的相關解決方案和算法的獨立研究都有重大進展,而對兩問題的集成研究極少.大多數(shù)在進行貨架優(yōu)化時根本不考慮路徑問題,忽略路徑對最終倉儲出庫效率的影響.舉個簡單例子:最優(yōu)的貨架優(yōu)化可能會帶來出貨時的AGV 擁堵,給AGV 路徑規(guī)劃帶來嚴重問題,從而影響到倉儲出庫效率.針對這種現(xiàn)象,本文將對AGV 路徑和貨架優(yōu)化進行集成研究,使用協(xié)同優(yōu)化的思想將貨物、貨架、路徑三者結(jié)合起來,使得在進行貨架優(yōu)化時,除了考慮到貨物,也將路徑納入到影響因素中,從而提高倉儲的整體效率,進一步降低倉儲成本.

2 貨位規(guī)劃與AGV 路徑規(guī)劃協(xié)同優(yōu)化算法

現(xiàn)有智能倉儲的主要優(yōu)化方法為采用傳統(tǒng)貨架優(yōu)化算法進行貨位計算后,執(zhí)行路徑規(guī)劃算法.這種優(yōu)化方法容易導致一定區(qū)域內(nèi)的車輛堵塞問題,大大降低了出貨效率.針對這個問題,本文基于協(xié)同進化思想的啟發(fā),分析貨物、貨架、AGV 車路徑規(guī)劃的相互影響關系,提出了貨架規(guī)劃和路徑規(guī)劃協(xié)同進化算法,實現(xiàn)貨架規(guī)劃和AGV 路徑規(guī)劃協(xié)同優(yōu)化.該協(xié)同優(yōu)化算法基于經(jīng)典遺傳算法上進行改進,其創(chuàng)新點在于將貨位規(guī)劃和路徑規(guī)劃協(xié)同考慮后,構(gòu)造的適應性函數(shù)能夠?qū)⑾嗨贫雀叩呢浖芊稚⒎胖?且高頻出庫貨物放置在易于出貨的位置上,從而實現(xiàn)在大量同時出庫任務到來時,AGV 調(diào)度不堵塞,從整體上提高倉庫出貨效率.

具體來說,本文提出的貨位規(guī)劃與AGV 路徑協(xié)同優(yōu)化算法(簡稱協(xié)同優(yōu)化算法)旨在通過設計合理的貨位擺放,為出貨路徑的規(guī)劃提供輔助,使用自啟發(fā)算法產(chǎn)生一個考慮貨位擺放因素的優(yōu)化運輸方案.其詳細方案如下:協(xié)同優(yōu)化算法首先根據(jù)歷史出貨批次對零散貨物進行編碼處理;利用貨物批次產(chǎn)生的編碼計算“貨品間”相似度,并因此對零散貨物進行組合,生成貨品組;每一個貨品組為待入庫狀態(tài),視為一個貨架單元,與貨位一一對應.其次,在貨品組入庫之前,先為每一個貨位計算相應的出貨路徑,記錄并保存貨架位置對應的出貨路徑.基于上述計算結(jié)果,算法進入?yún)f(xié)同優(yōu)化模塊,即貨品組放入貨位的順序是自由的,這種隨機放置的方案構(gòu)成協(xié)同優(yōu)化過程的貨位因素;而貨品組不同的擺放方案會在出貨任務到來時生成不同的運輸路線,這種不確定的運輸路線就是優(yōu)化過程的路徑因素;最后,利用遺傳算法框架對貨位因素編碼生成初始種群,計算不同出庫方案下適應度函數(shù)的值,在不斷迭代的過程中搜尋最優(yōu)方案,在確定貨品組入庫擺放的同時確定出庫路線.綜上,這種包含兩方面因素的迭代尋優(yōu)過程就是貨位-路徑協(xié)同優(yōu)化.

2.1 協(xié)同優(yōu)化數(shù)學模型

本文通過對智能倉儲環(huán)節(jié)中各部分的關系進行耦合分析,提出了貨位路徑協(xié)同優(yōu)化的數(shù)學模型.該模型與傳統(tǒng)智能倉儲優(yōu)化算法的區(qū)別在于:將路徑規(guī)劃和貨架優(yōu)化歸為一個整體,并用數(shù)學公式表達兩者間的關系.具體變量及變量約束條件描述如下:f(x)為協(xié)同優(yōu)化的總目標函數(shù),fpath為所有任務出庫總時間花費,fother為除AGV車輛路徑規(guī)劃外算法其他部分的開銷,α和β分別為影響系數(shù),且α+β=1.n為AGV 車輛總數(shù).ni為當前AGV 車輛編號,i=1,2,…,n,i∈N.M為出貨任務總數(shù).mi為當前出貨任務編號,i=1,2,…,M,i∈N.G為貨品總數(shù).gi為當前貨品編號,i=1,2,…,G,i∈N.(i,j)表示當前坐標點位置,i,j∈N,i≤I,j≤J.S為貨架總數(shù).μ為車輛從終點返回起點的懲罰系數(shù).

具體來說,本文協(xié)同優(yōu)化的總體目標如公式(1)表示:

其中,α和β為影響系數(shù):α系數(shù)為“路徑最短”的權(quán)重,關注算法尋找出來的路線最短;β系數(shù)為“額外開銷”的權(quán)重,關注碰撞、沖突、轉(zhuǎn)彎等額外時間消耗,即關注多個AGV 選擇的運輸路徑相互之間盡可能不重合,以免發(fā)生沖突等.

當M>N時,即任務數(shù)大于車輛總數(shù)時,車輛從終點返回起點需要一定時間,見公式(2):

當M≤N時,即車輛數(shù)大于任務數(shù)時,每個任務一輛AGV 車,見公式(3):

fm,n為某次調(diào)度時,車輛運行花費的時間,其中,(i,j)為目標點,fc為車輛出現(xiàn)堵塞后的等待時間,詳見公式(4):

fother主要包括兩個部分:一個是物品間相關度計算,用于物品的分類;另外一個就是貨架優(yōu)化算法的時間消耗,此處i+1

下面我們將從貨品相似度算法、多AGV 路徑規(guī)劃算法、貨位規(guī)劃和AGV 路徑規(guī)劃協(xié)同優(yōu)化算法這3 部分詳細描述本文提出的貨位規(guī)劃與AGV 路徑規(guī)劃協(xié)同優(yōu)化算法的實現(xiàn)思路.貨品相似度算法和多AGV 路徑規(guī)劃算法將為最終的貨位路徑協(xié)同優(yōu)化算法提供支持.

2.2 貨品相似度算法

本文對實際正在運維的倉儲貨物數(shù)據(jù)進行處理,清洗去除操作時間、貨品名稱等無關數(shù)據(jù),抽取貨品編號(即貨品的唯一標示)、批次(同一批次貨品可理解為在同一時間內(nèi)執(zhí)行出入庫)等數(shù)據(jù)進行數(shù)據(jù)分析,以0 和1標識是該編號貨品否在該批次出貨,每個貨品都是一個由批次數(shù)各維度組成的向量.通過余弦相似度算法計算該向量間的相似度,獲得貨品相似度.具體來說,基于余弦相似度的貨品相似度計算方法具體流程如圖1 所示.

首先,根據(jù)倉儲數(shù)據(jù)信息計算最大出貨批次數(shù).將貨品的出貨信息記錄下來,形成向量表.例如,1 號貨物的向量值為[0,1,1,0,1],分別代表在2 批次、3 批次、5 批次出貨,其他貨品以此類推.在此基礎上累加貨品出庫總次數(shù),計算出庫頻率.基于余弦公式(公式(6))計算兩兩貨物間的余弦值:

由于貨品和它本身和的余弦值為1,代表兩貨物最為相似.因此,我們將貨物余弦值減去1 再求其絕對值,和1 的差值越小,證明相似度越高.以這個新的值代表兩貨物間的相似度,最終會獲得一個貨品和貨品相似的上三角矩陣.根據(jù)這個矩陣的值,即可計算出一個貨品組.

2.3 路徑規(guī)劃算法

基于對遺傳算法的改進,本文設計的基于遺傳算法的多AGV 路徑規(guī)劃算法,將路徑長度、轉(zhuǎn)彎數(shù)加入適應度函數(shù),即轉(zhuǎn)彎次數(shù)越少,路徑總長越短,該個體越優(yōu)秀.同時,采用改進的靜態(tài)地圖法來解決多AGV 路徑?jīng)_突問題.路徑的規(guī)劃是貨位路徑協(xié)同優(yōu)化的基礎,是本文的重要內(nèi)容之一,主要使用遺傳算法執(zhí)行規(guī)劃路徑的操作,其偽代碼如下所示.

輸入:地圖信息、起點、終點;

輸出:規(guī)劃完成的路徑點集合.

具體來說,在遺傳算法計算過程中,首先對目標結(jié)果進行編碼,路徑編碼方式為排列編碼.例如,[1,2,5,6,7,8]表示從1 號點出發(fā),途徑2,5～7 這些點,最終到達8 號點.路徑坐標點序號作為基因參與算法運算.根據(jù)起始點到目標點序號,生成隨機可行的路徑序列,稱為初始種群.

然后對此種群進行適應值計算,如公式(7)所示:

其中:pathlength參數(shù)與fit適應度值成反比,表示路徑越短,適應度值越優(yōu)秀,選擇出來的路線也越貼近最優(yōu)解.適應值越大,意味著這個個體越優(yōu)秀.nodenum表示轉(zhuǎn)彎次數(shù),取值大于等于1.nodenum參數(shù)的添加,是考慮到轉(zhuǎn)彎因素對路徑規(guī)劃的影響,1+系數(shù)對pathlength參數(shù)的微調(diào),使算法在路徑選擇中盡可能避免選擇拐彎次數(shù)過多的路線.經(jīng)過實驗驗證:nodenum的加入,有效地減少了算法選擇轉(zhuǎn)彎次數(shù)過多的路線.將基于該公式計算出的初始種群中所有個體的適應值記錄下來,再對此種群進行交叉和變異操作.

本文基于輪盤賭法對交叉和變異操作的對象進行選取,以使得適應度越大的個體被選中的概率越大.輪盤賭選算子可以根據(jù)個體適應值在群體中所占比例,結(jié)合該算子被選中的累積概率,再取一個0 到1 之間的隨機值,比較子代個體的適應度比例和隨機值大小,選取子代適應值高的個體參與到遺傳運算中,進一步提高整個種群的適應值,從而取得更優(yōu)的最終結(jié)果,或者讓該種群向更優(yōu)的結(jié)果發(fā)展.具體來說,我們先計算該種群的適應值總和fit_sum,然后,計算每個個體的適應值占比rfit=fit/it_sum和各部分累積概率cfit(如公式(8)所示):

其中,i≤popsize(種群大小),popnexti為第i代種群,popcurrenti為第i代種群的副本.

隨后遍歷種群副本popcurrenti,而后生成一個0-1 之間的隨機數(shù)p.比較子代個體的cfit和p的值,直到cfit比p大時,該個體代替popcurrenti中此位置的個體.最后,將popcurrenti的所有值賦給popnexti.

在交叉操作的實現(xiàn)中,交叉次數(shù)是路徑點總數(shù)的1/4,具體計算出的次數(shù)向下取整.每次交叉操作方法相同.首先,隨機選取此種群中的某一條路徑,在此路徑上找到一個隨機點設為交叉點q,然后尋找另一條也通過此點的基因.設p1,p2 為原選出基因.將p1 中q點以后的點被p2 中q點以后的點代替生成新的基因p1,再將p2 中q點以后的點由p1 中q點以后的點代替生成新的基因p2.對p1 和p2 進行路徑再優(yōu)化,然后計算并更新p1 和p2的適應值、路徑長度和轉(zhuǎn)彎次數(shù),完成交叉操作.

在變異操作中,首先判定是否發(fā)生變異.基于預設變異幾率(mutationRate),根據(jù)random=Math.random(?)*(1.0/mutationRate)計算變異率(Math.random(?)為隨機數(shù)生成函數(shù)).此時,若random為0,則執(zhí)行變異.變異時,先隨機挑選種群中的一條染色體(即一個完整的可行路徑),再在此路徑上隨機選取一個路徑點,分別計算此條染色體上該路徑點的前一個點pre和后一個點next.而后在地圖上分別搜索pre和next所有相鄰點,并分別尋找所有相鄰點中的重合點.我們將這些重合點視為可變異點,以保證變異后路徑為通路.在重合點中隨機選取一個點作為新的連接點,代替一開始選中的點,生成新的染色體.計算并更新新染色體的適應值、路徑長度、轉(zhuǎn)彎次數(shù),完成變異操作.最后檢查是否迭代到最大代數(shù):若沒有,則繼續(xù)進行變異和交叉;若達到最大代數(shù),則對種群進行篩選,即比較所有染色體(個體)的適應值,適應值最大即為最優(yōu)結(jié)果.

除此之外,本文基于改進的靜態(tài)地圖法來解決多AGV 路徑?jīng)_突問題,以保證算法在多任務下各AGV 車輛不會相撞.本文對已有的靜態(tài)地圖法進行了改進,在假設車輛保持勻速運行時,估算了車輛的運行位置,以此將車輛已走過的路徑實時釋放掉,車輛未走過的路徑保持封鎖狀態(tài),彌補靜態(tài)地圖法存在的缺陷.具體來說,在計算新的任務路徑時,先獲取之前所有未完成的任務執(zhí)行情況,即在運行中的AGV 的當前位置,并獲取他們未來將要走的路徑.通過對每一個新任務執(zhí)行路徑封鎖,在優(yōu)化最初避免沖突,使得沖突不可能發(fā)生.對于可能會造成的當前時間點車輛無法搜索到可行路徑的情況,設置車輛等待.詳細來說,算法中使用的地圖不是創(chuàng)建的原始地圖,而是將其他AGV 車已占用的道路排除后的新地圖,這意味著每個AGV 車進行路徑規(guī)劃時都有一個屬于他自己的地圖.該地圖將其他AGV 已規(guī)劃但未走過的路徑點進行封鎖,已封鎖路徑上的點和貨架、充電樁等一樣視為不可通過的障礙物,以此保證新的車輛規(guī)劃避開這些障礙物,解決AGV 的路徑?jīng)_突問題.

2.4 貨位路徑協(xié)同優(yōu)化算法

本文對正在運維的智能倉儲出入口數(shù)據(jù)進行分析,發(fā)現(xiàn):如果相似度高的貨物擺放集中且密集,極有可能導致路徑堵塞;相反,相似度高的貨物擺放分散,則容易出現(xiàn)高頻貨物所在貨架出庫距離長這一問題.而分散與否,則是由最佳貨架出庫路徑的重合程度判斷的.因此,將貨架最佳出庫路徑和貨品的相關性結(jié)合起來,可有效地找到一個緩解AGV 路徑擁堵、提高出庫效率的貨品擺放結(jié)果.基于以上數(shù)據(jù)分析,本文提出的貨位規(guī)劃與路徑規(guī)劃協(xié)同優(yōu)化算法的適應度函數(shù)包含兩個參數(shù):貨架的出庫代價以及該貨架和周邊貨架的沖突代價.實驗表明:該設置的適應值可以用來篩選出合格的個體,從而產(chǎn)生合適的解.

本文提出的貨位規(guī)劃與路徑規(guī)劃協(xié)同優(yōu)化算法的基本思路為:首先計算貨品間的相似度,按照貨架最大載貨種類數(shù)對貨品進行聚類操作;再計算聚類后各個類別間貨品的相似度,之后再計算各個貨架的最佳出庫路徑.利用計算完成的數(shù)據(jù)以及當前地圖信息,使用改進的遺傳算法計算出貨架布局情況,也就是貨架的擺放方式,從而完成貨位布局和路徑規(guī)劃兩者的共同優(yōu)化.

貨位路徑協(xié)同優(yōu)化算法的具體流程如圖2 所示:首先,基于上文貨品相似度算法的描述,使用余弦相似度算法將實驗數(shù)據(jù)的貨品間的相似度計算出來,并統(tǒng)計出庫次數(shù);然后結(jié)合相似度,依據(jù)貨架的載貨種類數(shù),對當前貨品進行分類,并且賦予每個分類屬性.分類的出庫頻率為當前分類物品中出庫頻率最高的物品的出庫頻率,分類的出庫批次為當前分類物品中出庫頻率數(shù)前20%的貨品出庫批次總和.

舉個例子,假設1 號～10 號物品在一個分類中,此時,若1 號、4 號貨品的出庫頻率最高,且1 號、4 號貨品的出庫批次向量分別為[1,0,1,1,1,0,1,0]和[1,0,1,1,1,1,1,0],則該分類的出庫批次向量為[1,0,1,1,1,1,1,0].此時,一個分類有著貨品的屬性,且集成了更多的貨品,將這個分類看作是一個未被放入貨架位置的待入庫貨架,即將所有貨品轉(zhuǎn)化為待入庫貨架.

計算貨架間的相似度,同樣使用余弦相似度算法來進行計算.在計算出相似度后,對所有值減去1 再取其絕對值,絕對值越小越相似.設定一個閾值η,此時,計算出的相似度一切小于η的貨架認定為是高相似度貨架.高相似度貨架會參與到適應值的計算中,η過大,會認定多數(shù)貨架是都是相互相似的,算法會難以選出真正優(yōu)秀的解;η過小會導致選擇不到足夠的相似度貨架,雖然算法可以給出一個它認為“優(yōu)秀”的解.但在任務單來臨時,可能仍舊會造成擁堵的狀況,這也標志著算法的失敗.本文以倉儲實際運維數(shù)據(jù)(200 件貨品,14 個批次的數(shù)據(jù))為數(shù)據(jù)樣本對倉儲數(shù)據(jù)進行實驗,調(diào)整η取值,觀察了余弦值的取值規(guī)律,最終確選取0.25 為本文提出的協(xié)同優(yōu)化算法中η的值.

貨位路徑協(xié)同優(yōu)化的第2 步為計算每個應擺放貨架的位置.基于上文給出的路徑規(guī)劃算法,我們計算從該位置單獨出貨時的最佳出貨路徑,以獲得每個可能擺放貨架的位置和其出庫的最佳路徑,即最快出庫方式.在獲取并記錄了各個貨架位置的最佳出庫路徑后,開始對貨架位置進行綜合運算.

貨位路徑協(xié)同優(yōu)化算法的求解算法基于遺傳算法設計,首先對遺傳算法進行編碼.根據(jù)需要解決的問題,需要把未入庫的貨架,擺放到貨架位置上,需要計算的是貨架如何入庫的問題.在編碼上,選用排列編碼即可.在排列上,選取貨架位置作為空位,將未入庫貨架放入其中.例如,[5,4,2,3,1]意為將5 號未入庫貨架放入1 號貨架位,將4 號未入庫貨架放入2 號貨架位,以此類推.完成編碼的選擇和實現(xiàn)后,即可以生成初始種群.初始種群的建立是生成一組隨機數(shù),隨機數(shù)區(qū)間在未入庫貨架號區(qū)間范圍內(nèi).具體實現(xiàn)為:先獲取所有未入庫的貨架號放入集合A;再生成隨機數(shù),將其放入到個體的基因中記為集合B.此時,該貨架號從之前的集合A除去,防止再次選中.經(jīng)過不斷的生成,直到取完集合A中所有數(shù).在隨機生成的種群中,考慮個體重合問題,使用生成新的個體來替代重合個體,直到該種群中個體的數(shù)量滿足設定的值.完成初始種群的生成后,計算該種群中個體的適應值.適應值fit的計算方式如公式(9)所示:

其中,f是該貨架的出入庫頻率,此參數(shù)可以放大整體適應度,使出庫頻率影響到貨架擺放位置;Bestpath為當前貨架出庫的最佳路徑;為與所有當前貨架相似度較高的貨架的出庫路徑重合量的和,該參數(shù)可用來降低沖突發(fā)生的情況,將避免沖突考慮到貨架排放中;α和β為權(quán)重系數(shù),在滿足α+β=1 的約束下,調(diào)節(jié)兩個參數(shù)間的權(quán)重比,基于后續(xù)實驗調(diào)整,本文的α系數(shù)取值為0.8,β系數(shù)取值為0.2.此外,根據(jù)適應度函數(shù)分析來看,適應度與該未入庫貨架的出庫頻率、最佳出庫路徑長度以及與其相關性高的其他貨位路徑?jīng)_突數(shù)成正相關.

完成適應度的計算,算法開始代數(shù)迭代.首先使用錦標賽法選取算子,基于已計算出的適應度,在種群中隨機挑選個體并比較適應度,適應度大的被淘汰,最終選擇出一定量的個體進行交叉生成下一代.在基本的錦標賽基礎上,本文加入了被選擇系數(shù)以提高錦標賽選擇算子的效率,有效消弱了為了減少劣質(zhì)個體被多次比較從而導致選擇出不優(yōu)秀個體的情況發(fā)生.具體來說,我們?yōu)槊總€個體賦予一個被選擇系數(shù),其默認初值為1.一開始,各個個體的被選擇系數(shù)相等,開始選擇時為每個個體生成區(qū)間為[0,1]的隨機數(shù),再用該隨機數(shù)乘以被選擇系數(shù),最終獲得的按從小到大順序取進入錦標賽.一旦某一個體被淘汰,則減少它的被選擇系數(shù).

基于上述獲得的算子,算法開始依次進行交叉和變異操作.交叉操作時,選取集合B中任意兩個體,進行交叉操作.本文提出協(xié)同優(yōu)化算法選用有序交叉方法進行交叉,將父代中的某一段截取出來留給子代,再將另一個父代的基因按其順序,在保證解的完整性下,依次放入子代中.例如兩父代x為[1,2,3,4,5],y為[3,2,5,1,4]進行交叉.截取x的中間3 個為子代部分,當前子代狀態(tài)為[?,2,3,4,?].再將y的基因按順序,在不重復的情況下,依次填入其中,最終子代結(jié)果為[5,2,3,4,1].變異操作選用離散變異的方式進行,變異率P取0.7/chrom_length(chrom_length為編碼長度).同時,在變異的過程中,考慮變異檢測和變異位數(shù)因素.對種群中的個體進行變異檢測即產(chǎn)生隨機值,看是否小于變異率,當小于時執(zhí)行變異.在變異位數(shù)方面,如果貨位數(shù)大于貨架數(shù),取奇數(shù);如果貨位數(shù)等于貨架數(shù)時,變異位數(shù)取偶數(shù).基于交叉、變異的執(zhí)行,新的個體重新放入種群中.算法判斷是迭代代數(shù)否滿足迭代終止要求:若滿足,選取最優(yōu)個體為最終解.

3 實驗結(jié)果及分析

基于昆山某智能倉儲的實際運維數(shù)據(jù),我們在智能倉儲仿真平臺對本文提出的貨位規(guī)劃和路徑規(guī)劃協(xié)同優(yōu)化算法進行了實驗,并與傳統(tǒng)遺傳算法[24]、基于出貨頻率的貪心算法[25]進行了對比分析,實驗結(jié)果驗證了本文所提出的智能倉儲貨位規(guī)劃與路徑規(guī)劃協(xié)同優(yōu)化算法的有效性.

3.1 實驗數(shù)據(jù)和評價指標

本次實驗數(shù)據(jù)來自于昆山某生產(chǎn)廠商倉儲物流數(shù)據(jù),并額外加入一些干擾數(shù)據(jù)來模擬突發(fā)情況.實驗數(shù)據(jù)涉及庫存總貨品200 種,其中,物品間的相似度比例大致為6:2:2:1:1,分別代表貨物間兩種貨品間強相關、3 種貨品間強相關直到6 種貨品間強相關,該比例的獲取是從該廠商15 天內(nèi)共計14 個批次的出庫記錄中統(tǒng)計獲取的.實驗中,貨架、地圖等設置是根據(jù)單個貨架可放置貨品種類數(shù)、地圖預留的貨位位置、路徑點數(shù)等信息來配置的.基本的環(huán)境設置即為實際倉儲環(huán)境,貨位設置為單列連續(xù)擺放,總計32 個貨架,倉庫入口和倉庫出口分別位于倉儲兩側(cè).

本文所有的實驗基于以下假設.

1) AGV 以勻速進行直線行走、轉(zhuǎn)彎、運輸?shù)葎幼?且不出現(xiàn)偏離軌道的情況;

2) 路徑點間間距等長.在衡量算法運算效果時,設AGV 運行過兩路徑點間長度的時間為單位時間,即單位時間=路徑點間距/AGV 速度(本文假定AGV 平均運行速度為0.5m/s,路徑點間距為1m,即單位時間為2s);

3) AGV 車數(shù)量充足,能夠保證每個任務都有獨立的車輛立即執(zhí)行.

設置的對比算法為其他貨架優(yōu)化算法,一個為傳統(tǒng)遺傳算法[24],另一個為基于出貨頻率的貪心算法[25],采用的路徑計算統(tǒng)一為本文所實現(xiàn)的路徑規(guī)劃算法.本文的貨位路徑協(xié)同優(yōu)化算法(以下實驗數(shù)據(jù)分析中簡稱協(xié)同優(yōu)化算法)和傳統(tǒng)貨架優(yōu)化遺傳算法,設定變異率為0.07,交叉率為0.68,迭代代數(shù)均為300.為了讓遺傳算法可以和本文所設計的算法形成對比,在遺傳算法的適應性函數(shù)中添加了貨品相關性β的影響,并為其設置了影響系數(shù)0.2,出貨頻率的系數(shù)α為0.8.

在實驗結(jié)果的分析中,主要評價指標包括為完成出庫任務進行路徑規(guī)劃的算法自身耗時(記為出庫路徑規(guī)劃耗時)、AGV 車輛按規(guī)劃路徑執(zhí)行完出庫任務的預估耗時(記為AGV 運行耗時)、完成出庫任務總耗時(即出庫路徑規(guī)劃耗時和AGV 運行耗時之和,記為出庫總耗時)、為完成出庫任務所需調(diào)用的AGV 車輛數(shù)目(記為動用車輛數(shù))等.

3.2 實驗結(jié)果及分析

下面我們將基于14 個批次的出庫數(shù)據(jù),從不同的維度來對比分析貨位路徑協(xié)同優(yōu)化算法的表現(xiàn)情況.

首先,我們分析各算法在完成所有批次貨物出庫的情況下的總體實驗結(jié)果,即包含各類貨品特征的倉儲綜合場景,該場景對應于實際倉儲的綜合運行狀況;

其次,為了分析智能倉儲協(xié)同優(yōu)化算法在特定特征場景下的優(yōu)化效果,我們篩選出符合不同特點的出貨批次,分成下列3 個特征場景進行各算法間的對比分析,具體包括:1) 以貨品間相似度高、出貨頻率高為特點的場景1;2) 以貨品間相似度高、出貨頻率低為特點的場景2;3) 以貨品間相似度低、出貨頻率高為特點的場景3.

下面分別對以上場景的實驗結(jié)果進行具體描述和分析.

a) 總體實驗結(jié)果及分析

本文對所有批次數(shù)據(jù)分別進行了實驗,統(tǒng)計了3 種算法在完成各批次貨品時的出庫任務路徑規(guī)劃時間(見表1 中“出庫路徑規(guī)劃耗時”列)和AGV 車輛執(zhí)行完該批次任務所需時間(見表1 中“AGV 運行耗時”列).從而計算出各算法在實際運行過程中完成出貨任務的總時間消耗(見表1 中“出庫總耗時”列),即路徑規(guī)劃時間和AGV執(zhí)行任務時間之和.具體實驗結(jié)果數(shù)據(jù)見表1.

Table 1 Experimental data of all shipment batchs表1 各批次出庫情況實驗數(shù)據(jù)匯總表

首先,基于表1 中“出庫路徑規(guī)劃耗時”列所示實驗數(shù)據(jù),本文從路徑規(guī)劃時間角度對實驗結(jié)果進行分析.

如圖3 所示,本文提出的協(xié)同規(guī)劃算法在在路徑規(guī)劃時間上比較穩(wěn)定,且用時較短;而其他兩種算法用時不穩(wěn)定,且在大多數(shù)批次中,用時明顯大于協(xié)同優(yōu)化算法.探究其原因主要在于:

· 在多AGV 場景下,路徑規(guī)劃的最好情況是每個AGV 從起點出發(fā),按規(guī)劃路徑行駛,到終點無沖突,那么路徑規(guī)劃只需進行一次即可;

· 相反,若多AGV 在車輛規(guī)劃路徑時發(fā)生沖突時,算法會進行3 件事:等待1 個單位時間計算路徑;計算繞路的路徑;從兩種方案中決策較優(yōu)方案.因此,一旦多AGV 發(fā)生沖突,路徑規(guī)劃算法的工作量會急劇攀升,這就是導致其他兩算法路徑規(guī)劃時間不穩(wěn)定的原因.

而協(xié)同優(yōu)化算法將貨位路徑重合變成影響貨架擺放的因素,對貨架擺放結(jié)果產(chǎn)生影響.實驗數(shù)據(jù)證明:此方法可明顯地減少并避免了沖突,顯著降低了出庫路徑規(guī)劃用時的消耗.

其次,從AGV 完成出貨任務的時間消耗角度分析,本文統(tǒng)計了AGV 按規(guī)劃路線實際執(zhí)行任務所需時間.對于每一批次,我們將該批次中執(zhí)行出貨任務用時最長的AGV 運行時間計為該批次的AGV 執(zhí)行出貨任務耗時.在進行具體預估計算時,按照上文所述的假設給定的單位時間為2s.同時,考慮到實際運行中,車輛的停止、轉(zhuǎn)向和啟動這個過程會額外耗時.因此,每一次車輛轉(zhuǎn)彎額外增加1 個單位時間用時.再者,當AGV 發(fā)生沖突時,計算車輛間沖突視為1 個單位時間,和轉(zhuǎn)彎類似,AGV 在避免沖突時存在停止再啟動,等待時間系統(tǒng)設置為1 個單位時間,即每一次AGV 沖突共需要消耗2 個單位時間.綜合上述時間代價,計算出各算法在AGV 完成出貨任務耗時的總時間,實驗結(jié)果如基于表1 中“AGV 運行耗時”列實驗數(shù)據(jù)所示.基于實驗數(shù)據(jù)生成了AGV 運行預估耗時折線圖.如圖4 所示,按3 種算法所規(guī)劃出的AGV 路徑執(zhí)行出貨任務時,AGV 的預估耗時差距不明顯.本文對該實驗結(jié)果進行了進一步分析認為:協(xié)同優(yōu)化算法在計算貨架位置時,不是以出入庫頻率作為唯一的計算依據(jù),為了避免碰撞,會適當將相似度高的貨架分開放置,以有效避免高相似度貨品同時出貨時AGV 路徑?jīng)_突的現(xiàn)象.但其缺點在于,不能夠把高頻率的貨架放在最容易出貨的位置.而實驗中的預估出貨時間時會以同一批次多個AGV 中最長運行時間為準,因此從運行時間的角度來看,協(xié)同優(yōu)化算法的優(yōu)勢不大.還有兩個因素存會影響最終時間,即轉(zhuǎn)彎時間懲罰和沖突等待時間懲罰,懲罰力度的改變也會對結(jié)果產(chǎn)生比較大影響.本文設置的懲罰力度比較柔和,所以各算法在AGV 運行預估時間上比較相近.

最后,基于各算法的出庫任務路徑規(guī)劃時間和AGV 車輛執(zhí)行完該任務所需時間之和,本文計算出各算法在實際運行過程中完成出貨任務的總時間消耗(實驗數(shù)據(jù)見表1“出庫總耗時”列所示).如圖5 所示,協(xié)同優(yōu)化算法的出庫任務總耗時,在各個批次中都表現(xiàn)穩(wěn)定,且耗時較短.

在以上實驗數(shù)據(jù)分析的基礎上,本文進一步計算了3 種算法在所有批次中出庫任務總耗時方面的最優(yōu)值、平均值和方差(見表2).從計算結(jié)果可以看出:綜合所有批次的實驗數(shù)據(jù),協(xié)同優(yōu)化算法的耗時最優(yōu)值低于遺傳算法1.5%,低于貪心算法11.9%;在平均值方面,協(xié)同優(yōu)化算法耗時低于遺傳算法18.8%,低于貪心算法28.7%;此外,分析方差數(shù)據(jù)可以看出,協(xié)同優(yōu)化算法的穩(wěn)定性遠遠高于其他算法.因此,同其他兩種算法相比,本文提出的協(xié)同優(yōu)化算法在有效性和穩(wěn)定性方面具有顯著優(yōu)勢.

Table 2 Data analysis of the effectiveness and stability of proposed algorithm表2 算法有效性和穩(wěn)定性數(shù)據(jù)分析表

b) 特征場景實驗結(jié)果及分析

特征場景實驗分析,旨在驗證智能倉儲協(xié)同優(yōu)化算法在不同場景下的表現(xiàn)情況.按照倉儲貨物可能出現(xiàn)的特點,我們從所有出貨批次中篩選出包含該特點的出貨批次,分成下列3 個場景再進行算法間的對比分析.

· 場景1:貨品間相似度高、出貨頻率高的貨品需求任務單;

· 場景2:貨品間相似度高、出貨頻率低的貨品需求任務單;

· 場景3:貨品間相似度低、出貨頻率高的貨品需求任務單.

在實驗中,我們分別對貨位路徑協(xié)同優(yōu)化算法、傳統(tǒng)遺傳算法、貪心算法在特定場景下的路徑規(guī)劃算法耗時、AGV 運行時間、AGV 轉(zhuǎn)彎次數(shù)、沖突等待時間、完成出貨任務所需AGV 數(shù)量、綜合耗時進行了計算.下面分別對3 個場景的實驗結(jié)果進行分析.

場景1 的高相似度、高出貨頻率的貨品集中出貨是一般倉儲常規(guī)的出貨情況,一般而言,發(fā)生這種情況時也會伴隨出貨數(shù)量大這一特點,出貨量大更能夠考驗算法的優(yōu)化效果.這種常規(guī)情景下的算法優(yōu)化效果也是最值得注意和研究的.表3 描述了在該場景下,3 種算法的具體表現(xiàn)情況.從路徑規(guī)劃的時間消耗比較上來看:協(xié)同優(yōu)化算法任務路徑規(guī)劃時間消耗最短,貪心算法任務路徑規(guī)劃時間消耗最長;從優(yōu)化結(jié)果上分析,三者優(yōu)化結(jié)果運行時間相近,貨位路徑協(xié)同優(yōu)化算法和傳統(tǒng)貨架優(yōu)化算法為31 個單位時間,轉(zhuǎn)彎次數(shù)均為2 次,貪心算法為30 個單位時間.但是除了貨位路徑協(xié)同優(yōu)化算法外,其他兩個算法均存在AGV 運行時存在沖突.從綜合用時來看,貨位路徑協(xié)同優(yōu)化算法的表現(xiàn)更為出眾一些,也符合預期的估計,沒有造成車輛沖突的情況.因此,從貨品出庫效率的角度講,協(xié)同優(yōu)化算法優(yōu)于其他兩算法.

Table 3 Experimental data of Scenario 1表3 場景1 實驗結(jié)果匯總表

場景2 中,貨品的主要特征為貨品間相似度高、出貨頻率低,即高相似度、低出貨頻率的貨品集中出貨的場景,其主要應用于突發(fā)性缺少某些貨物而進行的少量貨物出庫的情況.在該場景下,3 種算法的表現(xiàn)情況見表4.具體來說,從路徑規(guī)劃時間上分析,貨位路徑協(xié)同優(yōu)化算法表現(xiàn)最好,遺傳算法其次,貪心算法較弱.其原因在于:貪心算法的關注點為出入庫頻率,不涉及相關性問題,在高相關貨品出庫時,貨品分散在其他貨架,導致其更有可能需要規(guī)劃更多的貨架進行出庫,更多出庫車輛數(shù)帶來的是更高的車輛部署成本以及更久的路徑規(guī)劃時間.從AGV 路徑?jīng)_突分析,貨位路徑協(xié)同優(yōu)化算法依然有效地避免了AGV 沖突.同時,與場景1 相比,在該場景下,傳統(tǒng)遺傳算法和貪心算法的沖突次數(shù)都有多所降低.其原因是:在這兩種算法所計算的貨架位置中,低頻率貨品安排位置一般孤立,出庫時不會總是占用主要出庫道路,因此相對沖突發(fā)生的機會變小.而貨位路徑協(xié)同優(yōu)化算法則是在高頻率貨品放在優(yōu)質(zhì)出庫位和集中出庫時防止碰撞之間做平衡,在處理低頻率貨物時更可能將其和高頻率貨物穿插放置,其優(yōu)點在于低頻出貨時也可能使其更近,缺點在于有些高頻貨物無法放在最佳出庫位置上.從整體優(yōu)化效果來看,盡管協(xié)同優(yōu)化算法仍舊比其他算法優(yōu)化效果更好,但優(yōu)勢不如場景1 中明顯.

Table 4 Experimental data of Scenario 2表4 場景2 實驗結(jié)果匯總表

場景3 中,貨品的主要特征為貨品間相似度低、但貨品本身歷史出貨頻率高.該場景主要發(fā)生于零散貨品補貨,一般貨品出貨量較小,AGV 路徑?jīng)_突問題相對不嚴重.在該場景下,3 種算法的表現(xiàn)情況見表5.從實驗結(jié)果可以看出:在該場景下,協(xié)同優(yōu)化算法的綜合表現(xiàn)稍弱于傳統(tǒng)遺傳算法.其原因在于:協(xié)同優(yōu)化算法關注貨品間的相似度的適應性函數(shù)在設計之初就是為了應對集中出貨導致AGV 出貨路徑規(guī)劃沖突嚴重這個問題,其更為關注貨品間的相似度;而傳統(tǒng)遺傳算法正好相反,它更為關注貨品的出貨頻率.因此,對于以貨品低相似度、高頻率為特征的場景3 中,AGV 沖突處理能力不再成為決定算法表現(xiàn)的核心因素,協(xié)同優(yōu)化算法不具優(yōu)勢.

Table 5 Experimental data of Scenario 3表5 場景3 實驗結(jié)果匯總表

綜上所述,我們在綜合場景和特定特征場景下各算法的表現(xiàn)情況均進行了相關實驗及結(jié)果分析.實驗結(jié)果表明:從出庫效率的角度來看,在不同特定特征場景下,貨位路徑協(xié)同優(yōu)化算法的表現(xiàn)有所差異,在高相似度、高出貨頻率的特征場景中最具優(yōu)勢.在綜合場景下,貨位路徑協(xié)同優(yōu)化算法的表現(xiàn)明顯優(yōu)于其他算法.因此,在實際的智能倉儲系統(tǒng)中,本文所提出的貨位路徑協(xié)同優(yōu)化算法可有效提高倉儲的出庫率.

4 總結(jié)與展望

智能倉儲的優(yōu)化是目前整個未來倉儲發(fā)展的重要方向之一.本文根據(jù)實際問題需求,參考協(xié)同優(yōu)化思想,提出了智能倉儲貨位路徑協(xié)同優(yōu)化的數(shù)學模型和相關求解算法,包括貨品相似度求解算法和改進適應度函數(shù)的路徑規(guī)劃算法;并在以上兩種算法的基礎上,基于貨位路徑協(xié)同優(yōu)化思想實現(xiàn)了貨位路徑協(xié)同優(yōu)化.同時,基于真實倉儲運維數(shù)據(jù),本文從不同的維度、場景分別對貨位路徑協(xié)同優(yōu)化算法的表現(xiàn)情況進行實驗并分析,實驗結(jié)果表明,本文提出的智能倉儲協(xié)同優(yōu)化算法在算法有效性和穩(wěn)定性上具有顯著優(yōu)勢.該算法可有效提高倉儲的出貨效率,降低運輸成本.

在后續(xù)工作中,我們將在以下方面繼續(xù)展開研究:(1) 本文所提出的解決方案主要針對于網(wǎng)格式AGV 布局,在其他布局下能否適用有待進一步考察和驗證;(2) 將貨品的相關性、體積、質(zhì)量均引入貨位路徑協(xié)同優(yōu)化算法中,以此保證貨架的穩(wěn)定性和放置貨品的效率,擴大本文所提出的貨位路徑協(xié)同優(yōu)化算法的適用條件,使其可以擴展至更多的應用場景;(3) 考慮當AGV 小車數(shù)量不充足時,即待執(zhí)行的出貨任務數(shù)多余可支配的AGV 數(shù)量時,智能倉儲協(xié)同優(yōu)化算法的研究.