賀紅燕 趙紅梅

(河北政法職業(yè)學(xué)院 河北 石家莊 050000)

0 引 言

隨著全球化發(fā)展，規(guī)模化廠房和鐵路等大型平臺的遠距離、跨區(qū)域布設(shè)已成為一種常見的經(jīng)濟現(xiàn)象。海上運輸是大型平臺的主要機動方式，其運輸對象包括各類獨立部門的設(shè)備器件以及對應(yīng)的專業(yè)型雇員，是一個“人貨同運”活動。為高效、快速和低成本地實施大型平臺的遠洋運輸，需要對運輸?shù)馁Y源與對象進行合理規(guī)劃，調(diào)配裝載方案，提高各部門到港后的快速作業(yè)反應(yīng)能力,壓縮船隊的控制維護成本,實現(xiàn)載具的空間使用最大化。

求解滿足特定要求的裝載方案的問題被抽象為集裝箱問題(Container Loading Problem,CLP)，在前人研究中被證明是NP-Hard問題[1-2]，即無法明確得到全局最優(yōu)的形式解。研究者們往往以智能算法為工具，基于問題背景有所側(cè)重地構(gòu)造模型,從而求得符合自身需求的滿意解。其中:Ramos等[3]提出了動態(tài)穩(wěn)定性度量指標，以提高貨物運輸?shù)陌踩?；程中文[4]和左先亮等[5]引入了三維空間分隔法，以實現(xiàn)裝載空間利用率最大化；Monaco等[6]主要關(guān)心單個港口上裝載所需時長的最小化；在多港口背景下，鄭斐峰等[7]討論了最小耗時的求解域建模，孫俊青等[8]則針對最高穩(wěn)定性進行研究。先前研究中當(dāng)CLP模型的自變量空間較小或優(yōu)化目標單一時，采用經(jīng)典搜索方法如樹形搜索[9]、鄰域搜索[10]、二次禁忌搜索[11-12]等能達到較好效果；當(dāng)約束及優(yōu)化目標復(fù)雜、搜索空間大時，采用遺傳算法[13]、蟻群算法[14]、自適應(yīng)細菌覓食算法[15]及其他改進啟發(fā)式算法[16-18]能達到較好效果?？傮w而言，CLP模型求解方法較為靈活，立足模型本身特點，謀求在高收斂速度和高全局尋優(yōu)能力兩種性能上達到一個理想的均衡中值。

雖然前人研究豐富詳實，但缺乏對人員、貨物與船舶三者間匹配性約束的討論，同時缺乏對運輸成本、靠港后作業(yè)效率的考量，尤其在大型平臺遠洋運輸背景中，應(yīng)考慮通用貨船只能運載設(shè)備，通用客船只能運載人員，而平臺架設(shè)專用船舶則可同步運輸人員貨物的客觀情況[19]。綜上所述，本文基于大型平臺遠海運輸現(xiàn)實情況，提出了靠港后快速作業(yè)反應(yīng)、縮減船隊規(guī)模以降低控制維護成本、最大化利用船舶空間三項度量指標，構(gòu)造了多目標優(yōu)化函數(shù)，建立了大型遠洋作業(yè)中涵蓋多類工種部門與船型之間的約束關(guān)系式。此外，本文立足于分治思想，基于對專用、通用兩類船舶特性詳細分析，對求解過程進行拆分，降低解空間復(fù)雜度，從而實現(xiàn)收斂速度的提升。

1 大型平臺海運裝載模型

基于大型平臺運輸?shù)膶嶋H情況，本文構(gòu)造模型時遵循以下假設(shè)：(1) 運輸對象涉及多個工種部門，各部門具有不同的設(shè)備、人員;(2) 一個部門由多個分隊組成，同一部門下的分隊人員物資情況一致;(3) 各部門登船以分隊為最小單位;(4) 當(dāng)船舶剩余空間不足裝載任何分隊時，不可將分隊拆散裝入船舶中;(5) 登船的前后順序不影響該船只的裝載能力;(6) 執(zhí)行任務(wù)的專用船舶數(shù)目有限，而通用船只數(shù)目可依需求增減;(7) 必須在一次行動中將所有部門裝載完畢，不可反復(fù)、多次運輸;(8) 可以將設(shè)備與人員分離運輸，但仍必須以分隊為最小單元;(9) 當(dāng)同一分隊下的設(shè)備和人員同時在一艘船只上運輸時，分隊在靠港后可直接執(zhí)行作業(yè)任務(wù)；(10) 當(dāng)設(shè)備和人員分離運輸時，必須先將兩者結(jié)合為整體，需要花費一定的反應(yīng)時間。

考慮到這一問題的特點，本文在建立模型時，以裝載方案為自變量，采用自然數(shù)矩陣XC×2N進行描述：

式中：N為待運輸?shù)牟块T種類數(shù);C為船舶數(shù)目。矩陣中的元素xi,j表示第i艘船只裝載第j類部門的分隊數(shù)量,采用2N的列數(shù)是由于每一類部門均可拆分為人員及設(shè)備兩部分。

1.1 模型優(yōu)化目標設(shè)計

結(jié)合實際環(huán)境，本文設(shè)計了三類優(yōu)化指標，并通過加權(quán)求和的方式組合為多目標優(yōu)化函數(shù)。

1) 空載率。遠洋運輸條件下，載具資源十分昂貴，但由于假設(shè)(3)和假設(shè)(4)，船舶難以實現(xiàn)滿載，必須考慮如何用有限的空間運輸盡量多的貨物。對此，本文提出了“空載率”指標，用于量化對載具資源的利用程度，公式如下：

(1)

2) 船隊規(guī)模。遠洋航行過程中，運輸船隊常保持一定隊形以實現(xiàn)相互補給、協(xié)同交流，有效規(guī)避海運事故或海洋犯罪事件；另外，船隊中的每艘船只本身都需要消耗一定的油料、物資。因此，船隊的規(guī)模越大，指揮、維護船隊的耗費越大，運輸?shù)某杀驹礁?，因此，在制定裝載方案時，必須考慮縮小船隊規(guī)模，減少不必要的運輸成本。對此，本文提出“船隊規(guī)模”指標，用于量化描述運輸裝載方案實施耗費的成本。

(2)

3) 人貨分離率。根據(jù)假設(shè)(9)和假設(shè)(10)，為使各部門在靠港后盡快投入作業(yè)任務(wù)，在運載時應(yīng)盡量使得同一個分隊下的人員及設(shè)備裝載在同一艘船只上，減免出現(xiàn)人貨分離運載的情況。對此，本文提出了“人貨分離率”指標，用于量化描述某裝載方案下的快速反應(yīng)作業(yè)能力。

(3)

式中：∑com_uniti表示裝載于同一艘船只上的同屬一個分隊的人員、設(shè)備的分隊數(shù)目;ZJZ表示分隊總數(shù)。式(3)的取值越小，則證明人員與設(shè)備越集中，作業(yè)反應(yīng)時間越短，效率越高。

基于上述三個指標，通過加權(quán)求和的方式組成多目標優(yōu)化函數(shù)：

f=w1·Rkz+w2·Rgm+w3·Rfl

(4)

式中：w1、w2、w3分別為各個指標權(quán)值。本模型的目的就是求得使式(4)取值盡可能小的一組解。

1.2 模型約束函數(shù)設(shè)計

本文主要從船舶可裝載面積限制、船舶可裝載重量限制、待運輸單元總體恒定限制、船舶與部門相互匹配限制考慮，制定了以下約束條件：

(5)

(6)

(7)

(8)

式(5)表示分配給j船只的所有單元的占地面積之和不大于j船只的最大可運輸面積;式(6)表示分配給j船只的所有單元的重量之和不大于j船只的可承重極限;式(7)表示第i類部門在本分配方案下可以全部分配完畢;式(8)表示第i類部門不可被裝載在與其不匹配的運輸資源上。

綜上所述，在N類部門、C艘可用船只的情形下，本模型構(gòu)造了4N個不等式約束及2C個等式約束。

1.3 模型復(fù)雜度分析

根據(jù)上述分析，模型的公式化表述如下：

minf(XC×2N)=w1·Rkz+w2·Rgm+w3·Rfl

(9)

對N類部門、C條船只，上述模型解可能的搜索空間大小為：

(10)

式中：mi為第i類部門的分隊數(shù)目。

(11)

根據(jù)模型的公式化表述，構(gòu)造拉格朗日函數(shù)如下：

f(X)+μTh(X)+λTg(X)

(12)

假設(shè)▽xxL(X*,λ*)正定，要獲得局部最優(yōu)值，必須符合的KKT條件為：

(13)

顯然，由于自變量維度大、等式不等式約束數(shù)目多，使拉格朗日算子復(fù)雜，即使作光滑化處理，依然不具備好的凸優(yōu)化方法應(yīng)用條件，且▽xxL(X*,λ*)正定條件嚴格，難以給出形式解。

綜上所述，模型復(fù)雜度較高，一方面，自變量搜索空間廣，無法通過簡單的枚舉求解;另一方面，繁瑣的拉格朗日函數(shù)難以用經(jīng)典凸優(yōu)化方法求解。上述分析結(jié)論反映了模型NP-Hard特性。因此，本文首先基于分治思想對自變量空間進行降維，而后采用遺傳算法快速收斂至理想的可行解。

2 基于分治思想和遺傳算法的求解

2.1 分治方法的應(yīng)用效益分析

本文構(gòu)建的模型較為復(fù)雜，對此引入了分治與遺傳算法兩種求解方法。分治是指將耦合度較高的復(fù)雜問題分解為多個相對簡單的可獨立求解的子問題，通過將多個子問題的解組合構(gòu)造出原問題的一個可行解。為證明分治思想在大型作業(yè)平臺遠海運輸裝載問題上的可行性，基于背景條件及模型的數(shù)學(xué)化描述，給出以下分析：

1) 裝載計劃中，應(yīng)優(yōu)先使用專用船舶。由于專用船舶具備同時裝載設(shè)備與人員的能力，可以完整運輸一個分隊，不占用多的運載空間、無須擴展船隊規(guī)模；相對地，由文獻[19] ，通用船只運載能力往往受限，客貨分離特征明顯，人貨結(jié)合度低，且有可能需要較大船隊規(guī)模完成運輸任務(wù)。因此，在裝載規(guī)劃中，專用船舶的使用優(yōu)先度高。當(dāng)專用船舶有剩余空間時，應(yīng)優(yōu)先裝載專用船舶。

2) 由于需裝載對象總量大于專用船舶承載量，結(jié)合優(yōu)先裝載專用船舶的分析，有以下推論：針對專用船舶的裝載規(guī)劃問題，在船隊規(guī)模、人貨分離率兩個指標上可達最優(yōu)邊際(規(guī)模壓縮至最小，為全體專用船舶的數(shù)目總和，是固定值；采用人貨結(jié)合形式裝載，分離率為局部最小值)。

因此，在討論整體裝載問題時，考慮到專用船舶裝載部分本身可以達到邊際最優(yōu)的解。在求解時，可以將該部分獨立分離，構(gòu)造子問題(1)——“專用船舶裝載規(guī)劃”。

3) 剩余需裝載對象以三大指標構(gòu)造的混合目標函數(shù)裝載到通用船舶上，可構(gòu)造子問題(2)——“通用船舶裝載規(guī)劃”。

兩個子問題的模型為原模型的調(diào)整變形，對子問題(1)的變形，模型如下：

minf(XnZC×N)=w1·Rkz+w2·Rfl

(14)

式中：nZC為專用船舶數(shù)量。

對子問題(2)，其模型如下：

minf(XnTC×2nSN)=w1·Rkz+w2·Rgm+w3·Rfl

(15)

式中：nTC為通用船舶數(shù)量;nSN為剩余的待裝載人員、貨物總和;smi為i類部門剩余的數(shù)目。

采用分治理論后，搜索空間大小為：

(16)

搜索空間數(shù)量級為：

(17)

式中：max(·)運算表示取括號內(nèi)元素的最大值。由于nZC

O2

(18)

即分治方法實現(xiàn)了解空間的收縮。

在通過分治將原模型分解為兩個子模型后，本文采用了遺傳算法進行解的尋優(yōu)。遺傳算法作為一種最常用的智能仿生算法，具有設(shè)計簡單、收斂較快、計算復(fù)雜度低等優(yōu)點。算法自然基因編碼規(guī)則令第i行第j列的值編碼值=自適應(yīng)變量矩陣X中對應(yīng)的元素xij。

令算法適應(yīng)度函數(shù)等同兩類子問題優(yōu)化函數(shù)，對子問題(1)：

fitness=w1·Rkz(XnZC×N)+w2·Rfl(XnZC×N)

(19)

對子問題(2)：

fitness=w1·Rkz(XnTC×2nSN)+

w2·Rgm(XnTC×2nSN)+w3·Rfl(XnTC×2nSN)

(20)

算法中遺傳算子采用交叉、變異兩類，基于算子變換產(chǎn)生的子代可實現(xiàn)對自變量矩陣空間的覆蓋。

綜上所述，采用分治方法與遺傳算法相結(jié)合的求解方法，從理論上得證能顯著收縮解的搜索范圍，顯著提高求解效率。

2.2 分治方法的適用性分析

根據(jù)式(10)，本文構(gòu)造的模型為NP-Hard問題，難以求出公式化完備解，無法確保解的全局最優(yōu)性。采用智能算法求解該類型問題，得到的解是鄰域內(nèi)極小點，具有局部最優(yōu)特性。

利用分治算法將問題拆分為兩個子問題，子問題的求解相互獨立，子問題(1)的解構(gòu)成了子問題(2)的條件。子問題(1)與子問題(2)都是可證具有全局優(yōu)化特點的解，因此當(dāng)兩者相互合并構(gòu)成的解必定是在子問題(1)的解的優(yōu)化方向的一個極值點，即該解在鄰域范圍內(nèi)最優(yōu)，為局部最優(yōu)點。

綜上所述，采用分治方法后取得的解與采用分治方法前的解一致，均為局部最優(yōu)解。

2.3 仿真結(jié)果分析

基于實際情況設(shè)計仿真場景，表格中數(shù)據(jù)由一次鐵路組件遠海安裝的航運實際數(shù)值簡化得到。表1展示了各部門與船舶的裝載匹配關(guān)系；表2展示了需要裝載的各部門數(shù)量、占地面積及重量；表3展示了各船只的最大載重量、最大運載面積及排水量及可使用數(shù)目。實驗中目標函數(shù)的優(yōu)化參數(shù)權(quán)值采用平均配置(子問題(1)為1/2，子問題(2)為1/3)。

表1 各部門工種與船舶裝載匹配關(guān)系

注：“○”表示可以裝載，“×”表示不能裝載。

表2 各部門工種數(shù)量、占地面積及重量

表3 各船舶最大載重量、運輸面積及排水量

設(shè)計遺傳算法種群數(shù)量為200，種群單基因點發(fā)生交叉、變換的概率分別為0.19和0.08。在有限次迭代下分析算法適應(yīng)度函數(shù)及三項優(yōu)化指標變化情況。

1) 模型收斂速度檢測實驗。以一定迭代范圍內(nèi)適應(yīng)度函數(shù)的變化情況描述模型的收斂速度，兩種求解方法的適應(yīng)度函數(shù)變化如圖1所示。

圖1 適應(yīng)度函數(shù)-迭代次數(shù)變化情況

可以看出，未采用分治方法適應(yīng)度函數(shù)折線下降平緩，在300次迭代中未能收斂到理想值。采用分支方法后，適應(yīng)度函數(shù)折線下降速率快，其中，從起始點到谷值為分治子問題(1)，總迭代次數(shù)為50，目標收斂值為0.195 8。隨后進入分治子問題(2)，總迭代次數(shù)為162，收斂值為0.352 0。顯然，不采用分治方法，在復(fù)雜度高問題的求解中，無法在較少迭代次數(shù)下完成收斂，采用分治方法后，可以更快求得理想解。

以計算時間為橫坐標，分析分治方法對模型求解速率的性能提升，結(jié)果如圖2所示。

圖2 適應(yīng)度函數(shù)-計算時間變化情況

不采用分治方法進行300次迭代運算所需時間為179.4秒，在相同計算條件下，采用分治方法僅需112.8秒，總運算時間減少了約37.1%。

2) 多目標優(yōu)化函數(shù)效果檢測。優(yōu)化目標函數(shù)的三類優(yōu)化指標隨迭代輪數(shù)變化如圖3和圖4所示。

圖3 子問題(1)各優(yōu)化目標變化情況

圖4 子問題(2)各優(yōu)化目標變化情況

對圖3分析可得，子問題(1)目的是以專用船只對貨物進行盡可能多的裝填。該過程中，艦隊規(guī)模為常數(shù)(艦隊規(guī)模=專用艦船總數(shù))，空置率及人貨分離率交替震蕩(采用不同的貨物組合形式)，在遺傳算法適應(yīng)度函數(shù)標準下，控制該過程總體呈下降趨勢。綜合三類優(yōu)化參數(shù)，混合優(yōu)化函數(shù)保持單調(diào)下降。該結(jié)果表明，分治子問題(1)可實現(xiàn)較為快速有效的收斂。

對圖4分析可得，分治子問題(2)目的是對剩余貨物采用盡可能少的通用船只進行完全裝載。由于通用船受船只類型本身人貨全部分離的約束，因此優(yōu)化目標人貨分離率為常數(shù)；另一方面，空置率與艦船規(guī)模交替震蕩；總優(yōu)化目標函數(shù)呈下降趨勢，在160次迭代后達到滿足要求的理想解。同樣地，該結(jié)果表明分支問題(2)可實現(xiàn)較為快速有效的收斂。

3) 蒙特卡洛測試魯棒性及全局最優(yōu)搜索能力。在相同條件下，多次仿真的適應(yīng)度函數(shù)變化折線如圖5所示。

圖5 多次蒙特卡洛實驗的收斂情況

由于本文采用遺傳算法引入了隨機性(初始化的隨機性及遺傳算子的隨機性)，使求得的最終解存在一定的方差。為避免隨機性對最終結(jié)果的影響，提高解的強健與穩(wěn)定能力，本文探索了通過多次重復(fù)實驗(蒙特卡洛原理)獲取最優(yōu)解的方法。圖5所示為重復(fù)次數(shù)為5時的實驗結(jié)果，由于采用隨機初始化策略，每次重復(fù)中的初態(tài)有所差異，進而影響了子問題(1)的收斂值及子問題(2)的初態(tài)，最終影響子問題(2)的收斂值。上述現(xiàn)象的問題根源在于，模型采用的分治方法犧牲了全局最優(yōu)性換取了時效性，因此在不同的初態(tài)下，陷入了不同的局部極值。

為對抗上述局部極值現(xiàn)象，本文采用多次重復(fù)實驗(蒙特卡洛)方法，并在仿真中起到了一定效果。表4記錄了多次獨立的重復(fù)實驗的適應(yīng)度最小值。

表4 蒙特卡洛實驗下的適應(yīng)度函數(shù)最優(yōu)值變化

顯然，重復(fù)次數(shù)大于5后，可以大概率取得較為穩(wěn)定的理想解。這是由于每次重復(fù)實驗都通過隨機方式生成系統(tǒng)初態(tài)，當(dāng)初態(tài)種群中能夠包含可以達到最優(yōu)值的初態(tài)時，后續(xù)算法可以快速檢索并收斂到最優(yōu)值。隨著重復(fù)次數(shù)增加，初態(tài)種群的規(guī)模增長，種群中包含最優(yōu)值初態(tài)的可能性就越高。

綜上所述，通過重復(fù)實驗方法可以增強模型的魯棒性。

4) 應(yīng)用評價與效能分析。根據(jù)本文構(gòu)建模型，對仿真問題求解，多目標函數(shù)與單目標函數(shù)在權(quán)重均等的情況下，求得的解如表5所示。

表5 求解情況

顯然，本文構(gòu)造的模型采用多目標優(yōu)化函數(shù)，與單目標相比，該模型選擇了船只數(shù)目少、排水總量低、空置率低的一組解，而其他模型只追求單一標準下的最優(yōu)而致使其他指標過大，邊際低收益狀況明顯。因此，仿真結(jié)果表明本文模型可以權(quán)衡靠港后快速作業(yè)反應(yīng)、縮減船隊規(guī)模以降低控制維護成本、最大化利用船舶空間三項度量指標。

3 結(jié) 語

本文針對大型平臺遠海運輸裝載方案規(guī)劃問題，提出了一種新的CLP模型。模型以空載率、船隊規(guī)模、人貨分離率為優(yōu)化指標，考慮了船舶承載面積、承重極限，以及與不同部門的匹配關(guān)系等約束。針對模型復(fù)雜度較高、難以用經(jīng)典方法求解的問題，利用分治思想將模型拆分后用遺傳算法尋得局部域最優(yōu)解。仿真實驗表明，分治方法可顯著提高收斂速度，多目標優(yōu)化函數(shù)可較好地反映實際需求，通過多次蒙特卡洛重復(fù)實驗可增強魯棒性，穩(wěn)定地取得理想解，且解具有對多目標權(quán)衡的特性，能夠滿足現(xiàn)實任務(wù)需求。