[發明專利]基于改進蟻群算法和啟發式算法的集裝箱裝載方法

有效

• 申請號: 201310301679.3
• 申請日: 2013-07-17
• 公開（公告）號: CN103455841A
• 公開（公告）日: 2013-12-18
• 發明（設計）人: 張德珍;陳剛;王婷;高鵬;李永華
• 申請（專利權）人: 大連海事大學
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06Q10/04;B65G65/30
• 代理公司: 大連東方專利代理有限責任公司 21212
• 代理人: 李馨;李洪福

技術領域

本發明涉及一種集裝箱內部貨物的擺放方法，尤其涉及一種融合啟發式算法和改進的蟻群算法的集裝箱內部貨物擺放方法。涉及專利分類號B65輸送；包裝；貯存；搬運薄的或細絲狀材料B65G運輸或貯存裝置，例如裝載或傾斜用輸送機；車間輸送機系統；氣動管道輸送機B65G65/00裝載或卸載B65G65/30裝填或排空料倉、料斗、罐或類似容器的方法或裝置，而不包括這些方法或裝置在特殊的化學或物理工藝過程中的使用或在特殊機械上的應用，例如不包含在其他單個小類中的。

背景技術

集裝箱的布局優化問題是一個具有復雜約束條件的三維組合優化問題，理論上是NP完全問題，不可能在有限時間內獲得最優解。近年來，人們不斷利用蟻群算法，遺傳算法，模擬退火算法等智能化算法以及啟發式方法優化求解該問題，獲得了一定的效果。

早在1980年，George等人就提出了沿著集裝箱寬度的層的概念，結合剩余空間有效的提高了裝載利用率。Gehring，Bortfeldt等人提出利用混合遺傳算法求解裝箱問題，首次提出了塔的概念，物品放入集裝箱之前先組合成一個一個不相關的“塔”，然后將這些“塔”按照一定的規則放入集裝箱，提高裝載效率。王麗，張慧等人在“C.Pimpawat,N.Chaiyaratana.Three-Dimensional?Container?Loading?Using?A?Cooperative?Co-Evolutionary?Genetic?Algorithm[J].Applied?Artificial?Intelligence,2004,18:581-601.”這篇文章中提出了將協同進化遺傳算法和一定的啟發式算法相融合的技術，通過對一個個較短的最優裝載序列的操作，實現高效率的裝載，該算法在時間空間方面都表現出了不錯的性能。

但是隨著問題規模的增大，以及實際應用中對算法運行時間等方面的要求，單一算法難以滿足實際應用。單一的智能化算法收斂最優解過程需要較長的時間，而啟發式算法能快速得到解，解的質量卻不容易讓人滿意。

發明內容

本發明針對以上問題的提出，而研制的一種基于改進蟻群算法和啟發式算法的集裝箱裝載方法，具有如下步驟：

—初始待裝載化貨物信息和集裝箱空間信息；初始化蟻群算法各參數、初始化每一只螞蟻的貨物裝載鏈信息以及初始化信息素信息；

—開始算法循環，當前的螞蟻根據當前蟻群算法的迭代次數和最大迭代次數，生成選貨概率，使用輪盤賭的方式選擇啟發式選貨方式或蟻群選貨方式；

—若選擇啟發式選貨方式：考慮當前的空間的左方和后方所裝載的貨物和當前待裝載空間，從待裝載的貨物中選擇適合的貨物進行遞歸裝載；若選擇蟻群選貨方式，查詢信息素矩陣，根據輪盤賭的方式選擇裝載貨物；

—重復上述步驟，直到貨物裝載完畢或集裝箱裝滿，輸出裝載鏈，作為集裝箱內部貨物的擺放方案。

所述步驟“綜合考慮當前空間的左方和后方所裝載的貨物和當前待裝載空間形態，從待裝載的貨物中選擇適合的貨物”具體為：

—若當前集裝箱為空，即為首次裝載，蟻群信息素為空：使用輪盤賭的方式選擇一貨物裝載在與集裝箱門相對的側壁和該側壁相鄰側壁形成的角落，形成上方、右方和前方的空間；

—在后續的裝載中，依據該貨物的上方、右方和前方空間的順序，首先選擇與上方空間體積最接近的貨物填充上方空間；若遍歷所有貨物體積后，上方空間無法容納至少一種待裝載貨物，則將該上方空間記入剩余空間鏈；

—按照上述規律遞歸的裝載右方和前方空間，直到有貨物完成裝載；

—若所述的上方、右方或前方的空間不能單獨裝載任一貨物，則將上方、右方或前方的空間記入剩余空間鏈；

—在每次裝載前，待裝載空間首先融合剩余空間鏈中的剩余空間，使當前待裝載空間最大化。

在每一步裝載貨物時，需要滿足懸空約束：