三維裝箱問題研究現(xiàn)狀與展望

李威 王士乾

摘要：裝箱問題自1830年被提出以來就是學(xué)術(shù)界研究的重要領(lǐng)域，三維裝箱問題是裝箱問題中最復(fù)雜的一種。結(jié)合前人研究成果，將三維裝箱問題按照多層次進行了詳細(xì)的分類解讀。系統(tǒng)地整理了三維裝箱問題建模的三大要素：前提假設(shè)、目標(biāo)函數(shù)、約束條件。同時提出了求解三維裝箱問題的5類方法。統(tǒng)計了近年來幾十篇文獻(xiàn)，結(jié)合這些文獻(xiàn)，對上述的問題分類、建模要素、求解方法等做出統(tǒng)計。最后針對目前三維裝箱研究存在的問題和短板，為使三維裝箱問題的研究可以更好地與實際工程問題相結(jié)合，提出了三點展望。

關(guān)鍵詞：三維裝箱問題;多約束問題;多目標(biāo)問題;啟發(fā)式算法

中圖分類號：TP311? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2021）08-0204-02

1 背景

裝箱問題可追溯到1831年高斯研究布局問題，屬于復(fù)雜組合優(yōu)化問題，是NPC問題。在1980年前，多數(shù)研究針對一維、二維裝箱問題，1980年后，隨著低維裝箱問題研究成果積累和計算機技術(shù)發(fā)展，三維裝箱問題逐漸成為學(xué)術(shù)界熱門方向。三維裝箱問題在物資裝載、物流等行業(yè)都有應(yīng)用。研究三維裝箱問題，對提高運輸效率、降低運輸成本、提升企業(yè)盈利能力、減少污染物排放等都有著非常積極的現(xiàn)實意義。

2 三維裝箱問題國內(nèi)外研究現(xiàn)狀

2.1 三維裝箱問題分類

三維裝箱問題涉及領(lǐng)域廣泛，且與實際工程結(jié)合緊密且沒有統(tǒng)一的研究標(biāo)準(zhǔn)，故對三維裝箱問題的研究較為混亂，如國外文獻(xiàn)對裝箱問題的描述包括但不限于“Bin Packing Problem”“Container Loading Problem”“Nesting Problem”“Knapsack Problem”“Pallet Packing Problem”等，國內(nèi)的描述包括但不限于“裝箱問題”“集裝箱裝載問題”“貨物裝載問題”“考慮體積的背包問題”。為了規(guī)范和統(tǒng)一裝箱問題，Dyckhoff等[1]于1990年第一次對裝箱問題進行了分類，之后Gerhard W等于2007年進行了更為全面的分類。對于不同分類的問題，其研究方法不同。

2.2 按待裝物資類型分類

參照Gehring和Bortfeldt提供的分類方法，按照待裝物資間規(guī)格的差異性，將待裝物資分為三類：

1）同構(gòu)（Identical）物資：只有一種形狀規(guī)格的待裝物資，即所有待裝載的形狀規(guī)格完全相同。

2）弱異構(gòu)（Weakly Heterogeneous）貨物：有少數(shù)幾種不同規(guī)格的待裝物資，每種規(guī)格物資有一定數(shù)量。

3）強異構(gòu)（Strongly Heterogeneous）貨物：待裝貨物中有很多不同的規(guī)格，甚至所有待裝物資規(guī)格都不相同。

2.3 三維裝箱問題混合分類

結(jié)合了裝載目標(biāo)類型、待裝物資類型、容器特征類型等分類方式的一種重要的混合分類方式。結(jié)合Bortfeldt等[3]將裝箱問題14類，又增加1類，得到15個分類;其中輸入最小化表示，容器數(shù)量無限，待裝物資數(shù)量有限，裝箱問題的目標(biāo)為使用成本最小的容器;輸出最大化問題表示，容器數(shù)量有限，裝箱問題的目標(biāo)為盡量裝載更多的物資。

在這種分類方式下，算法有向左向上兼容性，如一個能解決MIKP問題的算法可解決SKP、MILOPP、SLOPP、IIPP問題。

3 三維裝箱問題建模方法

為三維裝箱問題建模時，需明確問題的前提假設(shè)、優(yōu)化目標(biāo)函數(shù)、約束條件，稱之為模型三要素。本章通過歸納梳理常見的三要素。

3.1 前提假設(shè)

假設(shè)行為是建模問題的前提，該行為可描述建模的環(huán)境，簡化問題復(fù)雜度，消除問題異議。三維裝箱問題中最常見的共性前提假設(shè)包括：

待裝物資和容器為立方體;容器內(nèi)任意位置對于物資時平等的;待裝物資的重心和幾何中心重合;物資是剛體，不會因為堆疊而變形，也不可擠壓變形;物資擺向需與容器邊平行或正交;物資間不可重疊;物資裝載不可超越容器邊界。

3.2 優(yōu)化目標(biāo)函數(shù)

從分類上說，輸入最小化和輸出最大化問題的目標(biāo)分別為使用容器成本最低和裝載物資價值最高。使用容器成本最低可指使用最少數(shù)量的容器，使用最小體積的容器，容器裝載率最高等;裝載物資價值最高可指裝載物資總體積最大、裝載物資總質(zhì)量最重、裝載物資價值最高。對于三維裝箱問題而言，最終的一般描述最優(yōu)裝載可由容器空間利用率、容器載重利用率表示。有時，為了搜索尋優(yōu)，會將重心約束導(dǎo)出的懲罰函數(shù)（重心偏移量）加入目標(biāo)函數(shù)中。常見的裝箱問題模型的目標(biāo)函數(shù)可描述為式（1）。

其中[uv、um、ug、uo=0 or 1]，表示目標(biāo)函數(shù)是否包含容器空間利用率、容器載重利用率、重心偏移量、其他參數(shù)，[α、β、γ、δ]分別表示各參數(shù)的權(quán)重。

3.3 約束條件

當(dāng)三維裝箱問題考慮實際約束時，涉及的約束條件多種多樣，復(fù)雜程度不僅相同。結(jié)合Bortfeldt等[3]的成果和最新文獻(xiàn)，將常見約束進行分類整理。

1）容器相關(guān)約束（Container-related Constraint）

容器載重約束（Weight Limit）：所有裝入物資總重小于等于容器載重量。

容器空間約束：所有裝入物資總體積小于等于容器空間

重心約束（Weight Distribute Constraint）：所有裝入物資整體重心在裝載要求重心范圍內(nèi)。

2）待裝物資相關(guān)約束（Item-related Constraint）

物資正交約束：物資（立方體）邊與容器邊正交或平行，一般都需要滿足，表示于假設(shè)中。

物資朝向約束（Orientation Constraint）：物資裝載只能朝向某些方向，有時成為旋轉(zhuǎn)約束或方向約束。

物資承重約束（Stack Constraint）：當(dāng)物資出現(xiàn)堆疊時，下層物資的承重能力大于等于其上部物資重量。

物資穩(wěn)定性約束：物資整體重心較低，整體傾斜一定角度時每件物資的重心落在支撐面上。

批物資相關(guān)約束（Cargo-related Constraint）

批物資完整性約束（Complete-shipment Constraint）：一批物資必須保證一件不落地裝載或一件都不裝載。

批物資分裝約束（Allocation Constraint）：一批物資需分解裝載不同容器中。

3）裝卸相關(guān)約束（Load-related Constraint）

裝載順序約束（Loading Priority）：物資按照一定順序裝載。

完全切割約束（Guillotine Cutting Constraint）：所有物資可通過垂直平面完全切割成很多塔式物資塊，每個物資塊可通過水平面完全切割成物資空間，這個約束主要考慮方便叉車裝卸工作。

裝載過程穩(wěn)定性約束（Stability Constraint）：裝卸過程中不出現(xiàn)物資懸空情況出現(xiàn)。

容器開口約束：容器開口朝向為裝卸出入口。

裝載技術(shù)能力約束（Complexity Constraint）：裝卸過程保證人員有一定活動空間，人員或機械擁有裝載能力。

4 三維裝箱問題求解方法

三維裝箱問題復(fù)雜度高，相較低維裝箱問題出現(xiàn)“組合爆炸”現(xiàn)象，精確求解算法較少，絕大多數(shù)算法都是近似算法，主要的方法包括降維法、構(gòu)造啟發(fā)式算法、智能啟發(fā)式算法、混合算法。

精確求解算法：主要指數(shù)學(xué)規(guī)劃方法，主要應(yīng)用于中小規(guī)模三維裝箱問題、少約束裝箱問題、同構(gòu)物資的裝箱問題。近年來僅在處理IIPP時，有學(xué)者使用精確求解算法，在處理更復(fù)雜問題時，基本很少使用精確算法。

降維法：三維裝箱問題僅在布局過程中就需要考慮三個方向的制約關(guān)系，算法實現(xiàn)較為困難，很多算法通過某些方法、假設(shè)將三維裝箱問題降維成低維裝箱問題，再通過上述算法解決。常見的降維思想有分層裝載思想、高度相同降維思想、裝載塔思想、物品不可堆疊降維等。

構(gòu)造啟發(fā)式算法：類比于二維裝箱問題中的近似算法，模擬人工裝載過程，由一系列規(guī)則構(gòu)成，包括物資定序規(guī)則，物資擺放規(guī)則，空間分割規(guī)則、空間合并規(guī)則等，通過不同規(guī)則的組合可導(dǎo)出不同算法。經(jīng)典的構(gòu)造法包括George和Robinson提出的“層”構(gòu)造思想和三空間劃分法，Gehring和Bortfeldt提出的“塔”構(gòu)造思想，往后諸多研究都是在這兩種思想基礎(chǔ)上改進的。常見的物資定序規(guī)則有：隨機順序、按裝載順序、按體積遞減、按重量遞減、按底面積遞減、最短邊遞減、最長邊遞減、最大穴度優(yōu)先、評估函數(shù)排序等。常見的擺放規(guī)則包括：占角規(guī)則、砌墻法、極點法、穴度法、先四周后中心規(guī)則等。常見的空間分割規(guī)則包括：各種形式的三空間劃分法、五塊布局法、核心堆法、對稱分割法。

智能啟發(fā)式算法：類比于二維裝箱問題中的元啟發(fā)式算法，主要包括一些隨機搜索方法和智能搜索方法。因為智能啟發(fā)式算法的通用性、魯棒性等特性，現(xiàn)如今遺傳算法[3]、禁忌搜索算法[5]、模擬退火算法、蟻群算法[4]、文化算法、煙花算法、改進分布估計算法等算法在三維裝箱問題中應(yīng)用廣泛。

混合算法是指將上述幾種方法結(jié)合起來的，如智能啟發(fā)式算法雖然具有良好的鄰域搜索能力，但是受初始值影響大，可使用構(gòu)造法或數(shù)學(xué)規(guī)劃方法求得初值，再輸入到智能啟發(fā)式算法中尋優(yōu)，可極大地提高算法效率;通過降維法將三維裝箱問題轉(zhuǎn)換為低維裝箱問題，再通過構(gòu)造法或智能算法求解?；旌纤惴梢跃C合多個算法的優(yōu)勢，抵消劣勢，在解決三維裝箱問題時十分常見。

5 結(jié)束語

目前很多對三維裝箱問題的研究通過前提假設(shè)和減少復(fù)雜約束簡化問題，若為了學(xué)術(shù)研究，簡化無可厚非，但是問題越簡化與解決方法與實際工程的聯(lián)系越松散，最終導(dǎo)致很多算法難以更好地應(yīng)用于實際工程。隨著智能算法的出現(xiàn)，解決多約束問題不再需要復(fù)雜的數(shù)學(xué)規(guī)劃思想，通過更好地定義與建模實際約束，并盡可能多地采納這些約束，減少不必要的前提假設(shè)，使算法更加實用，是研究三維裝箱問題的重要趨勢。

目前針對輸出最大化裝箱問題的研究遠(yuǎn)多于輸入最小化裝箱問題，且多數(shù)輸入最小化問題都在第一步做了降維運算或者直接簡單地將輸入最小化問題看作N個輸出最大化問題處理。雖然這樣簡化了問題，但是并未考慮實際使用中的均衡負(fù)載、批貨物完成性、分裝混裝等要求。研究能滿足這些需求的輸入最小化問題是未來三維裝箱問題重要的重要課題。

多目標(biāo)裝箱問題成為新的學(xué)術(shù)熱點，該問題更加與實際工程貼合，不再局限于單一目標(biāo)，而是追求多個平行或沖突的目標(biāo)。如有時需在穩(wěn)定性和容器利用率之間尋求平衡，或在滿足嚴(yán)格重心約束條件下尋求最大裝載效率，都是典型的多目標(biāo)裝箱問題。但多目標(biāo)裝箱問題文獻(xiàn)較少，處于研究初級階段，還需更多研究。

參考文獻(xiàn)：

[1] Dyckhoff H.A typology of cutting and packing problems[J].European Journal of Operational Research，1990，44：145-159.

[2] Andreas Bortfeldt，Gerhard W?scher.Constraints in container loading – A state-of-the-art review[J]. European Journal of Operational Research，2013，229（1）：1-20.

[3] 朱向，雷定猷.帶平衡約束三維裝箱問題的雙層混合遺傳算法[J].交通運輸系統(tǒng)工程與信息，2015，15（2）：203-209.

[4] 屈援，王雪蓮.有卸貨排序約束的集裝箱裝載問題及算法研究[J].計算機工程與設(shè)計，2008（7）：1789-1791.

[5] 袁軍良，熊偉清，江寶釧.混合二元蟻群算法求解集裝箱裝載問題[J].計算機工程與應(yīng)用，2010，46（36）：222-225.

【通聯(lián)編輯：謝媛媛】