賀紅燕 趙紅梅
(河北政法職業(yè)學(xué)院 河北 石家莊 050000)
隨著全球化發(fā)展,規(guī)模化廠房和鐵路等大型平臺(tái)的遠(yuǎn)距離、跨區(qū)域布設(shè)已成為一種常見的經(jīng)濟(jì)現(xiàn)象。海上運(yùn)輸是大型平臺(tái)的主要機(jī)動(dòng)方式,其運(yùn)輸對(duì)象包括各類獨(dú)立部門的設(shè)備器件以及對(duì)應(yīng)的專業(yè)型雇員,是一個(gè)“人貨同運(yùn)”活動(dòng)。為高效、快速和低成本地實(shí)施大型平臺(tái)的遠(yuǎn)洋運(yùn)輸,需要對(duì)運(yùn)輸?shù)馁Y源與對(duì)象進(jìn)行合理規(guī)劃,調(diào)配裝載方案,提高各部門到港后的快速作業(yè)反應(yīng)能力,壓縮船隊(duì)的控制維護(hù)成本,實(shí)現(xiàn)載具的空間使用最大化。
求解滿足特定要求的裝載方案的問題被抽象為集裝箱問題(Container Loading Problem,CLP),在前人研究中被證明是NP-Hard問題[1-2],即無法明確得到全局最優(yōu)的形式解。研究者們往往以智能算法為工具,基于問題背景有所側(cè)重地構(gòu)造模型,從而求得符合自身需求的滿意解。其中:Ramos等[3]提出了動(dòng)態(tài)穩(wěn)定性度量指標(biāo),以提高貨物運(yùn)輸?shù)陌踩裕怀讨形腫4]和左先亮等[5]引入了三維空間分隔法,以實(shí)現(xiàn)裝載空間利用率最大化;Monaco等[6]主要關(guān)心單個(gè)港口上裝載所需時(shí)長(zhǎng)的最小化;在多港口背景下,鄭斐峰等[7]討論了最小耗時(shí)的求解域建模,孫俊青等[8]則針對(duì)最高穩(wěn)定性進(jìn)行研究。先前研究中當(dāng)CLP模型的自變量空間較小或優(yōu)化目標(biāo)單一時(shí),采用經(jīng)典搜索方法如樹形搜索[9]、鄰域搜索[10]、二次禁忌搜索[11-12]等能達(dá)到較好效果;當(dāng)約束及優(yōu)化目標(biāo)復(fù)雜、搜索空間大時(shí),采用遺傳算法[13]、蟻群算法[14]、自適應(yīng)細(xì)菌覓食算法[15]及其他改進(jìn)啟發(fā)式算法[16-18]能達(dá)到較好效果。總體而言,CLP模型求解方法較為靈活,立足模型本身特點(diǎn),謀求在高收斂速度和高全局尋優(yōu)能力兩種性能上達(dá)到一個(gè)理想的均衡中值。
雖然前人研究豐富詳實(shí),但缺乏對(duì)人員、貨物與船舶三者間匹配性約束的討論,同時(shí)缺乏對(duì)運(yùn)輸成本、靠港后作業(yè)效率的考量,尤其在大型平臺(tái)遠(yuǎn)洋運(yùn)輸背景中,應(yīng)考慮通用貨船只能運(yùn)載設(shè)備,通用客船只能運(yùn)載人員,而平臺(tái)架設(shè)專用船舶則可同步運(yùn)輸人員貨物的客觀情況[19]。綜上所述,本文基于大型平臺(tái)遠(yuǎn)海運(yùn)輸現(xiàn)實(shí)情況,提出了靠港后快速作業(yè)反應(yīng)、縮減船隊(duì)規(guī)模以降低控制維護(hù)成本、最大化利用船舶空間三項(xiàng)度量指標(biāo),構(gòu)造了多目標(biāo)優(yōu)化函數(shù),建立了大型遠(yuǎn)洋作業(yè)中涵蓋多類工種部門與船型之間的約束關(guān)系式。此外,本文立足于分治思想,基于對(duì)專用、通用兩類船舶特性詳細(xì)分析,對(duì)求解過程進(jìn)行拆分,降低解空間復(fù)雜度,從而實(shí)現(xiàn)收斂速度的提升。
基于大型平臺(tái)運(yùn)輸?shù)膶?shí)際情況,本文構(gòu)造模型時(shí)遵循以下假設(shè):(1) 運(yùn)輸對(duì)象涉及多個(gè)工種部門,各部門具有不同的設(shè)備、人員;(2) 一個(gè)部門由多個(gè)分隊(duì)組成,同一部門下的分隊(duì)人員物資情況一致;(3) 各部門登船以分隊(duì)為最小單位;(4) 當(dāng)船舶剩余空間不足裝載任何分隊(duì)時(shí),不可將分隊(duì)拆散裝入船舶中;(5) 登船的前后順序不影響該船只的裝載能力;(6) 執(zhí)行任務(wù)的專用船舶數(shù)目有限,而通用船只數(shù)目可依需求增減;(7) 必須在一次行動(dòng)中將所有部門裝載完畢,不可反復(fù)、多次運(yùn)輸;(8) 可以將設(shè)備與人員分離運(yùn)輸,但仍必須以分隊(duì)為最小單元;(9) 當(dāng)同一分隊(duì)下的設(shè)備和人員同時(shí)在一艘船只上運(yùn)輸時(shí),分隊(duì)在靠港后可直接執(zhí)行作業(yè)任務(wù);(10) 當(dāng)設(shè)備和人員分離運(yùn)輸時(shí),必須先將兩者結(jié)合為整體,需要花費(fèi)一定的反應(yīng)時(shí)間。
考慮到這一問題的特點(diǎn),本文在建立模型時(shí),以裝載方案為自變量,采用自然數(shù)矩陣XC×2N進(jìn)行描述:
式中:N為待運(yùn)輸?shù)牟块T種類數(shù);C為船舶數(shù)目。矩陣中的元素xi,j表示第i艘船只裝載第j類部門的分隊(duì)數(shù)量,采用2N的列數(shù)是由于每一類部門均可拆分為人員及設(shè)備兩部分。
結(jié)合實(shí)際環(huán)境,本文設(shè)計(jì)了三類優(yōu)化指標(biāo),并通過加權(quán)求和的方式組合為多目標(biāo)優(yōu)化函數(shù)。
1) 空載率。遠(yuǎn)洋運(yùn)輸條件下,載具資源十分昂貴,但由于假設(shè)(3)和假設(shè)(4),船舶難以實(shí)現(xiàn)滿載,必須考慮如何用有限的空間運(yùn)輸盡量多的貨物。對(duì)此,本文提出了“空載率”指標(biāo),用于量化對(duì)載具資源的利用程度,公式如下:
(1)

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

3) 人貨分離率。根據(jù)假設(shè)(9)和假設(shè)(10),為使各部門在靠港后盡快投入作業(yè)任務(wù),在運(yùn)載時(shí)應(yīng)盡量使得同一個(gè)分隊(duì)下的人員及設(shè)備裝載在同一艘船只上,減免出現(xiàn)人貨分離運(yùn)載的情況。對(duì)此,本文提出了“人貨分離率”指標(biāo),用于量化描述某裝載方案下的快速反應(yīng)作業(yè)能力。
(3)
式中:∑com_uniti表示裝載于同一艘船只上的同屬一個(gè)分隊(duì)的人員、設(shè)備的分隊(duì)數(shù)目;ZJZ表示分隊(duì)總數(shù)。式(3)的取值越小,則證明人員與設(shè)備越集中,作業(yè)反應(yīng)時(shí)間越短,效率越高。
基于上述三個(gè)指標(biāo),通過加權(quán)求和的方式組成多目標(biāo)優(yōu)化函數(shù):
f=w1·Rkz+w2·Rgm+w3·Rfl
(4)
式中:w1、w2、w3分別為各個(gè)指標(biāo)權(quán)值。本模型的目的就是求得使式(4)取值盡可能小的一組解。
本文主要從船舶可裝載面積限制、船舶可裝載重量限制、待運(yùn)輸單元總體恒定限制、船舶與部門相互匹配限制考慮,制定了以下約束條件:
(5)
(6)
(7)
(8)
式(5)表示分配給j船只的所有單元的占地面積之和不大于j船只的最大可運(yùn)輸面積;式(6)表示分配給j船只的所有單元的重量之和不大于j船只的可承重極限;式(7)表示第i類部門在本分配方案下可以全部分配完畢;式(8)表示第i類部門不可被裝載在與其不匹配的運(yùn)輸資源上。
綜上所述,在N類部門、C艘可用船只的情形下,本模型構(gòu)造了4N個(gè)不等式約束及2C個(gè)等式約束。
根據(jù)上述分析,模型的公式化表述如下:
minf(XC×2N)=w1·Rkz+w2·Rgm+w3·Rfl
(9)
對(duì)N類部門、C條船只,上述模型解可能的搜索空間大小為:
(10)
式中:mi為第i類部門的分隊(duì)數(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*,λ*)正定條件嚴(yán)格,難以給出形式解。
綜上所述,模型復(fù)雜度較高,一方面,自變量搜索空間廣,無法通過簡(jiǎn)單的枚舉求解;另一方面,繁瑣的拉格朗日函數(shù)難以用經(jīng)典凸優(yōu)化方法求解。上述分析結(jié)論反映了模型NP-Hard特性。因此,本文首先基于分治思想對(duì)自變量空間進(jìn)行降維,而后采用遺傳算法快速收斂至理想的可行解。
本文構(gòu)建的模型較為復(fù)雜,對(duì)此引入了分治與遺傳算法兩種求解方法。分治是指將耦合度較高的復(fù)雜問題分解為多個(gè)相對(duì)簡(jiǎn)單的可獨(dú)立求解的子問題,通過將多個(gè)子問題的解組合構(gòu)造出原問題的一個(gè)可行解。為證明分治思想在大型作業(yè)平臺(tái)遠(yuǎn)海運(yùn)輸裝載問題上的可行性,基于背景條件及模型的數(shù)學(xué)化描述,給出以下分析:
1) 裝載計(jì)劃中,應(yīng)優(yōu)先使用專用船舶。由于專用船舶具備同時(shí)裝載設(shè)備與人員的能力,可以完整運(yùn)輸一個(gè)分隊(duì),不占用多的運(yùn)載空間、無須擴(kuò)展船隊(duì)規(guī)模;相對(duì)地,由文獻(xiàn)[19] ,通用船只運(yùn)載能力往往受限,客貨分離特征明顯,人貨結(jié)合度低,且有可能需要較大船隊(duì)規(guī)模完成運(yùn)輸任務(wù)。因此,在裝載規(guī)劃中,專用船舶的使用優(yōu)先度高。當(dāng)專用船舶有剩余空間時(shí),應(yīng)優(yōu)先裝載專用船舶。
2) 由于需裝載對(duì)象總量大于專用船舶承載量,結(jié)合優(yōu)先裝載專用船舶的分析,有以下推論:針對(duì)專用船舶的裝載規(guī)劃問題,在船隊(duì)規(guī)模、人貨分離率兩個(gè)指標(biāo)上可達(dá)最優(yōu)邊際(規(guī)模壓縮至最小,為全體專用船舶的數(shù)目總和,是固定值;采用人貨結(jié)合形式裝載,分離率為局部最小值)。
因此,在討論整體裝載問題時(shí),考慮到專用船舶裝載部分本身可以達(dá)到邊際最優(yōu)的解。在求解時(shí),可以將該部分獨(dú)立分離,構(gòu)造子問題(1)——“專用船舶裝載規(guī)劃”。
3) 剩余需裝載對(duì)象以三大指標(biāo)構(gòu)造的混合目標(biāo)函數(shù)裝載到通用船舶上,可構(gòu)造子問題(2)——“通用船舶裝載規(guī)劃”。
兩個(gè)子問題的模型為原模型的調(diào)整變形,對(duì)子問題(1)的變形,模型如下:
minf(XnZC×N)=w1·Rkz+w2·Rfl
(14)
式中:nZC為專用船舶數(shù)量。
對(duì)子問題(2),其模型如下:
minf(XnTC×2nSN)=w1·Rkz+w2·Rgm+w3·Rfl
(15)
式中:nTC為通用船舶數(shù)量;nSN為剩余的待裝載人員、貨物總和;smi為i類部門剩余的數(shù)目。
采用分治理論后,搜索空間大小為:
(16)
搜索空間數(shù)量級(jí)為:
(17)
式中:max(·)運(yùn)算表示取括號(hào)內(nèi)元素的最大值。由于nZC O2 (18) 即分治方法實(shí)現(xiàn)了解空間的收縮。 在通過分治將原模型分解為兩個(gè)子模型后,本文采用了遺傳算法進(jìn)行解的尋優(yōu)。遺傳算法作為一種最常用的智能仿生算法,具有設(shè)計(jì)簡(jiǎn)單、收斂較快、計(jì)算復(fù)雜度低等優(yōu)點(diǎn)。算法自然基因編碼規(guī)則令第i行第j列的值編碼值=自適應(yīng)變量矩陣X中對(duì)應(yīng)的元素xij。 令算法適應(yīng)度函數(shù)等同兩類子問題優(yōu)化函數(shù),對(duì)子問題(1): fitness=w1·Rkz(XnZC×N)+w2·Rfl(XnZC×N) (19) 對(duì)子問題(2): fitness=w1·Rkz(XnTC×2nSN)+ w2·Rgm(XnTC×2nSN)+w3·Rfl(XnTC×2nSN) (20) 算法中遺傳算子采用交叉、變異兩類,基于算子變換產(chǎn)生的子代可實(shí)現(xiàn)對(duì)自變量矩陣空間的覆蓋。 綜上所述,采用分治方法與遺傳算法相結(jié)合的求解方法,從理論上得證能顯著收縮解的搜索范圍,顯著提高求解效率。 根據(jù)式(10),本文構(gòu)造的模型為NP-Hard問題,難以求出公式化完備解,無法確保解的全局最優(yōu)性。采用智能算法求解該類型問題,得到的解是鄰域內(nèi)極小點(diǎn),具有局部最優(yōu)特性。 利用分治算法將問題拆分為兩個(gè)子問題,子問題的求解相互獨(dú)立,子問題(1)的解構(gòu)成了子問題(2)的條件。子問題(1)與子問題(2)都是可證具有全局優(yōu)化特點(diǎn)的解,因此當(dāng)兩者相互合并構(gòu)成的解必定是在子問題(1)的解的優(yōu)化方向的一個(gè)極值點(diǎn),即該解在鄰域范圍內(nèi)最優(yōu),為局部最優(yōu)點(diǎn)。 綜上所述,采用分治方法后取得的解與采用分治方法前的解一致,均為局部最優(yōu)解。 基于實(shí)際情況設(shè)計(jì)仿真場(chǎng)景,表格中數(shù)據(jù)由一次鐵路組件遠(yuǎn)海安裝的航運(yùn)實(shí)際數(shù)值簡(jiǎn)化得到。表1展示了各部門與船舶的裝載匹配關(guān)系;表2展示了需要裝載的各部門數(shù)量、占地面積及重量;表3展示了各船只的最大載重量、最大運(yùn)載面積及排水量及可使用數(shù)目。實(shí)驗(yàn)中目標(biāo)函數(shù)的優(yōu)化參數(shù)權(quán)值采用平均配置(子問題(1)為1/2,子問題(2)為1/3)。 表1 各部門工種與船舶裝載匹配關(guān)系 注:“○”表示可以裝載,“×”表示不能裝載。 表2 各部門工種數(shù)量、占地面積及重量 表3 各船舶最大載重量、運(yùn)輸面積及排水量 設(shè)計(jì)遺傳算法種群數(shù)量為200,種群?jiǎn)位螯c(diǎn)發(fā)生交叉、變換的概率分別為0.19和0.08。在有限次迭代下分析算法適應(yīng)度函數(shù)及三項(xiàng)優(yōu)化指標(biāo)變化情況。 1) 模型收斂速度檢測(cè)實(shí)驗(yàn)。以一定迭代范圍內(nèi)適應(yīng)度函數(shù)的變化情況描述模型的收斂速度,兩種求解方法的適應(yīng)度函數(shù)變化如圖1所示。 圖1 適應(yīng)度函數(shù)-迭代次數(shù)變化情況 可以看出,未采用分治方法適應(yīng)度函數(shù)折線下降平緩,在300次迭代中未能收斂到理想值。采用分支方法后,適應(yīng)度函數(shù)折線下降速率快,其中,從起始點(diǎn)到谷值為分治子問題(1),總迭代次數(shù)為50,目標(biāo)收斂值為0.195 8。隨后進(jìn)入分治子問題(2),總迭代次數(shù)為162,收斂值為0.352 0。顯然,不采用分治方法,在復(fù)雜度高問題的求解中,無法在較少迭代次數(shù)下完成收斂,采用分治方法后,可以更快求得理想解。 以計(jì)算時(shí)間為橫坐標(biāo),分析分治方法對(duì)模型求解速率的性能提升,結(jié)果如圖2所示。 圖2 適應(yīng)度函數(shù)-計(jì)算時(shí)間變化情況 不采用分治方法進(jìn)行300次迭代運(yùn)算所需時(shí)間為179.4秒,在相同計(jì)算條件下,采用分治方法僅需112.8秒,總運(yùn)算時(shí)間減少了約37.1%。 2) 多目標(biāo)優(yōu)化函數(shù)效果檢測(cè)。優(yōu)化目標(biāo)函數(shù)的三類優(yōu)化指標(biāo)隨迭代輪數(shù)變化如圖3和圖4所示。 圖3 子問題(1)各優(yōu)化目標(biāo)變化情況 圖4 子問題(2)各優(yōu)化目標(biāo)變化情況 對(duì)圖3分析可得,子問題(1)目的是以專用船只對(duì)貨物進(jìn)行盡可能多的裝填。該過程中,艦隊(duì)規(guī)模為常數(shù)(艦隊(duì)規(guī)模=專用艦船總數(shù)),空置率及人貨分離率交替震蕩(采用不同的貨物組合形式),在遺傳算法適應(yīng)度函數(shù)標(biāo)準(zhǔn)下,控制該過程總體呈下降趨勢(shì)。綜合三類優(yōu)化參數(shù),混合優(yōu)化函數(shù)保持單調(diào)下降。該結(jié)果表明,分治子問題(1)可實(shí)現(xiàn)較為快速有效的收斂。 對(duì)圖4分析可得,分治子問題(2)目的是對(duì)剩余貨物采用盡可能少的通用船只進(jìn)行完全裝載。由于通用船受船只類型本身人貨全部分離的約束,因此優(yōu)化目標(biāo)人貨分離率為常數(shù);另一方面,空置率與艦船規(guī)模交替震蕩;總優(yōu)化目標(biāo)函數(shù)呈下降趨勢(shì),在160次迭代后達(dá)到滿足要求的理想解。同樣地,該結(jié)果表明分支問題(2)可實(shí)現(xiàn)較為快速有效的收斂。 3) 蒙特卡洛測(cè)試魯棒性及全局最優(yōu)搜索能力。在相同條件下,多次仿真的適應(yīng)度函數(shù)變化折線如圖5所示。 圖5 多次蒙特卡洛實(shí)驗(yàn)的收斂情況 由于本文采用遺傳算法引入了隨機(jī)性(初始化的隨機(jī)性及遺傳算子的隨機(jī)性),使求得的最終解存在一定的方差。為避免隨機(jī)性對(duì)最終結(jié)果的影響,提高解的強(qiáng)健與穩(wěn)定能力,本文探索了通過多次重復(fù)實(shí)驗(yàn)(蒙特卡洛原理)獲取最優(yōu)解的方法。圖5所示為重復(fù)次數(shù)為5時(shí)的實(shí)驗(yàn)結(jié)果,由于采用隨機(jī)初始化策略,每次重復(fù)中的初態(tài)有所差異,進(jìn)而影響了子問題(1)的收斂值及子問題(2)的初態(tài),最終影響子問題(2)的收斂值。上述現(xiàn)象的問題根源在于,模型采用的分治方法犧牲了全局最優(yōu)性換取了時(shí)效性,因此在不同的初態(tài)下,陷入了不同的局部極值。 為對(duì)抗上述局部極值現(xiàn)象,本文采用多次重復(fù)實(shí)驗(yàn)(蒙特卡洛)方法,并在仿真中起到了一定效果。表4記錄了多次獨(dú)立的重復(fù)實(shí)驗(yàn)的適應(yīng)度最小值。 表4 蒙特卡洛實(shí)驗(yàn)下的適應(yīng)度函數(shù)最優(yōu)值變化 顯然,重復(fù)次數(shù)大于5后,可以大概率取得較為穩(wěn)定的理想解。這是由于每次重復(fù)實(shí)驗(yàn)都通過隨機(jī)方式生成系統(tǒng)初態(tài),當(dāng)初態(tài)種群中能夠包含可以達(dá)到最優(yōu)值的初態(tài)時(shí),后續(xù)算法可以快速檢索并收斂到最優(yōu)值。隨著重復(fù)次數(shù)增加,初態(tài)種群的規(guī)模增長(zhǎng),種群中包含最優(yōu)值初態(tài)的可能性就越高。 綜上所述,通過重復(fù)實(shí)驗(yàn)方法可以增強(qiáng)模型的魯棒性。 4) 應(yīng)用評(píng)價(jià)與效能分析。根據(jù)本文構(gòu)建模型,對(duì)仿真問題求解,多目標(biāo)函數(shù)與單目標(biāo)函數(shù)在權(quán)重均等的情況下,求得的解如表5所示。 表5 求解情況 顯然,本文構(gòu)造的模型采用多目標(biāo)優(yōu)化函數(shù),與單目標(biāo)相比,該模型選擇了船只數(shù)目少、排水總量低、空置率低的一組解,而其他模型只追求單一標(biāo)準(zhǔn)下的最優(yōu)而致使其他指標(biāo)過大,邊際低收益狀況明顯。因此,仿真結(jié)果表明本文模型可以權(quán)衡靠港后快速作業(yè)反應(yīng)、縮減船隊(duì)規(guī)模以降低控制維護(hù)成本、最大化利用船舶空間三項(xiàng)度量指標(biāo)。 本文針對(duì)大型平臺(tái)遠(yuǎn)海運(yùn)輸裝載方案規(guī)劃問題,提出了一種新的CLP模型。模型以空載率、船隊(duì)規(guī)模、人貨分離率為優(yōu)化指標(biāo),考慮了船舶承載面積、承重極限,以及與不同部門的匹配關(guān)系等約束。針對(duì)模型復(fù)雜度較高、難以用經(jīng)典方法求解的問題,利用分治思想將模型拆分后用遺傳算法尋得局部域最優(yōu)解。仿真實(shí)驗(yàn)表明,分治方法可顯著提高收斂速度,多目標(biāo)優(yōu)化函數(shù)可較好地反映實(shí)際需求,通過多次蒙特卡洛重復(fù)實(shí)驗(yàn)可增強(qiáng)魯棒性,穩(wěn)定地取得理想解,且解具有對(duì)多目標(biāo)權(quán)衡的特性,能夠滿足現(xiàn)實(shí)任務(wù)需求。2.2 分治方法的適用性分析
2.3 仿真結(jié)果分析










3 結(jié) 語