船舶維修備件供應(yīng)調(diào)度路徑優(yōu)化研究

侯朵莉，姚玉南

(武漢理工大學(xué) 能源與動力工程學(xué)院，湖北 武漢 430063)

船舶裝備維修的高效性對保證船舶安全航行至關(guān)重要，同時是縮短裝備維修周期和提高航運(yùn)企業(yè)經(jīng)濟(jì)效益的保證。如果裝備維修費(fèi)用過高或維修時間過長，會增加航運(yùn)企業(yè)的經(jīng)營成本，致使企業(yè)經(jīng)濟(jì)效益降低。而保證船舶裝備高效維修的關(guān)鍵之一是維修備件能夠及時供應(yīng)，維修備件是船舶裝備臨時搶修、計劃修理、狀態(tài)維修的保障性物資，是開展船舶裝備維修作業(yè)的物質(zhì)基礎(chǔ)。隨著船舶裝備技術(shù)發(fā)展的智能化、系統(tǒng)功能的集成化、任務(wù)的多樣化、運(yùn)行環(huán)境的復(fù)雜化，維修備件供應(yīng)調(diào)度規(guī)劃往往面臨著裝備部組件故障的突發(fā)性高、備件消耗的不確定性增加、備件需求應(yīng)急性突出等情況，因此，維修備件能否合理調(diào)度與及時供應(yīng)成為制約船舶裝備維修保障能力提高的瓶頸。

在維修備件供應(yīng)調(diào)度規(guī)劃中，一個重要問題便是對維修備件供應(yīng)路徑的優(yōu)化。國內(nèi)外學(xué)者對供應(yīng)路徑優(yōu)化展開了研究，呂游等[1]提出一種改進(jìn)的蟻群算法用于解決作戰(zhàn)物資的車輛運(yùn)輸路徑規(guī)劃問題，并考慮不同作戰(zhàn)單元對物資需求的可能變化,用排隊策略對算法進(jìn)行求解,得出適應(yīng)需求變化的路徑,最后通過仿真實驗驗證了規(guī)劃路徑的合理性。文獻(xiàn)[2]介紹了一個涉及大型集裝箱的滾動式滾裝廢物收集運(yùn)輸路徑問題，并提出了一種基于大鄰域搜索的迭代啟發(fā)式解決方法。Lin Zhu[3]開發(fā)了一個配對的協(xié)同再優(yōu)化(PCR)策略來解決隨機(jī)需求(VRPSD)的運(yùn)輸路徑問題，提出了一種啟發(fā)式算法，可以根據(jù)更新的信息動態(tài)地改變訪問順序和運(yùn)輸車輛分配，比較分析結(jié)果，顯示PCR策略表現(xiàn)更好。馬祥麗等[4]在VRPTW問題的求解中引進(jìn)蝙蝠算法，為了克服基本蝙蝠算法的不足之處,將慣性權(quán)重引入蝙蝠速度更新公式中對其進(jìn)行改進(jìn)，并采用懲罰函數(shù)的方式對目標(biāo)函數(shù)進(jìn)行了簡化求解。郭森[5]提出了一種基于動態(tài)學(xué)習(xí)和突變因子的粒子群算法(DSPSO)來解決粒子群算法(PSO)及其變種在約束多目標(biāo)等復(fù)雜問題優(yōu)化過程中所遇到的易陷入局部最優(yōu)和收斂性問題,并在多目標(biāo)路徑問題實例優(yōu)化中取得了較好的效果。

目前，針對船舶裝備維修備件供應(yīng)路徑優(yōu)化方面的研究較少，且仍采用類比、依靠經(jīng)驗的傳統(tǒng)方法。這種傳統(tǒng)方法確定的維修備件供應(yīng)路徑規(guī)劃方式在維修任務(wù)多樣化時就會顯得不適用，在極大程度上影響維修活動的及時展開。

1 船舶維修備件兩級保障模式

隨著船舶裝備數(shù)量不斷增多，維修工作量日益增大，裝備對維修備件的需求量也越來越多，因此，合理的儲備維修備件十分重要[6]。同時，維修備件供應(yīng)路徑的合理選取也影響著裝備維修保障能力的提高。采用合理的供應(yīng)路徑能夠有效滿足自主式裝備維修備件調(diào)度所需求的時間響應(yīng)、供應(yīng)成本等方面要求。為此，本文在自主式維修保障[7]基礎(chǔ)上提出兩級維修保障(基層級和基地級)下的船舶備件供應(yīng)路徑優(yōu)化策略。

從20世紀(jì)90年代開始，美國軍方最先認(rèn)識到三級維修保障模式的局限性，隨后對裝備采用兩級維修保障模式，并取得了成功。實行兩級維修保障模式后，保證了基層級和基地級的維修能力。相較傳統(tǒng)的三級維修保障模式，其優(yōu)勢和特點(diǎn)主要表現(xiàn)在以下幾個方面：減少了中間運(yùn)轉(zhuǎn)機(jī)構(gòu)，信息流動更加順暢；減少了由于路徑原因使信息丟失或者發(fā)生偏差的概率；基地級可以更好的執(zhí)行總領(lǐng)調(diào)度協(xié)調(diào)的作用，而基層級的要求也可以更加及時準(zhǔn)確的得到反饋；縮短了供應(yīng)保障的周期，維修備件供應(yīng)直接從基地級到達(dá)基層級，提高了故障件的修復(fù)效率并提高了維修保障資源的利用率。兩級維修保障下備件供應(yīng)調(diào)度模式如圖1所示(實線為物流，虛線為信息流)。

圖1 兩級維修保障下的備件供應(yīng)調(diào)度模式

隨著聯(lián)供聯(lián)儲概念的提出，基于配送中心模式的供應(yīng)保障已成為備件供應(yīng)保障研究的熱點(diǎn)[8]。為實現(xiàn)船舶維修備件從基地級倉庫到各基層級倉庫準(zhǔn)確、高效的供應(yīng)，借助配送中心模式構(gòu)建供應(yīng)地或配送中心(基地級倉庫)—多需求地(基層級倉庫)的船舶維修備件供應(yīng)保障模式，以提高供應(yīng)配送能力。

2 船舶維修備件供應(yīng)調(diào)度路徑優(yōu)化模型

2.1 參數(shù)定義

模型參數(shù)及定義如表1所示。

表1 模型參數(shù)及定義

2.2 構(gòu)建懲罰函數(shù)

為提高船舶維修備件需求地的維修效率，本文引入軟時間窗[9]概念。由于軟時間窗路徑優(yōu)化問題考慮時間約束，因此這里引進(jìn)懲罰函數(shù)[10]。假設(shè)備件需求地i要求供應(yīng)時間范圍為[bi，ci]，允許的最大服務(wù)時間范圍為[ai，di]，如果供應(yīng)車輛在[ai，bi]和[ci，di]時間范圍內(nèi)到達(dá)受到的懲罰分別為：f1(bi-ti)和f2(ti-ci)，懲罰值設(shè)為一個很大的正數(shù)M；而在[bi，ci]時間范圍內(nèi)就不會有損失的懲罰，如圖2所示。

圖2 懲罰函數(shù)定義圖

現(xiàn)構(gòu)建懲罰函數(shù)f(ti)如下：

(1)

2.3 基本假設(shè)

在軟時間窗約束下，結(jié)合船舶維修備件供應(yīng)的特點(diǎn)，可對問題做以下假設(shè)：只考慮一種備件供應(yīng)方式，假設(shè)為公路運(yùn)輸；備件供應(yīng)地和需求地的地理位置已知，且供應(yīng)地?zé)o缺貨問題；備件供應(yīng)地車輛數(shù)一定，且為同類型車輛，供應(yīng)車輛每次完成供應(yīng)后返回供應(yīng)地；已知需求地備件需求量和時間窗，且無臨時變動；各供應(yīng)車輛只允許走一條線路，且線路上備件總載量不超過供應(yīng)車輛的最大裝載量，備件供應(yīng)地到需求地供應(yīng)的線路始終可行；不考慮供應(yīng)備件的型號和數(shù)量，僅以備件的質(zhì)量作為需求量的計算單位，單位假設(shè)為kg。

2.4 模型建立

決策變量如下：

(2)

運(yùn)輸成本Z1：

(3)

懲罰成本Z2：

(4)

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

minZ=min(Z1+Z2)，

(5)

s.t.：

(6)

(7)

(8)

(9)

(10)

公式(6)為每臺供應(yīng)車輛上船舶維修備件總需求量不超過車載量；公式(7)、(8)為每個需求地的船舶備件需求量只能由一輛供應(yīng)車輛配送，且每個需求地只能被供應(yīng)一次；公式(9)為供應(yīng)車輛從供應(yīng)地出發(fā)，完成供應(yīng)任務(wù)后全部返回到備件供應(yīng)地；公式(10)為軟時間窗約束。

3 算法設(shè)計

由于帶軟時間窗的路徑規(guī)劃問題具有多個條件約束，傳統(tǒng)的遺傳算法在解決此類問題時采用隨機(jī)化搜索，很容易得到劣質(zhì)解。通過添加算子優(yōu)化等操作來改進(jìn)遺傳算法，可以有效改善算法的局限性，在多條件約束下得到優(yōu)質(zhì)解。算法流程示意圖如圖3所示。

圖3 算法流程示意圖

4 仿真實驗結(jié)果及分析

4.1 適應(yīng)度函數(shù)的設(shè)計

算法適應(yīng)度定為成本的倒數(shù)：

fi=1/Zi，

(11)

式中：fi表示第i個個體適應(yīng)度；Zi表示種群中第i個個體對應(yīng)的成本。

算法終止條件：迭代次數(shù)為500次。

4.2 仿真實驗

某沿海城市10個基層級倉庫(編號1～10)提出需求，1個基地級倉庫(編號0)對其進(jìn)行維修備件供應(yīng)，算例可以描述為：由1個配送中心為10個需求地進(jìn)行維修備件供應(yīng)。參數(shù)f1，f2，α，K，mk值分別設(shè)定為1元、2元、15元、9輛、8 kg，求解目標(biāo)為維修備件供應(yīng)調(diào)度總成本最小化。維修備件需求地信息如表2所示(將某一地點(diǎn)的坐標(biāo)定為(0,0)，單位距離為1 km)。

表2 維修備件需求地信息

運(yùn)用MATLAB 2016a軟件對目標(biāo)函數(shù)進(jìn)行優(yōu)化，結(jié)果如表3所示。

表3 優(yōu)化結(jié)果 元

從表3可知，配送中心向需求地供應(yīng)維修備件的路徑規(guī)劃有4條。當(dāng)車輛按照規(guī)劃路徑中所對應(yīng)的需求地供應(yīng)順序配送維修備件時，此時供應(yīng)調(diào)度總成本最低為4 342.55 元。MATLAB 2016a軟件繪制的維修備件供應(yīng)最優(yōu)路徑示意圖如圖4所示。

圖4 維修備件供應(yīng)最優(yōu)路徑示意圖

傳統(tǒng)遺傳算法求得的維修備件供應(yīng)調(diào)度總成本為5 420.65元。圖5和圖6分別為遺傳算法改進(jìn)前后的迭代示意圖。

圖5 遺傳算法改進(jìn)前迭代示意圖

圖6 遺傳算法改進(jìn)后迭代示意圖

由圖5可知，算法改進(jìn)前在迭代次數(shù)為100次之后尋得目標(biāo)最優(yōu)值，而圖6中遺傳算法改進(jìn)后在迭代次數(shù)為100次之前就已尋得目標(biāo)最優(yōu)值。

5 結(jié)束語

本文以船舶維修備件為研究對象，針對其供應(yīng)調(diào)度總成本較高的問題建立了路徑優(yōu)化模型。以供應(yīng)調(diào)度總成本最小為優(yōu)化目標(biāo)，用改進(jìn)前后的遺傳算法對模型求解。本文所建模型有效實現(xiàn)了船舶維修備件供應(yīng)路徑的優(yōu)化，對于維修備件及時到達(dá)維修地點(diǎn)，提高船舶裝備維修效率，降低維修費(fèi)用具有重要意義；帶軟時間窗的維修備件供應(yīng)路徑優(yōu)化模型使路徑規(guī)劃更加科學(xué)有效；改進(jìn)后的遺傳算法較傳統(tǒng)遺傳算法收斂速度更快，維修備件供應(yīng)調(diào)度總成本下降了19.9%，大幅度降低了備件供應(yīng)調(diào)度的總成本。