智能倉(cāng)儲(chǔ)貨位規(guī)劃與AGV 路徑規(guī)劃協(xié)同優(yōu)化算法?

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

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

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

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

本文主要?jiǎng)?chuàng)新貢獻(xiàn)如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)M>N時(shí),即任務(wù)數(shù)大于車輛總數(shù)時(shí),車輛從終點(diǎn)返回起點(diǎn)需要一定時(shí)間,見(jiàn)公式(2):

當(dāng)M≤N時(shí),即車輛數(shù)大于任務(wù)數(shù)時(shí),每個(gè)任務(wù)一輛AGV 車,見(jiàn)公式(3):

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

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

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

2.2 貨品相似度算法

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

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

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

2.3 路徑規(guī)劃算法

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

輸入:地圖信息、起點(diǎn)、終點(diǎn);

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

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

然后對(duì)此種群進(jìn)行適應(yīng)值計(jì)算,如公式(7)所示:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

3.1 實(shí)驗(yàn)數(shù)據(jù)和評(píng)價(jià)指標(biāo)

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

本文所有的實(shí)驗(yàn)基于以下假設(shè).

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

2) 路徑點(diǎn)間間距等長(zhǎng).在衡量算法運(yùn)算效果時(shí),設(shè)AGV 運(yùn)行過(guò)兩路徑點(diǎn)間長(zhǎng)度的時(shí)間為單位時(shí)間,即單位時(shí)間=路徑點(diǎn)間距/AGV 速度(本文假定AGV 平均運(yùn)行速度為0.5m/s,路徑點(diǎn)間距為1m,即單位時(shí)間為2s);

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

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

首先,我們分析各算法在完成所有批次貨物出庫(kù)的情況下的總體實(shí)驗(yàn)結(jié)果,即包含各類貨品特征的倉(cāng)儲(chǔ)綜合場(chǎng)景,該場(chǎng)景對(duì)應(yīng)于實(shí)際倉(cāng)儲(chǔ)的綜合運(yùn)行狀況;

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

下面分別對(duì)以上場(chǎng)景的實(shí)驗(yàn)結(jié)果進(jìn)行具體描述和分析.

a) 總體實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

b) 特征場(chǎng)景實(shí)驗(yàn)結(jié)果及分析

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

· 場(chǎng)景1:貨品間相似度高、出貨頻率高的貨品需求任務(wù)單;

· 場(chǎng)景2:貨品間相似度高、出貨頻率低的貨品需求任務(wù)單;

· 場(chǎng)景3:貨品間相似度低、出貨頻率高的貨品需求任務(wù)單.

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

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

Table 3 Experimental data of Scenario 1表3 場(chǎng)景1 實(shí)驗(yàn)結(jié)果匯總表

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

Table 4 Experimental data of Scenario 2表4 場(chǎng)景2 實(shí)驗(yàn)結(jié)果匯總表

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

Table 5 Experimental data of Scenario 3表5 場(chǎng)景3 實(shí)驗(yàn)結(jié)果匯總表

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

4 總結(jié)與展望

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

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