錢 鋮，王 淳，王瑞龍，陳英革

（常熟理工學(xué)院 電氣與自動化工程學(xué)院，江蘇 常熟 215500）

0 引言

隨著國內(nèi)外電商行業(yè)的蓬勃發(fā)展，對于快遞運輸行業(yè)的要求也越來越高．而快遞裝箱問題的優(yōu)化求解，其基本目標是提高空間利用率（暫不考慮載重），在節(jié)約資源和提高效率方面起到重要作用．在實際應(yīng)用中，快遞裝箱問題有不同的優(yōu)化目標和裝載約束，于是涌現(xiàn)出許多關(guān)于裝箱問題的解決方法．

裝箱問題屬于NP-Hard問題[1]，故精確求解算法對于裝箱問題來說是不現(xiàn)實的．Lim[2]、Bortfeldt等[3]分別提出了一些啟發(fā)式算法及一些三維裝箱實例；Mourat等[4]提出了GRASP隨機自適應(yīng)啟發(fā)式算法；張德富等給出了組合啟發(fā)式算法[5]、砌墻式啟發(fā)式算法[6]、多層啟發(fā)式搜索算法[7]；何大勇等[8]、張德富等[9]、李偉等[10]分別通過遺傳算法來尋求裝箱問題的最優(yōu)解；李廣強等[11]、何琨等[12]、王程等[13]還分別針對三維裝箱的空間分解及布局做了相關(guān)研究．

研究上述文獻后可知，這些算法更多的是強調(diào)填充率和最優(yōu)裝填搜索，而針對智能車快遞分裝的裝箱問題，需求上更傾向于裝填和分發(fā)的時間效率．為此，本文在前人研究的基礎(chǔ)上，加強了裝箱問題的約束，并以擬人的啟發(fā)式算法為基礎(chǔ)，將目標分解成子目標進行逐層裝填，并在子目標實現(xiàn)中采用貪心算法，以提高目標達成的科學(xué)性和合理性．在降低數(shù)據(jù)的搜索維度方面，依據(jù)快遞貨物的特點，當(dāng)箱體尺寸小于某一個閾值時，采用模糊策略進行改造移植，進一步滿足實用性需求，最終得到適合快遞車智能化改造的裝箱算法HHFS（Heuristic hybrid fuzzy strategy）．對于邊長100～200 cm強異構(gòu)的裝箱問題的仿真測試結(jié)果表明：此混合算法不僅在填充率上不輸以往結(jié)果數(shù)據(jù)，同時還具有提取過程中減少箱體往復(fù)搬運，適應(yīng)快遞多點分發(fā)的優(yōu)點．

1 裝箱問題模型

1.1 一般裝箱問題描述和約束條件

Dyckhoff和Finke[1]概述了不同類型的裝箱問題．本文所研究的三維快遞分裝裝箱問題屬于裝箱問題中的一類，可以形式化定義如下：

給定一個容器（其體積為V）和一系列待裝載的貨物．假定容器和貨物的形狀都是長方體，需確定一個可行的貨物放置方案，使得在滿足給定裝載約束的情況下，容器中包含的貨物總體積S盡可能大，即填充率filling rate = （S/V* 100%） 盡可能大．其約束條件應(yīng)滿足以下3個條件：

（1）被裝載的貨物必須完全被包含在容器中；

（2）任何兩個被裝載的貨物不能空間互相重疊；

（3）所有被裝載的貨物以與容器平行的方式放置，即不能斜放．

1.2 智能車快遞分裝問題的約束條件強化

基于智能車的快遞分裝還需要進一步考慮快遞分發(fā)的先后關(guān)系，因此存在堆放次序的優(yōu)化問題．算法應(yīng)根據(jù)快遞分發(fā)目標的行程先后，目的地靠后的應(yīng)放置于底層，目的地靠前的應(yīng)放置于上層．在實際應(yīng)用中，特定的裝箱問題還有其他約束，本文對以下幾個約束做了強化：

（1）方向約束：貨物的裝載有方向約束，也就是說，每個貨物只有它的1條或幾條邊可以豎直放置作為高度．沒有此約束的問題可以被簡單地視為所有貨物的3條邊都可以作為高度．

（2）穩(wěn)定性約束：在許多應(yīng)用中，特別是在交通運輸業(yè)中，裝載必須滿足穩(wěn)定性約束．這意味著每個被裝載的貨物必須得到容器底部或者其他貨物的支撐．即穩(wěn)定性約束禁止被裝載的貨物懸空．

（3）基于智能車快遞分裝的放置方案必須滿足上述兩個約束條件．同時，快遞的包裝種類繁復(fù)，所有3條邊長不同且方向約束也不同即屬于異構(gòu)裝箱問題．本文主要考慮異構(gòu)裝箱問題．

（4）出于快遞分發(fā)的考慮，基于智能車快遞分裝的放置方案的優(yōu)化目標，還要考慮分發(fā)時對于多目的地的提取優(yōu)先的約束．

2 基于經(jīng)驗的啟發(fā)式算法

啟發(fā)式算法（Heuristic Algorithms）是基于直觀或經(jīng)驗構(gòu)造的算法，在計算時間、占用空間等方面有先天優(yōu)勢，能快速給出實例的一個可行解，缺點是可行解與最優(yōu)解的偏離程度不可以預(yù)計．

2.1 容器及容器放置的空間分割策略

（1）當(dāng)一個空的容器（設(shè)定長Xi、寬Yi、高Zi）占據(jù)一個規(guī)則物體（設(shè)邊長分別為Aj、Bj、Cj），就把剩余空間分割成3個空間不相交的容器．鑒于智能車快遞分裝自下而上先進后出的特點，我們選取如圖1所示的上下分割方式．同時出于穩(wěn)定性考慮，在無方向約束條件下，優(yōu)先選取規(guī)則貨物最短邊長min（aj、bj、cj）定為垂直高度放置，則分割出一個Xi*Yi*（Zi-min（Aj、Bj、Cj））容器．在圖1中，我們假設(shè)Cj=min（Aj、Bj、Cj），若出現(xiàn)狹長容器等放置約束條件時，則優(yōu)先選取規(guī)則貨物次短邊長為垂直高度放置，其他亦然．

圖1 快遞物品在容器放置中的空間分割

（2）在z軸被確定為上下分割的前提下，x、y方向的邊長又有兩種分割方式，分別為xz軸方向截面分割和yz軸方向截面分割，如圖 1（a）和圖 1（b）所示．每種分割又有兩種新容器生成的可能，如圖2（a）～圖2（d）所示，因此可看成是一種二維分割．

對應(yīng)上述4種選項，采用貪心算法，以產(chǎn)生最大截面積為優(yōu)選分割容器方案．

圖2 快遞物品在容器放置中的進一步二維分割

（3）若容器體積小于某一個閾值，則不再繼續(xù)被分割，而作為小型貨物填充空間碎片使用．

2.2 貨物擇取優(yōu)先級策略及放置容器優(yōu)先級策略

根據(jù)智能車快遞分裝穩(wěn)固性及取件整體先進后出的特點，擇取貨物優(yōu)先級和選取容器的優(yōu)先級做如下設(shè)定：

（1）快遞貨物根據(jù)貨物“體積”和貨物“目的地”兩個要素，采用二級優(yōu)先級進行分配；

（2）“目的地”要素：對快遞貨物的目的地先后順序進行編排，貨物目的地次序越靠后的優(yōu)先級越高；

（3）“體積”要素：對于同一目的地的貨物，體積越大則優(yōu)先級越高；

（4）融入模糊策略：當(dāng)貨物最大邊長小于某一個閾值時，將其定義為容器碎片填充貨物，計算中用給定的填充率經(jīng)驗值消耗容器碎片．如果同為容器碎片填充貨物的，則依據(jù)目的地優(yōu)先原則選?。?/p>

（5）在容器選取上，依次對具有最高優(yōu)先級的貨物分配容器，以容器體積從小到大的順序安排容器．若貨物能容納則分配該容器，并對此容器按1.1節(jié)所述進行容器放置的空間分割．

2.3 上述算法的優(yōu)點與缺陷

基于經(jīng)驗的啟發(fā)式算法在智能車快遞的分裝中不僅考慮了貨物填充率參數(shù)，還考慮了提取貨物的優(yōu)先級參數(shù)來分配容器．該算法簡單、易于機器快速實現(xiàn)．但通過仿真結(jié)果觀測發(fā)現(xiàn)上述算法還存在兩個致命缺陷．

（1）大貨物單側(cè)堆積效應(yīng)：由于同目的地大貨物優(yōu)先級較高，優(yōu)先安排分配容器，而可分配的優(yōu)選容器基本是挨著前一個更大貨物，很容易形成大貨物如圖3所示的集中單側(cè)堆積效應(yīng)．

圖3 快遞物品的集中單側(cè)堆積效應(yīng)

（2）對于目的地優(yōu)先級高的大貨物，堆積到上層時，若其底面積較大，很容易出現(xiàn)底部支撐度不足的情況，從而會降低貨物裝箱的穩(wěn)定性，如圖4所示．

圖4 快遞物品堆積的底部支撐度不足現(xiàn)象

因此，我們修正了選取貨物和放置容器優(yōu)先級策略，擬人地消除每一層間的空隙．

3 快遞裝箱啟發(fā)式混合模糊算法

在容器及容器放置的空間分割策略中實際上隱含了“層”的概念．若存在一個容器，其邊長等于整個箱體對應(yīng)的兩個邊，此容器必然在箱體頂部．若這個容器一旦被分配，則產(chǎn)生貨物堆積的最高高度，此高度對應(yīng)的面就是新的層．

依據(jù)人工平時貨物裝箱的經(jīng)驗，對于引發(fā)產(chǎn)生新層容器的貨物選取時不再以提取同優(yōu)先級中體積最大貨物為選取對象，而應(yīng)以最短邊長為最大值（即貨物隱含高度）作為選取對象，因為其決定了新的層高參照．

同時，在確定了一個新層后，應(yīng)盡量填充這個層為子目標，且應(yīng)不破壞此層高．在達成子目標后再生成新的層，以此類推．

在對一個層的填充過程中，我們選用貪心算法：優(yōu)先選取放置后所需產(chǎn)生的容器新分割的容器數(shù)量最少為原則，否則選取容器總空間為最小的貪心選擇條件．下面是在子層填充中引入貪心子算法的修正：

（1）當(dāng)產(chǎn)生一個新層i時，首先確定應(yīng)參與本層搜索的貨物隊列子集Cargo_queuei，以目的地Destination_leveli優(yōu)先級最高為優(yōu)先選擇標準．若同一目的地的貨物體積Size_leveli總和大于此新層的容器體積總和，則采納此目的地的貨物作為參與搜索的貨物隊列子集Cargo_queue_subj，否則搜索范圍擴展到次優(yōu)目的地貨物，直到滿足搜索范圍內(nèi)貨物體積總和大于此新層的剩余容器空間總和．

（2）在層搜索子集貨物中，依據(jù)貪心算法，遍歷選取貨物，并遍歷容器Volumetric_queuek．貪心優(yōu)選條件是：優(yōu)先選取放置該貨物時所產(chǎn)生的新分割容器數(shù)K最少的貨物，否則選取體積最大的貨物．選中該貨物后，將其從層搜索子集鏈表Cargo_queue_subj中刪除．

（3）依次執(zhí)行（2），若在層搜索子集中選取任何貨物時都將產(chǎn)生新層，則將此層的碎片容器用之前定義的容器碎片填充貨物進行填充．結(jié)束此層子模塊計算，并將層搜索子集帶入下一層計算．

具體算法流程如圖5所示．采用這個方法的好處是：

圖5 快遞裝箱啟發(fā)式混合模糊算法HHFS流程圖

（1）可以優(yōu)先選取與容器尺寸相符的貨物，恰當(dāng)?shù)叵娜萜麝犃校?/p>

（2）若不然，擬人地優(yōu)選比較大的貨物快速填充此層；

（3）算法僅做了小范圍的遍歷搜索，相對科學(xué)合理，算法復(fù)雜度為O(n2)，滿足應(yīng)用的時效性需求；

（4）雖然達不到最優(yōu)解，但綜合填充率、先進后出命中率、時效性等整體性能滿足智能車快遞裝載的迫切需求．

4 仿真實驗與分析

本文的HHFS算法以C++在Windows 10環(huán)境下實現(xiàn)，處理器為Intel(R) Core(TM)i7-7700HQ CPU @ 2.80 GHz．在實驗中，設(shè)置假想智能車快遞分裝箱體容器長X1=200 cm、寬Y1=150 cm、高X1=150 cm；貨物數(shù)據(jù)集的長Xi、寬Yi、高Zi在5～50 cm范圍內(nèi)隨機生成．為近似應(yīng)用，同時做了最長邊/最短邊≤2的約束；朝向擺放約束隨機概率5%生成；貨物總體積＞箱體總體積時結(jié)束數(shù)據(jù)集生成．另外，貨物目的地Destination_leveli=random{3、4、5}；碎片容器體積閾值設(shè)置為200 cm3；填充碎片容器貨物體積閾值設(shè)置為100 cm3；碎片填充率的經(jīng)驗值設(shè)置為0.6．按照上述的約束設(shè)置，分別生成了20組數(shù)據(jù)，如表1所示．

表1 20組快遞貨物FFHS仿真數(shù)據(jù)

為了驗證本文所提算法的有效性，我們將快遞裝箱啟發(fā)式混合模糊算法FFHS與文獻[13]中的最優(yōu)剩余空間算法Optimal Algorithm of Remaining Space以及文獻[8]中的混合模擬退火算法Hybrid Simulated Annealing Algorithm進行了分析對比，分別考察了填充率Filling rate、先進后出命中率FILO rate以及運行時長Run time，結(jié)果分別如圖6、圖7、圖8所示．

圖6 貨物填充率對比分析

圖7 貨物FILO命中率對比分析

圖8 算法Run time對比分析

3個算法在填充率的整體表現(xiàn)上都存在明顯的波動，說明對于強異構(gòu)性的裝箱問題，其優(yōu)化的策略及所采用的參數(shù)對結(jié)果都會有很大的影響．無論是策略還是參數(shù)在實際的應(yīng)用中都難以得到最優(yōu)的抉擇．一般來說，遍歷搜索越深，則填充率越高．在圖6中，Hybrid Simulated Annealing Algorithm 的填充率平均為91.372%，Optimal Algorithm of Remaining Space平均為88.213%，本文的Heuristic hybrid fuzzy strategy 平均為86.335%．

在FILO先進后出的命中率方面，Optimal Algorithm of Remaining Space做了局部約束處理，Hybrid Simulated Annealing Algorithm沒有做約束，而本文在尋求貨物裝載的穩(wěn)定性目標上，對先進后出約束做了輕微弱化．從圖7可以看出，仿真結(jié)果表現(xiàn)良好，平均達到了91.84%．Optimal Algorithm of Remaining Space平均為72.92%，Hybrid Simulated Annealing Algorithm平均為60.96%．

在程序運行時長方面，本文的Heuristic hybrid fuzzy strategy和Optimal Algorithm of Remaining Space都在減小數(shù)據(jù)搜索規(guī)模上做了工作．本文更是依據(jù)實際應(yīng)用擬人地引入了模糊數(shù)學(xué)理論，在數(shù)據(jù)搜索規(guī)模上做了更進一步的縮減．圖8的仿真結(jié)果表明，在運行時長方面取得了相當(dāng)?shù)膬?yōu)勢．本文運算時間平均為7.86 s，而Hybrid Simulated Annealing Algorithm平均為100.93 s、Optimal Algorithm of Remaining Space 平均為 23.76 s．

5 結(jié)論

本文在吸收消化以往諸多裝箱算法的基礎(chǔ)上，針對快遞分裝更強調(diào)裝填和分發(fā)時間效率的特點，提出了快遞裝箱啟發(fā)式混合模糊算法HHFS，將啟發(fā)式算法、貪心算法以及模糊算法有機結(jié)合應(yīng)用于快遞分裝策略的計算過程中，最終形成了一套適合快遞分裝行業(yè)智能化控制改造方案，以貼合實際的裝填操作．仿真實驗結(jié)果表明這是一套值得推廣的實用算法．

盡管本文針對三維裝箱問題中取件的便利性、裝箱的穩(wěn)定性以及實施的時效性，有針對性地展開了綜合性的初步探究，但算法上還有較大的提升空間．比如對于每個層的平整性問題，同樣可以在數(shù)據(jù)搜索中加強優(yōu)化，以進一步提高裝載支撐的穩(wěn)定性，這也是下一步的工作．