一種考慮組裝工藝的自動化立體倉庫調度方法與流程
2023-12-01 14:34:16
本發明屬於智能製造技術領域,更進一步涉及考慮組裝工藝的一種新型的自動化立體倉庫調度方法。
背景技術:
隨著《中國製造2025》新興產業戰略規劃的出臺,智能製造被定位為中國製造的主攻方向,並在各個領域中得到應用。對生產製造企業來講,智能車間、智能工廠是智能製造的核心,在此背景下,自動化立體倉庫在生產製造企業逐步得到應用,組裝車間是其應用的一個場合。在組裝過程中,如果不結合組裝工藝對倉儲機器人進行調度,將會使組裝效率降低,甚至影響到組裝作業的正常進行。因而,尋求一種考慮組裝工藝的自動化立體倉庫調度方法具有很好的科學意義和社會價值。
截止目前,學者考慮的倉庫調度問題主要局限在物流、供應鏈及港口等傳統領域,比如Lu et al.(An algorithm for dynamic order-picking in warehouse operations,European Journal of Operational Research,2016)針對供應鏈訂單調整的情況,運用路由幹涉算法對動態訂單揀選問題進行了研究;宋等(航空貨站自動化存取系統作業調度優化,哈爾濱工業大學學報,2015)以指令序列完工時間最短為優化目標,採用蟻群算法對航空貨站存取系統進行調度優化研究,以提高自動化存取系統的效率。這些情況還未將自動化立體倉庫應用到企業生產環節當中,本發明結合實際組裝車間中的倉庫調度優化問題進行了認真的分析研究,提出了一種考慮組裝工藝的新型自動化立體倉庫調度方法,不僅提高了產品的組裝效率,而且提升了組裝車間的智能化水平,具有很高的推廣價值。
技術實現要素:
有鑑於此,本發明的目的在於提出一種基於改進布穀鳥算法考慮組裝工藝的自動化立體倉庫調度優化方法,以提高企業組裝車間的組裝效率和智能化水平。
為了實現上述目的,本發明的構思是:本發明以組裝工藝、機器人機械手數量、出庫終點為約束條件,以工件出庫完成時間及組裝任務完工時間總和為優化目標,把考慮組裝工藝的自動化立體倉庫調度抽象成帶約束的組合優化問題。採用改進的布穀鳥算法對該優化問題進行求解。根據上述發明構思,本發明採用下述技術方案:
一種基於改進布穀鳥算法的自動化立體倉庫調度方法(Improved Cuckoo Search Algorithm,ICSA),其特徵在於包括如下步驟:
(1)對組裝車間現場存在的一些約束及要優化的目標進行分析,並抽象成數學模型,組裝車間對參與組裝工件的安裝順序有一定的要求,因而工件到達組裝區域時間的早晚將對組裝任務的完工時間產生一定的影響;
(2)初始化參數:進化代數計數器t、最大進化代數Na、鳥巢數量Nn、發現概率最小值和最大值
(3)構建Nn個可行的初始鳥巢;
採用隨機數編碼技術隨機生成Nn長度與待揀選貨位個數相同的一維向量,該向量即為鳥巢的位置,根據倉儲機器人機械手數量,對解碼後的候選解進行插入出入庫緩衝區位處理,這樣可防止產生不可行解,從而構建出可行的初始鳥巢種群;
(4)計算所有鳥巢的適應度,記錄具有最高適應度的鳥巢Xbest;
(5)全局搜索:t=t+1;
(6)局部搜索:i=i+1;
(7)通過更新鳥巢位置;
(8)將當前代與上一代的布穀鳥巢位置作比較,保留較好的布穀鳥巢;
(9)產生隨機數r,如果r>pa,則隨機產生新的鳥巢;
(10)如果ipa,則隨機產生新的鳥巢;
(10)如果i<Nn,則返回步驟(6);否則,按步驟執行;
(11)計算所有鳥巢的適應度,並記錄具有最高適應度的鳥巢Xbest;
(12)如果搜索沒有達到最大迭代次數,則返回步驟(5);否則,停止搜索,並輸出Xbest。
實施例2
本實施例與實施例一基本相同,特別之處如下:
1所述步驟(1)中所建立的數學模型是基於以下考慮建立的:①為提高組裝車間的智能化水平,將組裝工藝引入到倉庫調度環節;②本著節能降耗的目的對倉庫機器人出入庫路徑進行優化。因而待優化的目標為產品組裝所需工件的出入庫及產品組裝完成時間總和最小,其數學模型表示如下:
minf(t)=O1+O2+O3
其中minf(t)為待優化的目標,O1為所需工件的出入庫時間,O2為組裝過程中等待工件的時間,O3為非等待情況下工件的安裝時間;u為所需工件的總量;m,n分別為工件和產品的類別數量;Qab為安裝每類產品所需工件的數量;tij為機器人連續經過兩個待揀選貨位所需要的時間;Tb為b型工件安裝所需時間;為貨位pi中的b型工件到達安裝區域的時間;eij為機器人在某條路徑下是否連續經過貨位pi和貨位pj的標記;gir為第i個工件 是否屬於子路徑r的標記;sr為機器人是否經過子路徑r的標記;σib為貨位pi中的工件是否屬於b型工件的標記;為貨位pi和pj中的工件是否都分配a型產品,且安裝呈先後順序並連續的標記。
2所述步驟(3)構建Nn個可行的初始鳥巢:採用隨機數編碼技術構建Nn個鳥巢,其規則為:根據待揀選貨位的個數,隨機生成一個長度與待揀選貨位個數相同的一維向量。該向量即為鳥巢的位置,接著對該向量中的元素以升序的方式與待揀選任務號進行一一映射,這樣鳥巢位置就可以將待求解表示出來。同時,考慮到倉儲機器人機械手數量的限制,對映射後的候選解進行插入出入庫緩衝區位處理,這樣可防止產生不可行解,從而構建出可行的初始鳥巢種群。
3所述步驟步驟(7)中的可進一步描述為:
1)
其中上式中為第i個鳥巢第t+1代的步長;為第i個鳥巢第t代的位置;Xbest為截至第t代所有鳥巢中最好的位置;Na、Nc分別為最大進化代數和當前進化代數。
2)在1)中,表示可針對性的引導算法向最優或次優的方向搜索,表示步長因子可根據進化階段進行靈活調整,即在進化的早期,算法呈現全局搜索的特性,此時步長因子較大,有利於提高搜索的廣度,隨著進化的進行,算法所求解將會越來越接近全局最優或次優解,此時步長因子較小,有利於加大搜索的深度。因而,這兩個方面保證了步長的動態智能性,將大大提高算法的尋優效率。
4所述步驟(9)中的pa可進一步描述為:
1)
其中,分別為pa的最小值和最大值;fi是第i個鳥巢的適應度;fmax是所有鳥巢的最大適應度。
2)在1)中,pa為自適應發現概率,的值越小,表示個體對種群的貢獻越小,其被淘汰的概率就越大,這樣可有效避免固定的pa所帶來的兩個弊端:其一,太大的pa容易使搜索陷入局部最優, 致使收斂精度降低;其二,太小的pa容易又使搜索具有盲目性。自適應發現概率策略的實施,不僅保持了種群的多樣性,降低算法陷入局部最優的概率,而且能保留較好的個體。
實施例3
參見圖1,本考慮組裝工藝的自動化立體倉庫調度方法,其具體步驟如下:
(1)確立目標,建立優化模型
該實例組裝任務中倉庫調度問題具有如下特徵:
某企業組裝車間組裝4種不同型號的產品,並且組裝所需工件均在立體倉儲中存放,該企業組裝車間的總體布局如圖1所示。
設倉儲機器人水平運動平均速度和垂直運動平均速度分別為vx、vy,並且水平和垂直方向的運動相互獨立,同時機器人擁有N個機械手;倉儲每個貨位的寬、高分別記為W、H,相鄰巷道中心間距為Dl,每排貨架的列數為C,並把貨位坐標定義為li(xi,yi,zi),3個坐標分量依次表示所在貨架的列號、層號及巷道號,出入庫緩衝區指定為l0(0,0,0)。
定義1如果機器人在執行任務過程中經過路徑r,則sr=1;否則,sr=0。如果貨位pi屬於子路徑r,則gir=1;否則,gir=0。
定義2如果機器人在執行任務過程中連續經過貨位li(xi,yi,zi)、lj(xj,yj,zj),則eij=1;否則,eij=0。對於巷道兩端可進出的倉儲系統,機器人所用時間tij可表示為
其中,
A1=(W×|xi-xj|)/vx,
A2=(W×(xi+xj)+Dl×|zi-zj|)/vx,
A3=(W×((C-xi)+(C-xj))+Dl×|zi-zj|)/vx,
B=(H×|yi-yj|)/vy
假定某企業組裝車間可組裝n類產品,組裝產品的工件共有m類,並且完成每類產品的組裝需要每類工件的數量為Qab,組裝每類單個工件所需時間為Tb,(a∈(1,2,…,n),b∈(1,2,…,m))。
定義3如果貨位pi中的工件屬於b(b∈(1,2,…,m))類工件,則σib=1;否則,σib=0;並且該工件到達所屬組裝區域的時間為
定義4如果貨位li(xi,yi,zi)和lj(xj,yj,zj)中的工件都分配給a(a∈(1,2,…,n))型產品進行組裝,且安裝呈先後順序並連續,則ψij=1;否則,ψij=0。
該倉儲調度的優化目標為所需工件的出入庫及產品組裝完成時間總和最小,其數學模型包括目標函數和約束,定義如下:
minf(t)=O1+O2+O3 (2)
其中,
(2)釐清約束條件,確立約束關係
t1<t2<…pa,則隨機產生新的鳥巢;
9)如果i<Nn,則返回步驟5);否則,按步驟執行;
10)計算所有鳥巢的適應度,並記錄具有最高適應度的鳥巢Xbest;
11)如果搜索沒有達到最大迭代次數,則返回步驟4);否則,停止搜索,並輸出Xbest。
實施例4
本實施例設計某企業一個組裝車間的倉庫調度優化問題,利用本發明求出滿足約束條件的最優解或次優解。該企業組裝車間組裝4種不同型號的產品,並且組裝所需工件均在立體倉儲中存放,該企業組裝車間的總體布局如圖2所示。
(1)問題概況
按照上述技術方案以某企業組裝車間的自動化立體倉庫為應用背景進行示例說明,同時與原始布穀鳥算法(Cuckoo Search Algorithm,CSA)及遺傳算法(Genetic Algorithm,GA)進行了比較,為保證對比的公平性,實驗均在在Windows XP系統平臺,主頻2.19GHz,內 存1.99GB,Matlab7.0開發環境下進行。所有算法的種群大小及進化代數分別為40和600;對ICSA來說,和分別為0.1和0.5;對CSA來說,pa為0.4;對遺傳算法來說,交叉概率及變異概率分別為0.8、0.1。其他參數為:W、H分別為30cm、40cm。vx、vy分別為1m/s,0.5m/s,Dl為1.2m,C為80列,N為2。假定目前組裝4類產品,組裝數量均為1。組裝產品所需工件共有5類,組裝每類產品對每類工件的數量需求如表1所示。
需要的各類工件的具體貨位坐標為:1型工件,{(12,5,1),(2,14,3),(42,6,2)};2型工件,{(22,2,4),(20,4,5),(30,1,3),(18,4,3)};3型工件,{(24,3,1),(67,5,12),(10,5,6),(50,2,5)};4型工件,{(59,5,5),(74,4,3),(27,4,6),(42,4,21)};5型工件,{(55,3,5),(32,5,9),(13,5,9),(73,5,5),(62,4,7)}。5類工件的安裝所需時間分別為:T1=6s,T2=8s,T3=3s,T4=10s,T5=14s。
(2)優化結果對比分析
為了使比較具有普適性,對每個算法各運行30次,結果如圖3、圖4和表2。
由圖3可知,ICSA相對傳統的CSA和GA在最優解、收斂速度上都表現出良好的性能。對於圖3出現的現象,圖4從兩個方面給予了證明:首先,本文提出的發現概率自適應策略不僅保留了較好的鳥巢,而且改進了種群的多樣性,提高了算法搜索的廣度;其次,本文提出的步長動態調整策略能夠引導算法向最優或次優方向,提高了算法搜索的深度。這兩者對ICSA在求解精度及收斂效率上起到至關重要的作用。表2中的結果進一步表明,改進的ICSA的確改善了解的質量與求解效率,同時,較小的標準差揭示了ICSA具有較好的收斂穩定性。
表1組裝每類產品對每類工件的數量需求
表2算法求解情況比較
這些實施例僅用於說明本發明而不用於限制本發明的範圍。另外本領域技術人員可以 對本發明作各種改動或修改,這些等價形式同樣屬於本申請所附權利要求書所限定的範圍之內。