一種考慮可靠性指標(biāo)的備件運(yùn)送路徑優(yōu)化方法

趙 瑞,陳浩然,葛子陽(yáng)

(1.天津理工大學(xué) 理學(xué)院,天津 300384;2.北京航空航天大學(xué) 可靠性與系統(tǒng)工程學(xué)院,北京 100191)

保障系統(tǒng)在維持裝備的正常使用中發(fā)揮了重要作用,也就是說(shuō)在裝備使用時(shí)保障系統(tǒng)需要能夠保障其正常運(yùn)行操作,并且一旦裝備發(fā)生故障,能夠及時(shí)修復(fù)。為使保障系統(tǒng)發(fā)揮其作用和功能,需在保障組織中開(kāi)展相應(yīng)的保障活動(dòng),合理地運(yùn)用保障資源,以保證保障系統(tǒng)功能正常執(zhí)行。

在保障資源中,備件資源非常重要,直接制約著裝備系統(tǒng)的戰(zhàn)備完好性和持續(xù)作戰(zhàn)能力。在備件保障活動(dòng)中,備件在各級(jí)不同站點(diǎn)間如何合理地進(jìn)行流轉(zhuǎn)是一個(gè)研究的熱點(diǎn)問(wèn)題。優(yōu)化備件保障過(guò)程,可以減少備件缺貨量、提高備件供應(yīng)水平、降低備件缺貨損失。對(duì)于備件供應(yīng)保障,李文等[1]給出了備件保障中心可靠度的概念以及量化方法,并提出了基于可靠度的備件保障中心多目標(biāo)選址模型;翟亞利等[2]建立了考慮維修時(shí)間的隨艦備件保障概率模型與串聯(lián)系統(tǒng)的基于使用可用度的系統(tǒng)備件配置優(yōu)化模型,給出了隨艦備件配置優(yōu)化算法;Liu等[3]分析證明了增材制造技術(shù)可以有效提升備件供應(yīng)的動(dòng)力,降低運(yùn)輸費(fèi)用及供應(yīng)時(shí)間;Tiacci等[4]分析驗(yàn)證了通過(guò)平行供應(yīng)來(lái)降低備件供應(yīng)時(shí)間的情況;Braglia等[5]建立了一種有效快速的方法挑選出適用具體情況的備件優(yōu)化模型;Wang[6]認(rèn)為備件的保障水平是影響保障資源延遲時(shí)間的主導(dǎo)因素。

Dantzig等[7]在1959年首先定義了車輛的路徑規(guī)劃問(wèn)題(Vehicle routing problem,VRP)。Baker[8]首先研究了帶時(shí)間窗的車輛調(diào)度問(wèn)題。Padberg[9]利用切平面法求解大型旅行商問(wèn)題。Beheshti等[10]研究了帶軟時(shí)間窗的車輛調(diào)度問(wèn)題。Savelsbergh等[11-12]證明了車輛的路徑規(guī)劃是一個(gè)NP難題,傳統(tǒng)方法很難求得最優(yōu)解。遺傳算法[13]、蟻群算法[14]等啟發(fā)式算法及其改進(jìn)算法[15-17]被廣泛地應(yīng)用于求解該問(wèn)題。

近年來(lái),研究人員對(duì)于備件供應(yīng)路徑優(yōu)化問(wèn)題進(jìn)行了探索[18-19]。文獻(xiàn)[18]和文獻(xiàn)[19]均設(shè)站點(diǎn)需求量為確定值,并且把滿足站點(diǎn)需求作為裝備保障性的約束條件,沒(méi)有考慮到通常情況下站點(diǎn)需求量是隨機(jī)變量,而且沒(méi)有考慮備件供應(yīng)系統(tǒng)的其他重要保障性指標(biāo)。本文對(duì)單車輛備件運(yùn)輸路徑優(yōu)化問(wèn)題進(jìn)行研究,分析影響備件運(yùn)輸路徑的保障性及可靠性指標(biāo),考慮維修站點(diǎn)需求是隨機(jī)變量的情況,以機(jī)會(huì)約束規(guī)劃[20]的思想進(jìn)行建模,并且設(shè)計(jì)混合智能算法對(duì)模型求解。

1 模型構(gòu)建

1.1 問(wèn)題描述

在備件供應(yīng)系統(tǒng)中,當(dāng)某站點(diǎn)的裝備運(yùn)行發(fā)生故障時(shí),備件庫(kù)為該站點(diǎn)供應(yīng)新的備件。出現(xiàn)備件需求的站點(diǎn)需要及時(shí)得到供給,使得整個(gè)系統(tǒng)的保障性可以得到滿足,減少由于備件短缺造成的損失。由于供應(yīng)體系的運(yùn)輸能力有限,選擇合理的路徑是提升保障效率的關(guān)鍵,建模需考慮裝備保障性約束和保障費(fèi)用的情況下選擇合適的運(yùn)輸路線。

1.2 模型假設(shè)

對(duì)于保障區(qū)域較小、維修站點(diǎn)較少的備件供應(yīng)保障系統(tǒng),一個(gè)備件庫(kù)就能夠滿足所有站點(diǎn)的備件供應(yīng),在此條件下,對(duì)問(wèn)題做出以下假設(shè):

假設(shè)1各維修站點(diǎn)的需求量是隨機(jī)變量,并且維修站點(diǎn)需求相互獨(dú)立。

假設(shè)2備件庫(kù)和維修站點(diǎn)的運(yùn)輸路徑是直線連接,運(yùn)輸費(fèi)用只和站點(diǎn)之間距離有關(guān),道路是可以雙向行駛的。

假設(shè)3各站點(diǎn)的重要等級(jí)是相同的。

1.3 符號(hào)說(shuō)明

模型使用的基本符號(hào)和含義如下:i為i=1,2,…,n,表示基層級(jí)站點(diǎn);i=0表示備件庫(kù);d(i,j)為站點(diǎn)i,j之間距離;x1,x2,…,xn為1到n的全排列;c1為單個(gè)備件訂貨成本;c2為單位距離成本;yi為站點(diǎn)i的分配運(yùn)輸量;ξi為站點(diǎn)i的備件隨機(jī)需求數(shù);l為懲罰系數(shù);αi為站點(diǎn)i短缺率的置信水平上限;Di為站點(diǎn)i供應(yīng)延遲時(shí)間上限;V為運(yùn)輸車速度;Ni為站點(diǎn)i的設(shè)備數(shù)目;Z為每臺(tái)設(shè)備安裝備件數(shù);Ai為站點(diǎn)i的供應(yīng)可用度下限;A0為系統(tǒng)整體可用度下限;βi為供站點(diǎn)i應(yīng)可用度的置信水平下限;γ為系統(tǒng)整體可用度的置信水平下限。

1.4 單車輛備件運(yùn)輸路徑優(yōu)化機(jī)會(huì)約束規(guī)劃模型

1.4.1 決策變量

模型以運(yùn)輸路徑x1,x2,…,xn(1到n的全排列)和站點(diǎn)的分配運(yùn)輸量yi(i=1,2,…,n)為決策變量。

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

訂購(gòu)費(fèi)用

(1)

運(yùn)輸費(fèi)用

(2)

式中:l作為一個(gè)懲罰系數(shù),表示不同情況下,由于備件延誤導(dǎo)致的損失;運(yùn)輸車從站點(diǎn)i到達(dá)i+1這段路徑的運(yùn)輸費(fèi)用與路徑長(zhǎng)度正相關(guān),也與站點(diǎn)i的保障概率相關(guān)。

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

minC1+C2

(3)

1.4.3 約束條件

保障系統(tǒng)包含保障站點(diǎn)和備件兩個(gè)重要的部分,裝備的戰(zhàn)備完好性和持續(xù)作戰(zhàn)能力都會(huì)受到這兩個(gè)部分的影響。本文考慮的重點(diǎn)是保障站點(diǎn)的備件供應(yīng)過(guò)程,戰(zhàn)備完好率、使用可用度、平均保障延誤時(shí)間、能執(zhí)行任務(wù)率、備件保障概率、供應(yīng)可用度等指標(biāo)作用于評(píng)價(jià)備件保障方案時(shí),都會(huì)影響決策者對(duì)備件保障方案的選取。以優(yōu)化備件庫(kù)到各站點(diǎn)的運(yùn)輸路徑和備件運(yùn)輸量為模型目標(biāo),對(duì)上述指標(biāo)進(jìn)行篩選,其中保障延誤時(shí)間用于描述需求站點(diǎn)的備件等待時(shí)間,這一指標(biāo)對(duì)路徑的選擇有極大影響;備件保障概率、供應(yīng)可用度都可用于度量站點(diǎn)的裝備保障任務(wù)完成情況,對(duì)于備件運(yùn)輸量的優(yōu)化有直接影響。

選用備件保障概率、供應(yīng)可用度和保障延誤時(shí)間作為模型的約束條件,使得備件發(fā)生短缺時(shí),能夠維持系統(tǒng)保障性在一定水平。由于站點(diǎn)的需求量是隨機(jī)變量,不能直接比較大小,此時(shí)采用如下的原則:允許事先所做的決策在一定風(fēng)險(xiǎn)程度中不滿足約束條件,但要設(shè)置一定的置信水平,使得約束條件成立的概率有一個(gè)評(píng)判的閾值,在此原則下建立的模型稱為機(jī)會(huì)約束規(guī)劃模型。求解機(jī)會(huì)約束規(guī)劃時(shí),各項(xiàng)指標(biāo)符合要求的置信水平都要大于等于預(yù)先規(guī)定的值,把機(jī)會(huì)約束轉(zhuǎn)化為各自的確定約束,然后求解其等價(jià)的確定性模型。下面對(duì)約束進(jìn)行描述。

(1)備件保障概率。當(dāng)備件庫(kù)對(duì)站點(diǎn)的供給量yi小于站點(diǎn)的需求量ξi時(shí)就會(huì)發(fā)生備件短缺,式(4)保證維修站點(diǎn)i的備件需求ξi不能夠得到滿足的置信水平要不大于αi。

1-Pr{ξi≤yi}≤αii=1,2,…,n

(4)

(2)平均保障延誤時(shí)間。平均保障延誤時(shí)間主要包含3個(gè)方面的延誤時(shí)間:等待備件、維修人員及保障設(shè)備造成的延誤時(shí)間。除去人為因素,備件保障概率和描述備件供應(yīng)速度的平均供應(yīng)反應(yīng)時(shí)間TSR是影響平均保障延誤時(shí)間的主要因素,式(5)表示平均保障延誤時(shí)間不超過(guò)Di。

(1-Pr{ξi≤yi})TSR≤Dii=1,2,…,n

(5)

式(6)表示站點(diǎn)i的平均保障延誤時(shí)間不超過(guò)Di。

i=1,2,…,n

(6)

(3)供應(yīng)可用度。在實(shí)際應(yīng)用中,站點(diǎn)的供應(yīng)可用度指在任意時(shí)刻站點(diǎn)處于可工作或者可使用狀態(tài)的程度,表示為未因任何備件短缺而停機(jī)的裝備數(shù)量所占裝備總數(shù)百分比,式(7)是站點(diǎn)i的供應(yīng)可用度。

(7)

站點(diǎn)i的供應(yīng)可用度不低于Ai。運(yùn)用機(jī)會(huì)約束的思想,要求站點(diǎn)i的可用度能夠得到滿足的置信水平要大于等于βi,式(8)是保證維修站點(diǎn)i的供應(yīng)可用度要求。

(8)

式(9)為系統(tǒng)整體可用度,要求系統(tǒng)可用度A0能夠得到滿足的置信水平要大于等于γ。

i=1,2,…,n

(9)

于是可建立單車輛備件運(yùn)輸路徑優(yōu)化機(jī)會(huì)約束規(guī)劃模型

(10)

2 混合智能算法

由于式(10)的模型中含有關(guān)于隨機(jī)變量的函數(shù),無(wú)法直接求解,因此本文設(shè)計(jì)了隨機(jī)模擬來(lái)求解,將其嵌入遺傳算法形成了混合智能算法。在生成染色體時(shí),采用混合編碼。染色體分為兩部分,第一段采用整數(shù)編碼,對(duì)應(yīng)站點(diǎn)的排序;第二段采用實(shí)數(shù)編碼,對(duì)應(yīng)站點(diǎn)備件供給量。在后續(xù)的選擇、交叉、變異操作中染色體不同的部分分別單獨(dú)進(jìn)行操作。在這里選擇的交叉策略是在其中一段的運(yùn)算結(jié)果收斂后,再調(diào)整另一段,不斷循環(huán),直到整體收斂。

具體步驟如下:

步驟1初始化產(chǎn)生若干染色體,采用隨機(jī)模擬方法檢驗(yàn)染色體是否能夠滿足提出的約束條件;

步驟2對(duì)染色體進(jìn)行交叉和變異操作;

步驟3計(jì)算染色體的目標(biāo)值;

步驟4根據(jù)染色體的目標(biāo)值計(jì)算每個(gè)染色體適用度;

步驟5采用旋轉(zhuǎn)賭輪方法選擇染色體;

步驟6重復(fù)步驟2到步驟5,直到完成給定的循環(huán)次數(shù);

步驟7選擇效果最好的染色體作為模型的最優(yōu)解。

3 算例驗(yàn)證

應(yīng)用本文提出的單車輛備件運(yùn)輸路徑優(yōu)化機(jī)會(huì)約束規(guī)劃模型對(duì)某備件供應(yīng)保障系統(tǒng)進(jìn)行算例分析,用以驗(yàn)證上述模型方法的適用性與可操作性。關(guān)于單車輛備件供應(yīng)情況,將采用下列供應(yīng)保障系統(tǒng),不計(jì)出發(fā)點(diǎn)共計(jì)9個(gè)站點(diǎn)。已知備件訂購(gòu)成本為6,單位距離成本為1。備件需求量為服從泊松分布的隨機(jī)變量,各站點(diǎn)參數(shù)如表1所示。采用本文提出的混合智能算法求解,可得到圖1所示的運(yùn)輸路徑優(yōu)化結(jié)果,各站點(diǎn)運(yùn)輸量見(jiàn)表2。在圖1中,點(diǎn)0代表備件庫(kù),最小總費(fèi)用為2 998。

表1 路徑優(yōu)化站點(diǎn)參數(shù)

表2 模型備件運(yùn)輸量

4 結(jié)論

對(duì)于備件供應(yīng)保障過(guò)程,在系統(tǒng)地考慮保障性指標(biāo)要求的前提下,建立了單車輛的備件運(yùn)輸路徑優(yōu)化模型,模型主要考慮了保障費(fèi)用和保障效能指標(biāo)兩方面的因素,將路徑變量與備件供應(yīng)量作為決策變量,建立起路徑優(yōu)化與目標(biāo)函數(shù)關(guān)聯(lián)的模型,最后通過(guò)算例分析驗(yàn)證了該模型的有效性與可操作性,為綜合保障研究提供了一個(gè)新方向。