裝備維修器材生產(chǎn)路徑?jīng)Q策的兩階啟發(fā)式算法*

滕尚儒，何成銘，叢 彬

(1. 陸軍裝甲兵學院 裝備保障與再制造系， 北京 100072； 2. 陸軍裝備部信息保障室， 北京 100072)

裝備維修器材供應(yīng)保障是裝備保障工作的重要組成部分，直接影響著裝備完好率、任務(wù)成功性以及壽命周期費用，其重要性毋庸置疑[1]。其主要目的是保證器材供應(yīng)的不間斷，涉及軍工企業(yè)生產(chǎn)、倉庫存儲、車輛配送到部隊用戶消耗全過程的決策問題。

如何對生產(chǎn)控制、庫存管理和配送路徑進行集成優(yōu)化決策的問題稱為生產(chǎn)路徑問題(Production Routing Problem，PRP)，涵蓋了兩類相互關(guān)聯(lián)和相互制約的子決策問題：生產(chǎn)—直達配送問題(Production Direct-distribution Problem，PDP)和庫存—配送問題(Inventory Routing Problem，IRP)。其中，PDP旨在同時確定生產(chǎn)調(diào)度計劃和直達配送計劃，使得整個規(guī)劃周期內(nèi)工廠的生產(chǎn)、生產(chǎn)準備和庫存總成本最小[2]；IRP是指在規(guī)劃周期內(nèi)由單工廠向多用戶提供配送服務(wù)，在滿足一定約束條件下，確定每個決策階段的庫存策略以及相應(yīng)的配送策略，使存儲和配送總成本最小，其實質(zhì)就是研究庫存補充和配送之間的協(xié)調(diào)問題[3]。

現(xiàn)有研究主要根據(jù)下列特征對PRP的約束條件進行分類：單工廠或多工廠；單品種或多品種產(chǎn)品；帶或不帶能力約束。表1給出了PRP的部分代表性研究文獻。通過分析發(fā)現(xiàn)，學者針對此類問題的研究大多集中在單工廠、單品種和帶能力約束的經(jīng)典PRP，較少涉及多品種PRP。此外，現(xiàn)有研究通常假設(shè)工廠產(chǎn)量始終能滿足用戶需求，但在實際運行過程中，單靠內(nèi)部生產(chǎn)往往不能及時滿足用戶需求[4]。外包是指從外部公司獲得半成品、成品或服務(wù)以及時滿足客戶需求的行為，在PRP中采用外包策略能夠進一步降低系統(tǒng)成本并提高服務(wù)水平[5]。Adulysak等[6]在研究需求不確定的單品種PRP時間接地考慮了外包，其他較少有研究涉及允許外包的多品種PRP。

表1 生產(chǎn)路徑問題的代表性研究文獻

組成PRP的IRP中涉及的VRP是NP-難題，因此PRP更加復(fù)雜。CPLEX是當前求解整數(shù)規(guī)劃問題的主流軟件，以分支定界法作為算法框架，其本質(zhì)上是基于精確算法，雖然求解精度高，但無法避開指數(shù)爆炸問題，局限于求解小規(guī)模問題且需耗費大量計算時間，很少被用來研究PRP[7]；而且PRP中，PDP和IRP存在依賴關(guān)系，單一的啟發(fā)式算法難以同時解決兩個子問題[8]，不能保證PRP的全局最優(yōu)。近年來，部分學者提出了基于數(shù)學規(guī)劃的啟發(fā)式算法，在求解PRP方面展現(xiàn)出良好的性能，且靈活性較強。代表性的研究有：Absi等[9]提出了一種兩階迭代啟發(fā)式算法(two-phase Iterative heuristic Method，IM)對未約束生產(chǎn)能力的PRP進行求解，該算法在測試實例上表現(xiàn)優(yōu)異。通過模型分解，將初始PRP分解為一個PDP和由此產(chǎn)生的一系列VRPs；之后IM在第一階段求解一個PDP來確定生產(chǎn)、存儲和給每個客戶交付的器材量，第二階段求解一系列VRP或旅行商問題(Traveling Salesman Problems，TSPs)來整合車輛路徑。該算法在給定迭代次數(shù)內(nèi)不斷更新近似訪問成本這個迭代變量，在達到最大迭代次數(shù)或解再無改進時停止運行。此后，Chitsaz等[10]提出了一個類似的三階迭代算法。算法在第一階段確定一個帶有總近似訪問成本的生產(chǎn)計劃；在固定該生產(chǎn)計劃后，第二階段確定生產(chǎn)、庫存和給每個客戶交付的數(shù)量；第三階段求解規(guī)劃周期內(nèi)的所有VRP并更新近似訪問成本。在288個測試實例上，該算法更新了其中70%的最優(yōu)解。

裝備維修器材供應(yīng)保障模式通常都為一對多，即從兵工廠或軍需倉庫配送到各分散的作戰(zhàn)單元，具有用戶多、分布廣、要求繁雜等特質(zhì)，如何科學高效地將各作戰(zhàn)單元所需器材供應(yīng)到位，就成了亟須解決的問題。本文旨在立足于我軍裝備維修器材供應(yīng)保障實際，為決策者提供一個有效的裝備維修器材供應(yīng)保障優(yōu)化決策方法。在資源和能力約束下，將生產(chǎn)、庫存、運輸和外包總成本作為優(yōu)化目標，構(gòu)建一種適用于軍事要求的生產(chǎn)路徑問題優(yōu)化決策模型。

本文借鑒文獻[9]中IM算法分解與迭代的求解思想，提出一種兩階啟發(fā)式算法(Two-Level Heuristic，TLH)來尋求模型的近似最優(yōu)解。與IM相比，TLH的創(chuàng)新之處在于：IM在每一次迭代中都生成生產(chǎn)調(diào)度計劃TLH只在第一次迭代和多樣化迭代中生成生產(chǎn)調(diào)度計劃，節(jié)約了求解時間；IM利用局部分支不等式改變生產(chǎn)調(diào)度計劃以多樣化搜索，TLH則通過不斷更新近似訪問成本來多樣化尋優(yōu)區(qū)域搜索；IM一旦求得非可行解，便對其進行修正，而TLH只在第二階段對非可行解進行修正。

1 裝備維修器材PRP模型構(gòu)建

裝備維修器材PRP優(yōu)化決策模型具有多變量、多約束等特點[11]。鑒于此，本節(jié)在資源和能力約束下，建立以最小化總成本為目標的裝備維修器材PRP混合整數(shù)規(guī)劃(Mixed Integer Linear Programming，MILP)模型。

1.1 問題描述

允許外包的裝備維修器材PRP優(yōu)化決策問題是指在滿足各部隊用戶需求的前提下，對生產(chǎn)計劃、庫存計劃、運輸路徑規(guī)劃和外包策略進行集成，以最小化生產(chǎn)、庫存、運輸和外包總成本。每階段的主要決策內(nèi)容包括：工廠的生產(chǎn)量；給每個作戰(zhàn)單元的交付量；工廠和作戰(zhàn)單元需存儲的器材量；配送路徑；第三方供應(yīng)商需要承擔的器材供應(yīng)量。本文中，器材的外包供應(yīng)成本由第三方供應(yīng)商與軍隊裝備管理部門協(xié)商制訂。該問題可用圖1概略描述。

圖1 允許外包的生產(chǎn)路徑問題網(wǎng)絡(luò)規(guī)劃Fig.1 Network representations of PRP with outsourcing

為簡化建模過程，在上述保障過程描述的基礎(chǔ)上，做出如下幾點假設(shè)和說明：每輛車在完成每次配送任務(wù)后返回工廠；每階段每輛車至多執(zhí)行一次配送任務(wù)；每階段每個作戰(zhàn)單元僅能由同一車輛為其提供一次服務(wù)。

1.2 符號說明

參數(shù)設(shè)定如下：

cij：(i,j)∈A的運輸成本；

ap：器材p(p∈P)的單位生產(chǎn)成本；

ep：器材p(p∈P)的外包供應(yīng)成本；

bp：器材p(p∈P)的生產(chǎn)準備成本；

C：工廠的生產(chǎn)能力；

Ui：節(jié)點i(i∈N)的庫存能力；

V：車輛最大允許裝載量。

決策變量定義如下：

qpt：階段t內(nèi)器材p的生產(chǎn)量；

wpt：0-1變量，若階段t內(nèi)工廠生產(chǎn)了器材p，則wpt=1，否則其值為0；

1.3 模型建立

綜上所述，可用如下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)

其中：目標函數(shù)(1)表示最小化生產(chǎn)、外包、庫存和運輸總成本；式(2)、式(3)保證了工廠和作戰(zhàn)單元之間的庫存守恒；式(4)保證了每階段生產(chǎn)器材所占用的產(chǎn)能都不能超過工廠現(xiàn)有的總產(chǎn)能；式(5)表示沒有生產(chǎn)計劃時，器材的生產(chǎn)量為0；式(6)限制了作戰(zhàn)單元的庫存能力；式(7)保證了車輛不超載；式(8)表示器材的交付活動只在作戰(zhàn)單元被訪問時發(fā)生；式(9)表示每個作戰(zhàn)單元至多被一輛車訪問；式(10)確保了車輛的進和出發(fā)生在同一節(jié)點；式(11)表示任意作戰(zhàn)單元只與兩個作戰(zhàn)單元相連；式(12)保證了每輛車每階段至多執(zhí)行一次配送任務(wù)；式(13)表示子回環(huán)消除約束；式(14)～(20)界定了決策變量的取值范圍。

2 求解方法

針對模型特點，設(shè)計了一個TLH算法，來尋求模型P的近似最優(yōu)解，分為以下兩步：

步驟1：初始解生成。步驟1旨在構(gòu)造一個較好的初始解。為降低求解難度，原問題首先被分解為一個PDP和一系列VRP(t)。之后利用兩階迭代方法(Two-phase Iterative Method，TIM)來求解分解后的子問題，從而構(gòu)造一個初始解。將初始解帶到P中檢測是否滿足約束條件，若滿足，則該初始解是P的一個可行解，否則在步驟2中對其進行修正。

步驟2：不可行性修正。步驟2旨在修正步驟1提供的非可行解，直到滿足P的所有約束條件，即可得出P的一個可行解。該步驟依次求解一個規(guī)模更小，即變量數(shù)比原問題少的限制PDP(Restricted PDP，RPDP)和一系列TSP(t,k)。如果步驟1得到的解可行，便可直接求解TSP(t,k)來整合車輛路徑，從而得到一個完整的可行解。

TLH算法的主框架如圖2所示。

圖2 TLH算法主框架Fig.2 General framework of TLH

2.1 初始解生成

該步驟的主要思路是，將原問題分解為一個PDP和一系列VRP(t)子問題，并對其不斷迭代求解，直到達到停止標準。

2.1.1 多樣化機制

在給定迭代次數(shù)內(nèi)，如果現(xiàn)有解無改進，便可重新初始化一個訪問成本來多樣化搜索，稱該機制為多樣化機制，下一次迭代為多樣化迭代。

多樣化機制的目的是引導算法離開局部最優(yōu)解，從而增強算法多樣化搜索的能力。為節(jié)約運算時間，該算法僅在TIM的第一次迭代和多樣化迭代過程中生成生產(chǎn)調(diào)度計劃。之后固定該生產(chǎn)調(diào)度計劃并在隨后的非多樣化迭代過程中調(diào)用，直到再次出現(xiàn)多樣化迭代。

2.1.2 子問題PDP求解

求解第一個子問題PDP可確定器材的生產(chǎn)階段和生產(chǎn)量，以及每階段需要交付到各作戰(zhàn)單元的器材量，但無法得到車輛的配送路徑。在此基礎(chǔ)上求解一系列VRP(t)，可將上述求得的器材量分配到具體車輛。

在第一次迭代和多樣化迭代過程中，將與車輛相關(guān)的變量和約束從初始模型P中移除后，可得到一個新模型，記為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 子問題VRP(t)求解

2.1.4 訪問成本更新策略

近似訪問成本的初始值一般設(shè)置為c0i+ci0，表示給每個作戰(zhàn)單元派一輛車配送并返回工廠，共形成k條0→i→0運輸路徑。

該設(shè)置可驅(qū)使PDP求解程序得到以較低配送頻率滿足較遠作戰(zhàn)單元需求的解，從而減少運輸成本。 但該設(shè)置沒有考慮到配送區(qū)域聚類，即無法衡量單一階段訪問的作戰(zhàn)單元的鄰近性，這就導致相互距離較遠的作戰(zhàn)單元聚簇并在同一階段被訪問，從而產(chǎn)生較高的運輸成本。 因此，在之后的迭代中，要根據(jù)路徑問題解中包含的信息來更新訪問成本，從配送區(qū)域聚類的角度驅(qū)使PDP求解程序產(chǎn)生更好的解。

(30)

(31)

(32)

算法在給定迭代次數(shù)內(nèi)重復(fù)上述過程，之后停止運算并輸出最優(yōu)解，供步驟2使用。

2.2 不可行性修正

步驟2旨在修正步驟1提供的非可行解并整合車輛路徑，通過求解一個RPDP和一系列TSP(t,k)來構(gòu)造初始模型P的一個可行解。

(33)

約束條件：

(34)

(35)

(36)

(37)

(38)

其中，約束式(34)表示每階段的生產(chǎn)量必須服從給定的生產(chǎn)計劃；約束式(35)和式(36)表示器材的交付活動只在作戰(zhàn)單元被訪問時才發(fā)生；約束式(37)表示每階段作戰(zhàn)單元i∈B所需器材必須一次性交付。此外，約束條件還包括模型P中的約束式(2)～(4)、式(6)～(7)以及式(14)～(17)。

上述TLH算法的主流程如圖3所示。

圖3 TLH算法主流程Fig.3 Main process of TLH

2.3 算法偽代碼

該兩階啟發(fā)式算法的偽代碼，見算法1。其中，sol*和sol分別用來儲存得到的最優(yōu)解和當前解；obj*和obj分別表示得到的最優(yōu)目標值和當前目標值；s為迭代計數(shù)器；M表示TIM算法允許的總迭代次數(shù)；flag用作第一階段的迭代指示器，其中flag=0表示第一次迭代或多樣化迭代，flag=1表示其他迭代。

算法1中，第1～20行表示初始解生成步驟。其中，第1～9行求解PDP和VRP(t)來構(gòu)造P的一個解，但該解未必可行；第10～14行更新最優(yōu)解和近似訪問成本；第15～18行表示多樣化迭代；第21～26行表示不可行性修正步驟，其中，第21～23行修正不可行解，第24行求解若干TSP(t,k)。

算法1 兩階啟發(fā)式算法

3 實例分析

3.1 模型可行性驗證

在規(guī)劃周期內(nèi)，決策者需協(xié)調(diào)工廠應(yīng)急生產(chǎn)多品種裝備維修器材，并調(diào)用一組同類型車輛將器材配送給各作戰(zhàn)單元。

表2 工廠參數(shù)設(shè)置

這里給出求解器CPLEX求得的車輛訪問序列。階段1：0→4→2→5→10→3→6→7→1→0，節(jié)點8、節(jié)點9的需求由第三方供應(yīng)商滿足；階段2和階段3無交付計劃。

由于本實例中的器材存儲成本較小，各作戰(zhàn)單元在規(guī)劃周期內(nèi)產(chǎn)生的庫存積壓費用要小于配送費用，故各作戰(zhàn)單元在規(guī)劃周期內(nèi)的總需求量在階段1便得到全部滿足。CPLEX的求解結(jié)果比較符合實際情況，這表明本文提出的模型可行。

3.2 實驗對比分析

影響TLH算法以及求解器CPLEX運行效率與效果的主要因素是作戰(zhàn)單元數(shù)、階段數(shù)以及器材品種數(shù)。因此，為評估TLH算法的有效性，參考文獻[15]中參數(shù)的生成規(guī)則，利用60個隨機小規(guī)模實例進行對比實驗計算，包括12組不同規(guī)模問題，每組問題下生成5個實例。

對比實驗采用以下符號定義來評價TLH算法與求解器CPLEX：obj*列表示TLH求解的最優(yōu)值；objC列表示CPLEX求解的最優(yōu)值或下界值；Gap列表示TLH求解的最優(yōu)值與CPLEX求解的最優(yōu)值的相對誤差，由Gap=(obj*-objC)/objC×100%計算得出；T-TLH列和T-CPLEX列分別表示TLH和CPLEX的求解時間。實驗結(jié)果如表4所示。

分析表4中各列實驗數(shù)據(jù)可以看出：

表4 小規(guī)模實例計算結(jié)果

1)TLH求解的最優(yōu)值與CPLEX求得的最優(yōu)解的相對誤差平均只有1.77%；

2)TLH的平均求解時間為116 s，是CPLEX的1/24，且隨著問題規(guī)模的增大，CPLEX求解時間的增幅明顯高于TLH算法。

綜上，TLH算法在小規(guī)模實例上求解效果好，計算效率優(yōu)于求解器CPLEX。

表3 作戰(zhàn)單元參數(shù)設(shè)置

3.3 算法性能評估

為進一步檢驗TLH算法，在文獻[16]提出的兩組基準實例集A和B上測試了TLH算法和IM算法求解一般PRP的性能。集合A共包含1440個實例，根據(jù)參數(shù)設(shè)置不同可分為A1、A2和A3三組不同規(guī)模的子集，各包含480個實例；集合B共包含90個實例，根據(jù)參數(shù)設(shè)置不同可分為B1、B2和B3三組不同規(guī)模的子集，各包含30個實例。表5給出了基準實例集A和B的詳細信息。

表5 基準實例信息

表6 算法對比

分析表6中各列數(shù)據(jù)可以發(fā)現(xiàn)：

1)對于基準實例集A，TLH在中規(guī)模實例集A2和大規(guī)模實例集A3上求得最優(yōu)解的實例數(shù)量要多于IM，且質(zhì)量較好；但在小規(guī)模實例集A1上的求解效果不如IM。求解的計算時間方面，TLH在A2和A3上明顯占優(yōu)，且隨著問題規(guī)模的增大，IM求解時間的增幅要明顯高于TLH。

2)對于基準實例集B，TLH和IM在最大規(guī)模實例集B3上都沒有求得最優(yōu)解，但TLH在實例集B1和B2上的求解效果要強于IM。從算法的求解時間可以看出，TLH的計算效率更高。

總體來看，TLH算法在基準實例集上表現(xiàn)出了較好的性能，與IM算法相比，在中規(guī)模和大規(guī)模實例上求解效果較好，計算效率較高。

4 結(jié)論

裝備維修器材供應(yīng)保障是裝備保障中的關(guān)鍵一環(huán)。本文首先將器材供應(yīng)保障中的生產(chǎn)、庫存和配送環(huán)節(jié)的集成優(yōu)化決策問題轉(zhuǎn)化為經(jīng)典的生產(chǎn)路徑優(yōu)化決策問題進行研究，并在集成過程中考慮了供應(yīng)任務(wù)外包。以此為基礎(chǔ)，構(gòu)建了一個混合整數(shù)線性規(guī)劃模型，之后提出了一個兩階啟發(fā)式算法進行求解。該算法首先將原問題分解為兩個子問題，并采用兩階迭代方法來獲得一個初始解，之后采用修正策略尋得一個可行解。將提出的模型與算法應(yīng)用于裝備保障實例，結(jié)果顯示：求解器CPLEX的求解結(jié)果比較符合實際情況，表明本文提出的模型可行；TLH算法的求解結(jié)果與求解器CPLEX求得的最優(yōu)解的相對誤差很小，所用的平均求解時間更短?；鶞蕦嵗臏y試結(jié)果表明：TLH算法與IM算法相比，在中等規(guī)模和大規(guī)模實例上求解效果好、計算效率高。本文研究成果可為決策者制訂裝備維修器材供應(yīng)保障計劃提供科學依據(jù)，提出的模型和算法也適用于其他類似的單目標優(yōu)化決策問題。