寫在前面

由于某些原因，這篇文章還沒寫完就作者就搞別的問題去了，寫到一半很不好意思，大家可以去看原文對應(yīng)的論文進一步研究：【A skyline heuristic for the 2D rectangular packing and strip packing problems】。祝大家學(xué)習(xí)順利~

前言

今天為大家介紹二維矩形裝箱問題（2D rectangular packing problem， 簡稱2DRP）以及在此基礎(chǔ)上拓展的二維帶裝箱問題（2D strip packing problem，簡稱2DSP）。
這次介紹的算法運用了啟發(fā)式算法**禁忌搜索算法（Tabu search，簡稱TS）**的相關(guān)知識，如果小伙伴們還沒有掌握，可以在公眾號內(nèi)查閱以下推文：

對了解禁忌搜索的同學(xué)而言，相信這次的算法不會很難接受。話不多說，這就開始今天的介紹吧！

問題介紹

裝箱問題廣泛存在于物流運輸?shù)能噹b載、集裝箱裝載、托盤裝載,以及工廠企業(yè)的材料切割、成品包裝、設(shè)施布局規(guī)劃等場合中。在當(dāng)前經(jīng)濟環(huán)境下，庫存與物流活動越來越顯示出其重要性，如何降低庫存與物流成本就成為一個很重要且迫切的問題。

本文中提到的“”二維矩形裝箱裝箱問題（2DRP）**，主要考慮二維情形下，所有目標(biāo)項目都為矩形，目的是最大化可用面積，并允許矩形放置時正交旋轉(zhuǎn)，是經(jīng)典的NP-Hard問題：
給出n個wi?hiw_i*h_iwi??hi?的維數(shù)為矩形。目標(biāo)是將沒有重疊的矩形正交地放置在一個尺寸為W?HW*HW?H的大矩形(稱為sheet)中，使所有放置的矩形的總面積最大化。所有的維數(shù)都被認為是整數(shù)。本文介紹的算法允許矩形旋轉(zhuǎn)90°，但不處理的斷頭可分性（guillotine-cut constraint）。

在此基礎(chǔ)上，另一個和2DRP密切相關(guān)的切割和包裝問題是二維帶包裝問題(2DSP)。給定n個矩形，任務(wù)是將所有矩形放置在一個寬度為W的矩形帶，目標(biāo)是最小化矩形帶的高度H。

算法介紹

描述裝箱模式

算法通過上界線（skyline） 和 坐標(biāo)點（candidate position） 的概念來描述裝箱模式。
在算法中，我們盡量將矩形放置在下方。簡單來講，上界線表示最上層矩形的上邊界；坐標(biāo)點代表所有上界線的左下角和右下角坐標(biāo)。
如圖所示，圖中最上層水平直線部分為該裝箱方式的上界線，分為5段，分別記作s1,s2,s3,s4,s5s_1,s_2,s_3,s_4,s_5s1?,s2?,s3?,s4?,s5?。圖中實心圓點代表坐標(biāo)點，共有3個左側(cè)坐標(biāo)點，3個右側(cè)坐標(biāo)點。

嚴謹表述為：

用上界線表示當(dāng)前的裝箱模式，表示為一組水平線，滿足以下性質(zhì)：
1.每條線段的y坐標(biāo)與下一條線的不同；
2.線段sjs_jsj?右端的x坐標(biāo)和sj+1s_{j +1}sj+1?左側(cè)末端的x坐標(biāo)相同。

si?1s_{i -1}si?1?左端點的y坐標(biāo)大于sis_isi?左端點的y坐標(biāo)，或線段sis_isi?右端點的y坐標(biāo)大于si+1s_{i+1}si+1?大于右端點的y坐標(biāo)時，標(biāo)記sis_isi?左端點或右端點為坐標(biāo)點。
其中s1s_1s1?的左端點和sks_ksk?的右端點一直是坐標(biāo)點。

算法按順序一個一個放置矩形。每個矩形的位置，要么是左下角接觸到線段的左端點，要么是其右下角接觸到線段的右端點。每次放置矩形后，更新上界線和坐標(biāo)點，用來描述新的裝箱方式。
當(dāng)矩形b被放置在線段sis_isi?上時，上界線被更新。這需要兩個步驟：

1.生成與b的上邊緣對應(yīng)的新線段，并更新受影響的現(xiàn)有線段。

b的寬度是否大于sis_isi?會產(chǎn)生兩種情況，下圖分別展示了兩種情況的示例，以及上界線如何更新。注意，(d)中的陰影區(qū)域被認為是浪費的空間，因為我們的算法不會考慮在其中放置任何矩形。

2.檢查每條線段，如果它比相鄰的兩個線段都低，并且沒有未放置的矩形可以放置在這個線段上（對于第一個和最后一個段，我們只將它們與它們相鄰的一條線段進行比較），我們將它提升到它的下相鄰段的高度并合并它們。
如圖所示，陰影部分同樣被認為是浪費的空間。

評估裝箱策略

這里的裝箱策略指：在當(dāng)前裝箱模式下，具體某個矩形的放置位置。我們利用以下規(guī)則評估每個位置：

1.spread construction。
對放置后y坐標(biāo)的差值進行約束。放置矩形后，所有線段s的y坐標(biāo)最大值與最小值之差不得超過限定值max_spread。

2.only fit。

3.minimum local waste。

4.maximum fitness number。

5.earlist in sequence。

禁忌搜索

拓展：2DSP

總結(jié)

以上是生活随笔為你收集整理的二维矩形装箱问题（2D rectangular packing problem， 简称2DRP）介绍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。