基于0-1整數(shù)規(guī)劃的艦船內(nèi)集裝物資存放方法

于輝，王治國，李晶晶，葉又東，韓海榮

1 海軍駐大連船舶重工集團有限公司軍事代表室，遼寧大連116005

2 中國艦船研究設計中心，湖北武漢430064

0 引 言

大中型水面艦船在執(zhí)行作戰(zhàn)任務及海上補給的時候，需要運輸大量的武器彈藥、零部件和生活物品等物資。為了滿足作戰(zhàn)需求，避免較高危險性的物資長時間暴露于甲板，需安全高效地進行物資運輸［1-2］。采用軍用物資集裝化儲運對提高物資保障速度至關重要［3］，美國海軍將船內(nèi)物資的快速運輸作為一項重要內(nèi)容寫入海上補給發(fā)展規(guī)劃［4］。要想在未來信息化戰(zhàn)爭中實施高速度、大運量、遠距離和全方位的物資保障，必須大力推進軍用物資集裝化運輸工作的開展［5］。但由于集裝物資一般體積較大，受船型和船體結(jié)構(gòu)的影響，物資集裝化后不利于在艙內(nèi)儲存和運輸。

艦船內(nèi)部集裝物資的存放實質(zhì)是一種三維箱裝問題（3D packing problem）［6-7］，即在滿足艦船約束和貨物要求的條件下，以存放效益最大化為目標，找到一種將集裝物資裝滿船艙的方案。目前有大量關于船舶集裝化物資存放的研究。例如：孫俊清等［8］對船舶穩(wěn)定性的多港口集裝箱配載問題進行了研究，基于0-1 整數(shù)規(guī)劃，通過改進遺傳算法對問題進行求解，使得集裝箱配載效益得到明顯提升；汪達欽等［9］通過對散貨擺放規(guī)則的分析，將三維問題簡化為一維問題，提出了出廠物流整體優(yōu)化的散貨船舶配載模型與算法；Todd 等［10］以針對單港口的配載為題，根據(jù)多個標準，采用遺傳算法進行配載計算。但這些研究大多是針對集裝箱船舶，目標函數(shù)為單一經(jīng)濟指標，只考慮在船舶甲板上的裝卸，并未涉及到船舶內(nèi)部的存放問題，并且對船舶內(nèi)部物資存放效益指標也缺乏指導。因此，針對艦船內(nèi)部集裝物資存放的特點，研究集裝物資存放方法以提高存放效益，具有較大的研究和實用價值。

本文首先根據(jù)艦船內(nèi)部集裝物資存放的特點，對問題進行形式化描述，接下來根據(jù)形式化描述，定義艦船內(nèi)部集裝物資存放的一般目標函數(shù)和約束條件，提出基于層次分析法（AHP）［11］的集裝物資價值量評估方法，從而構(gòu)建基于0-1 整數(shù)規(guī)劃的艦船內(nèi)部集裝物資存放數(shù)學模型，并給出加速該模型計算的思路。最后，利用Excel 對實例進行規(guī)劃求解，并通過運用CAD 布置來證明方法的有效性。

1 問題描述

集裝物資一般采用標準化接口，分為若干種規(guī)格，可以描述成規(guī)整的長方體。集裝物資相對散貨物資而言，最大的特點就是采用了標準化的接口，減少因接口轉(zhuǎn)換而帶來的時間浪費，且簡化了操作，便于物資流轉(zhuǎn)，因此應用廣泛。集裝物資在艦船內(nèi)的存放不同于集裝箱運輸船舶在船體外的存放，其存放有以下特點：

1）集裝物資存放需要一定的操作空間。集裝物資是采用集裝儲具（托盤、包裝箱等）存放的。由于艦船出海時間較長，需要對存放的物資進行定期檢查、維護、管理和消防等工作，因此合理的存放間距是必要的。不同集裝物資之間的安全間距因物資種類的不同而不同。

2）某些集裝物資因某些原因不能存放在同一個艙室。譬如出于安全性考慮，強還原性物資和強氧化性物資不能存放在同一個艙室；油氣不能與精密電子產(chǎn)品放在同一個艙室；有毒有害物資不能與食物水源放置在同一個艙室等。

3）物資存放受船型、船體結(jié)構(gòu)等影響。一般物資儲存艙室位于船體底部，受船型影響較大，特別是對V 型等高速船舶而言，越往底部，船型收縮越嚴重。在存放集裝物資時，需考慮到船型的影響，充分利用船上寶貴的空間資源。

4）物資存放受運輸設備和運輸通道的影響。由于物資一般存放在船體底部，因此需要較長的運輸通道。另外，對于大型集裝儲具，需要借助運輸設備才能運輸，因此，在布置物資時需要考慮運輸設備的行程。

5）相比運輸船舶而言，艦船裝載的集裝物資排水量占比不大，因此對艦船穩(wěn)定性影響不大。

6）對于既定的基本任務，需要一定量的必備保障物資。對用戶來說，基本的生活保障物資和保障任務基本完成的物資是必須滿足的，即保障基本所需的物資數(shù)量具備一定的門限值，且所有存放方案必須滿足該值。

艦船出海一般伴隨著多項任務，不同的任務對物資有著不同的需求，因此各類物資具備不同的價值量，即物資在艦上存放的效益。從上述分析中，可以發(fā)現(xiàn)，艦船內(nèi)部集裝物資存放方法是一類典型的多約束多目標決策問題。對于該決策問題，進行如下描述：

1）存放問題P=(A，F(xiàn))，其中，A 是集裝物資單體價值量，F(xiàn) 為集裝物資存放方案。

2）存放方案F=(M，T，V，N)，其中，M 是規(guī)劃的某類物資儲存量的門限值，T 是集裝物資單體尺寸，V 是船艙容量，N 是集裝儲備物資混放的約束。

2 基于0-1整數(shù)規(guī)劃的存放方法

2.1 總體思路

對問題的描述進行分析。若是采用傳統(tǒng)的三維箱裝問題求解方法，則需考慮集裝物資的長、寬、高三維空間因素，其算法計算量會因變量的增加呈指數(shù)上升，不僅計算速度慢，而且可能導致內(nèi)存溢出致使無法得到計算結(jié)果。

針對該問題，最有效的方法是降低問題維度，將復雜的三維問題轉(zhuǎn)化為二維甚至是一維問題，以快速求解，得到滿意答案。基本思路如下：

1）根據(jù)運輸通道能力，考慮艙室內(nèi)同一垛布置同一類集裝物資，將三維問題轉(zhuǎn)化成二維問題，每個儲存位置作為1個0-1變量。

2）將通過單一集裝物資布置填充整個可布置的二維空間。

3）將填充完成的二維空間重合，枚舉其中的干涉情況。

4）剔除同一艙室內(nèi)不可混放的集裝物資布置。

5）考慮門限值，作為集裝物資存放的最小值約束。

6）以價值量為目標函數(shù)系數(shù)，求取定義模型的最大值。

2.2 目標函數(shù)

某集裝物資是否存放于艙內(nèi)某處空間，會有2 種狀態(tài)，可以用0 或1 來表示，與0-1 整數(shù)規(guī)劃思想吻合。

將整個艙室存放空間用某一類集裝物資全部填充，則任意一處集裝物資存放空間可以視為1個存放單元xi，j，其中i 為集裝物資的種類編號，j為該類集裝物資的布置單元編號，xi，j=1 表示該存放單元存放集裝物資，xi，j=0 表示該存放單元不存放集裝物資。其他集裝物資也采用xi，j來表示，并檢查空間干涉情況。

令λi為集裝物資i 單體的價值量，z 為總價值量。則整個存放問題P 的目標函數(shù)為：

2.3 價值量

價值量的確定采用層次分析法（Analytic Hierarchy Process，AHP）。該方法是一種定性與定量分析結(jié)合的多目標決策分析方法，其將決策者的經(jīng)驗判定給予量化，適用于目標（因素）結(jié)構(gòu)復雜且缺乏必要數(shù)據(jù)的情況，在國內(nèi)外應用廣泛。使用AHP 對艦船內(nèi)物資存放價值量進行分析的示意圖如圖1 所示。

圖1 貯存價值量層次結(jié)構(gòu)圖Fig.1 Hierarchy of stored value

其中，目標層反映了提高物資存放效益是本次出海總存放目標；準則層反映了一大類物資，按照具體的任務分類，增加該類物資效益即增加了任務完成的能力，例如生活保障物資、救援醫(yī)療物資、作戰(zhàn)物資等；措施層反映了存放的具體物資，其中某項具體物資可能對應多個準則層的大類物資；比如桶裝飲用水既是生活保障類物資，也是救援醫(yī)療物資。

依據(jù)圖1 進行矩陣運算可以得到A～K 等集裝物資的價值量。具體步驟如下：

1）先對目標層和準則層以“增加一類物資效益”為權(quán)重1，然后以其為基礎，以專家經(jīng)驗和認知標準，讓多個專家打分，得到“增加二類物資效益”和“增加三類物資效益”的價值量。

2）對各個專家打分求平均值，然后對這3 個數(shù)值進行歸一化處理，得到準則層物資大類相對目標層的價值量，整理為矩陣Ⅰ。

3）然后對準則層和措施層采用步驟1）和2），得到措施層物資相對準則層物資大類的價值量，整理為矩陣Ⅱ。

4）最后，通過矩陣Ⅰ和矩陣Ⅱ的矩陣相乘得到措施層物資相對目標層的價值量λi，整理為矩陣Ⅲ。矩陣Ⅲ即為目標函數(shù)式（1）中的輸入λi。

2.4 約束條件

存放方案F 必須滿足約束條件。令布置單元長度為Li，寬度為Wi，高度為Hi，則集裝物資單體尺寸T={Li，Wi，Hi} ；令集裝物資i 儲存量門限值為mi，則mi∈M ；令艙室可存放空間橫向尺寸為p，縱向尺寸為q，垂向尺寸為g，則船艙容量尺寸V={p，q，g }。根據(jù)尺寸參數(shù)，用集裝物資對每一個艙室進行全部填充，而后將填充后的圖樣疊放在一起，明確集裝物資之間的干涉關系，以及根據(jù)混放約束N 得到存放方案F 的一般約束條件，具體敘述如下。

干涉約束：

對于任意集裝物資i 的布置單元j 和與它干涉的其他集裝物資a 的布置單元b 有如下關系：

不可混放約束：對于任意艙室內(nèi)的集裝物資i和a，不可混放下的約束如下：

式中，j 和b 為同一艙室所有的布置單元。

門限值約束：

式中，j 為艙內(nèi)所有布置單元。

0-1整數(shù)約束：

2.5 加速計算建議

基于0-1 整數(shù)規(guī)劃會隨著問題規(guī)模的不斷擴大呈現(xiàn)指數(shù)上漲，所以在0-1 規(guī)劃的基礎上，還需進一步改進，以縮小算法搜索空間來加速計算。針對上述方法特點，給出加速計算的建議：

1）分支界定法。該方法是一類常用的加速計算方法，為通過已經(jīng)求解的一個可行解，將解的目標值作為約束插入數(shù)學描述中，其理由是希望找到一個比這更優(yōu)的解。該約束將最優(yōu)解和其他解分離開來，使其能夠在更小的空間進行搜索。當執(zhí)行一段時間后，再從中找到一個更優(yōu)解，以該解作為約束替換之前的。如此，則將原本指數(shù)性增長的搜索方法替換成多項式類型，極大減少了搜索空間和時間。

2）根據(jù)艙室要求，減少艙室內(nèi)不同集裝物資的組合種類。比如有些艙室門開口太小，大型集裝物資無法進出；有些艙室有嚴格的衛(wèi)生要求，那么該類艙室只能存放符合衛(wèi)生標準的集裝物資。

3）某幾類集裝物資可以等同考慮，減少輸入?yún)?shù)數(shù)量。由于集裝物資采用了統(tǒng)一的規(guī)格，因此會出現(xiàn)幾種集裝物資采用同一種儲具的情況。這時可以將這些采用同一種儲具的物資等同考慮。

4）根據(jù)物資的特殊存放要求，減少不同物資的存放組合。比如食品類物資宜分塊集中存放，以方便使用；質(zhì)量大的物資宜在艙底存放，以減小對船舶穩(wěn)性的影響。

3 實例分析

本文選擇Excel 為規(guī)劃軟件。“規(guī)劃求解”是Excel 中的一個加載宏，其線形和整數(shù)規(guī)劃問題取自Frontline Systems 公司的John Watson 和Dan Fylstra 提供的有界變量單純形法和分支定界法。由于Excel 的應用廣泛，且易于操作，對低復雜度的規(guī)劃模型具備一定的規(guī)劃能力，因此，采用Excel規(guī)劃案例能夠證明方法的有效性。

例子說明：有A～F 6 種集裝物資需放入2 個船艙內(nèi)，其中A，B 為甲類物資，C，D 為乙類物資，E，F(xiàn) 為丙類物資，甲類物資和丙類物資不可混放。6種集裝物資門限值分別為2，2，1，1，1，1，集裝物資尺寸如表1 所示，艙室尺寸如表2 所示，求各種集裝物資的布置方案。

表1 集裝物資尺寸Tab.1 Size of integrated materials

表2 艙室尺寸Tab.2 Size of the cabin

根據(jù)實例說明，進行求解，流程如圖2 所示。

圖2 求解流程圖Fig.2 Resolving flow chart

求解步驟如下：

1）根據(jù)AHP 方法，由專家打分，分解得到6種集裝物資準則層與指施層的價值量比值分別為1，1，3，3，5，5，如圖3 所示。

2）考慮加速計算。根據(jù)例子可以看到，集裝物資A 和B 的尺寸相當，B 可以等同集裝物資A 處理；同樣，C 和D 的尺寸相當，E 和F 的尺寸相當，D可以等同集裝物資C 處理，F(xiàn) 可以等同集裝物資E處理。

圖3 AHP 分解圖Fig.3 Decomposition chart by AHP

3）建立目標函數(shù)：

式中，x1，j表示集裝物資A（B）的存放，x2，j表示集裝物資C（D）的存放，x3，j表示集裝物資E（F）的存放。x1，j，x2，j，x3，j的價值量與所表示的集裝物資相同，分別為1，3，5，門限值為所表示的集裝物資門限值之和，分別為4，2，1。

4）根據(jù)上述數(shù)據(jù)，畫出填充圖（數(shù)字表示布置單元編號）如圖4 所示。

圖4 物資填充圖Fig.4 Materials fill diagram

5）根據(jù)填充圖和例子數(shù)據(jù)，列出如下約束條件。

干涉約束條件為

式中i，j，a，b 表示任意集裝物資i 的布置單元j 和與它干涉的其他集裝物資a 的布置單元b。

不可混放約束：

門限值約束條件為：

0-1整數(shù)約束：

6）使用Excel進行規(guī)劃，求解值見表3。

表3 Excel規(guī)劃結(jié)果Tab3 Programmed results by Excel

7）根據(jù)規(guī)劃結(jié)果進行CAD 布置，以驗證規(guī)劃結(jié)果的合理性，如圖5所示。

圖5 CAD 布置結(jié)果Fig.5 Placement result by CAD

由表3 和圖5 可以看出，規(guī)劃結(jié)果合理，驗證了本文提出的規(guī)劃方法的有效性。能夠通過Excel 進行快速求解，說明該方法有效控制了算法規(guī)模，成功降低了運算維度，具有較大的學術研究和工程實用價值。

4 結(jié) 語

集裝物資存放是艦船內(nèi)部物流中常見的問題，本文根據(jù)艦船內(nèi)部集裝物資的存放特點，進行問題的形式化描述，提出了基于0-1 整數(shù)規(guī)劃的存放方法。該方法首先定義了艦船內(nèi)部集裝物資存放的一般目標函數(shù)和約束條件，提出了基于AHP 的集裝物資價值量評估方法和基于0-1 規(guī)劃的數(shù)學模型，然后給出了加速該問題0-1 整數(shù)規(guī)劃的計算思路，最后，利用Excel 對實例進行規(guī)劃求解，并通過CAD 布置來證明該方法的有效性。結(jié)果證實，該方法能夠較快速地進行求解，結(jié)果正確合理，具有較大的研究和實用價值。

但是，本方法是依據(jù)已有的填充方案，因而只是在已有方案的基礎上進行的優(yōu)化，最優(yōu)解也是局部最優(yōu)解，不能代表整個問題的最優(yōu)解，這也是加速運算，縮減搜索空間的代價。所以，下一步考慮通過合理增加已有填充方案，擴大搜索空間，采用遞進求解的方式，在保證運算時間的基礎上，盡量擴大搜索空間，以最大限度地逼近最優(yōu)解。

［1］王凱，趙彥森.基于改進遺傳算法的艦船物資轉(zhuǎn)運方案研究［J］.艦船電子工程，2013，33（6）：114-115，162.WANG Kai，ZHAO Yansen. Material transport scheme on ships based on improved genetic arithmetic［J］.Ship Electronic Engineering，2013，33（6）：114-115，162.

［2］張曉東，童劍，郭敏，等.艦船物資轉(zhuǎn)運方案計算機輔助決策算法研究［J］.中國艦船研究，2011，6（4）：104-110.ZHANG Xiaodong，TONG Jian，GUO Min，et al. Com?puter aided decision-making method for material trans?fer planning on ship deck［J］. Chinese Journal of Ship Research，2011，6（4）：104-110.

［3］陳興剛，劉振華，郭寶華.實施軍用物資集裝包裝之我見［J］.包裝工程，2006，27（3）：229-233.CHEN Xinggang，LIU Zhenhua，GUO Baohua.Discus?sion on implementing integrated packaging of military supplies［J］. Packaging Engineering，2006，27（3）：229-233.

［4］王曉林.美國海軍海上補給裝備發(fā)展趨勢研究［J］.物流技術，2007，26（6）：127-128.WANG Xiaolin. Research on the trend of replenishing equipment of US Navy［J］. Logistics Technology，2007，26（6）：127-128.

［5］侯仁海，王金松，殷鵬.集裝箱滾裝托盤系統(tǒng)在軍用物資運輸中的應用研究［J］. 國防交通工程與技術，2010（6）：60-63.HOU Renhai，WANG Jinsong，YIN Peng. A study of the application of the container roll-in-and-roll-out platform to the transport of military materials［J］. Traf?fic Engineering and Technology for National Defence，2010（6）：60-63.

［6］DYCKHOFF H.A typology of cutting and packing prob?lems［J］. European Journal of Operational Research，1990，44（2）：145-159.

［7］DYCKHOFF H. A new linear programming approach to the cutting stock problem［J］. Operations Research，1981，29（6）：1092-1104.

［8］孫俊清，陳忱，劉鳳連.考慮船舶穩(wěn)定性的多港口集裝箱配載問題［J］.計算機工程與應用，2012，48（32）：236-243.SUN Junqing，CHEN Chen，LIU Fenglian. On stow?age planning for mult-port container transportation based on stability constraint［J］. Computer Engineering and Applications，2012，48（32）：236-243.

［9］汪達欽，霍佳震，張麗華.出廠物流整體優(yōu)化的散貨船舶配載模型與算法［J］.工業(yè)工程與管理，2010，15（5）：11-16.WANG Daqin， HUO Jiazhen， ZHANG Lihua.Bulk-cargo ship stowage model and algorithm for the optimization of external logistics［J］. Industrial Engi?neering and Management，2010，15（5）：11-16.

［10］TODD D S，SEN P. A multiple criteria genetic algo?rithm for containership loading［C］//IEEE Proceedings of the 7th International Conference on Genetic Algo?rithms，1977：674-680.

［11］汪應洛.系統(tǒng)工程［M］.2 版.北京：機械工業(yè)出版社，2002.