高效求解三維裝箱問(wèn)題的剩余空間最優(yōu)化算法

高效求解三維裝箱問(wèn)題的剩余空間最優(yōu)化算法尚正陽(yáng);顧寄南;唐仕喜;孫曉紅期刊名稱】《《計(jì)算機(jī)工程與應(yīng)用》》年(卷),期】2019(055)005【總頁(yè)數(shù)】7頁(yè)(P44-50)【關(guān)鍵詞】三維裝箱問(wèn)題;啟發(fā)式算法;快速求解;調(diào)度優(yōu)化【作者】尚正陽(yáng);顧寄南;唐仕喜;孫曉紅【作者單位】安徽工程大學(xué)機(jī)械與汽車(chē)工程學(xué)院安徽蕪湖241000;江蘇大學(xué)制造業(yè)信息化研究中心江蘇鎮(zhèn)江212000【正文語(yǔ)種】中文【中圖分類】TP3011引言裝箱問(wèn)題是指將一組二維矩形或者三維長(zhǎng)方體，放置到二維或者三維空間中，以使得空間的填充率最大或者容積最小。它作為一個(gè)傳統(tǒng)的優(yōu)化組合問(wèn)題，不僅得到了大量的理論研究，還被廣泛地應(yīng)用在了實(shí)際生產(chǎn)和生活的各個(gè)領(lǐng)域。特別是針對(duì)三維裝箱問(wèn)題，由于其更加貼近真實(shí)情況，已經(jīng)在工業(yè)中得到了大量使用，例如以三維空間利用率為目標(biāo)的集裝箱放置和木材切割問(wèn)題，或是將第三維看作是時(shí)間的時(shí)空調(diào)度問(wèn)題等等。隨著智能制造和精益生產(chǎn)的不斷推進(jìn)，這類以三維裝箱為模型的資源配置問(wèn)題日益受到重視，而相關(guān)的算法研究與實(shí)踐也就有著積極的現(xiàn)實(shí)意義。三維裝箱問(wèn)題是裝箱問(wèn)題的一個(gè)子問(wèn)題，Dyckhoff等［1］根據(jù)裝箱過(guò)程中的不同約束和目標(biāo)，進(jìn)行了詳細(xì)分類：容器裝載問(wèn)題、箱柜裝載問(wèn)題、背包裝載問(wèn)題。本文所研究的是以體積為價(jià)值的三維背包裝載問(wèn)題(Three-DimensionalKnapsackLoadingProblems，3D-KLP)，即將一組不同尺寸的小長(zhǎng)方體放入到一個(gè)給定尺寸的大長(zhǎng)方體中，旨在使所有被放入的小長(zhǎng)方體的總體積最大。在此，將小長(zhǎng)方體稱為箱子，大長(zhǎng)方體稱為容器，裝載的目標(biāo)是使容器的空間填充率最大。這是一個(gè)典型的NP-hard問(wèn)題，傳統(tǒng)算法往往因其解空間的“組合爆炸”而難于求解。所以三維裝箱問(wèn)題的求解通常被分為兩個(gè)部分：?jiǎn)l(fā)式的放置方法和較優(yōu)解的搜索算法。綜合國(guó)內(nèi)外相關(guān)研究，George等［2］提出了基于“層”和“墻”的啟發(fā)式放置方法。Bortfeldt等［3］設(shè)計(jì)了一種混合遺傳算法來(lái)實(shí)現(xiàn)較優(yōu)解的搜索，而Pisinger［4］則將樹(shù)搜索引入其中。隨后，Gehring等［5］提出了“塔”的放置方法，并和Bortfeldt等［6］分別設(shè)計(jì)了相應(yīng)的遺傳算法和禁忌搜索算法。值得一提的是，Eley［7］給出了一種基于“塊”裝載的啟發(fā)式算法，這種特別的前處理方式，經(jīng)過(guò)Fanslau等［8啲發(fā)展，能夠針對(duì)三維裝箱問(wèn)題取得不錯(cuò)的解。當(dāng)前，張德富等［9-10］，Zhu等［11］和劉勝等［12-13嘟以“塊”為基礎(chǔ)，結(jié)合不同搜索算法實(shí)現(xiàn)了容器的高效填充。除此之外，一些著重于搜索操作改進(jìn)和提升的啟發(fā)式算法［14-16］，也在特定領(lǐng)域中得到了快速發(fā)展。實(shí)際上，三維裝箱是二維裝箱的擴(kuò)展與分支，許多經(jīng)典的二維裝箱策略和求解方式都能夠在三維裝箱中得以應(yīng)用。在裝箱策略上，張德富等［17］將二維的砌墻策略引入到了三維問(wèn)題；Huang等［18］將擬人穴度算法擴(kuò)展到了三維領(lǐng)域，并取得了不錯(cuò)的填充效果；而He等［19-20］、Araya等［21］則對(duì)穴度的評(píng)價(jià)規(guī)則進(jìn)行了進(jìn)一步的改進(jìn)與完善；劉勝等［12］通過(guò)基于優(yōu)條的預(yù)處理方式將三維問(wèn)題降維為二維問(wèn)題進(jìn)行分步填裝；Toffolo等［22］則通過(guò)二維操作實(shí)現(xiàn)了“塊”或者“堆”的簡(jiǎn)化填裝。在求解方式上，除對(duì)填充率的更高追求外，如何實(shí)現(xiàn)算例尤其是大規(guī)模算例的高效求解也越來(lái)越多地受到關(guān)注。Polyakovsky等［23］針對(duì)大規(guī)模二維裝箱問(wèn)題的快速求解提出了GBL算法；Imahori等［24］致力于降低算法的求解復(fù)雜度。最近，Zhang等［25］提出了一個(gè)高效的PH算法，其在運(yùn)算過(guò)程中不需要任何的回溯和搜索策略，能夠在計(jì)算復(fù)雜度僅為T(mén)(n)=O(n2)的情況下直接求解，極大地縮減了運(yùn)算成本。然而這種高效的直接求解方式，還未被引入到三維裝箱中。特別是隨著三維裝箱問(wèn)題的不斷深入研究，其解的空間填充率已經(jīng)十分令人滿意。然而，在目前的研究和應(yīng)用中存在以下問(wèn)題：一方面當(dāng)箱子的種類和數(shù)量特別巨大時(shí)，傳統(tǒng)算法難于甚至于不能夠在合適的時(shí)間內(nèi)進(jìn)行求解，其計(jì)算復(fù)雜度較高；另一方面，在以三維裝箱為模型的實(shí)際應(yīng)用中，經(jīng)常出現(xiàn)“箱子”的刪除、增加或者手動(dòng)調(diào)整等情況，需要相關(guān)算法能夠迅速響應(yīng)。所以無(wú)論是學(xué)術(shù)研究還是工業(yè)實(shí)際，這種基于直接求解的快速算法都十分必要。為實(shí)現(xiàn)三維裝箱問(wèn)題的高效求解，在綜合考慮剩余空間分割和箱子布置的前提下，本文借鑒二維PH算法［25］的直接求解方式，提出了啟發(fā)式的剩余空間最優(yōu)化算法(Three-DimensionalResidual-Space-OptimizedAlgorithm，3D-RSO)。該算法在求解過(guò)程中不需要額外的預(yù)處理和最優(yōu)解搜索操作，能夠在極少的計(jì)算消耗下得到一個(gè)較優(yōu)的解，相對(duì)于現(xiàn)階段其他算法在求解效率上具有明顯優(yōu)勢(shì)。2問(wèn)題介紹為詳細(xì)對(duì)3D-KLP問(wèn)題進(jìn)行描述，給定一個(gè)長(zhǎng)方體容器C和一個(gè)箱子的集合B。容器C的長(zhǎng)、寬、高分別表示為L(zhǎng)、W、H如公式(1)所示；B中包含有一系列的箱子bi如公式(2)所示；每一個(gè)bi中又包含有6個(gè)參數(shù)如公式(3)所示，其中l(wèi)i、wi、hi分別表示箱子的長(zhǎng)、寬、高，rli、rwi、rhi則代表了箱子是否可以圍繞其自身的長(zhǎng)、寬、高三個(gè)方向旋轉(zhuǎn)放置。對(duì)于一次完整的裝載，設(shè)F為所有已放入容器C中的箱子集合，則其總體積可表示為公式（4）：為便于表達(dá)，通常用最大空間填充率來(lái)表示最終的容器裝載效果，如公式（5）所示。裝載的目標(biāo)是最大化容器的空間填充率。箱子在裝載過(guò)程中的約束條件如下：C1:方向性約束，箱子的裝載具有方向性約束，也就是說(shuō)，每個(gè)箱子只能按照其給定的放置姿態(tài)進(jìn)行放置。即箱子的裝載必須滿足其自身的rli、rwi、rhi屬性。C2:穩(wěn)定性約束，每個(gè)被裝載箱子必須得到容器底部或者其他已裝載箱子的支撐。本文主要考慮箱子的完全支撐約束，即被裝載箱子的底部不允許有任何懸空。C3:完全切割約束，此約束是二維裝箱中一刀切約束的擴(kuò)展。它要求在最終的裝填狀態(tài)中，已放入箱子的集合可以由多個(gè)豎直的平面分割成多個(gè)子空間，并且每個(gè)子空間又可以被多個(gè)水平的平面分割成更小的子空間。以此方式，每個(gè)箱子都可以通過(guò)豎直或者水平的平面被完整地分割出來(lái)。綜合考慮C2和C3約束，并將其反應(yīng)到每個(gè)箱子的具體裝填狀態(tài)上，就如圖1所示。圖1（a）和（b）是允許的放置狀態(tài)，而圖1（c）和（d）是不被允許的放置狀態(tài)。實(shí)際上，C2和C3約束具有一定的實(shí)際意義，例如在集裝箱的裝卸過(guò)程中，當(dāng)集裝箱的放置狀態(tài)同時(shí)滿足以上兩個(gè)約束時(shí)，叉車(chē)就可以從集裝箱的底部直接叉取貨物，大大減少其裝卸的難度和時(shí)間消耗［12］。圖1箱子的四種放置狀態(tài)3基于直接求解的三維裝箱算法由于C2約束的存在，箱子只能放置在容器底部或者已存在箱子的上方，并且為滿足C3約束，當(dāng)箱子放入后，其剩余空間將會(huì)被劃分為更小且相互獨(dú)立的子空間。于是如圖2所示，剩余空間可被分割為如圖2（a）或圖2（b）所示的三個(gè)子空間S1、S2、S3，且每個(gè)箱子只能被完全放置到某個(gè)子空間中。實(shí)際上，基于C2和C3的共同約束，箱子在其底面投影方向上的布局不但決定著其子空間的形成，還影響著整個(gè)后續(xù)箱子的放置。所以在此將這個(gè)三維裝箱問(wèn)題看作是一種帶有高度約束的二維裝箱問(wèn)題進(jìn)行求解。圖2剩余空間的兩種分割方式總的來(lái)看，三維裝箱是二維裝箱的擴(kuò)展，其裝載過(guò)程同樣存在兩個(gè)關(guān)鍵問(wèn)題：一是空間分割，即當(dāng)一個(gè)箱子被放入后，其所在空間如何被劃分為更小的子空間。如圖2所示，需要在圖2(a)和圖2(b)的兩種分割方式中選取一種。二是放置位置選擇，即如何為待放置箱子選擇一個(gè)合適的放置位置，如圖3所示，bi需要在滿足其高度約束的條件下，選擇一個(gè)合適的放置空間和放置方式。所以本文圍繞這兩個(gè)關(guān)鍵問(wèn)題展開(kāi)算法設(shè)計(jì)。圖3放置位置選擇正如PH算法［25］在不需要最優(yōu)解搜索和預(yù)處理操作的條件下，能夠?qū)ΧS裝箱問(wèn)題進(jìn)行直接求解一樣，本研究旨在提出一種高效的三維裝箱算法。為此，本文首先發(fā)展了一種三維的剩余空間最優(yōu)化布局策略，即當(dāng)一個(gè)箱子被放入空間中后，希望其所產(chǎn)生的較大子空間越大越好。如圖4所示，當(dāng)箱子能夠以某一側(cè)為底面進(jìn)行放置時(shí)，其基于二維平面上的子空間分割類型有圖4(a)~(d)四種。明顯可見(jiàn)，當(dāng)箱子以圖4(d)的狀態(tài)放置時(shí)，所產(chǎn)生子空間S3的面積最大(相應(yīng)的體積也是最大)，所以在此選擇如圖4(d)所示的空間分割方式和箱子放置位置。實(shí)際上，這種策略的目的是：一方面使所產(chǎn)生的較大子空間的體積更大，增加后續(xù)較大箱子的放置概率；另一方面也使得所產(chǎn)生的小空間較小，減少可能出現(xiàn)的基于小空間的浪費(fèi)。雖然這種啟發(fā)式的放置策略不能獲得一個(gè)最優(yōu)的裝載效果，但是其能夠在不進(jìn)行最優(yōu)解搜索和預(yù)處理操作的條件下，以較大概率得到一個(gè)較優(yōu)的解。于是，根據(jù)這個(gè)三維的剩余空間最大化布局策略，相應(yīng)的空間分割方法和箱子放置規(guī)則被提出了。圖4放置狀態(tài)的選擇實(shí)例分割方法當(dāng)箱子被放置后，其所在空間可被分割為如圖5(a)所示的S1、S2和S3或者如圖5(b)所示的S*1、S*2和S*3三個(gè)包含有各自高度的子空間。由于圖5(b)的分割方式能夠得到一個(gè)更大的子空間S*3和更小的子空間S*2，所以遵循剩余空間最優(yōu)化策略，按圖5(b)進(jìn)行空間分割。換而言之，在每一次的空間分割中，都選擇能夠產(chǎn)生具有較大體積子空間的分割方式。其偽代碼如下所示。分割方法：When—個(gè)箱子被放入到空間中計(jì)算S3的面積為Area(S3),S*2的面積為Area(S*2)IfArea(S3)>Area(S*2)縱向分割以形成子空間S*1、S*2和S*3Else橫向分割以形成子空間S1、S2和S3EndEnd圖5剩余空間分割方式的選擇放置規(guī)則放置規(guī)則的作用是能夠?yàn)楫?dāng)前箱子選擇一個(gè)合適的放置空間和放置方式?；谑Ｓ嗫臻g最優(yōu)化的基本求解策略，具體放置規(guī)則如下：(1)首先認(rèn)為箱子的底面積與其放置空間的底面積越接近，則越需要被優(yōu)先匹配布置。這是因?yàn)橐环矫鎸⑤^大的可放置子空間空出，以便于增加后續(xù)箱子的放置概率，另一方面也有利于減少箱子放置后所產(chǎn)生的可能浪費(fèi)剩余空間。(2)當(dāng)存在多個(gè)與箱子底面積大小類似的放置空間時(shí)，優(yōu)先選擇能生成較大剩余子空間的放置方式。于是，一個(gè)綜合性的評(píng)價(jià)規(guī)則被給出如公式(6)所示：其中,l(Sj)、w(Sj)分別表示放置空間的長(zhǎng)和寬，l(bi)和w(bi)表示箱子放入時(shí)底面積的長(zhǎng)和寬，a是被賦值為0.1的修正參數(shù)，f(bi,Sj)的值越大越好(當(dāng)bi可被放入到子空間Sj時(shí))。一個(gè)例子如圖6所示，基于所提出的放置規(guī)則評(píng)價(jià)公式，圖6(b)和圖6(c)的放置效果是明顯優(yōu)于圖6(a)的。而對(duì)于同一個(gè)空間的不同放置方式：圖6(b)和圖6(c)，由于圖6(c)能夠產(chǎn)生較大的剩余子空間(評(píng)價(jià)值較高)，所以選擇其為當(dāng)前的箱子放置方式。其中，修正參數(shù)a的作用是使得當(dāng)l(Sj)-l(bi)或者w(Sj)-w(bi)為0時(shí)，評(píng)價(jià)規(guī)則仍然能夠選出一個(gè)最優(yōu)的箱子放置方式。圖6放置規(guī)則圖例算法構(gòu)建每當(dāng)有箱子需要被放置時(shí)，算法便檢索其所有可能的放置空間和放置方式，并根據(jù)放置規(guī)則選擇出一個(gè)具有最高評(píng)價(jià)值的放置狀態(tài)。在此，定義剩余箱子的集合為BR二{bp,...,bi,...,bq},容器中可進(jìn)行放置的子空間的集合為SR二{Sm,...,Sj,...,Sn},其算法的偽代碼如下所示：算法3D-RSO將所有箱子按照其可能產(chǎn)生的最大底面積降序排列，以此形成集合BRWhenBR不為空集選擇BR中的第一個(gè)箱子作為當(dāng)前箱子，并計(jì)算其在所有可放置狀態(tài)下的評(píng)價(jià)度f(wàn)(b1,Sj)，形成集合SFIfSF不為空以評(píng)價(jià)度最高的狀態(tài)對(duì)當(dāng)前箱子進(jìn)行放置空間分割按照分割方法刪除箱子bl在BR中Else刪除箱子bl在BR中End更新BR更新SREnd在C1、C2和C3的共同約束下，箱子的底面積尺寸對(duì)自身和后續(xù)箱子的放置起著關(guān)鍵性作用，所以首先將所有箱子按照其可能產(chǎn)生的最大底面積排序，進(jìn)而逐個(gè)地對(duì)箱子進(jìn)行擇優(yōu)放置。這個(gè)快速的求解過(guò)程是與PH算法［25］相似的，不同的是3D-RSO以箱子為單位（而非子空間為單位）進(jìn)行算法執(zhí)行。又由于每放入一個(gè)箱子，最多可產(chǎn)生三個(gè)后續(xù)子空間，所以針對(duì)評(píng)價(jià)值的最壞計(jì)算復(fù)雜度如公式（7）所示：然而，一方面并不是所有箱子被放入后都會(huì)產(chǎn)生三個(gè)子空間，另一方面在SR的更新過(guò)程，某些不能放下任何箱子的子空間也可被主動(dòng)剔除。所以所提出算法的計(jì)算復(fù)雜度遠(yuǎn)遠(yuǎn)小于O（2n2）。4實(shí)驗(yàn)與分析3D-RS0算法以Matlab實(shí)現(xiàn)，并運(yùn)行在 處理器的個(gè)人電腦，運(yùn)行環(huán)境為Windows7。實(shí)驗(yàn)數(shù)據(jù)來(lái)自于文獻(xiàn)［26］，其中包含有從BR1到BR15的異構(gòu)性從弱到強(qiáng)的15個(gè)算例組，每個(gè)算例組中又包含100個(gè)單獨(dú)的子算例。由于強(qiáng)異構(gòu)的三維裝箱問(wèn)題較難被求解且運(yùn)算時(shí)間較長(zhǎng)，所以本文以算例組BR8~BR15為對(duì)象進(jìn)行對(duì)比實(shí)驗(yàn)分析。其中，算例組BR8~BR15中的箱子種類數(shù)分別為30、40、50、60、70、80、90和100?；谒惴℉SA[9]、MLHS[10]、H0BTS[12]、TS_CLP[13]和3D-RSO的求解容器填充率和運(yùn)算時(shí)間如表1所示。HSA和MLHS是在C1和C2約束下構(gòu)建的，它們首先通過(guò)“塊”的預(yù)處理操作對(duì)箱子進(jìn)行整合，然后依靠不同的搜索策略來(lái)獲得一個(gè)較優(yōu)的容器裝載狀態(tài)。HSA將退火搜索引入其中，其運(yùn)算效果具有一定的隨機(jī)性不夠穩(wěn)定。MLHS采用了帶有回溯功能的多層啟發(fā)式搜索操作，運(yùn)算前要對(duì)6組參數(shù)進(jìn)行計(jì)算優(yōu)選。而HOBTS和TS_CLP能夠同時(shí)滿足C1、C2和C3的約束條件，它們同樣使用了箱子的預(yù)處理組合方式，其中HOBTS需要根據(jù)具體目標(biāo)反復(fù)運(yùn)行21次以得到一個(gè)較優(yōu)的參數(shù)設(shè)置，TS_CLP使用了樹(shù)搜索的操作方式，平均運(yùn)行時(shí)間最長(zhǎng)。雖然3D-RSO的平均填充率只有76.14%，相較于相同約束的TS_CLP低了14.84%，然而平均運(yùn)算時(shí)間卻從391.5s縮減到了0.26s。相比于其他三種算法，一方面HSA、MLHS和HOBTS的構(gòu)造復(fù)雜且需要大量的參數(shù)設(shè)置，另一方面這些參數(shù)也不固定，往往需要根據(jù)實(shí)際問(wèn)題來(lái)反復(fù)實(shí)驗(yàn)確定。所以總的來(lái)看，所提出3D-RSO極大縮減了算例的求解時(shí)間，適用于對(duì)快速響應(yīng)有要求的場(chǎng)合。算例BR15-1（填充率80.48%）和BR15-2（填充率75.39%）的裝載效果如圖7所示。表1各種算法的裝箱效果比較注：*表示BR1~BR15的平均運(yùn)算時(shí)間。算例約束時(shí)間/s時(shí)間/s時(shí)間/s時(shí)間/s時(shí)間/s時(shí)間/s時(shí)間/s時(shí)間/s時(shí)間/sHSAMLHSHOBTSTS_CLP3D-RSOC1&C2C1&C2C1，C2&C3C1，C2&C3C1，C2&C3填充率/%90.5693.1291.1891.9579.26261.87—83.62202.300.28填充率/%89.7092.4890.8491.6477.84276.12—104.78243.700.26填充率/%89.0691.8390.5991.4277.20288.90—134.16302.100.28填充率/%88.1891.2390.2891.1475.93287.25—157.55346.400.25填充率/%87.7390.5990.1490.9875.30306.36—192.81440.300.27填充率/%86.9789.9989.8590.6075.03307.68—224.88476.700.24填充率/%86.1689.3489.6190.2774.43305.82—237.37530.900.23填充率/%85.4488.5489.3889.8474.12301.26—268.72589.500.23填充率/%87.9890.8990.2390.9876.14291.90187.30*175.50391.500.26圖7算例BR15-1和BR15-2的裝載效果圖實(shí)際上，隨著箱子種類和數(shù)量的增加，以往算法中基于箱子預(yù)處理和最優(yōu)解搜索的計(jì)算消耗不斷膨脹，特別是針對(duì)大型三維裝箱問(wèn)題，其求解時(shí)間將會(huì)變得非常巨大為了進(jìn)一步驗(yàn)證所提出算法的高效求解性能，在此構(gòu)建了一個(gè)強(qiáng)異構(gòu)的三維裝箱算例組BR8_15，其中每個(gè)算例由相對(duì)應(yīng)的BR8到BR15共8個(gè)子算例組合而成，算例中箱子的種類數(shù)為520，容器的長(zhǎng)寬高分別擴(kuò)充為原來(lái)的兩倍。所提出算法的求解結(jié)果如表2所示，其平均填充率為83.64%，平均運(yùn)行時(shí)間為1.97s，子算例BR8_15-1和BR8_15-2的最終裝載效果如圖8所示?？梢?jiàn)，3D-RS0除結(jié)構(gòu)簡(jiǎn)單運(yùn)算高效外，還特別適用于對(duì)大規(guī)模強(qiáng)異構(gòu)三維裝箱問(wèn)題的快速求解。5結(jié)束語(yǔ)隨著裝箱問(wèn)題的深入研究，除了對(duì)單純填充率的不斷追求外，如何實(shí)現(xiàn)三維裝箱的高效求解也受到了越來(lái)越多的關(guān)注。本文首先借鑒二維裝箱中PH算法［25］的直接求解方式，通過(guò)發(fā)展一種三維的剩余空間最優(yōu)化策略，實(shí)現(xiàn)了每個(gè)箱子的概率性較優(yōu)放置。之后，基于所提出的剩余空間分割方法和箱子布置規(guī)則，構(gòu)建了啟發(fā)式的3D-RSO算法。該算法能夠在不需要額外預(yù)處理和最優(yōu)解搜索的情況下快速求解，其最壞的計(jì)算復(fù)雜度為O(2n2)。針對(duì)常規(guī)算例，雖然3D-RSO在填充率上有所不足，但是其極大地縮減了運(yùn)算時(shí)間，相較于同樣約束的TS_CLP算法，其將平均求解時(shí)間從391.5s減少到了0.26s。特別的，針對(duì)所提出包含有520類箱子的大規(guī)模強(qiáng)異構(gòu)體算例，3D-RSO能夠在1.97s的時(shí)間內(nèi)獲得83.64%的平均空間填充率，在整體的求解效率上具有優(yōu)勢(shì)。本文首次提出了一種快速的三維裝箱問(wèn)題直接求解算法，它適用于對(duì)運(yùn)算時(shí)間和運(yùn)算規(guī)模有特殊要求的情況，具有積極的研究和實(shí)際意義。但是現(xiàn)階段算法的求解效果仍有不足，下一步將綜合考慮運(yùn)算時(shí)間與填充率，對(duì)所提出算法進(jìn)一步地改進(jìn)與優(yōu)化。表23D-RS0對(duì)算例組BR8_15的計(jì)算結(jié)果？圖8算例BR8_15-1和BR8_15-2的裝載效果圖【相關(guān)文獻(xiàn)】DyckhoffUH,FinkeDOU.Cuttingandpackinginproductionanddistribution[M].Berlin：Springer，1992.GeorgeJA，RobinsonDF.Aheuristicforpackingboxesintoacontainer[J].Computers&OperationsResearch，1980，7（3）：147-156.BortfeldtA，GehringH.Ahybridgeneticalgorithmforthecontainerloadingproblem[J].EuropeanJournalofOperationalResearch，2001，131（1）：143-161.PisingerD.Heuristicsforthecontainerloadingproblem[J].EuropeanJournalofOperationalResearch，2002，141（2）：382-392.GehringH，BortfeldtA.Ageneticalgorithmforsolvingthecontainerloadingproblem[J].InternationalTransactionsinOperationalResearch，2010，4（5/6）：401-418.BortfeldtA，GehringH.Atabusearchalgorithmforweaklyheterogeneouscontainerloadingproblems[J].Operations-Research-Spektrum，1998，20（4）：237-250.EleyM.Solvingcontainerloadingproblemsbyblockarrangement[J].EuropeanJournalofOperationalResearch，2002，141（2）：393-409.FanslauT，BortfeldtA.Atreesearchalgorithmforsolvingthecontainerloadingproblem[J].InformsJournalonComputing，2010，22（2）：222-235.張德富，彭煜，朱文興，等?求解三維裝箱問(wèn)題的混合模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào)，2009,32（11） ：2147-2156.張德富，彭煜，張麗麗?求解三維裝箱問(wèn)題的多層啟發(fā)式搜索算法J].計(jì)算機(jī)學(xué)報(bào)，2012,35（12） ：2553-2561.ZhuW，LimA.Anewiterative-doublingGreedy-Lookaheadalgorithmforthesinglecontainerloadingproblem[J].EuropeanJournalofOperationalResearch，2012，222（3）：408-417.[12]劉勝，朱鳳華，呂宜生，等?求解三維裝箱問(wèn)題的啟發(fā)式正交二叉樹(shù)搜索算法J].計(jì)算機(jī)學(xué)報(bào)，2015，38(8)：1530-1543.LiuS，ShangX，ChengC，etal.Heuristicalgorithmforthecontainerloadingproblemwithmultipleconstraints[J].Computers&IndustrialEngineering，2017，108(C)：149-164.ZhengJN，ChienCF，GenM.Multi-objectivemultipopulationbiasedrandom-keygeneticalgorithmforthe3-Dcontainerloadingproblem[J].Computers&IndustrialEngineering，2015，89(C)：80-87.LiX，ZhangK.Ahybriddifferentialevolutionalgorithmformultiplecontainerloadingproblemwithheterogeneouscontainers[J].Computers&IndustrialEngineering，2015，90(C)：305-313.李孫寸，施心陵，張松海，等?基于多元優(yōu)化算法的三維裝箱問(wèn)題的研究[J].自動(dòng)化學(xué)報(bào)，2018，44(1)：106-115.張德富，魏麗軍，陳青山，等.三維裝箱問(wèn)題的組合啟發(fā)式算法[J].軟件學(xué)報(bào)，2007，18(9):2083-2089.HuangW，HeK.Acavingdegreeapproachforthesinglecontainerloadingproblem[J].EuropeanJournalofOperationalResearch，2009，196(1):93-101.HeK，HuangW.Anefficientplacementheuristicforthree-dimensionalrectangularpacking[J].Computers&OperationsResearch，2011，