基于啟發式算法的貨物裝配策略研究

藍機滿 （惠州工程職業學院，廣東 惠州 516001）

0 引 言

在一般貨物的二次流通的運輸環節中，貨物的裝配運送工作是中間最復雜、費時與費力最小的一部分，直接影響著各運輸相關部門間的協作活動的質量與時間成本。隨著運輸信息技術的不斷發展，貨物運輸工具的裝配設計方案將完全可以通過計算機仿真模擬來自動生成，并將以此直接指導裝配工作人員之間的裝配運送活動，以準確提升運輸貨物操作環節的協調效率和質量并最終達到降低成本的目的。

本文旨在試圖系統構建能自動生成車輛裝配運輸方案的算法，該自動算法可以實現將裝載貨物快準狠且有效安全地自動裝入車輛車廂系統中，而且可同時滿足任何給定的車輛車廂系統，自動裝配完車上所有余留的貨物。為了有效驗證該算法中生成的自動裝配工藝方案的整體可行性，本文利用了SharpGL圖形包來對生成工藝的整體方案的正確性做了進一步驗證，實驗最終結果表明，該算法可以較為合理、高效、經濟地設計完成自動化裝配。

國內學者提出了以下觀點：張游天等（2021）提出，在美國時下比較廣泛流行使用的對貨物進行自動化裝配問題的分類研究方法[1]；江峰等（2020）提出，大規模貨物列車，在運行階段需要通過編制啟發式的算法，對物流運輸方式進行優化整合[2]；王張峰等（2017）提出，基于啟發式算法的托盤貨物優化裝載方法，依據貨物數量進行自動裝配繼而將所有可能同時出現的車輛車廂的貨物進行自動化裝配[3]；鄭煒等（2016）提出，在貨物混裝模式中，可以通過啟發式的算法，對貨物裝載問題進行研究，提高貨物運輸質量[4]；宿偉偉等（2007）提出，多品種貨物混裝配載模型可以通過啟發式的算法，對貨物的運輸方法進行計算與整合[5]；徐海東等（2004）提出，啟發式算法在非滿載貨物運輸優化調度中的應用，需要通過對啟發式算法進行預判，進而優化物流運輸中的路徑，對風險起到一定的規避作用[6]。

1 貨物自動化裝配問題

1.1 貨物自動化裝配概述

貨物集裝箱的計算機自動化的裝配及設計問題，就是指怎樣利用現代工業計算機通過自動編程把各種型號、不同規格的一些大型特殊包裝貨物自動、合理、準確地安裝到專用車廂系統內的裝配系統方案。貨物方面的綜合裝配設計技術問題實際上已經不是某一類最原始、簡單的技術設計理論問題，而是由許多不同形式和種類各異的技術裝配和工藝問題所共同組成的關于裝配設計的綜合理論問題。根據不同層次的研究內容和約束限制條件，可以適當地將其研究細分為兩個不同階段的分支。貨物裝配最優化是一類多目標組合的優化完全問題，其理論本質仍然是NP-HARD問題，而目前解決NP問題的較為傳統的方法就是利用元啟發算法模式不斷地去找尋算法，不斷地在不同的空間中找尋最優解。

1.2 貨物自動化裝配問題的分類

一個三維空間的裝配問題是貨物的自動化裝配。近些年來有較多的分類方法。將裝配問題大致劃分為兩類：裝配多的車輛車廂問題；集裝箱車輛車廂問題。

1.3 貨物自動化裝配問題的技術難點

實際上，在運輸過程中，貨物的形狀、數量復雜，并且在整個貨物車廂的尺寸不確定的情況下，解決好對整體貨物的準確自動裝配，并且同時又要能滿足在貨物自動準確裝配作業時存在著的許多約束性條件和可控制性技術條件是當前面臨著的重要技術難點。

在實際進行貨物的組裝與擺放或運輸活動時，貨物可能就存在著以下7種不同類型的實際裝配、擺放及運輸活動狀態，在貨物的包裝結構的實際幾何形狀是長方體的情況下，仍然有6種不同類型的實際裝配狀態。見圖1。

圖1 長方體6種貨物擺放圖

2 核心算法

2.1 算法的基本思想

本文的目的主要是在求解貨物的自動裝配法約束原則下，尋求到一種以劃分平面理論為基礎的求解貨物在自動化裝配下的誤差的方法。將車廂的底部分為20個等面積的小格。如果想要提高自動化裝配系統的標準度，可將車廂劃分為若干個更多數量的小格子。

假設貨物的裝配層數要求為NumLayer，貨物將只有圖1所示的第一種和第二種放置狀態。將當前被選擇到的貨物號碼的長記為Li，寬記為Wi，高記為Hi；由原點出發，然后沿著X軸正方向不斷疊加查找，找到第一個空白小格子，再開始依次累加長，記小格子的累加長為Lsum，當Lsum≥Wi，從找到的第一個空白小格子的位置開始順著Y軸正方向依次不斷累加小格子的寬，直至到達車廂內的底面邊緣或小格子上已經填上順序編號，則停止累加。記小格子的累加寬為Wsum，當Wsum≥Li，就可以判斷出車廂長度與貨物長度之間的關系，在累加過程中，若不能同時滿足Lsum≥Wi、Wsum≥Li的條件時， 就需要變換到圖一貨物的放置狀態，經過不斷操作得出貨物高度小于車廂內高。

假設車廂內長為Lcarriage，寬為Wcarriage，高為Hcarriage。通過公式（1）與公式（2）將貨物放置狀態設置為圖 1 所示的第一種和第二種放置狀態時，單個貨物進行裝配時的一般約束條件為公式（1）（2）。

2.2 改進思想

上述計算模型提供了最終貨物裝配的另一個基本思路，但是算法仍然存在著以下三個顯著缺陷：算法在對最后的貨物和最終裝配的設計進行處理時，只先考慮了如圖1所展示的狀態；算法有貪婪性，讓算法無法實現最優解；在一定的車輛數量下，會要求其裝配貨物的數量、體積等，但是此算法下對此要求無法達到百分之百符合，而且還存在問題。啟發式的算法需要將貨物運輸的體積與運行方式計算進去，套用啟發式算法公式，對之后的模型建設進行相關處理，以提高物流運輸的效率。

3 實驗仿真與分析

3.1 實驗配置

本文作者擬嘗試選用一種基于微軟C語言平臺環境下所開發出的OpenGL函數庫仿真軟件SharpGL來仿真模擬以及對裝配的算法結果進行仿真模擬和驗證。SharpGL開發者們應該可以比較輕松地使用微軟視窗的Windows操作系統中的Forms或WPF，應用中能夠輕松實現使用OpenGL函數庫來開發出圖形可視化設計。借助SharpGL，可以保證在較短期范圍內迅速實現和建立出對裝配算法效果的模擬分析及仿真。

3.2 實驗結果

本實驗對算法進行了操作與驗證，該實驗具有三個約束條件如下：先尋找一批貨物和卡車，要求都為長方形，需要將給定貨物裝配到給定的車輛車廂中；貨物可以分為4類，其中第一、二、三類不可以混裝，第四類可以混裝；要求貨物底面接地，按照表1的車廂尺寸放置貨物，當 NumLayer 為 1 時，1 層就是貨物裝配 ，并且采用表2的貨物尺寸。表1和表2分別是給定的車輛車廂尺寸和給定的貨物尺寸。

表1 給定的車輛車廂尺寸mm

表2 給定的貨物尺寸mm

4 結 論

三維貨物中的裝配約束問題是另一個難以完全被有效的方法解決的NP-HARD問題，當對三維貨物中裝配的各種約束條件和限制條件都給定很多遍時，很難得到一個完全滿意的結果。

本文擬利用研究結果提出來另一種基于平面分割的設計算法方案，提供給廣大用戶一種基于集裝箱貨物的自動化裝配的算法方案，但研究發現目前本方法設計及算法模型設計仍存在很多局限，如尚不能很充分合理地利用車廂內的面積和空間，對于各種異構貨物集裝箱的自動裝配，尚還不能很充分地滿足車廂空間布置需求以及實現集裝箱貨物自動化裝配系統的基本約束條件和設計條件。基于存在的各種問題，本文已分別提出了對其改進的舉措和一些新想法，預計今后將會在進一步的研究調查工作中給出一些相關的數據以支持和證明。