滕尚儒,何成銘,叢 彬
(1. 陸軍裝甲兵學(xué)院 裝備保障與再制造系, 北京 100072; 2. 陸軍裝備部信息保障室, 北京 100072)
裝備維修器材供應(yīng)保障是裝備保障工作的重要組成部分,直接影響著裝備完好率、任務(wù)成功性以及壽命周期費(fèi)用,其重要性毋庸置疑[1]。其主要目的是保證器材供應(yīng)的不間斷,涉及軍工企業(yè)生產(chǎn)、倉(cāng)庫(kù)存儲(chǔ)、車(chē)輛配送到部隊(duì)用戶消耗全過(guò)程的決策問(wèn)題。
如何對(duì)生產(chǎn)控制、庫(kù)存管理和配送路徑進(jìn)行集成優(yōu)化決策的問(wèn)題稱為生產(chǎn)路徑問(wèn)題(Production Routing Problem,PRP),涵蓋了兩類(lèi)相互關(guān)聯(lián)和相互制約的子決策問(wèn)題:生產(chǎn)—直達(dá)配送問(wèn)題(Production Direct-distribution Problem,PDP)和庫(kù)存—配送問(wèn)題(Inventory Routing Problem,IRP)。其中,PDP旨在同時(shí)確定生產(chǎn)調(diào)度計(jì)劃和直達(dá)配送計(jì)劃,使得整個(gè)規(guī)劃周期內(nèi)工廠的生產(chǎn)、生產(chǎn)準(zhǔn)備和庫(kù)存總成本最小[2];IRP是指在規(guī)劃周期內(nèi)由單工廠向多用戶提供配送服務(wù),在滿足一定約束條件下,確定每個(gè)決策階段的庫(kù)存策略以及相應(yīng)的配送策略,使存儲(chǔ)和配送總成本最小,其實(shí)質(zhì)就是研究庫(kù)存補(bǔ)充和配送之間的協(xié)調(diào)問(wèn)題[3]。
現(xiàn)有研究主要根據(jù)下列特征對(duì)PRP的約束條件進(jìn)行分類(lèi):?jiǎn)喂S或多工廠;單品種或多品種產(chǎn)品;帶或不帶能力約束。表1給出了PRP的部分代表性研究文獻(xiàn)。通過(guò)分析發(fā)現(xiàn),學(xué)者針對(duì)此類(lèi)問(wèn)題的研究大多集中在單工廠、單品種和帶能力約束的經(jīng)典PRP,較少涉及多品種PRP。此外,現(xiàn)有研究通常假設(shè)工廠產(chǎn)量始終能滿足用戶需求,但在實(shí)際運(yùn)行過(guò)程中,單靠?jī)?nèi)部生產(chǎn)往往不能及時(shí)滿足用戶需求[4]。外包是指從外部公司獲得半成品、成品或服務(wù)以及時(shí)滿足客戶需求的行為,在PRP中采用外包策略能夠進(jìn)一步降低系統(tǒng)成本并提高服務(wù)水平[5]。Adulysak等[6]在研究需求不確定的單品種PRP時(shí)間接地考慮了外包,其他較少有研究涉及允許外包的多品種PRP。
表1 生產(chǎn)路徑問(wèn)題的代表性研究文獻(xiàn)
組成PRP的IRP中涉及的VRP是NP-難題,因此PRP更加復(fù)雜。CPLEX是當(dāng)前求解整數(shù)規(guī)劃問(wèn)題的主流軟件,以分支定界法作為算法框架,其本質(zhì)上是基于精確算法,雖然求解精度高,但無(wú)法避開(kāi)指數(shù)爆炸問(wèn)題,局限于求解小規(guī)模問(wèn)題且需耗費(fèi)大量計(jì)算時(shí)間,很少被用來(lái)研究PRP[7];而且PRP中,PDP和IRP存在依賴關(guān)系,單一的啟發(fā)式算法難以同時(shí)解決兩個(gè)子問(wèn)題[8],不能保證PRP的全局最優(yōu)。近年來(lái),部分學(xué)者提出了基于數(shù)學(xué)規(guī)劃的啟發(fā)式算法,在求解PRP方面展現(xiàn)出良好的性能,且靈活性較強(qiáng)。代表性的研究有:Absi等[9]提出了一種兩階迭代啟發(fā)式算法(two-phase Iterative heuristic Method,IM)對(duì)未約束生產(chǎn)能力的PRP進(jìn)行求解,該算法在測(cè)試實(shí)例上表現(xiàn)優(yōu)異。通過(guò)模型分解,將初始PRP分解為一個(gè)PDP和由此產(chǎn)生的一系列VRPs;之后IM在第一階段求解一個(gè)PDP來(lái)確定生產(chǎn)、存儲(chǔ)和給每個(gè)客戶交付的器材量,第二階段求解一系列VRP或旅行商問(wèn)題(Traveling Salesman Problems,TSPs)來(lái)整合車(chē)輛路徑。該算法在給定迭代次數(shù)內(nèi)不斷更新近似訪問(wèn)成本這個(gè)迭代變量,在達(dá)到最大迭代次數(shù)或解再無(wú)改進(jìn)時(shí)停止運(yùn)行。此后,Chitsaz等[10]提出了一個(gè)類(lèi)似的三階迭代算法。算法在第一階段確定一個(gè)帶有總近似訪問(wèn)成本的生產(chǎn)計(jì)劃;在固定該生產(chǎn)計(jì)劃后,第二階段確定生產(chǎn)、庫(kù)存和給每個(gè)客戶交付的數(shù)量;第三階段求解規(guī)劃周期內(nèi)的所有VRP并更新近似訪問(wèn)成本。在288個(gè)測(cè)試實(shí)例上,該算法更新了其中70%的最優(yōu)解。
裝備維修器材供應(yīng)保障模式通常都為一對(duì)多,即從兵工廠或軍需倉(cāng)庫(kù)配送到各分散的作戰(zhàn)單元,具有用戶多、分布廣、要求繁雜等特質(zhì),如何科學(xué)高效地將各作戰(zhàn)單元所需器材供應(yīng)到位,就成了亟須解決的問(wèn)題。本文旨在立足于我軍裝備維修器材供應(yīng)保障實(shí)際,為決策者提供一個(gè)有效的裝備維修器材供應(yīng)保障優(yōu)化決策方法。在資源和能力約束下,將生產(chǎn)、庫(kù)存、運(yùn)輸和外包總成本作為優(yōu)化目標(biāo),構(gòu)建一種適用于軍事要求的生產(chǎn)路徑問(wèn)題優(yōu)化決策模型。
本文借鑒文獻(xiàn)[9]中IM算法分解與迭代的求解思想,提出一種兩階啟發(fā)式算法(Two-Level Heuristic,TLH)來(lái)尋求模型的近似最優(yōu)解。與IM相比,TLH的創(chuàng)新之處在于:IM在每一次迭代中都生成生產(chǎn)調(diào)度計(jì)劃TLH只在第一次迭代和多樣化迭代中生成生產(chǎn)調(diào)度計(jì)劃,節(jié)約了求解時(shí)間;IM利用局部分支不等式改變生產(chǎn)調(diào)度計(jì)劃以多樣化搜索,TLH則通過(guò)不斷更新近似訪問(wèn)成本來(lái)多樣化尋優(yōu)區(qū)域搜索;IM一旦求得非可行解,便對(duì)其進(jìn)行修正,而TLH只在第二階段對(duì)非可行解進(jìn)行修正。
裝備維修器材PRP優(yōu)化決策模型具有多變量、多約束等特點(diǎn)[11]。鑒于此,本節(jié)在資源和能力約束下,建立以最小化總成本為目標(biāo)的裝備維修器材PRP混合整數(shù)規(guī)劃(Mixed Integer Linear Programming,MILP)模型。
允許外包的裝備維修器材PRP優(yōu)化決策問(wèn)題是指在滿足各部隊(duì)用戶需求的前提下,對(duì)生產(chǎn)計(jì)劃、庫(kù)存計(jì)劃、運(yùn)輸路徑規(guī)劃和外包策略進(jìn)行集成,以最小化生產(chǎn)、庫(kù)存、運(yùn)輸和外包總成本。每階段的主要決策內(nèi)容包括:工廠的生產(chǎn)量;給每個(gè)作戰(zhàn)單元的交付量;工廠和作戰(zhàn)單元需存儲(chǔ)的器材量;配送路徑;第三方供應(yīng)商需要承擔(dān)的器材供應(yīng)量。本文中,器材的外包供應(yīng)成本由第三方供應(yīng)商與軍隊(duì)裝備管理部門(mén)協(xié)商制訂。該問(wèn)題可用圖1概略描述。
圖1 允許外包的生產(chǎn)路徑問(wèn)題網(wǎng)絡(luò)規(guī)劃Fig.1 Network representations of PRP with outsourcing
為簡(jiǎn)化建模過(guò)程,在上述保障過(guò)程描述的基礎(chǔ)上,做出如下幾點(diǎn)假設(shè)和說(shuō)明:每輛車(chē)在完成每次配送任務(wù)后返回工廠;每階段每輛車(chē)至多執(zhí)行一次配送任務(wù);每階段每個(gè)作戰(zhàn)單元僅能由同一車(chē)輛為其提供一次服務(wù)。
參數(shù)設(shè)定如下:
cij:(i,j)∈A的運(yùn)輸成本;
ap:器材p(p∈P)的單位生產(chǎn)成本;
ep:器材p(p∈P)的外包供應(yīng)成本;
bp:器材p(p∈P)的生產(chǎn)準(zhǔn)備成本;
C:工廠的生產(chǎn)能力;
Ui:節(jié)點(diǎn)i(i∈N)的庫(kù)存能力;
V:車(chē)輛最大允許裝載量。
決策變量定義如下:
qpt:階段t內(nèi)器材p的生產(chǎn)量;
wpt:0-1變量,若階段t內(nèi)工廠生產(chǎn)了器材p,則wpt=1,否則其值為0;
綜上所述,可用如下MILP模型P描述允許外包的裝備維修器材PRP。
(1)
約束條件:
(2)
(3)
(4)
qpt≤Cwpt,?(p∈P,t∈T)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
qpt≥0,?(p∈P,t∈T)
(14)
(15)
(16)
(17)
wpt∈{0,1},?(p∈P,t∈T)
(18)
(19)
(20)
其中:目標(biāo)函數(shù)(1)表示最小化生產(chǎn)、外包、庫(kù)存和運(yùn)輸總成本;式(2)、式(3)保證了工廠和作戰(zhàn)單元之間的庫(kù)存守恒;式(4)保證了每階段生產(chǎn)器材所占用的產(chǎn)能都不能超過(guò)工廠現(xiàn)有的總產(chǎn)能;式(5)表示沒(méi)有生產(chǎn)計(jì)劃時(shí),器材的生產(chǎn)量為0;式(6)限制了作戰(zhàn)單元的庫(kù)存能力;式(7)保證了車(chē)輛不超載;式(8)表示器材的交付活動(dòng)只在作戰(zhàn)單元被訪問(wèn)時(shí)發(fā)生;式(9)表示每個(gè)作戰(zhàn)單元至多被一輛車(chē)訪問(wèn);式(10)確保了車(chē)輛的進(jìn)和出發(fā)生在同一節(jié)點(diǎn);式(11)表示任意作戰(zhàn)單元只與兩個(gè)作戰(zhàn)單元相連;式(12)保證了每輛車(chē)每階段至多執(zhí)行一次配送任務(wù);式(13)表示子回環(huán)消除約束;式(14)~(20)界定了決策變量的取值范圍。
針對(duì)模型特點(diǎn),設(shè)計(jì)了一個(gè)TLH算法,來(lái)尋求模型P的近似最優(yōu)解,分為以下兩步:
步驟1:初始解生成。步驟1旨在構(gòu)造一個(gè)較好的初始解。為降低求解難度,原問(wèn)題首先被分解為一個(gè)PDP和一系列VRP(t)。之后利用兩階迭代方法(Two-phase Iterative Method,TIM)來(lái)求解分解后的子問(wèn)題,從而構(gòu)造一個(gè)初始解。將初始解帶到P中檢測(cè)是否滿足約束條件,若滿足,則該初始解是P的一個(gè)可行解,否則在步驟2中對(duì)其進(jìn)行修正。
步驟2:不可行性修正。步驟2旨在修正步驟1提供的非可行解,直到滿足P的所有約束條件,即可得出P的一個(gè)可行解。該步驟依次求解一個(gè)規(guī)模更小,即變量數(shù)比原問(wèn)題少的限制PDP(Restricted PDP,RPDP)和一系列TSP(t,k)。如果步驟1得到的解可行,便可直接求解TSP(t,k)來(lái)整合車(chē)輛路徑,從而得到一個(gè)完整的可行解。
TLH算法的主框架如圖2所示。
圖2 TLH算法主框架Fig.2 General framework of TLH
該步驟的主要思路是,將原問(wèn)題分解為一個(gè)PDP和一系列VRP(t)子問(wèn)題,并對(duì)其不斷迭代求解,直到達(dá)到停止標(biāo)準(zhǔn)。
2.1.1 多樣化機(jī)制
在給定迭代次數(shù)內(nèi),如果現(xiàn)有解無(wú)改進(jìn),便可重新初始化一個(gè)訪問(wèn)成本來(lái)多樣化搜索,稱該機(jī)制為多樣化機(jī)制,下一次迭代為多樣化迭代。
多樣化機(jī)制的目的是引導(dǎo)算法離開(kāi)局部最優(yōu)解,從而增強(qiáng)算法多樣化搜索的能力。為節(jié)約運(yùn)算時(shí)間,該算法僅在TIM的第一次迭代和多樣化迭代過(guò)程中生成生產(chǎn)調(diào)度計(jì)劃。之后固定該生產(chǎn)調(diào)度計(jì)劃并在隨后的非多樣化迭代過(guò)程中調(diào)用,直到再次出現(xiàn)多樣化迭代。
2.1.2 子問(wèn)題PDP求解
求解第一個(gè)子問(wèn)題PDP可確定器材的生產(chǎn)階段和生產(chǎn)量,以及每階段需要交付到各作戰(zhàn)單元的器材量,但無(wú)法得到車(chē)輛的配送路徑。在此基礎(chǔ)上求解一系列VRP(t),可將上述求得的器材量分配到具體車(chē)輛。
在第一次迭代和多樣化迭代過(guò)程中,將與車(chē)輛相關(guān)的變量和約束從初始模型P中移除后,可得到一個(gè)新模型,記為P1(s),這里定義以下參數(shù)和決策變量。
參數(shù):
決策變量:
(21)
(22)
(23)
(24)
(25)
(26)
(27)
此外,約束條件還包括模型P中的約束式(4)~(6)和式(14)~(16)以及式(18)。
(28)
(29)
此外,約束條件還包括模型P中的約束式(4)、式(6)、式(14)~(16)以及式(22)~(27)。
2.1.3 子問(wèn)題VRP(t)求解
2.1.4 訪問(wèn)成本更新策略
近似訪問(wèn)成本的初始值一般設(shè)置為c0i+ci0,表示給每個(gè)作戰(zhàn)單元派一輛車(chē)配送并返回工廠,共形成k條0→i→0運(yùn)輸路徑。
該設(shè)置可驅(qū)使PDP求解程序得到以較低配送頻率滿足較遠(yuǎn)作戰(zhàn)單元需求的解,從而減少運(yùn)輸成本。 但該設(shè)置沒(méi)有考慮到配送區(qū)域聚類(lèi),即無(wú)法衡量單一階段訪問(wèn)的作戰(zhàn)單元的鄰近性,這就導(dǎo)致相互距離較遠(yuǎn)的作戰(zhàn)單元聚簇并在同一階段被訪問(wèn),從而產(chǎn)生較高的運(yùn)輸成本。 因此,在之后的迭代中,要根據(jù)路徑問(wèn)題解中包含的信息來(lái)更新訪問(wèn)成本,從配送區(qū)域聚類(lèi)的角度驅(qū)使PDP求解程序產(chǎn)生更好的解。
(30)
(31)
(32)
算法在給定迭代次數(shù)內(nèi)重復(fù)上述過(guò)程,之后停止運(yùn)算并輸出最優(yōu)解,供步驟2使用。
步驟2旨在修正步驟1提供的非可行解并整合車(chē)輛路徑,通過(guò)求解一個(gè)RPDP和一系列TSP(t,k)來(lái)構(gòu)造初始模型P的一個(gè)可行解。
(33)
約束條件:
(34)
(35)
(36)
(37)
(38)
其中,約束式(34)表示每階段的生產(chǎn)量必須服從給定的生產(chǎn)計(jì)劃;約束式(35)和式(36)表示器材的交付活動(dòng)只在作戰(zhàn)單元被訪問(wèn)時(shí)才發(fā)生;約束式(37)表示每階段作戰(zhàn)單元i∈B所需器材必須一次性交付。此外,約束條件還包括模型P中的約束式(2)~(4)、式(6)~(7)以及式(14)~(17)。
上述TLH算法的主流程如圖3所示。
圖3 TLH算法主流程Fig.3 Main process of TLH
該兩階啟發(fā)式算法的偽代碼,見(jiàn)算法1。其中,sol*和sol分別用來(lái)儲(chǔ)存得到的最優(yōu)解和當(dāng)前解;obj*和obj分別表示得到的最優(yōu)目標(biāo)值和當(dāng)前目標(biāo)值;s為迭代計(jì)數(shù)器;M表示TIM算法允許的總迭代次數(shù);flag用作第一階段的迭代指示器,其中flag=0表示第一次迭代或多樣化迭代,flag=1表示其他迭代。
算法1中,第1~20行表示初始解生成步驟。其中,第1~9行求解PDP和VRP(t)來(lái)構(gòu)造P的一個(gè)解,但該解未必可行;第10~14行更新最優(yōu)解和近似訪問(wèn)成本;第15~18行表示多樣化迭代;第21~26行表示不可行性修正步驟,其中,第21~23行修正不可行解,第24行求解若干TSP(t,k)。
算法1 兩階啟發(fā)式算法
在規(guī)劃周期內(nèi),決策者需協(xié)調(diào)工廠應(yīng)急生產(chǎn)多品種裝備維修器材,并調(diào)用一組同類(lèi)型車(chē)輛將器材配送給各作戰(zhàn)單元。
表2 工廠參數(shù)設(shè)置
這里給出求解器CPLEX求得的車(chē)輛訪問(wèn)序列。階段1:0→4→2→5→10→3→6→7→1→0,節(jié)點(diǎn)8、節(jié)點(diǎn)9的需求由第三方供應(yīng)商滿足;階段2和階段3無(wú)交付計(jì)劃。
由于本實(shí)例中的器材存儲(chǔ)成本較小,各作戰(zhàn)單元在規(guī)劃周期內(nèi)產(chǎn)生的庫(kù)存積壓費(fèi)用要小于配送費(fèi)用,故各作戰(zhàn)單元在規(guī)劃周期內(nèi)的總需求量在階段1便得到全部滿足。CPLEX的求解結(jié)果比較符合實(shí)際情況,這表明本文提出的模型可行。
影響TLH算法以及求解器CPLEX運(yùn)行效率與效果的主要因素是作戰(zhàn)單元數(shù)、階段數(shù)以及器材品種數(shù)。因此,為評(píng)估TLH算法的有效性,參考文獻(xiàn)[15]中參數(shù)的生成規(guī)則,利用60個(gè)隨機(jī)小規(guī)模實(shí)例進(jìn)行對(duì)比實(shí)驗(yàn)計(jì)算,包括12組不同規(guī)模問(wèn)題,每組問(wèn)題下生成5個(gè)實(shí)例。
對(duì)比實(shí)驗(yàn)采用以下符號(hào)定義來(lái)評(píng)價(jià)TLH算法與求解器CPLEX:obj*列表示TLH求解的最優(yōu)值;objC列表示CPLEX求解的最優(yōu)值或下界值;Gap列表示TLH求解的最優(yōu)值與CPLEX求解的最優(yōu)值的相對(duì)誤差,由Gap=(obj*-objC)/objC×100%計(jì)算得出;T-TLH列和T-CPLEX列分別表示TLH和CPLEX的求解時(shí)間。實(shí)驗(yàn)結(jié)果如表4所示。
分析表4中各列實(shí)驗(yàn)數(shù)據(jù)可以看出:
表4 小規(guī)模實(shí)例計(jì)算結(jié)果
1)TLH求解的最優(yōu)值與CPLEX求得的最優(yōu)解的相對(duì)誤差平均只有1.77%;
2)TLH的平均求解時(shí)間為116 s,是CPLEX的1/24,且隨著問(wèn)題規(guī)模的增大,CPLEX求解時(shí)間的增幅明顯高于TLH算法。
綜上,TLH算法在小規(guī)模實(shí)例上求解效果好,計(jì)算效率優(yōu)于求解器CPLEX。
表3 作戰(zhàn)單元參數(shù)設(shè)置
為進(jìn)一步檢驗(yàn)TLH算法,在文獻(xiàn)[16]提出的兩組基準(zhǔn)實(shí)例集A和B上測(cè)試了TLH算法和IM算法求解一般PRP的性能。集合A共包含1440個(gè)實(shí)例,根據(jù)參數(shù)設(shè)置不同可分為A1、A2和A3三組不同規(guī)模的子集,各包含480個(gè)實(shí)例;集合B共包含90個(gè)實(shí)例,根據(jù)參數(shù)設(shè)置不同可分為B1、B2和B3三組不同規(guī)模的子集,各包含30個(gè)實(shí)例。表5給出了基準(zhǔn)實(shí)例集A和B的詳細(xì)信息。
表5 基準(zhǔn)實(shí)例信息
表6 算法對(duì)比
分析表6中各列數(shù)據(jù)可以發(fā)現(xiàn):
1)對(duì)于基準(zhǔn)實(shí)例集A,TLH在中規(guī)模實(shí)例集A2和大規(guī)模實(shí)例集A3上求得最優(yōu)解的實(shí)例數(shù)量要多于IM,且質(zhì)量較好;但在小規(guī)模實(shí)例集A1上的求解效果不如IM。求解的計(jì)算時(shí)間方面,TLH在A2和A3上明顯占優(yōu),且隨著問(wèn)題規(guī)模的增大,IM求解時(shí)間的增幅要明顯高于TLH。
2)對(duì)于基準(zhǔn)實(shí)例集B,TLH和IM在最大規(guī)模實(shí)例集B3上都沒(méi)有求得最優(yōu)解,但TLH在實(shí)例集B1和B2上的求解效果要強(qiáng)于IM。從算法的求解時(shí)間可以看出,TLH的計(jì)算效率更高。
總體來(lái)看,TLH算法在基準(zhǔn)實(shí)例集上表現(xiàn)出了較好的性能,與IM算法相比,在中規(guī)模和大規(guī)模實(shí)例上求解效果較好,計(jì)算效率較高。
裝備維修器材供應(yīng)保障是裝備保障中的關(guān)鍵一環(huán)。本文首先將器材供應(yīng)保障中的生產(chǎn)、庫(kù)存和配送環(huán)節(jié)的集成優(yōu)化決策問(wèn)題轉(zhuǎn)化為經(jīng)典的生產(chǎn)路徑優(yōu)化決策問(wèn)題進(jìn)行研究,并在集成過(guò)程中考慮了供應(yīng)任務(wù)外包。以此為基礎(chǔ),構(gòu)建了一個(gè)混合整數(shù)線性規(guī)劃模型,之后提出了一個(gè)兩階啟發(fā)式算法進(jìn)行求解。該算法首先將原問(wèn)題分解為兩個(gè)子問(wèn)題,并采用兩階迭代方法來(lái)獲得一個(gè)初始解,之后采用修正策略尋得一個(gè)可行解。將提出的模型與算法應(yīng)用于裝備保障實(shí)例,結(jié)果顯示:求解器CPLEX的求解結(jié)果比較符合實(shí)際情況,表明本文提出的模型可行;TLH算法的求解結(jié)果與求解器CPLEX求得的最優(yōu)解的相對(duì)誤差很小,所用的平均求解時(shí)間更短?;鶞?zhǔn)實(shí)例的測(cè)試結(jié)果表明:TLH算法與IM算法相比,在中等規(guī)模和大規(guī)模實(shí)例上求解效果好、計(jì)算效率高。本文研究成果可為決策者制訂裝備維修器材供應(yīng)保障計(jì)劃提供科學(xué)依據(jù),提出的模型和算法也適用于其他類(lèi)似的單目標(biāo)優(yōu)化決策問(wèn)題。