裝箱算法在卷煙配載驗證系統中的應用

王 瑋，張潔華，張菡子，李景舒，季靖寒

（上海煙草集團有限責任公司上海煙草儲運公司，上海 200439）

1 研究背景和意義

隨著上海煙草集團產銷規模的擴大，客戶對卷煙的需求朝著多樣化、小批量、多頻次和個性化方向發展，不僅花式煙品種規格增加，拼車訂單也逐年遞增，導致卷煙配載業務的復雜程度與日俱增。在卷煙單車配載環節，長期以來都是依賴人工經驗進行的，對于是否已經達到運輸車輛使用率的最大化、配載效益的最大化無從評估，同時這種配載方式強烈依賴員工的個人能力和經驗，不利于大規模推廣[1–2]。在面臨日益復雜的配載要求時，人工耗時變長，單車滿載率降低，若是導致翻箱，會極大浪費人力成本、時間成本。因此，有必要設計一種煙草配載驗證系統，根據煙草訂單信息、車輛信息以及各類件煙規格信息等，對人工設計的配載方案進行驗證并生成裝車圖，指導工作人員進行裝車，用于替代目前基于經驗的人工配載方式，達到有效減少裝車時間、提高裝車效率，提高單車滿載率和裝車一次成功率，從而達到降低物流成本，提高經濟效益的目的。

2 卷煙自動配載及驗證系統

卷煙自動配載及驗證系統可以根據煙草訂單信息、車輛信息、各類件煙規格信息等生成卷煙裝車圖，也可以輸入人工配載方案進行驗證并生成裝車圖，以指導工作人員進行現場裝車。系統功能框圖如圖1所示，文章重點介紹了配載驗證功能模塊中的卷煙裝車驗證算法。

圖1 卷煙自動配載及驗證系統功能框圖

3 卷煙裝車驗證算法

裝車驗證算法是對人工設計的配載方案，即人工選出需要運輸的貨物和運輸這批貨物的車輛，在正式運輸之前驗證其準確率，降低翻箱率。這在本質上是三維裝箱問題，給定一些不同類型的箱子和不同規格的容器，如何將所有的箱子裝入最少數量的容器中[3–4]。

裝車驗證算法的核心是啟發式擬人裝箱算法。解決這類利用計算機幫助人工或優化人工操作的實際問題，通常借鑒豐富的人工經驗，使計算機通過擬人的方式解決問題是非常有效的[5]。在實際的裝箱過程中，人們通常會在車廂內一角開始放置，先裝滿一行，再在一行的基礎上向上放置裝滿一面，最后從車廂內側到外側依次裝滿整個車廂。受人工裝箱方式的影響，在算法的裝箱過程中，通過設定初始放置點放置箱子，下一個箱子的放置位置通過查找放置點集合進行確定，并通過對放置點集合進行排序完成從車廂內側到外側的放置過程。

3.1 放置點

可以將車廂看成一個三維坐標系，將車廂內側右下角坐標（0，0，0）作為初始放置點并存入放置點集合，放置一個貨物后會生成3個新的放置點，并存入放置點集合中。設車廂的長寬高分別為H，W，D，貨物的長寬高分別為h，w，d，則生成的3個放置點分別為（h，0，0），（0，w，0），（0，0，d），如圖2所示。

圖2 貨物產生的三個放置點

因為需要將貨物按照從車廂內側到外側的順序放置，則需要對放置點集合進行排序。通過對放置點按照先y 軸從低到高，再z 軸從低到高，最后x 軸從低到高的順序完成對放置點的排序，完成實際的裝箱效果。

3.2 裝箱約束條件

3.2.1 方向約束

貨物在車廂內部一共有6種放置方向，但是根據人工的裝箱經驗，為了保證煙草在運輸過程中不會出現倒絲的現象，實際貨物的放置過程中只會出現4種方向，分別是方向1（h，w，d），方向2（w，h，d），方向3（h，w，d），方向4（d，h，w）如圖3 所示。方向1是將貨物的長邊作為h也就是長，而短邊作為寬w，這樣的放置方向可以保證車廂的寬度得到最大利用。當方向1放置貨物在車廂內長度無法滿足時，則使用方向2調轉貨物長和寬，使得車廂內的長度得到最大利用。當方向1放置貨物在車廂內高度無法滿足時，使用方向3或方向4，將貨物水平放置，使得車廂內的高度得到最大利用。

圖3 四種放置方向

3.2.2 重疊約束

每一個貨物的放置位置是根據之前放置貨物產生的放置點確定的。但是同一車廂內會運輸不同種類的貨物，其規格是不一致的。這樣貨物在放置過程中會出現間隙，從而導致計算機在放置貨物時會出現重疊的情況。如果兩個貨物沒有發生重疊，這兩個貨物之間的相交面的個數是0代表不相交或者是1代表相鄰放置，但是如果兩個貨物之間發生重疊，則這兩個貨物之間的相交面的個數一定會超過兩個。利用這一規則設計重疊檢測條件，當貨物之間的相交面個數小于等于1時允許放置，否則認為其相交取消放置。

3.2.3 懸空約束

計算機在計算貨物的放置位置過程中，某些放置點可能會因為貨物之間發生重疊或其他原因而取消放置，導致接下來的貨物可能會出現懸空的情況，這是違反實際物理條件的。因此，需要設置懸空檢測條件。通過計算放置點和貨物規格以及之前已經放置的貨物之間的高度信息來判斷貨物是否懸空，滿足條件則放置，否則會計算懸空貨物與其底部最近貨物之間的高度，在不違反約束條件的情況下將懸空貨物落到離其底部最近的貨物上。

3.2.4 行間約束

實際裝箱過程中因為貨物種類的不同，若兩種貨物之間不加以約束而直接根據放置點集合中的位置放置，會出現貨物放置位置混亂，車廂內空間利用率降低，不利于貨物的穩定運輸。所以需要設計行間約束條件，保證貨物放置過程中每一行的整齊。主要約束條件有，若下一批貨物的長度超過了其底下已經放置好的貨物長度，則會判斷貨物的寬度和其底下貨物長度之間的關系，若小于則按方向2進行放置，若還是超過底下貨物的長度則改變貨物的裝載順序，并且貨物的上方只能放置一件貨物，除非多件貨物的長度不會超過其底下的貨物。當貨物因行間y軸長度不一致發生貨物重疊的情況時，會記錄此時已經放置的貨物的y軸最大值和因重疊而無法放置貨物的放置點的x值，并依據這兩個值生成新的放置點存入放置點集合中，增大空間利用率，保證接下來貨物放置的整齊。

3.3 裝箱算法

基于上述放置點的生成方法和約束條件，可以得到用于配載驗證系統的三維裝箱算法。算法設貨物集合為B={b1，b2，…，bn}，放置點集合為items，其初始值為（0，0，0）用于確定第一個貨物的放置位置，算法的返回值是一個集合output 代表已經放置貨物在車廂內的坐標和貨物種類。算法流程圖如圖4所示。

圖4 裝箱算法流程圖

在該裝箱算法中，首先分別從貨物集合B 和放置點集合items 中取出需要的數據，之后根據取出的貨物bi（i ∈1，…，n）的規格以及放置點的位置判斷其在方向1的情況下能否裝入車內。若可以裝入則判斷貨物bi與其他貨物是否發生重疊，若發生重疊但是因為行間長度不一致導致的重疊則會根據行間約束規則生成新的放置點并存入集合，否則不對該放置點進行放置。若沒有發生重疊則判斷貨物bi是否懸空。若不懸空并且bi的長度小于其底部貨物的長度則在此放置點進行放置并生成新的放置點，再去除下一個放置點和貨物，判斷貨物集合是否裝完。否則按照相應的約束規則進行放置。若方向1無法放置貨物則判斷方向2是否可以裝入，若可以則判斷相關的約束條件是否成立執行操作，否則判斷方向3是否可以裝入。若3個方向都無法裝入貨物則該放置點不進行貨物放置，取出下一個放置點。當貨物集合全部裝完返回貨物在車廂內的坐標和貨物種類并存入output 中。配載驗證系統根據output 來繪制所需的裝車圖。

4 測試結果

使用兩天內的實際訂單裝車數據來進行配載驗證功能模塊的測試，部分測試結果如下表1所示，測試結果表明卷煙裝車算法可以成功驗證人工配載訂單。

表1 測試結果

5 結束語

文章設計了一套基于人工經驗的卷煙裝車驗證算法，裝車時可以充分利用車廂的長寬高，提高單車滿載率。通過配載驗證功能模塊可以對人工配載訂單進行驗證，從而提高卷煙裝車效率，保證裝車一次成功，杜絕翻箱現象。由于考慮裝車過車中卷煙的穩定性，導致貨物之間會產生一定空隙從而浪費一定的體積，因此該算法還需要進一步研究和優化。