現代軍事物流集裝箱單箱配載算法思考

李 峰，王亞玲，劉小平

（軍事科學院系統工程研究院 后勤科學與技術研究所，北京 100166）

0 引言

現代軍事物流集裝箱單箱裝載問題主要是解決一定約束條件下軍用物資集裝箱的裝載順序和裝載位置問題，其合理性直接關系集裝箱運輸成本以及軍用物資運輸保障效率。在研究領域，通常把這一類問題歸結為幾何分配問題，即滿足基本幾何可行性條件下對目標函數的優化[1]，但在軍事領域因時間性、對抗性、彈藥物資特殊性等要求，約束條件相對更為復雜，相關研究很少。

結合現代軍事物流集裝化運輸保障特點，開展現代軍事物流集裝箱單箱配載問題研究，能夠為我軍現代化物流保障的發展提供科學依據和理論支撐。

1 單箱配載典型求解算法文獻分析

集裝箱單箱配載問題在計算機領域常被視為組合優化問題，需要尋找最優編排、分組或篩選策略等，以求解最優解。盡管近年來精確算法和近似算法的開發取得了重大進展，但在算法領域，求最優解的計算量與存儲空間的增長速度隨問題復雜性的增強而增大，通常會導致所謂的“組合爆炸”問題，需運用啟發式算法來求解此類問題。根據求解結果空間的普遍性或特殊性，解決集裝箱單箱配載問題的啟發式算法大致可分成基本啟發式算法和改進啟發式算法。

1.1 基本啟發式算法文獻分析

基本啟發式算法可用于建立具有實際經驗的直接搜索策略和搜索規則以及基于這些規則的搜索解決方案，許多類似研究中都涉及到基本啟發式算法。

Terno，等[2]研究了托盤等的裝載問題，在滿足一系列實際限制條件的基礎上尋求最佳空間利用率的理論目標，考慮了一般的分支和邊界框架，并針對多托盤裝載問題開發了一種有效的啟發式方法，最后用計算實驗表明了所提算法的有效性。Bischoff，等[3-4]針對所涉及的貨物承載強度約束相關集裝箱裝載問題，提出了一種新的啟發式方法，要求集裝箱裝載規則必須確保放置在物品上的重量保持在可以承受的最大重量之下，而不會被壓碎損壞，該啟發式算法可被嵌入到搜索算法中以尋求優化裝箱過程的參數設置，同時實驗結果表明，在不考慮承載強度時該算法結果也表現較好。Egeblad，等[5]提出了一種按照最大利潤總和作為最終約束條件來確定可裝載到給定尺寸的集裝箱中的物品組合模型，其實例包含多種不同物品，為解決這個復雜問題，其先后應用了一組啟發式算法，每個方法都解決了一部分問題，并將大型物品組合成特定的結構，以確保在運輸過程中對物品進行適當的保護并簡化了問題模型，最后驗證得出該啟發式方法生成的解決方案的平均加載利用率為91%，達到了預期目的。閻威武，等[6]提出了一種三維集裝箱裝載的啟發式算法，此算法采用了三維空間分割法、平均高度裝載、貨物合并、空間合并等策略，通過逐步排除較差的裝載方案得到滿意的裝載方案，最后通過實例仿真說明了該算法的有效性和實用性。

基本啟發式算法是解決集裝箱單箱裝載問題的一類基礎性重要算法，在存在約束的情況下，該算法能夠在可接受的計算時間內提供比其他方法更快、更合理的解決方案，能夠為實際問題解決提供較好的策略。其缺點主要是該算法需通過犧牲其運算速度的最優性、精確性或完整性來求解，且并不保證獲取的結果就是最優解。

1.2 改進啟發式算法文獻分析

為了解決上述問題，找到全局或近似最優解，研究人員在此基礎上提出了一類更為高級的啟發式算法：改進啟發式算法。改進啟發式算法是一種結合了基本啟發式算法與鄰域搜索算法的混合算法，主要包括遺傳算法、貪婪自適應算法、禁忌搜索算法和模擬退火算法等。

Gehring，等[7]設計了一種遺傳算法（GA）用于解決具有不同尺寸的長方體和單個集裝箱的裝載問題，該算法采用復雜數據結構表示裝載策略，并使用基于綜合貪婪啟發法的特定遺傳算子生成遺傳算法的后代，最后通過測試證明了GA的良好性能，結果表明該算法尤其適用于強異構類物品的裝載場景。Alonso，等[8]設計了一種混合啟發式算法來解決集裝箱單箱裝載問題，并將它們組合成了GRASP（貪婪隨機自適應搜索）算法，該算法由一個建設性階段和一個反應性階段組成，能夠根據不同的情況選擇最適合的啟發式方法，其中還新采用了系列算法改進方法，最后通過測試表明其模型與算法取得了較好的實驗效果。屈援，等[9]采用了禁忌搜索算法求解多約束集裝箱裝載問題，該算法基于自然數編碼規則設計了貨品放置規則和序列產生方式，根據所設定的兩種不同鄰域構造了兩種禁忌表，其采用的算例實驗結果體現了該禁忌搜索算法對優化多約束集裝箱裝載問題的有效性。張德富，等[10]提出了一種用于求解三維集裝箱裝載問題的混合模擬退火算法，該算法引入了基于塊裝載的基礎啟發式算法，將可行的裝載方案編碼成裝載序列，然后使用模擬退火算法在編碼空間中搜索近似解，接著通過并行化技術對算法進行了進一步優化，最后通過測試表明混合模擬退火算法的空間利用率較高。

與基本啟發式算法相比，改進啟發式算法是一種更高級別的指導搜索過程的策略，可以提高啟發式過程的效率，可以使用較少的計算量、有限的計算時間和內存找到優化問題的近乎全局最佳的解決方案。此外，改進啟發式算法對優化問題的提出沒有任何要求（例如，要求約束和目標函數表示為決策變量的線性函數等）。近年來理論研究或實踐應用領域多采用改進啟發式算法來解決集裝箱單箱裝載問題。然而，該算法的靈活性導致其通常需要進行大量針對特定問題的設計和調整，才能達到更好的性能，對具體應用方面的要求相對較高。

2 存在的主要問題

2.1 最優解科學性問題

盡管在解決單箱裝載問題的方法中，啟發式算法成為了一類主流解決方法，但是這些啟發式算法通常聚焦于提供更高的空間利用率。而在多數實際生產應用場景中，空間利用率并不一定是最佳或重要約束目標，往往需要同時處理多個具有不同權重的內外約束，這一點仍然是困擾實際應用場景中單箱裝載問題的關鍵。此外，從算法的科學性來看，集裝箱單箱裝載算法的科學性也難以達成一致，主要原因是沒有標準的統一數據集，結合實際問題進行建模測試的案例相對較少，許多研究多局限于算法的探討與改進上，難以進行科學的橫向比較，也難以在實踐中檢驗模型與算法的有效性。約束條件、測試數據的差異，以及實踐檢驗的不足，導致單箱裝載問題解決方法的科學性很難達成共識。

2.2 計算空間復雜度問題

集裝箱裝載問題進行模型抽象后是一個計算機領域典型的NP問題，在求解此類組合優化問題時，每一個可行的解（即“合理的解”）都有一個關聯的值，但找出一個具有最佳值的可行解的計算空間卻較為復雜。根據所要解決的問題，最優解可以定義成具有最大可能代價的解或具有最小可能代價的解，即該問題可能是最大化問題，也可能是最小化問題。對于很多問題，已經設計出具有較小的固定近似比的多項式近似算法，然而對于一些復雜度稍高的問題，在其已知的最佳多項式近似算法中，近似比是輸入規模的函數，當輸入規模增大時，其計算復雜度也會隨之幾何倍增加。集裝箱裝載問題在模型構建和算法求解時，也會因為約束條件的數量、單個約束條件的權重等增加，帶來計算空間復雜度的指數增長問題。

2.3 現實應用效果問題

現有的集裝箱單箱裝載相關研究考慮的問題類型及約束條件較少，通常僅考慮方向性、穩定性及矩形物品的裝載模型，很少針對多種實際約束及組合類型的情形（如長方體和圓柱體或其它不規則物體混載），且大多為了研究方便或為了降低算法的復雜度，而預置一些假設條件或進行較大幅度簡化。例如，Pisinger，等[11]設定裝載對象為長方體，且在垂直和水平方向上都只能使用單一方向，即所有長方體不能旋轉；Maculan，等[12]假設所有裝載物體均為矩形且密度相同，并且其重量與體積成正比。而有些研究者雖然考慮到了一些特定的實際約束，但卻未能真正將其融入到算法設計中；Junqueira，等[13]雖將裝載優先級描述為重要的約束條件，但在集裝箱單箱裝載算法的設計中卻沒有將這一影響因子融入算法流程；Ratcliff，等[14]雖然提到可以通過調整目標函數中的系數來處理相對優先級的情況，但也未將這種很重要的約束條件引入算法等。約束條件的簡化、前提條件的假設預置，導致對單箱裝載相關算法的討論多數停留在理論研究層面，或者僅起到一定的輔助支撐作用，實際應用效果和價值難以體現。

2.4 軍用集裝箱裝載的特殊性問題

集裝化運輸作為現代軍事物流的關鍵組成，對軍事物流發展具有重要的推動和拉動作用，但針對現代軍事物流集裝化運輸單箱配載問題的相關研究還相對較少，相關描述還僅停留在理論探討層面，對模型的設計抽象、軍用集裝箱的特點提煉不夠充分，相關算法研究還處于空白，整體上落后于民用或商用領域。在軍用集裝箱單箱裝載問題的研究上，應在充分借鑒國內外學術研究成果的基礎上，著重針對軍用集裝箱裝載問題的特殊性，提煉適合于軍事應用場景的多組綜合約束條件。例如：軍用集裝箱體積、重量及負載平衡，軍品完整性、定位、方向、堆疊、加載優先級、穩定性及復雜性等系列約束等，以及軍事高對抗條件下各類約束條件的權重系數、快節奏軍事打擊時間窗約束條件下的非關鍵性約束條件裁剪問題等[15]。

3 軍事物流集裝箱單箱配載問題求解思路

3.1 軍事物流集裝箱單箱配載特點

在現代軍事物流集裝化運輸單箱配載問題研究中，需要在通用的基礎上把握其專業性。與常見的單箱配載算法相比，其專業性特點主要有：

（1）模型與算法對空間利用率及裝載時間權重要求更高。在軍事演習、救災搶險等任務中，軍用物資供應通常具有保障時間緊、任務密集等特點，因而軍事物流集裝箱單箱配載作業目標成為使用最少的箱子裝配更多的物資，并要在最短的時間內完成物資的配載，即這兩種要求應同時滿足，這就對模型和算法所涉及的策略提出了新的要求，需要綜合考慮不同的因素來求解更為科學的裝載方案。

（2）集裝對象形狀種類等屬性差異更大。在軍用集裝箱單箱裝載作業中，同一箱體需要裝載的軍用物資種類往往并不局限于一種，且這些物資的形態可能并不是長方體型，帶來了諸如非長方體物品放置方向、穩定性等特殊差異，同時還要考慮不同物品的堆疊極限等。這些特殊的約束條件在一個模型或算法中完成，通常具有較為復雜的計算復雜度，受限于短時間內求解最優模型，需要在約束條件裁剪和實用價值之間做出均衡。

（3）集裝對象組套裝載要求更為明顯。軍事集裝化對象多數具備典型的組套特征。例如：槍支和彈藥、炮彈和發射架、帳篷和支架等。這類物資通常為了取得更好的集裝化效果，會被拆解為空間利用率更佳的集裝方式，在到達目的地后再進行組套拼裝，因而不允許不完整的裝載現象發生。因而在軍事物流集裝化運輸中，單箱配載必須要考慮集裝對象的組套裝載帶來的約束條件，不能單方面僅考慮空間利用率和時間窗條件約束，這將為相關模型與算法設計帶來新的挑戰。

3.2 軍用集裝箱單箱配載問題求解約束條件

3.2.1 考慮物流集裝箱通用約束

（1）重量、體積約束。在軍用集裝箱單箱裝載中應充分考慮重量、體積限制且將其視為硬約束，即已裝載軍用物資的重量、體積總和必須小于或等于集裝箱施加的重量、體積限制，且在集裝箱裝載算法中應首先檢查該約束條件是否滿足來減少模型計算的復雜度。

（2）載重平衡約束。載重平衡約束是要求貨物的重量盡可能均勻地分布在整個集裝箱底板上，在集裝箱運輸過程中，不平衡的負載可能導致軸重的分布不可接受，或野外路況條件下的箱體側翻等問題。為了獲得均衡的重量分布，需控制負載的中心盡可能地靠近負載的重心，且與集裝箱底部的幾何中點偏差值在一定的范圍之內。

3.2.2 引入軍用集裝箱單箱裝載專用約束

（1）組套約束。在單箱配載問題中，模型與算法輸出值的最優化要求必須以最佳方式裝載容納配載對象。然而，在實際中會由于沒有足夠的集裝箱空間而不可避免地剩下一些物資，在這種情況下，如果裝載了物資的某些子集的一項，則必須裝載該子集的所有其它項，如果無法裝載其中一項，則子集中的任何物品都不可被裝載。如前文所述，在軍用集裝箱配載過程中，組套特性更加突出，必須優先考慮。

（2）定位約束。定位約束以絕對或相對的方式限制軍用集裝箱中特定軍用物資的裝載位置。絕對定位約束要求將某些物資放置（或不放置）在集裝箱的特定位置或特定區域中，這種限制通常是由尺寸、重量或者軍品的類別等決定的，例如較重較大的物資或需要優先卸載的物資通常僅在位于集裝箱門旁邊時才方便裝卸。相對定位約束需要將某些軍品的子集緊密放置在集裝箱中，或者至少位于彼此之間一定距離內，例如那些需同時同地交付的物資，就需要引入該種約束，在裝載過程中緊密放置該類物資子集，將有助于提升裝卸效率并降低出錯率。另一方面，相對定位約束也適用于要求某些子集物資不被放置為彼此相鄰或不允許緊密相鄰的情況，例如對彼此質量有負面影響的物資（如炸藥和汽油，食品與易沾染化工品等）不應被相鄰放置。

（3）方向約束。為了防止物資和包裝被損壞或確保負載的穩定性，需引入垂直方向約束。理論上裝入集裝箱的立方體的每個尺寸都可以視為高度，從而產生三個垂直方向，通過選擇特定尺寸作為高度，可以定義立方體的垂直方向，然后在僅允許正交裝載模式的情況下，可以通過兩個水平方向將長方體水平對準集裝箱壁，但方向約束通常將立方體的垂直方向限制為一個尺寸，因此在實際裝載過程中，可能無法使用所有可能的垂直方向，需根據軍品類型及穩定性等情況對其進行方向約束。除了限制長方體的垂直方向外，還可引入水平約束，例如雙向入口軍用托盤必須由叉車裝載，并且只能從特定側及其相對側這兩個側面接近。在軍用集裝箱單箱裝載過程中，方向約束是最常見的約束類型之一，因多數軍品放置要求方向性，因而這一條件應被視為硬約束。

（4）堆疊約束。為避免損壞物資和包裝，通常會引入堆疊約束。這主要是由物資本身及包裝有限的承載強度引起的，針對長方體的有限承載強度，可采用以下幾種堆疊處理方式：在較少限制的情況下，可以將物資分為易碎箱和不易碎箱的子集，在軍用集裝箱單箱裝載作業時，不易碎的長方體只能放在其它不易碎的長方體上，而不能放在易碎的長方體上，而易碎的長方體可以放在不易碎的長方體和其他易碎的長方體上。另一種方法是禁止將特定的長方體類型放置在另一種類型的長方體上面，例如禁止將較大的長方體放在較小的長方體上，需將較重的物品放置在較輕的物品下面，將較高密度的物品包裝在較低密度的物品下面等。

（5）裝載優先級約束。由于存在集裝箱可用空間不足以容納所有軍品的情況，因此在實際設計中需要確定哪些軍品是必須裝載的，以及哪些軍品是可以被放棄裝載的。這樣的優先級通常由軍品需求的迫切度、供應保障時間窗等特殊要求而產生，例如彈藥的優先級通常要明顯高于野戰食品，而在前方彈藥充足食品匱乏時，野戰食品的優先級也可能會更高。如果將裝載優先級視為硬約束，則除非集裝箱中已容納所有高優先級對象，否則低優先級的對象不得包括在裝載方式中，而如果是軟約束，則可以通過調整目標函數中的系數來靈活處理。

（6）復雜性約束。復雜性約束通常是由集裝箱裝卸工具等引起的，即模型與算法求出的最優解可能會因為裝卸手段不足，而難以在實際中應用。在軍事應用中，由于野外各類輔助條件受限，這種約束體現得更為明顯，若忽視了該項約束極有可能出現裝不進去或卸不下來的情況。可采用自動裝載模式，即配備與集裝箱或托盤底座平行的智能化機器手，舉起軍品箱子并將其放到集裝箱中指定位置，或者采用更先進的機械設備和自動包裝/裝載技術來應對復雜的集裝箱物資裝載作業場景。這種外在輔助條件帶來的實際復雜性約束，在軍事對抗場景中，應將其視為硬約束。

在軍用集裝箱單箱配載問題研究中，應在充分考慮物流集裝箱通用約束的基礎上，結合軍用集裝箱單箱配載的特點，根據軍事應用需要引入系列專用約束，從而為相關模型與算法的設計提供科學性、實用性和高效性保障。

4 總結與展望

本文對國內外集裝箱單箱配載問題進行了深入研究，系統歸納并分類總結了當前單箱配載問題的典型求解算法，指出了現有研究存在的共性問題。在此基礎上，明確了當前軍事領域相關問題研究較少的現狀，同時結合軍事物流集裝化運輸單箱配載特點，提出了在軍事領域研究該問題時的主要思路，即在通用約束的基礎上，需要引入軍事應用帶來的專用約束，最后進行了相關約束條件的分析，為后續研究者設計相關模型與算法提供思路和依據。

在現代軍事物流集裝化運輸中，因其應用場景、對抗強度、軍品特殊性等外在條件的變化，帶來了單箱裝載問題的復雜化，相應的建模與求解復雜度將同步提升，對于實際約束條件的系統集成與模型算法設計將是一個集科學性和實踐性于一體的難題，而當前能夠綜合解決該類問題的研究還難以見到，未來可在此方向展開更為系統和詳細的研究。