李威 王士乾

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

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

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

文章編號(hào)：1009-3044（2021）08-0204-02

1 背景

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

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

2.1 三維裝箱問(wèn)題分類

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

2.2 按待裝物資類型分類

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

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

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

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

2.3 三維裝箱問(wèn)題混合分類

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

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

3 三維裝箱問(wèn)題建模方法

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

3.1 前提假設(shè)

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

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

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

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

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

3.3 約束條件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

容器開(kāi)口約束：容器開(kāi)口朝向?yàn)檠b卸出入口。

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

4 三維裝箱問(wèn)題求解方法

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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

參考文獻(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] 朱向，雷定猷.帶平衡約束三維裝箱問(wèn)題的雙層混合遺傳算法[J].交通運(yùn)輸系統(tǒng)工程與信息，2015，15（2）：203-209.

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

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

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