[發明專利]基于混合粒子群算法的AGV優化調度方法

有效

• 申請號: 201410577414.0
• 申請日: 2014-10-24
• 公開（公告）號: CN104408589B
• 公開（公告）日: 2018-03-06
• 發明（設計）人: 楊瑋;李國棟;李程;曹薇;高賀云;楊超群
• 申請（專利權）人: 陜西科技大學
• 主分類號: G06F17/00
• 分類號: G06F17/00
• 代理公司: 西安通大專利代理有限責任公司61200
• 代理人: 蔡和平

技術領域

本發明屬于自動化立體倉庫優化調度技術領域，涉及一種AGV優化調度方法，具體涉及一種基于遺傳算法、模擬退火算法及蟻群算法的混合粒子群算法的自動化立體倉庫輸送系統AGV優化調度方法。

背景技術

AS/RS(Automated Storage and Retrieval System)系統硬件設備的研究發展己趨于完整，現代企業對AS/RS工作效率的要求增加，更多集中在對系統優化管理、調度和作業的優化。AS/RS的輸送系統已經成為影響倉庫作業的瓶頸，因此需要采用合適的方法解決輸送系統AGV優化調度問題，以增加倉儲系統的工作效率、提升企業的營業利潤，降低企業物流費用，提高企業競爭力。

輸送系統是自動化立體倉庫的一個重要組成部分。對它調度問題的優化研究，能夠使輸送系統資源得到充分的利用，同時避免發生系統死鎖及系統瓶頸效應，從而提高輸送系統的作業效率。輸送系統的調度優化實質上就是指AGV的優化調度問題，它的研究目標主要就是在多個約束條件下，將要完成的輸送任務合理分配給AGV，使系統的輸送能力和設備的資源利用率得到提高，進而提高自動化立體倉庫系統的吞吐率，降低系統的物流成本。

粒子群算法(PSO，particle swarm optimization)起源于1987年Reynolds對鳥群社會系統的仿真實驗研究。PSO是一種群智能算法，優化過程就是群體迭代過程，由粒子在其搜索空間中不斷靠攏最佳點進行尋優。PSO的優勢在于參數設置少，簡單易操作，又具有改進空間，在科學研究與工程應用中普遍具有可行性及有效性。粒子群算法的研究按其研究方向包含了理論研究、性能改進研究、應用研究和離散算法研究四部分。理論研究主要是算法的收斂性、運算復雜性等數學性方面研究；性能改進研究主要是針對算法的缺陷以及不足；應用研究就是研究如何將算法應用到一些理論問題，或者需要解決的實際優化問題中；離散性研究是針對算法本身提出的一種研究方向。

但標準粒子群算法(參考文獻：《粒子群算法及應用》)一般兼顧不了收斂速度、全局及局部精細搜索能力，且作為一種通用的隨機全局搜索算法，它也存在早熟收斂和陷入局部搜索的缺點。

發明內容

本發明的目的在于提供一種基于混合粒子群算法的AGV優化調度方法，解決了自動化立體倉庫輸送系統優化調度的問題。

為達到上述目的，本發明采用了以下技術方案：

步驟1：將上/下包臺、入/出庫臺及AGV定為調度對象，并以AGV完成輸送任務所花費的工作時間最小作為優化調度的目標構造AGV調度優化問題數學模型；

步驟2：以基于調度對象的三維矩陣對粒子位置進行編碼，并運用基于遺傳算法、模擬退火算法及蟻群算法的混合粒子群算法對AGV調度優化問題數學模型進行求解，得到給定任務量下AGV的最優調度方案。

所述編碼采用整數編碼方式。

所述AGV調度優化問題數學模型表示為：

min{max(T₁,T₂,...,T_k,...,T_L)} (2)

T_k＝d_ik-r_ik+P_k×s_k×t_ijk+d_jk-r_jk+P_k×s_k×t_ijk

s.t d_ik≥r_ik,d_jk≥r_jk,

其中，T_k表示第k輛AGV的工作時間，L表示AGV數量；d_ik表示第k輛AGV離開第i個入/出庫臺的時間，r_ik表示第k輛AGV到達第i個入/出庫臺的時間，d_jk表示第k輛AGV離開第j個上/下包臺的時間，r_jk表示第k輛AGV到達第j個上/下包臺的時間，Q表示AGV的編號集合，S表示入/出庫臺的編號集合，S'表示上/下包臺的編號集合，t_ijk表示第k輛AGV從第i個入/出庫臺到第j個上/下包臺的時間。

所述步驟(2)具體包括以下步驟：

1)種群初始化