一種三維貨櫃裝載布局優化方法及系統的製作方法

2023-05-03 19:16:21 1

專利名稱：一種三維貨櫃裝載布局優化方法及系統的製作方法
技術領域：
本發明屬於貨櫃裝載布局優化設計領域，尤其涉及一種三維貨櫃裝載布局優化的方法及系統。
背景技術：
三維貨櫃裝載布局優化方法指的是在一定約束條件下，將一批貨物按照適當的裝載方法裝入貨櫃中，以使得貨櫃的容積利用率或裝載質量利用率最大，從而實現對貨櫃進行合理有效使用的方法，其目標函數可以表示為
ηη
maxZ = Ai^ll-Wi-HrSrm)/V+ (I-A)^gl -Sl-In/G，其中，li、wi、hi、gi、m 分別表示 i 類貨
i=l i=l
物的長、寬、高、質量、件數；V，G分別表示貨櫃的最大裝載容積、最大裝載質量；λ是0-1 變量，當追求目標為容積利用率最大時λ = 1，當追求目標為裝載質量利用率最大時λ = 0;i是0-1變量，若貨物i裝載則Si = l，否則δ = 0。現有技術提供的三維貨櫃裝載布局優化方法多基於單一智能優化算法，如基於遺傳算法的三維貨櫃裝載布局優化方法、基於蟻群算法的三維貨櫃裝載布局優化方法和基於啟發式算法的三維貨櫃裝載布局優化方法等。由於採用的算法單一，在解決三維貨櫃裝載布局優化問題時，無法結合不同算法的優越性而均表現出一定的缺陷。例如，基於啟發式算法的三維貨櫃裝載布局優化方法，可實施確定的布局塊排放策略、裝載效率較高，但其僅考慮了裝箱容積約束而對裝箱其它方面的約束條件考慮不足；基於遺傳算法的三維貨櫃裝載布局優化方法，作為其理論基礎的遺傳算法具有群體性全局搜索能力， 可擴展性強，易與其他技術結合等優點，但由於沒有充分利用系統反饋信息，使得搜索具有盲目性，當算法求解到一定範圍時往往形成冗餘迭代，導致尋求最優解的效率降低；基於蟻群算法的三維貨櫃裝載布局優化方法，作為其理論基礎的蟻群算法是一種結合了分布式計算、正反饋機制和貪婪式搜索的算法，具有很強的搜索較優解能力，其通過信息素的更新高效收斂到最優解，但由於初期信息素匱乏，導致搜索初期積累信息素佔用的時間較長。

發明內容
本發明實施例的目的在於提供一種三維貨櫃裝載布局優化的方法，以解決現有技術提供的三維貨櫃裝載布局優化方法多基於單一智能優化算法，在解決三維貨櫃裝載布局優化問題時，無法結合不同算法的優越性而均表現出一定缺陷的問題。本發明實施例是這樣實現的，一種三維貨櫃裝載布局優化的方法，所述方法包括以下步驟對待裝箱貨物進行編碼，生成待裝箱貨物的多個初始貨物集，並利用遺傳算法生成所述初始貨物集的子代貨物集；計算子代貨物集中各個體的適應度值及其父代貨物集中各個體的適應度值，當子代貨物集中各個體的適應度值之和相對其父代貨物集中各個體的適應度值之和不再增加時，對相應子代貨物集進行個體解碼，得到可行解；將多個初始貨物集對應的多個可行解構成的集合作為蟻群算法的輸入，利用蟻群算法迭代搜索得到所述待裝箱貨物的最優裝箱方案。其中，所述利用遺傳算法生成所述初始貨物集的子代貨物集的步驟還可以包括以下步驟初始化遺傳算法控制參數；根據適應度函數計算所述初始貨物集中各個體的適應度值；根據計算得到的所述適應度值以及預存的變異概率，以所述初始貨物集為基礎進行選擇、交叉、變異迭代處理，得到所述初始貨物集的多個連續子代貨物集。進一步地，所述適應度函數可以滿足關係式F= (Ii · Wi · VLj · Wj · Hj) X 100%其中，F為適應度函數；li為第i類貨物的長度，Wi為第i類貨物的寬度，比為第i 類貨物的高度；h為貨櫃的長度，Wj為貨櫃的寬度，Hj為貨櫃的高度。進一步地，所述選擇處理可以採用最優保存策略和輪盤賭選擇法，此時，所述根據計算得到的所述適應度值以及預存的變異概率，以所述初始貨物集為基礎進行選擇、交叉、 變異迭代處理，得到所述初始貨物集的多個連續子代貨物集的步驟還可以包括以下步驟根據計算得到的個體適應度值及最優保存策略和輪盤賭選擇法，確定所述初始貨物集中每個個體的選擇概率；根據確定的所述每個個體的選擇概率在所述初始貨物集內選擇兩個父個體；根據預存的變異概率對選擇的所述兩個父個體進行變異處理或交叉處理，將處理後的兩個父個體插入到所述初始貨物集的下一連續子代貨物集中，並計算所述初始貨物集的下一連續子代貨物集中各個體的適應度值；根據計算得到的當前子代貨物集中各個體的適應度值及最優保存策略和輪盤賭選擇法，確定當前子代貨物集中每個個體的選擇概率；根據確定的當前子代貨物集中每個個體的選擇概率在當前子代貨物集內選擇兩個父個體；根據根據預存的變異概率對選擇的所述兩個父個體進行變異處理或交叉處理，將處理後的兩個父個體插入到當前子代貨物集的下一連續子代貨物集中，從而迭代得到所述初始貨物集的多個連續子代貨物集。其中，所述對相應子代貨物集進行個體解碼，得到可行解的步驟還可以包括以下步驟從相應子代貨物集中順次取出一待裝箱貨物，根據取出的所述待裝箱貨物信息計算取出的所述待裝箱貨物的體積；根據裝箱約束條件V' +Ii -Wi -h, < V判斷取出的所述待裝箱貨物是否可以裝入貨櫃中，其中，V'為已裝入貨櫃的貨物體積，Ii · Wi . h,為取出的所述待裝箱貨物的體積，V為貨櫃的有效容積；根據判斷結果，當判斷取出的所述待裝箱貨物可以裝入貨櫃中時，將取出的所述待裝箱貨物的體積累加到所述已裝入貨櫃的貨物體積V'中，當判斷取出的所述待裝箱貨物不可以裝入貨櫃中時，從相應子代貨物集中順次取出下一待裝箱貨物，當相應子代貨物集中全部待裝箱貨物取完或取出的待裝箱貨物的體積與已裝入貨櫃的貨物體積之和大於所述貨櫃的有效容積時，得到相應子代貨物集轉化後的可行解。其中，所述將多個初始貨物集對應的多個可行解構成的集合作為蟻群算法的輸入，利用蟻群算法迭代搜索得到所述待裝箱貨物的最優裝箱方案的步驟還可以包括以下步驟計算待裝載貨物的初始信息素；根據所述待裝載貨物的種類計算螞蟻數量，初始化蟻群算法的控制參數；隨機放置每隻螞蟻在每一可行解中待裝載貨物的初始位置上；根據所述待裝載貨物的質量約束、重心約束，判斷所述待裝載貨物中的螞蟻所在初始位置上的一類貨物是否可以裝入貨櫃中，並讀入所述待裝載貨物的重心坐標後，按放置方向約束對可以裝入貨櫃中的所述類貨物進行布局優化；根據狀態轉移概率搜索當前類待裝載貨物的下一類待裝載貨物，並根據搜索結果控制所述螞蟻置於所述下一類待裝載貨物上，根據所述待裝載貨物的質量約束、重心約束， 判斷所述待裝載貨物中的螞蟻所在位置上的一類貨物是否可以裝入貨櫃中，並按放置方向約束對可以裝入貨櫃中的所述類貨物進行布局優化；當對可行解的集合的一次循環搜索完成後記錄搜索結果，並根據信息素更新模型更新所述信息素，進行可行解的集合的下一次循環搜索，當循環次數與所述多個可行解的個數相等時，結束蟻群算法，輸出得到所述待裝箱貨物的最優裝箱方案。進一步地，所述計算待裝載貨物的初始信息素的步驟可以表示為τ Jj (0) = τ c+ τ G其中，τ u(0)為所述待裝載貨物的初始信息素，、為一預設的信息素常數，τ e滿足Tg = (Σ Ii .Wi .Vlj Ij .Hj) X 100%，Ii為第i類貨物的長度，Wi為第i類貨物的寬度，h為第i類貨物的高度；h為貨櫃的長度，W」為貨櫃的寬度，&為貨櫃的高度。進一步地，所述判斷所述待裝載貨物中的螞蟻所在初始位置上的一類貨物是否可以裝入貨櫃中的步驟，和/或判斷所述待裝載貨物中的螞蟻所在位置上的一類貨物是否可以裝入貨櫃中的步驟可以表示為
權利要求
1.一種三維貨櫃裝載布局優化的方法，其特徵在於，所述方法包括以下步驟對待裝箱貨物進行編碼，生成待裝箱貨物的多個初始貨物集，並利用遺傳算法生成所述初始貨物集的子代貨物集；計算子代貨物集中各個體的適應度值及其父代貨物集中各個體的適應度值，當子代貨物集中各個體的適應度值之和相對其父代貨物集中各個體的適應度值之和不再增加時，對相應子代貨物集進行個體解碼，得到可行解；將多個初始貨物集對應的多個可行解構成的集合作為蟻群算法的輸入，利用蟻群算法迭代搜索得到所述待裝箱貨物的最優裝箱方案。
2.如權利要求1所述的三維貨櫃裝載布局優化的方法，其特徵在於，所述利用遺傳算法生成所述初始貨物集的子代貨物集的步驟還包括以下步驟初始化遺傳算法控制參數；根據適應度函數計算所述初始貨物集中各個體的適應度值；根據計算得到的所述適應度值以及預存的變異概率，以所述初始貨物集為基礎進行選擇、交叉、變異迭代處理，得到所述初始貨物集的多個連續子代貨物集。
3.如權利要求2所述的三維貨櫃裝載布局優化的方法，其特徵在於，所述適應度函數滿足關係式F= (Ii · Wi · VLj · Wj · Hj) X 100%其中，F為適應度函數；li為第i類貨物的長度，Wi為第i類貨物的寬度，比為第i類貨物的高度；h為貨櫃的長度，Wj為貨櫃的寬度，Hj為貨櫃的高度。
4.如權利要求2所述的三維貨櫃裝載布局優化的方法，其特徵在於，所述選擇處理採用最優保存策略和輪盤賭選擇法，所述根據計算得到的所述適應度值以及預存的變異概率，以所述初始貨物集為基礎進行選擇、交叉、變異迭代處理，得到所述初始貨物集的多個連續子代貨物集的步驟還包括以下步驟根據計算得到的個體適應度值及最優保存策略和輪盤賭選擇法，確定所述初始貨物集中每個個體的選擇概率；根據確定的所述每個個體的選擇概率在所述初始貨物集內選擇兩個父個體；根據預存的變異概率對選擇的所述兩個父個體進行變異處理或交叉處理，將處理後的兩個父個體插入到所述初始貨物集的下一連續子代貨物集中，並計算所述初始貨物集的下一連續子代貨物集中各個體的適應度值；根據計算得到的當前子代貨物集中各個體的適應度值及最優保存策略和輪盤賭選擇法，確定當前子代貨物集中每個個體的選擇概率；根據確定的當前子代貨物集中每個個體的選擇概率在當前子代貨物集內選擇兩個父個體；根據預存的變異概率對選擇的所述兩個父個體進行變異處理或交叉處理，將處理後的兩個父個體插入到當前子代貨物集的下一連續子代貨物集中，從而迭代得到所述初始貨物集的多個連續子代貨物集。
5.如權利要求1所述的三維貨櫃裝載布局優化的方法，其特徵在於，所述對相應子代貨物集進行個體解碼，得到可行解的步驟還包括以下步驟從相應子代貨物集中順次取出一待裝箱貨物，根據取出的所述待裝箱貨物信息計算取出的所述待裝箱貨物的體積；根據裝箱約束條件V' +Ii -Wi-h^V判斷取出的所述待裝箱貨物是否可以裝入貨櫃中，其中，V'為已裝入貨櫃的貨物體積，Ii-W^hi為取出的所述待裝箱貨物的體積，V 為貨櫃的有效容積；根據判斷結果，當判斷取出的所述待裝箱貨物可以裝入貨櫃中時，將取出的所述待裝箱貨物的體積累加到所述已裝入貨櫃的貨物體積Ψ中，當判斷取出的所述待裝箱貨物不可以裝入貨櫃中時，從相應子代貨物集中順次取出下一待裝箱貨物，當相應子代貨物集中全部待裝箱貨物取完或取出的待裝箱貨物的體積與已裝入貨櫃的貨物體積之和大於所述貨櫃的有效容積時，得到相應子代貨物集轉化後的可行解。
6.如權利要求1所述的三維貨櫃裝載布局優化的方法，其特徵在於，所述將多個初始貨物集對應的多個可行解構成的集合作為蟻群算法的輸入，利用蟻群算法迭代搜索得到所述待裝箱貨物的最優裝箱方案的步驟還包括以下步驟計算待裝載貨物的初始信息素；根據所述待裝載貨物的種類計算螞蟻數量，初始化蟻群算法的控制參數；隨機放置每隻螞蟻在每一可行解中待裝載貨物的初始位置上；根據所述待裝載貨物的質量約束、重心約束，判斷所述待裝載貨物中的螞蟻所在初始位置上的一類貨物是否可以裝入貨櫃中，並讀入所述待裝載貨物的重心坐標後，按放置方向約束對可以裝入貨櫃中的所述類貨物進行布局優化；根據狀態轉移概率搜索當前類待裝載貨物的下一類待裝載貨物，並根據搜索結果控制所述螞蟻置於所述下一類待裝載貨物上，根據所述待裝載貨物的質量約束、重心約束，判斷所述待裝載貨物中的螞蟻所在位置上的一類貨物是否可以裝入貨櫃中，並按放置方向約束對可以裝入貨櫃中的所述類貨物進行布局優化；當對可行解的集合的一次循環搜索完成後記錄搜索結果，並根據信息素更新模型更新所述信息素，進行可行解集合的下一次循環搜索，當循環次數與所述多個可行解的個數相等時，結束蟻群算法，輸出得到所述待裝箱貨物的最優裝箱方案。
7.如權利要求6所述的三維貨櫃裝載布局優化的方法，其特徵在於，所述計算待裝載貨物的初始信息素的步驟表示為τ (0) = τ c+ τ G其中，Tu(O)為所述待裝載貨物的初始信息素，、為一預設的信息素常數，、滿足 Tg= (Σ Ii-W^hiZLj-Wj. Hj) X 100%, Ii為第i類貨物的長度，Wi為第i類貨物的寬度，Iii為第i類貨物的高度&為貨櫃的長度，Wj為貨櫃的寬度，Hj為貨櫃的高度。
8.如權利要求6所述的三維貨櫃裝載布局優化的方法，其特徵在於，所述判斷所述待裝載貨物中的螞蟻所在初始位置上的一類貨物是否可以裝入貨櫃中的步驟，和/或判斷所述待裝載貨物中的螞蟻所在位置上的一類貨物是否可以裝入貨櫃中的步驟表示為Cq = Σ g ^ G其中，Σ g為待裝載貨物中的螞蟻所在初始位置上的一類貨物的重量之和，和/或待裝載貨物中的螞蟻所在位置上的一類貨物的重量之和；G為貨櫃可裝載的貨物的重量之和；[cxl，cx2]、[cyl, cy2]、[czl,cz2]分別為貨櫃在x、y、z軸向的重心安全範圍的邊界值為待裝載貨物中的螞蟻所在初始位置上的第i類貨物的質量；(xi，yi, zi)是待裝載貨物的重心坐標。
9.如權利要求6所述的三維貨櫃裝載布局優化的方法，其特徵在於，所述狀態轉移概率表示為『τ/( ).η/( )P,-it) =Σ⑴ N allowedkzcdlowedotherwise其中力= i為啟發函數，dz(j)為待裝載貨物j的承重能力…是待裝載貨物j的體積；Hi/ (t)為螞蟻從待裝載貨物i搜索到待裝載貨物j的啟發程度；allowedk = (1， 2…n)-tabuk表示螞蟻k下一次被允許放置的待裝載貨物，tabuk為記錄了螞蟻k在t時刻已經搜索過而在本次循環結束前禁止再訪問的待裝載貨物的禁忌表；τ / (t)是貨物j上的信息素強度；所述信息素更新模型表示為 τ j(t+l) = P · τ j (t) + Δ τ j(t, t+1)mΑτ^ , + ^^Ατ^ , + Ι)k=\|fk(0第α只螞蟻在t循環時刻搜索到貨物j並將其裝入貨櫃 T]|o否則其中，+ 是螞蟻k在時刻(t，t+1)留在貨物j上的信息素量；(l-p)為信息素的揮發係數；fk(t)是螞蟻k在t時刻搜索到的貨櫃裝載率。
10. 一種三維貨櫃裝載布局優化的系統，其特徵在於，所述系統包括 子代貨物集生成模塊，用於對待裝箱貨物進行編碼，生成待裝箱貨物的多個初始貨物集，並利用遺傳算法生成所述初始貨物集的子代貨物集；適應度值計算模塊，用於計算所述子代貨物集生成模塊生成的子代貨物集中各個體的適應度值及其父代貨物集中各個體的適應度值；判斷模塊，用於判斷所述適應度值計算模塊計算得到的子代貨物集中各個體的適應度值之和相對其父代貨物集中各個體的適應度值之和是否增加；可行解輸出模塊，用於當所述判斷模塊判斷所述適應度值計算模塊計算得到的子代貨物集中各個體的適應度值之和相對其父代貨物集中各個體的適應度值之和不再增加時，輸出可行解；最優方案搜索模塊，用於將所述可行解輸出模塊輸出的多個可行解構成的集合作為蟻群算法的輸入，利用蟻群算法迭代搜索得到待裝箱貨物的最優裝箱方案。
全文摘要
本發明公開了一種三維貨櫃裝載布局優化的方法及系統。其中的方法是利用遺傳算法的隨機快速搜索能力、潛在並行性、全局收斂性在解空間內尋找一組粗略的可行解，之後以該組粗略的可行解作為蟻群算法的輸入，利用蟻群算法的正反饋機制、並行性和搜索較好解的能力求得裝箱的最優方案，從而實現了遺傳算法與蟻群算法在解決貨櫃裝載布局問題上的融合，避免了現有採用單一算法解決三維貨櫃裝載布局問題的缺陷，在兼顧全局搜索能力的同時，兼顧了影響裝載效率的幾個重要約束條件，可應用性好。
文檔編號G06N3/12GK102214321SQ20111019785
公開日2011年10月12日 申請日期2011年7月14日 優先權日2011年7月14日
發明者史金餘, 張德珍, 張維石, 杜立寧, 陳世峰 申請人:大連海事大學