船舶維修備件供應調度路徑優化研究

侯朵莉，姚玉南

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

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

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

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

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

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

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

圖1 兩級維修保障下的備件供應調度模式

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

2 船舶維修備件供應調度路徑優化模型

2.1 參數定義

模型參數及定義如表1所示。

表1 模型參數及定義

2.2 構建懲罰函數

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

圖2 懲罰函數定義圖

現構建懲罰函數f(ti)如下：

(1)

2.3 基本假設

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

2.4 模型建立

決策變量如下：

(2)

運輸成本Z1：

(3)

懲罰成本Z2：

(4)

目標函數：

minZ=min(Z1+Z2)，

(5)

s.t.：

(6)

(7)

(8)

(9)

(10)

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

3 算法設計

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

圖3 算法流程示意圖

4 仿真實驗結果及分析

4.1 適應度函數的設計

算法適應度定為成本的倒數：

fi=1/Zi，

(11)

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

算法終止條件：迭代次數為500次。

4.2 仿真實驗

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

表2 維修備件需求地信息

運用MATLAB 2016a軟件對目標函數進行優化，結果如表3所示。

表3 優化結果 元

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

圖4 維修備件供應最優路徑示意圖

傳統遺傳算法求得的維修備件供應調度總成本為5 420.65元。圖5和圖6分別為遺傳算法改進前后的迭代示意圖。

圖5 遺傳算法改進前迭代示意圖

圖6 遺傳算法改進后迭代示意圖

由圖5可知，算法改進前在迭代次數為100次之后尋得目標最優值，而圖6中遺傳算法改進后在迭代次數為100次之前就已尋得目標最優值。

5 結束語

本文以船舶維修備件為研究對象，針對其供應調度總成本較高的問題建立了路徑優化模型。以供應調度總成本最小為優化目標，用改進前后的遺傳算法對模型求解。本文所建模型有效實現了船舶維修備件供應路徑的優化，對于維修備件及時到達維修地點，提高船舶裝備維修效率，降低維修費用具有重要意義；帶軟時間窗的維修備件供應路徑優化模型使路徑規劃更加科學有效；改進后的遺傳算法較傳統遺傳算法收斂速度更快，維修備件供應調度總成本下降了19.9%，大幅度降低了備件供應調度的總成本。