基於改進蟻群算法和啟發式算法的貨櫃裝載方法
2023-12-12 11:34:12 1
基於改進蟻群算法和啟發式算法的貨櫃裝載方法
【專利摘要】本發明公開了一種基於改進蟻群算法和啟發式算法的貨櫃貨物擺放方法，具有如下步驟：初始待裝載化貨物信息和貨櫃空間信息；初始化蟻群、初始化每一隻螞蟻的貨物裝載鏈信息以及初始化信息素信息；當前的螞蟻根據當前蟻群算法的迭代次數和最大迭代次數，生成選貨概率，使用輪盤賭的方式選擇啟發式選貨方式或蟻群選貨方式；若選擇啟發式：考慮當前的空間的左方和後方所裝載的貨物和當前待裝載空間，從待裝載的貨物中選擇適合的貨物進行遞歸裝載；若選擇蟻群，查詢信息素矩陣，根據輪盤賭的方式選擇裝載貨物；對選出的貨物，用回溯的方式，選出當前貨物的最佳擺放姿態。
【專利說明】基於改進蟻群算法和啟發式算法的貨櫃裝載方法
【技術領域】
[0001]本發明涉及一種貨櫃內部貨物的擺放方法，尤其涉及ー種融合啟發式算法和改進的蟻群算法的貨櫃內部貨物擺放方法。涉及專利分類號B65輸送；包裝；貯存；搬運薄的或細絲狀材料B65G運輸或貯存裝置，例如裝載或傾斜用輸送機；車間輸送機系統；氣動管道輸送機B65G65/00裝載或卸載B65G65/30裝填或排空料倉、料鬥、罐或類似容器的方法或裝置，而不包括這些方法或裝置在特殊的化學或物理工藝過程中的使用或在特殊機械上的應用，例如不包含在其他單個小類中的。
【背景技術】
[0002]貨櫃的布局優化問題是ー個具有複雜約束條件的三維組合優化問題，理論上是NP完全問題，不可能在有限時間內獲得最優解。近年來，人們不斷利用蟻群算法，遺傳算法，模擬退火算法等智能化算法以及啟發式方法優化求解該問題，獲得了一定的效果。
[0003]早在1980年，George等人就提出了沿著貨櫃寬度的層的概念，結合剩餘空間有效的提高了裝載利用率。Gehring, Bortfeldt等人提出利用混合遺傳算法求解裝箱問題，首次提出了塔的概念，物品放入貨櫃之前先組合成一個ー個不相關的「塔」，然後將這些「塔」按照一定的規則放入貨櫃，提高裝載效率。王麗，張慧等人 社「C.Pimpawat, N.Chaiyaratana.Three-Dimensional Container Loading UsingA Cooperative Co-Evolutionary Genetic Algorithm[J].Applied ArtificialIntelligence, 2004, 18:581-601.」這篇文章中提出了將協同進化遺傳算法和一定的啟發式算法相融合的技木，通過對ー個個較短的最優裝載序列的操作，實現高效率的裝載，該算法在時間空間方面都表現出了不錯的性能。
[0004]但是隨著問題規模的増大，以及實際應用中對算法運行時間等方面的要求，単一算法難以滿足實際應用。単一的智能化算法收斂最優解過程需要較長的時間，而啟發式算法能快速得到解，解的質量卻不容易讓人滿意。
【發明內容】
[0005]本發明針對以上問題的提出，而研製的一種基於改進蟻群算法和啟發式算法的貨櫃裝載方法，具有如下步驟:
[0006]一初始待裝載化貨物信息和貨櫃空間信息；初始化蟻群算法各參數、初始化每一隻螞蟻的貨物裝載鏈信息以及初始化信息素信息；
[0007]—開始算法循環，當前的螞蟻根據當前蟻群算法的迭代次數和最大迭代次數，生成選貨概率，使用輪盤賭的方式選擇啟發式選貨方式或蟻群選貨方式；
[0008]一若選擇啟發式選貨方式:考慮當前的空間的左方和後方所裝載的貨物和當前待裝載空間，從待裝載的貨物中選擇適合的貨物進行遞歸裝載；若選擇蟻群選貨方式，查詢信息素矩陣，根據輪盤賭的方式選擇裝載貨物；
[0009]一重複上述步驟，直到貨物裝載完畢或貨櫃裝滿，輸出裝載鏈，作為貨櫃內部貨物的擺放方案。
[0010]所述步驟「綜合考慮當前的空間的左方和後方所裝載的貨物和當前待裝載空間形態，從待裝載的貨物中選擇適合的貨物」具體為:
[0011]一若當前貨櫃為空，即為首次裝載，蟻群信息素為空:使用輪盤賭的方式選擇一貨物裝載在與貨櫃門相對的側壁和該側壁相鄰側壁形成的角落，形成上方、右方和前方的空間；
[0012]一在後續的裝載中，依據該貨物的上方、右方和前方空間的順序，首先選擇與上方空間體積最接近的貨物填充上方空間；若遍歷所有貨物體積後，上方空間無法容納至少一種待裝載貨物，則將該上方空間記入剩餘空間鏈；
[0013]一按照上述規律遞歸的裝載右方和前方空間，直到有貨物完成裝載；
[0014]一若所述的上方、右方或前方的空間不能單獨裝載任一貨物，則將上方、右方或前方的空間記入剩餘空間鏈；
[0015]一在每次裝載前，待裝載空間首先融合剩餘空間鏈中的剩餘空間，使當前待裝載空間最大化。
[0016]在每一步裝載貨物時，需要滿足懸空約束:
【權利要求】
1.一種基於改進蟻群算法和啟發式算法的貨櫃裝載方法，具有如下步驟: 一初始待裝載化貨物信息和貨櫃空間信息；初始化蟻群算法各參數、初始化每一隻螞蟻的貨物裝載鏈信息以及初始化信息素信息； ー開始算法循環，當前的螞蟻根據當前蟻群算法的迭代次數和最大迭代次數，生成選貨概率，使用輪盤賭的方式選擇啟發式選貨方式或蟻群選貨方式； 一若選擇啟發式選貨方式:考慮當前的空間的左方和後方所裝載的貨物和當前待裝載空間，從待裝載的貨物中選擇適合的貨物進行遞歸裝載；若選擇蟻群選貨方式，查詢信息素矩陣，根據輪盤賭的方式選擇裝載貨物； 一重複上述步驟，直到貨物裝載完畢或貨櫃裝滿，輸出裝載鏈，作為貨櫃內部貨物的擺放方案。
2.根據權利要求1所述的ー種基於改進蟻群算法和啟發式算法的貨櫃裝載方法，其特徵還在於所述步驟「綜合考慮當前俯空間的左方和後方所裝載的貨物和當前待裝載空間形態，從待裝載的貨物中選擇適合的貨物」具體為: 一若當前貨櫃為空，即為首次裝載，蟻群信息素為空:使用輪盤賭的方式選擇ー貨物裝載在與貨櫃門相對的側壁和該側壁相鄰側壁形成的角落，形成上方、右方和前方的空間； 一在後續的裝載中，依據該貨物的上方、右方和前方的順序，首先選擇與上方空間體積最接近的貨物填充上方空間；若遍歷所有貨物體積後，上方空間無法容納至少ー種待裝載貨物，則將該上方空間記入剩餘空間鏈； ー按照上述規律遞歸的裝載右方和前方空間，直到有貨物完成裝載； 一若所述的上方、右方或前方的空間不能単獨裝載任ー貨物，則將上方、右方或前方的空間記入剩餘空間鏈； 一在毎次裝載前，待裝載空間首先融合剰餘空間鏈中的剰餘空間，使當前待裝載空間最大化。
3.根據權利要求2所述的ー種基於改進蟻群算法和啟發式算法的貨櫃裝載方法，其特徵還在於:在每ー步裝載貨物時，需要滿足懸空約束:
4.根據權利要求1所述的ー種基於改進蟻群算法和啟發式算法的貨櫃裝載方法，其特徵還在於裝載算法完成後，需要對得出的裝載鏈進行重心約束和重量約束的檢查: 重量約束:
5.根據權利要求1所述的ー種基於改進蟻群算法和啟發式算法的貨櫃裝載方法，其特徵還在於採用的蟻群算法為基於狀態的改進蟻群算法: 在所述選出當前貨物的最佳擺放姿態後，根據裝載鏈生成一個多位狀態值，所述狀態值包含當前裝載貨物的種類和每種貨物的數量；蟻群的信息素矩陣查詢，剪枝信息的查詢都需要此狀態值； 所述裝載鏈為記錄ー只螞蟻對應的裝載信息，至少包括裝載順序、每ー個貨物的擺放姿態以及放置貨物的坐標。
6.根據權利要求5所述的ー種基於改進蟻群算法和啟發式算法的貨櫃裝載方法，其特徵還在於:所述蟻群算法的信息素更新模型表示為:
7.根據權利要求5所述的基於改進蟻群算法和啟發式算法的貨櫃裝載方法，其特徵還在於:具有以所述狀態值為關鍵字的剪枝矩陣，該矩陣為查詢某一狀態值對應的剩餘空間總體積大小的哈希表:隨著算法的執行，將蟻群裝載鏈產生的狀態值和所對應的剰餘空間體積值存儲到剪枝矩陣中；在以後的迭代中，算法首先查找剪枝矩陣，若當前狀態下得到的剰餘空間總體積大於剪枝矩陣中的剰餘空間體積，即當前狀態下計算獲得的解劣於剪枝矩陣中記錄的解，則放棄此次迭代則放棄此次迭代。
8.根據權利要求1所述的ー種基於改進蟻群算法和啟發式算法的貨櫃裝載方法，其特徵還在幹:在選出裝載貨物的方法後，使用回溯的方法，選出當前貨物的最佳擺放姿態。
9.根據權利要求8所述的ー種基於改進蟻群算法和啟發式算法的貨櫃裝載方法，其特徵還在於所述步驟「用回溯的方式，選出當前貨物的最佳擺放姿態」具體為:
定義貨物共有六種擺放姿態，hk//L，wk//ff, lk//H、hk//L，lk//ff, wk//H,wk//L, hk//ff, lk"H、wk//L, lk//ff, hk//H、lk//L, hk//ff, wk//H 和 lk//L, wk//ff, hk//H ； 其中，lk、wk、hk分別表示第k類貨物的長度、寬度、高度；L、W、Η分別表示貨櫃的長度、寬度和高度； 所述回溯的方式為遍歷所述的六種擺放方式，並計算按每種擺放方式，在水平和豎直方向擺放最多數量該種貨物後，在水平和豎直方向剰餘的體積； 回溯選取剩餘體積最小的擺放方式作為結果，即最終所述貨物的擺放方式。
【文檔編號】G06N3/00GK103455841SQ201310301679
【公開日】2013年12月18日 申請日期:2013年7月17日 優先權日:2013年7月17日
【發明者】張德珍, 陳剛, 王婷, 高鵬, 李永華 申請人:大連海事大學