現(xiàn)代軍事物流集裝箱單箱配載算法思考

李 峰，王亞玲，劉小平

（軍事科學(xué)院系統(tǒng)工程研究院 后勤科學(xué)與技術(shù)研究所，北京 100166）

0 引言

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

結(jié)合現(xiàn)代軍事物流集裝化運(yùn)輸保障特點(diǎn)，開展現(xiàn)代軍事物流集裝箱單箱配載問題研究，能夠?yàn)槲臆姮F(xiàn)代化物流保障的發(fā)展提供科學(xué)依據(jù)和理論支撐。

1 單箱配載典型求解算法文獻(xiàn)分析

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

1.1 基本啟發(fā)式算法文獻(xiàn)分析

基本啟發(fā)式算法可用于建立具有實(shí)際經(jīng)驗(yàn)的直接搜索策略和搜索規(guī)則以及基于這些規(guī)則的搜索解決方案，許多類似研究中都涉及到基本啟發(fā)式算法。

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

基本啟發(fā)式算法是解決集裝箱單箱裝載問題的一類基礎(chǔ)性重要算法，在存在約束的情況下，該算法能夠在可接受的計(jì)算時(shí)間內(nèi)提供比其他方法更快、更合理的解決方案，能夠?yàn)閷?shí)際問題解決提供較好的策略。其缺點(diǎn)主要是該算法需通過犧牲其運(yùn)算速度的最優(yōu)性、精確性或完整性來求解，且并不保證獲取的結(jié)果就是最優(yōu)解。

1.2 改進(jìn)啟發(fā)式算法文獻(xiàn)分析

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

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

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

2 存在的主要問題

2.1 最優(yōu)解科學(xué)性問題

盡管在解決單箱裝載問題的方法中，啟發(fā)式算法成為了一類主流解決方法，但是這些啟發(fā)式算法通常聚焦于提供更高的空間利用率。而在多數(shù)實(shí)際生產(chǎn)應(yīng)用場景中，空間利用率并不一定是最佳或重要約束目標(biāo)，往往需要同時(shí)處理多個(gè)具有不同權(quán)重的內(nèi)外約束，這一點(diǎn)仍然是困擾實(shí)際應(yīng)用場景中單箱裝載問題的關(guān)鍵。此外，從算法的科學(xué)性來看，集裝箱單箱裝載算法的科學(xué)性也難以達(dá)成一致，主要原因是沒有標(biāo)準(zhǔn)的統(tǒng)一數(shù)據(jù)集，結(jié)合實(shí)際問題進(jìn)行建模測試的案例相對較少，許多研究多局限于算法的探討與改進(jìn)上，難以進(jìn)行科學(xué)的橫向比較，也難以在實(shí)踐中檢驗(yàn)?zāi)Ｐ团c算法的有效性。約束條件、測試數(shù)據(jù)的差異，以及實(shí)踐檢驗(yàn)的不足，導(dǎo)致單箱裝載問題解決方法的科學(xué)性很難達(dá)成共識。

2.2 計(jì)算空間復(fù)雜度問題

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

2.3 現(xiàn)實(shí)應(yīng)用效果問題

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

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

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

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

3.1 軍事物流集裝箱單箱配載特點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在軍用集裝箱單箱配載問題研究中，應(yīng)在充分考慮物流集裝箱通用約束的基礎(chǔ)上，結(jié)合軍用集裝箱單箱配載的特點(diǎn)，根據(jù)軍事應(yīng)用需要引入系列專用約束，從而為相關(guān)模型與算法的設(shè)計(jì)提供科學(xué)性、實(shí)用性和高效性保障。

4 總結(jié)與展望

本文對國內(nèi)外集裝箱單箱配載問題進(jìn)行了深入研究，系統(tǒng)歸納并分類總結(jié)了當(dāng)前單箱配載問題的典型求解算法，指出了現(xiàn)有研究存在的共性問題。在此基礎(chǔ)上，明確了當(dāng)前軍事領(lǐng)域相關(guān)問題研究較少的現(xiàn)狀，同時(shí)結(jié)合軍事物流集裝化運(yùn)輸單箱配載特點(diǎn)，提出了在軍事領(lǐng)域研究該問題時(shí)的主要思路，即在通用約束的基礎(chǔ)上，需要引入軍事應(yīng)用帶來的專用約束，最后進(jìn)行了相關(guān)約束條件的分析，為后續(xù)研究者設(shè)計(jì)相關(guān)模型與算法提供思路和依據(jù)。

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