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

有效

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

1.一種基于改進蟻群算法和啟發式算法的集裝箱裝載方法，具有如下步驟：

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

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

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

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

2.根據權利要求1所述的一種基于改進蟻群算法和啟發式算法的集裝箱裝載方法，其特征還在于所述步驟“綜合考慮當前空間的左方和后方所裝載的貨物和當前待裝載空間形態，從待裝載的貨物中選擇適合的貨物”具體為：

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

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

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

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

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

3.根據權利要求2所述的一種基于改進蟻群算法和啟發式算法的集裝箱裝載方法，其特征還在于：在每一步裝載貨物時，需要滿足懸空約束：

ΣSpi=(xTi-xBi)(yTi-yBi)]]>

其中，表示貨物p和貨物i重合部分的面積，表示貨物i的左前上坐標，表示貨物i的右后下坐標；其中和p的定義如下：

p∈{p|zTp=zBi,xBp≤xBi,xTp≥xTi,yBp≤yBi,yTp≥yTi}∪]]>

{p|zTp=zBi,Max(xTp,xTi)-Min(xBp,xBi)<xTi-xBi+xTp-xBp,]]>

Max(yTp,yTi)-Min(yBp,yBi)<yTi-yBi+yTp-yBp}]]>

Spi=[(xTi-xBi+xTp-xBp)-(Max(xTp,xTi)-min(xBp,xBi))]×]]>

[(yTi-yBi+yTp-yBp)-(Max(yTp,yTi)-Min(yBp,yBi))].]]>