張游天 金辰禹 劉漢威 吳珊

[摘要]根據(jù)三維裝箱問題的特點，考慮貨物存在不同的擺放方式、集裝箱剩余空間最大利用率等多項影響因素建立了貨物空運裝配多目標約束模型，采用以遺傳算法和模擬退火算法為主的混合啟發(fā)式算法運行求解，快速制定出貨物的裝載布局方案，有效解決了在多約束下的貨物空運裝配策略問題。

[關鍵詞]三維裝箱問題;模擬退火算法;遺傳算法;貨物裝運;空運;裝配策略

[中圖分類號]F560.8[文獻標識碼]A[文章編號]1005-152X（2021）12-0070-08

Air Cargo Loading Strategy Based on Hybrid Heuristic Algorithm

ZHANG Youtian1，JIN Chenyu1，LIU Hanwei2，WU Shan3

（1. School of Economics & Management，Dalian Jiaotong University，Dalian 116028;

2. School of Mathematics & Computer Application Technology，Jining University，Jining 273199;

3. School of Transportation & Logistics Engineering，Wuhan University of Technology，Wuhan 430070，China）

Abstract：In this paper，according to the characteristics of the three-dimensional packing problem，and considering the various factors such as placement of goods，and the maximum utilization of the remaining space of the container，etc.，we established a multi- objective constraint model of air cargo loading，used a hybrid heuristic algorithm mainly consisting of the genetic algorithm and simulated annealing algorithm to solve it，and for the purpose to quicken cargo loading layout planning，effectively dealt with the problem of air cargo loading strategy under multiple constraints.

Keywords：three- dimensional packing problem;simulated annealing algorithm;genetic algorithm;cargo loading and shipment;air transportation;loading strategy

0引言

隨著全球貿易自由化與物流業(yè)的快速發(fā)展，航空貨運進入了蓬勃發(fā)展階段。航空貨運相對于集裝箱運輸?shù)某杀靖偁幜涂煽啃杂兴岣?，空運相對于海運的平均價格已大幅度下降。國際航空運輸協(xié)會（IATA）日前發(fā)布的全球航空貨運定期報告預測顯示，貨運強勁的表現(xiàn)將會持續(xù)。為滿足不斷增長的航空貨運需求，實現(xiàn)高質量的集裝箱裝載是目前急需解決的問題。研究貨物的裝載優(yōu)化問題，對提高空間效率、節(jié)約運費、規(guī)范作業(yè)等有著積極的現(xiàn)實意義。

貨物空運裝運策略問題屬于三維裝箱問題（Three Dimensional Container Loading Problem，3D- CLP），應用面廣，專業(yè)性較強，同時也屬于NP-hard問題[1]。根據(jù)提供的數(shù)據(jù)和要求不同，三維裝箱問題可以分成箱柜裝載問題、背包裝載問題以及容器裝載問題。而一般在運輸過程中存在不同規(guī)格箱柜裝載問題、柔性集裝箱問題以及裝運最佳利潤問題等，所以三種問題均有涉及，模型程序較為繁瑣，且不同種類的貨物量較大，因此在有限的時間范疇內可以獲得問題的最優(yōu)近似解而難以獲得精確解。

1問題描述

1.1航空貨物運輸策略描述

在航空貨物運輸?shù)臏蕚潆A段，由于存在各類不同的機型以及內部構造，差異性較大，因此將該因素考慮在三維裝箱問題范圍內，視為規(guī)格不統(tǒng)一的箱柜裝載問題。且由于貨運飛機在空中飛行時受到力學因素的影響，前、中、后艙需要保持一定載重比例，為了方便計算，需把各機型的貨艙分離開來，將同機型的貨艙看為有一定比例關系的獨立箱柜，因此需要考慮其存在的間隙以及是否超重。

由于貨物形態(tài)多種多樣且毫無規(guī)律，為了方便規(guī)劃裝配，假設將其包裝為長方體，將貨物視為長方體安排裝配。貨物為長方體，因此需要決策其擺放方式，選擇將長寬面朝下、寬高面朝下或長高面朝下。此外，由于貨艙之間存在著連接關系，貨艙互相受到約束無法自由轉動，所以需要貨物的擺放轉動來確定貨物在貨艙內的狀態(tài)，因此貨物的擺放狀態(tài)有六種方式，如圖1所示。

一般情況下貨物會從某角落開始擺放，如圖2所示，由于重力影響需要從下往上進行擺放，且需要考慮其重心的穩(wěn)定性，其重心點要落在承重貨物的上方而非懸空，如圖3所示。

在該類問題中，為了提高裝運貨物的裝卸空間效率、貨物安全程度等，加入集裝箱元素，集裝箱作為裝運容器可以很好的將小型貨物整理入內并進行裝運，以此提高貨運飛機的整體效用。集裝箱分為普通集裝箱和柔性集裝箱。增加集裝箱后，需要集裝箱內的小型貨物也按照上述的規(guī)則進行排列[2]，考慮其擺放方式、重心位置等，需要先挑選出符合小體積條件的貨物，在集裝箱內部進行排樣，裝運完成后將集裝箱看為整體再在貨艙內繼續(xù)按約束擺放，如圖4所示。

在此基礎上，考慮到貨物的價值和效益問題，空運貨物的費用較高，難以持續(xù)、及時的供應貨物，因此存在著貨運周期。為了適當降低組織貨源數(shù)量帶來的風險，供應商一般會設置可靠性，將其設置為固定的百分比數(shù)值，從而預測利潤最大值以及選擇合適的裝運策略。

1.2問題假設

（1）貨物裝載順序約束。考慮到重力的影響，貨物需要從最底層開始裝，不存在直接放置在懸浮狀態(tài)或頂部，盡量呈垛型擺放。

（2）貨物需要考慮其重心狀況，以免出現(xiàn)重心懸浮等違反物理常識的現(xiàn)象，并設定所有貨物均為質量均勻的長方體且不會變形。

（3）假定所有貨物具有很強的承重能力。

（4）貨物在裝載完成后至重新開艙取貨之前不會存在任何移動，即忽略飛機斜度、慣性、摩擦力減小等任何會讓貨物移動的情況。

（5）貨物與飛機的貨艙之間呈正交分布，即各邊與相應的貨艙面對應平行。

2問題分析及模型建立

2.1貨運飛機內貨艙的裝運策略分析

假設某個進出口公司需要將貨物運到目的地進行銷售，該公司去航空公司求助運輸業(yè)務。航空公司現(xiàn)有大、中、小三種類型的貨運飛機，且每種貨運飛機都分為前、中、后艙，每個貨艙都可以裝載一定的貨物，但其容積和載重是有限制的?？紤]到飛機飛行過程中的安全和平穩(wěn)，三個貨艙中的貨物需要成一定比例來裝載，以免出現(xiàn)“頭重腳輕”等情況。不同類型的貨運飛機的貨艙情況不同，需要選擇合適的裝運策略以盡可能地提高各自的貨艙空間利用率，且不考慮貨物裝完，只裝入部分貨物即可。本文考慮到貨物存在不同的擺放方式，因此將各種類的所有貨物進行編號，每一件貨物都有其表達式，將各貨艙的利用率之和作為目標函數(shù)，限制各個貨艙的承重和體積，并考慮同一架貨運飛機內各艙之間的載重盡量符合承重比率以維持穩(wěn)定，并將誤差設為0.1，建立相關模型。

為了方便更好地建立模型，將飛機各貨艙進行分割，大、中、小三種類型飛機的前、中、后三個貨艙分離并編號為p，其中p₁為大型貨運飛機的前艙，p₉為小型貨運飛機的后艙。具體貨艙編號如圖5所示。

設需要載運的貨物共有N種，且每種貨物的編號為第n₁，n₂，…，n_n件。

2.1.1目標函數(shù)。模型的目標是實現(xiàn)各類貨物在三架飛機貨艙內裝載后的空隙盡可能小，即在三架飛機貨艙的總空間利用率最大，因此構建如下優(yōu)化模型：

2.1.2約束條件

（1）貨物在貨艙內的體積和質量約束。為了防止其貨物在單個貨艙內質量大于其貨艙的載重量，或其貨物的體積大于其貨艙的最大容積，約束如下：

其中，M_p和V_p分別表示第p個貨艙的最大承重量和容積。

式（4）表示x方向即長度的約束，式（5）表示y方向即寬度的約束，式（6）表示z方向即高度的約束。

（3）重心約束。為了確保貨物的重心處于正常合理狀態(tài)，引入橫向容許偏移量、縱向容許偏移量和貨物和重心最大允許高度[3]，約束如下：

其中，Δ_a表示橫向容許偏移量，Δ_b表示縱向容許偏移量，Δ_c表示貨物總重心最大允許高度。為了簡化模型，貨物在裝載完成后至重新開艙取貨之前不會存在任何移動，即忽略飛機斜度、慣性、摩擦力減小等任何會讓貨物移動的情況，因此現(xiàn)定

（4）保證飛機平穩(wěn)的約束。三個貨艙內載重的物品重量需要與其最大載重成比例，否則會影響飛機的平穩(wěn)性?，F(xiàn)約束如下：

其中，P₁，P₄，P₇分別為大、中、小型飛機的前艙，比例約束誤差最大不超過0.1。

綜上所述，貨運飛機內貨艙的裝運策略優(yōu)化模型構建如下：

2.2增加集裝箱元素的貨運裝配策略分析

加入集裝箱因素后，將小體積貨物裝入集裝箱，集裝箱與中大型貨物一起進行裝運，同時要求集裝箱和飛機貨艙的利用率盡可能大，且需要選擇合適的機型而不再同時選擇多種機型。該問題中存在兩個目標函數(shù)，即集裝箱的最大空間利用率和飛機貨艙的空間利用率[4]。因此需要先通過約束條件界定小體積貨物和中大型體積貨物，并需要滿足無集裝箱狀態(tài)下貨物裝運的部分約束，通過比較三種類型飛機的最大空間利用率，以選擇合適的機型，并求出該型號貨運飛機裝運貨物所用的最少架次。由于要求集裝箱和貨運飛機貨艙的空間利用率盡可能大，因此可以參考無集裝箱狀態(tài)下的部分目標函數(shù)和約束條件。y為集裝箱的型號，K_M為飛機的型號，M=（1，2，3），（P₁，P₂，P₃）∈K₁，（P₄，P₅，P₆）∈K₂，（P₇，P₈，P₉）∈K₃。

2.2.1目標函數(shù)。首先考慮小型貨物在集裝箱內的空間利用率，目標函數(shù)如下：

其次考慮中大型貨物和集裝箱在各種飛機貨艙的空間利用率，目標函數(shù)如下：

其中，S_y為第y種集裝箱的數(shù)量，G₁，G₂，G₃分

別為需要出動的大、中、小型貨運飛機架次數(shù)量。ω為三種飛機取各利用率之和最大的數(shù)據(jù)為目標。

2.2.2約束條件

（1）小型貨物的約束。對貨物進行分類，將貨物分為小型貨物和中大型貨物，約束如下：

若貨物的體積大于等于2時，被定義為中大型貨物;若貨物的體積小于2時，則被定義為小型貨物。

（2）小型貨物在集裝箱內的約束。該約束可以參考2.1.2節(jié)中貨物在各貨艙內的體積和質量約束，載重物品將貨物更換為小型貨物，承載空間將貨艙更換為集裝箱，因此不再贅述。

（3）集裝箱體積的約束。集裝箱除了普通的航空集裝箱之外還有柔性航空集裝箱，由于其材質為塑料制品，且規(guī)定集裝箱為長方體，因此定義在一定的高度范圍內，集裝箱內部貨物總高度則為柔性航空集裝箱的高度，具體約束如下：

普通的航空集裝箱

柔性航空集裝箱

（4）質量和體積的約束。除了小型貨物的重量之外，集裝箱本身也存在著一定的質量，因此其質量為：

（5）飛機數(shù)量的約束。

其中，G₁，G₂，G₃分別表示大型、中型和小型貨運飛機的數(shù)量，要求所有中大型貨物的體積與集裝箱體積之和剛好小于所有可用架次飛機貨運體積總量之和。

綜上所述，帶有集裝箱因素的模型構建如下：

目標函數(shù)：

2.3考慮貨物效益問題的可靠性分析

在加入集裝箱因素的基礎上繼續(xù)增加經(jīng)濟效益因素，選擇合適的裝運策略以實現(xiàn)效益最大化，同時考慮到市場對產(chǎn)品的需求是不確定的，為達到公司希望得到可靠性為95%的最大利潤值，降低貨物銷售量的平均值來組織貨源的風險，重新利用時間序列法預測貨物需求量，在滿足最佳利潤下，采用3D 裝箱程序求解，得出新的裝運策略[5]。

考慮到數(shù)據(jù)的特性，首先在置信區(qū)間為95%的估計誤差下，利用時間序列預測法得出各貨物的需求量，考慮到對于本文所要解決的問題，對本文研究的預測需求量問題采用指數(shù)平滑法模型解決。

然后將更精準的需求量代替之前用貨物銷售量來組織貨源算出的貨物需求量并代入問題3最大利潤模型得出新的裝運策略。

2.3.1時間序列預測法模型的建立。設貨物需求量時間序列為y₁，y₂，…，y_t，α為加權系數(shù)，0<α<1，一次指數(shù)平滑公式為：

式（22）是由移動平均公式改進而來的，移動平均數(shù)的遞推公式為：

將式（22）展開，有：

由于加權系數(shù)符合指數(shù)規(guī)律，又具有平滑數(shù)據(jù)的功能，故稱之為指數(shù)平滑。以這種平滑值進行預測，就是一次指數(shù)平滑法[6]。預測模型為：

即：

得出以第t期指數(shù)平滑值作為t+1期的預測值，則為貨物需求量n。

2.3.2最大利潤貨運裝配模型的建立。按照用前50個周期各種貨物銷售量預測出的貨物需求量n，調整貨物裝配方案，以達到最佳的利潤，設置目標函數(shù)如下：

2.3.3約束條件。由于裝配策略是在加入集裝箱因素裝配策略的基礎上，希望能夠得到在可靠性為95%下的最大利潤值，因此目標函數(shù)一樣，需更為精準的預測出各類貨物的需求量，同樣需要考慮其穩(wěn)定性、易裝載、易分揀等情況，因此約束條件與前面相同，在此不再贅述。

3混合啟發(fā)式算法設計

在無集裝箱因素時，貨運飛機裝配策略問題視為規(guī)格不統(tǒng)一的貨物裝載問題，并考慮到重心穩(wěn)定性，貨物有三種不同的擺放方法，長寬面朝下，寬高面朝下，長高面朝下。而且每個貨物又有三種不同的排放方法，所以就可以將10種貨物看成90個變量。采用啟發(fā)式算法，主要是基于遺傳和模擬退火算法求解目標函數(shù)的最大值和最優(yōu)解。

算法流程如下：

算法一：解決貨物擺放問題

step1：保留每個貨物的（x，0，0）、（0，y，0）、（0，0，z）三個頂點;

step2：求出所有的不重復點;

step3：求步驟一和步驟二的交點;

step4：算出最前沿的這些點的位置即可。

算法二：分類打包程序算法

step1：對可能出現(xiàn)的超高貨物進行處理;

step2：按照尺寸進行分類，記錄分類結果，如果x，y，z相同則為同一類;

step3：對分類結果按照每類的個數(shù)大于1或等于1進行分離并且記錄;

step4：對個數(shù)大于1的種類，調用同類裝箱算法進行打包;

step5：對未達到優(yōu)化目標的種類，更換擺放方式，即重新制定貨物的長、寬、高之后，再次進行打包。

加入集裝箱元素后，以裝配體積為2m³以下的貨物為例，先在集裝箱內進行優(yōu)化擺放，通過隨機模擬來尋優(yōu)，采用主裝箱算法求解。

step1：打包，將體積在2m³以下的貨物在集裝箱內按照最優(yōu)擺放方法擺放后打包;

step2：對打包后的集裝箱和未打包的貨物進行裝運;

step3：解包，將最優(yōu)化擺放方式解碼;

step4：評價。

再增加經(jīng)濟效益因素，并選擇合適的裝運策略以實現(xiàn)效益最大化，同時考慮到市場對產(chǎn)品的需求是不確定的，采用3D裝箱程序[7]。

step1：進行篩選，除去不滿足約束的集裝箱，最后將該集裝箱放入surplus_box;

step2：如果PATH為空，設置初始PATH，并判斷貨物的高度是否超出貨車的高度;

step3：若當前所有的箱子高度都超過艙位高度，則直接輸出，或者當艙位被裝滿或是貨物被裝完，停止，統(tǒng)計未裝運的集裝箱;

step4：統(tǒng)計下一步可行的落腳點，統(tǒng)計所有貨物的上頂點，用于判斷支撐面積，如果支撐面積超過底面積的80%，保存新的箱子;

step5：進行解包以及評價。

4實例分析

進出口公司需要銷售的貨物共有WH1-WH10十種，每種貨物都被簡化為立方體形狀，貨物的屬性，即尺寸、體積、重量、運輸單價是已知的。收集公司之前的平均周期銷售數(shù)量和銷售價格，飛機貨運成本為銷售額的40%，具體見表1、表2。

一周期內貨物若沒銷售完，則剩余的貨物按照其銷售價的30%甩賣，且在加入集裝箱元素后，小體積的貨物（2m³以下）需要裝在集裝箱中，集裝箱為長方體且有厚度5cm，需要選擇合適的方法將小體積貨物裝進集裝箱，再將集裝箱與中大體積貨物裝運上貨艙，集裝箱的具體數(shù)據(jù)見表3。

根據(jù)所提出的模型和算法，利用matlab進行求解?？紤]到實際情況，飛機貨物裝運貨艙的承重比率存在一定的誤差承受能力，無需嚴格按照比率精準配重，因此將符合承重比率設置為誤差0.1。得出相應貨物擺放方案見表4，且在加入集裝箱因素后，選擇使用飛機型號為大型貨運飛機，且至少兩架次，預估最大利潤值為6 914 380元。

表4中，2號、6號、7號和10號貨物經(jīng)判定為小貨物，需要裝配至集裝箱內進行運輸。以在大型飛機的前艙為例，表示裝運2號集裝箱10個，3號集裝箱9 個，5號集裝箱20個，7號集裝箱10個。

由于精度原因，考慮的每件貨物和集裝箱擺放方式不再列出，僅描述出該件貨物和集裝箱所在的位置。其中c1-c10為10種不同貨物的數(shù)量，p11- p13為第一架大飛機前艙、中艙、后艙中裝運各貨物的數(shù)量和集裝箱數(shù)量，p21-p23為第二架大飛機前艙、中艙、后艙中裝運各貨物的數(shù)量和集裝箱數(shù)量，y1-y7為7種不同集裝箱的數(shù)量。

5結語

本文根據(jù)三維裝箱問題的特點，考慮貨物存在不同的擺放方式、集裝箱剩余空間最大利用率等多項影響因素，建立了多目標約束模型，采用多種算法結合求解，快速制定出貨物的裝載布局方案，有效求解三維裝箱問題。本文通過編程方法，對具體不同問題給出了相應裝運方案，為復雜三維裝箱問題裝載過程提供了智能的決策指導，同時模型考慮到諸多現(xiàn)實因素，可應用于飛機救援物資運送、工廠裝箱等多項現(xiàn)實場景中。

本文在對三維裝箱問題策略研究上仍存在一些問題，第一，僅考慮了部分約束條件，影響現(xiàn)有研究成果的實用性。第二，在假設前提下進行簡化處理，得到優(yōu)化后的模型，降低了三維裝箱問題本身的復雜程度，但會造成改進后的模型出現(xiàn)失真的現(xiàn)象，使計算結果應有的實用性及可信性降低。第三，根據(jù)集裝箱三維裝載自身的復雜性和特殊性，不規(guī)則貨物與不規(guī)則集裝箱裝載、更多目標與約束等問題有待進一步研究。針對上述問題，三維裝箱問題在未來一段時間還有較大的研究價值。

[參考文獻]

[1]王祎樓.基于貨物組合的三維裝箱啟發(fā)式算法[J].物流工程與管理，2018，40（12）：73-75.

[2]張鈞，賀可太.求解三維裝箱問題的混合遺傳模擬退火算法[J].計算機工程與應用，2019，55（14）：32-39，47.

[3]杜振，宮會麗.解決約束三維裝箱問題的混合粒子群算法[J].計算機光盤軟件與應用，2014，17（22）：115-116.

[4]張德富，彭煜，張麗麗.求解三維裝箱問題的多層啟發(fā)式搜索算法[J].計算機學報，2012，35（12）：2 553-2 561.

[5] YARU S，et al.A hybrid chemical reaction optimisation algorithm for solving 3D packing problem[J].International Journal of Autonomous and Adaptive Communications Sys- tems，2021，14（1-2）.

[6]謝英.基于時間序列和灰色預測的原煤產(chǎn)量預測[J].煤炭技術，2021，40（6）：221-224.

[7]張德富，魏麗軍，陳青山，等.三維裝箱問題的組合啟發(fā)式算法[J].軟件學報，2007（9）：2 083-2 089.