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

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

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

2 中國艦船研究設(shè)計(jì)中心，湖北武漢430064

0 引 言

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

2.1 總體思路

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

針對(duì)該問題，最有效的方法是降低問題維度，將復(fù)雜的三維問題轉(zhuǎn)化為二維甚至是一維問題，以快速求解，得到滿意答案?；舅悸啡缦拢?/p>

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

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

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

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

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

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

2.2 目標(biāo)函數(shù)

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

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

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

2.3 價(jià)值量

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

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

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

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

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

2）對(duì)各個(gè)專家打分求平均值，然后對(duì)這3 個(gè)數(shù)值進(jìn)行歸一化處理，得到準(zhǔn)則層物資大類相對(duì)目標(biāo)層的價(jià)值量，整理為矩陣Ⅰ。

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

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

2.4 約束條件

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

干涉約束：

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

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

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

門限值約束：

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

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

2.5 加速計(jì)算建議

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

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

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

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

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

3 實(shí)例分析

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

例子說明：有A～F 6 種集裝物資需放入2 個(gè)船艙內(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ù)實(shí)例說明，進(jìn)行求解，流程如圖2 所示。

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

求解步驟如下：

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

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

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

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

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

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

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

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

干涉約束條件為

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

不可混放約束：

門限值約束條件為：

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

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

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

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

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

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

4 結(jié) 語

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

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

［1］王凱，趙彥森.基于改進(jìn)遺傳算法的艦船物資轉(zhuǎn)運(yù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)運(yùn)方案計(jì)算機(jī)輔助決策算法研究［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］陳興剛，劉振華，郭寶華.實(shí)施軍用物資集裝包裝之我見［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］王曉林.美國海軍海上補(bǔ)給裝備發(fā)展趨勢(shì)研究［J］.物流技術(shù)，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)在軍用物資運(yùn)輸中的應(yīng)用研究［J］. 國防交通工程與技術(shù)，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］.計(jì)算機(jī)工程與應(yīng)用，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］汪達(dá)欽，霍佳震，張麗華.出廠物流整體優(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］汪應(yīng)洛.系統(tǒng)工程［M］.2 版.北京：機(jī)械工業(yè)出版社，2002.