基于分治思想和遺傳算法的集裝箱裝載優(yōu)化模型

賀紅燕 趙紅梅

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

0 引 言

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

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

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

1 大型平臺海運裝載模型

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

(4)

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

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

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

(5)

(6)

(7)

(8)

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

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

1.3 模型復雜度分析

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

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

(9)

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

(10)

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

(11)

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

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

(12)

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

(13)

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

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

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

2.1 分治方法的應用效益分析

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

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

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

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

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

兩個子問題的模型為原模型的調整變形，對子問題(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(·)運算表示取括號內元素的最大值。由于nZC

O2

(18)

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

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

令算法適應度函數(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)

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

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

2.2 分治方法的適用性分析

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

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

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

2.3 仿真結果分析

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

表1 各部門工種與船舶裝載匹配關系

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

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

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

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

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

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

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

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

圖2 適應度函數(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ù))，空置率及人貨分離率交替震蕩(采用不同的貨物組合形式)，在遺傳算法適應度函數(shù)標準下，控制該過程總體呈下降趨勢。綜合三類優(yōu)化參數(shù)，混合優(yōu)化函數(shù)保持單調下降。該結果表明，分治子問題(1)可實現(xiàn)較為快速有效的收斂。

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

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

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

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

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

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

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

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

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

表5 求解情況

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

3 結 語

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