裝備維修器材生產路徑雙目標問題優(yōu)化決策方法研究

滕尚儒，何成銘，叢 彬

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

0 引言

裝備維修器材供應保障是裝備保障工作的重要組成部分，其基本職能是彌補器材供需之間在空間上和時間上的不一致，以保證平時和戰(zhàn)時器材供應的不間斷[1]。其主要任務涉及到生產和庫存計劃的制定、運輸方式和運輸工具的合理選擇、配送路徑規(guī)劃等[2]。研究合理地制定生產、庫存及配送計劃，使得供應鏈上總成本最低，該優(yōu)化問題被稱為生產路徑問題(production routing problem，PRP)。PRP一般研究：已知各客戶點物品的初始存儲量、每天消耗規(guī)律、最大庫存能力，以及生產廠家的生產、庫存水平、配送車輛運輸能力，需要確定生產廠家的生產策略、客戶的庫存策略，以及給各客戶配送物品的時間、數量、配送路徑，以保證在各客戶不缺貨的情況下，規(guī)劃周期內的總成本最小。

在一般的單目標PRP中，最小化總成本或最大化總利潤是最常見的優(yōu)化目標，但在實際問題中，決策者通常需要用多個目標來比較，而這些目標有時不甚協調，甚至是矛盾的。同樣對器材供應保障工作而言，如果只考慮成本，而對部隊的需求反應滯緩，不能在一個合理的期限內，將部隊所需的器材送達目的地，其后果也許是相當嚴重的，提出申請的部隊會因此失去應有的戰(zhàn)斗力，甚而整場戰(zhàn)爭也會因此而失利。同時，現代戰(zhàn)爭具有節(jié)奏快、攻防轉換頻繁的特點，部隊用戶往往對器材保障的精度有嚴格要求。超過部隊用戶的實際需求量，會增加部隊用戶的倉儲成本，浪費人力物力，而且過多的輜重會影響部隊的機動性，使部隊受到攻擊的風險增大。這種情況下，衡量一個器材保障優(yōu)化方案的好壞往往難以只用經濟指標來判斷。器材保障能否在保證經濟效益的前提下，在恰當的時間和恰當的地點為部隊用戶提供恰當品種、數量器材，亦即精確保障理論中的“適時、適地、適量”保障[3]，成為保障部隊用戶實現軍事效益的關鍵。

裝備維修器材PRP優(yōu)化涉及到時間、經濟、效用等諸多目標，這種多目標、多約束、多要求、動態(tài)性等特點，使得傳統優(yōu)化方法和模型的應用受到很大限制[4]。關于多目標優(yōu)化問題，目前國內外有較多研究。龔延成[5]在分析戰(zhàn)時物流運輸路線選擇時，綜合考慮了安全性、時效性和經濟性三個決策目標，通過無量綱化轉化成單目標決策問題，并用最短路徑方法求解最優(yōu)路徑。石玉峰[6]針對目標的模糊性，建立了基于時間、風險和保障代價三個方面的模糊多目標決策模型，通過消弧和最小費用路法求得了最優(yōu)解。Amorim和Almada-Lobo[7]研究了一個帶時間窗的雙目標生產運輸問題，同時優(yōu)化了運輸費用和用戶滿意度。

本文以總成本最小為主要目標和訂單精準執(zhí)行率最高為輔助目標，建立裝備維修器材PRP雙目標優(yōu)化決策模型，并開發(fā)一個基于ε-約束法的兩階迭代啟發(fā)式算法進行求解之后采用一種模糊邏輯決策法幫助決策者選擇折中最優(yōu)解，最后利用實例驗證提出的模型與算法。

1 問題描述與建模

1.1 問題描述與符號說明

假設用有向圖G=(N,A)表示配送網絡，其中N={0,1,…,n}表示節(jié)點集，A為弧集。節(jié)點0表示裝備維修器材生產工廠，其庫存能力記為U0，最大生產能力記為C。工廠可生產單品種器材，并可調用一組容量為V的相同類型車輛K={1,2,…,|K|}。圖G中分布有一組部隊用戶R={1,2,…,n}，每個部隊用戶i∈R的最大庫存能力為Ui，在計劃期T={1,2,…,|T|}內，對器材的需求具有確定性和時變性。

裝備維修器材PRP的雙目標優(yōu)化決策問題是指在滿足各部隊用戶需求的前提下，對生產計劃、庫存計劃和運輸路徑規(guī)劃進行整合，以最小化生產、庫存、運輸總成本，同時最大化訂單精準執(zhí)行率。其中，訂單精準執(zhí)行率是器材精確保障中重要的指標，它包含多方面因素，如供貨準時率、數量準確率、質量合格率、資料齊備率等。本文利用每個時間段結束時部隊用戶的庫存持有量與該階段實際需求量的比值來表示訂單精準執(zhí)行率，這里需要注意的是，該比值越小，表示訂單精準執(zhí)行率越高。

每階段需要決策的問題如下：(1)工廠生產多少；(2)給每個部隊用戶交付多少；(3)工廠和每個部隊用戶各需持有多少庫存；(4)如何確定最佳運輸路徑。

為公式化該問題，定義了以下參數和變量：

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

at：階段t∈T的單位生產成本；

bt：階段t∈T的生產準備成本；

C：工廠的生產能力；

gi：i∈N的初始庫存；

Ui：i∈N的庫存能力；

hi：每階段節(jié)點i∈N的庫存成本；

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

引入決策變量如下：

pt：階段t工廠生產的器材量；

wt：0-1決策變量，若階段t工廠啟動生產，則wt=1，否則其值為0；

為了簡化建模過程，在上述供應保障過程描述的基礎上，做出如下幾點假設和說明：(1)每輛車在完成每次配送任務后返回工廠；(2)每階段每輛車至多執(zhí)行一次配送任務；(3)每階段每個部隊用戶僅能由同一車輛為其提供一次服務。

1.2 模型建立

本文提出的裝備維修器材PRP雙目標優(yōu)化決策模型P表示如下：

目標函數：

(1)

(2)

約束條件:

(3)

(4)

(5)

pt≤Cwt,?t∈T

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

pt≥0,?t∈T

(14)

(15)

(16)

wt∈{0,1},t∈T

(17)

(18)

(19)

其中，目標函數(1)由生產、庫存和運輸成本三部分組成；目標函數(2)表示最大化訂單精準執(zhí)行率，這里目標值越小，訂單精準執(zhí)行率越高。式(3)～(5)確保工廠和部隊用戶之間的庫存守恒；式(6)確保工廠每階段的生產量不超過工廠最大生產能力；式(7)限制了每個節(jié)點的最大庫存；式(8)確保車輛在配送過程中的實際載貨量不超過其最大允許裝載量；式(9)表示只有部隊用戶被訪問時才允許車輛交付器材；式(10)表示每個部隊用戶至多被一輛車訪問；式(11)表示車流量守恒，即車輛到達一個節(jié)點后必須從該節(jié)點離開；式(12)確保每輛車每階段至多執(zhí)行一次配送任務；式(13)消除了子回環(huán)，避免了子回路解產生；式(14)～(19)界定了決策變量的范圍。

2 求解算法

從上述的模型可以看出，裝備維修器材PRP雙目標優(yōu)化決策問題是一個復雜的最優(yōu)化問題。為此，本文開發(fā)了一個基于ε-約束法的兩階迭代啟發(fā)式算法(ε-constraint-based two-phase iterative heuristic,ε-CTIH)并利用模糊邏輯決策法，幫助決策者在兩個目標之間找到平衡點，實現雙目標函數在給定區(qū)域上的最優(yōu)化。

2.1 雙目標優(yōu)化問題原理

一般的雙目標優(yōu)化問題可以用如下公式表示：

minf1=φ(x)

(20)

minf2=ω(x)

(21)

約束條件：

x∈X

(22)

式中，f1和f2表示兩個可能矛盾的目標，即，可能不存在使和同時達到最小的解；X是雙目標優(yōu)化模型的約束集，φ(x)和ω(x)分別對應于兩個目標函數。

若φ(x)≤φ(x′)且ω(x)≤ω(x′)，稱一個可行解x∈X不劣于另一個可行解x′∈X，當且僅當x不劣于x′，同時兩個不等式中至少有一個不等式取嚴格小于號，則稱解x占優(yōu)于x′，記為x′x。如果不存在其他x′∈X，使得x′x，則稱x∈X是多目標優(yōu)化模型的Pareto最優(yōu)解，或稱為非劣解，其對應的目標值φ(x)和ω(x)形成一個Pareto最優(yōu)點，在目標函數可行解空間里所有的未被占優(yōu)的點構成Pareto前沿。綜上，Pareto解集可定義為PS={x∈X|x為Pareto最優(yōu)}，Pareto前沿定義為Pf={(φ(x),ω(x))|x∈PS}。

2.2 ε-約束法

ε-約束法的基本思想是通過適當處理將最初的多目標問題轉化為一系列單目標問題。首先求得目標函數ω(x)的最優(yōu)值ε，之后將其轉化為ω(x)的約束條件，即在ω(x)≤ε約束下，尋找另一目標φ(x)的最優(yōu)值，從而獲得一組Pareto解。對于給定的ε值，單目標問題M(ε)描述如下:

min{φ(x)|ω(x)≤ε,x∈X}

(23)

求解該問題可得x*(ε)∈X，f1(ε)=φ(x*(ε)),f2(ε)=ω(x*(ε))<ε。這里可以很容易地證明，對任意x∈PS，存在一個ε，使得x=x*(ε)。因此，然后逐漸增加或減少ε的值并以此為約束求得φ(x)的最優(yōu)值，通過多次求解，逐漸求得多組在ω(x)不同值情況下φ(x)的Pareto解，獲得Pareto解集PS，便是初始問題的最優(yōu)解集，決策者可以根據偏好從中選擇理想的Pareto解。對于本文研究的問題，可將第二個目標訂單精準執(zhí)行率轉化為一個約束條件，得到如(23)所示的單目標模型M(ε)。

(24)

(25)

(26)

(27)

理想情況下，通過列舉ε的所有可能取值來求解一系列M(ε)，可以生成精確的Pareto前沿。但由于參數ε的連續(xù)性，該步驟需要求解大量復雜且耗時的M(ε)，可行性不強。實踐中，決策者期望在合理的計算時間內獲得一些有代表性的Pareto解來構成近似Pareto前沿AF。因此，本文提出了一個基于ε-約束的兩階迭代啟發(fā)式算法ε-CTIH來獲取近似Pareto前沿。根據ε的|M|個不同取值，首先對一組共計M=1,2,…,|M|個單目標M(ε)進行求解，并利用兩階迭代啟發(fā)式算法(two-phase iterative heuristic, TIH)來求解第m個單目標問題M(εm)。

2.3 兩階迭代啟發(fā)式算法

2.3.1 子問題LSP求解

求解LSP(εm,δm,λm)可確定工廠在哪個階段生產和相應的生產量，以及每階段給每個部隊用戶交付的器材量，但無法確定每個車輛具體的配送路徑。在此基礎上求解一系列VRP(εm)，可將求解LSP(εm,δm,λm)確定的每階段給每個部隊用戶交付的器材量分配給每個車輛。

目標函數:

(28)

約束條件：(3)，(6)，(7)，(17)～(19)

(29)

(30)

(31)

(32)

(33)

(34)

(35)

其中，目標函數(28)表示最小化生產，庫存和近似訪問總成本；式(29)表示訂單精準執(zhí)行率受εm約束；式(32)確保給所有部隊用戶的總交付量不超過所有車輛的總裝載量與車輛載荷利用率的乘積；其它約束式與模型P中相應約束式含義相同。

2.3.2 子問題VRP求解

目標函數：

(36)

約束條件：

(37)

(38)

(39)

(40)

(41)

(42)

(43)

其中，目標函數(36)表示最小化配送路徑總成本；式(37)～(41)為車輛路徑約束。

本文之后調用Gro?r等[8]提出的VRPH算法對VRP(t,εm)進行求解，可確定每個車輛具體的配送路徑Rkt，路徑的數量NRt，和配送總成本RC。在所有VRP(t,εm)的解中，如果路徑的數量NRt不超過物流服務商提供的車量總數|K|，LSP(εm,δm,λm)和VRP(εm)這兩個子問題的解便可構成M(εm)的一個可行解。

2.3.3 參數更新機制

為尋得近似最優(yōu)解，需要依次迭代地求解LSP(εm,δm,λm)和VRP(t,εm)這兩個子問題，每次迭代過程中，算法會根據上一次迭代中VRP(t,εm)的解來更新參數集δm和λm。

2.4 基于ε-約束的兩階迭代啟發(fā)式算法

一般的ε-約束法只利用ε作為鏈接，而本文提出的ε-CTIH則通過ε、δ和λ這三個參數鏈接了M(εm)和M(εm+1)。

2.5 偏好解選擇

(44)

(45)

綜上，利用ε-CTIH獲取偏好解的主流程如圖1所示。

圖1 ε-CTIH獲取偏好解的主流程圖

3 實例計算與結果分析

3.1 實例背景

本文以某重型合成旅陸地陣地進攻戰(zhàn)斗裝備保障為背景，裝備保障指揮部需協調某兵工廠臨時應急生產單品種裝備維修器材，并調用3輛相同類型車輛配送給陣地上的40個部隊用戶。決策者需要依據以往戰(zhàn)斗裝備損壞規(guī)律，為未來7天的戰(zhàn)斗制定一個集成的器材供應保障計劃，包括工廠每天生產多少，每天給每個部隊用戶交付多少，如何為給定的交付計劃規(guī)劃好配送路徑，在降低總成本的前提下盡可能地最大化訂單精準執(zhí)行率。表1給出了該實例詳細的參數設置。

表1 實例參數設置

本文首先設計了一個簡單的三階啟發(fā)式算法來對總成本目標直接尋優(yōu)。假設生產的器材只能存儲在工廠，決策者首先根據各部隊用戶的需求確定每天的器材生產量以最小化生產成本，在此基礎上求得一個最小化總庫存成本的交付計劃，最后根據確定的交付計劃來生成車輛配送路徑。本文之后調用CPLEX求解部分子問題，得到了一個總成本為439,630RMB，訂單精準執(zhí)行率為71.8%的方案。

3.2 結果對比分析

通過所提出的模型和ε-CTIH獲得的Pareto解集如圖2。圖中，支配解已被剔除，縱坐標和橫坐標分別表示訂單精準執(zhí)行率和總成本。求得Pareto解集后，可直接將所有解提供給決策者參考，也可以通過模糊邏輯決策法幫助決策者選擇一個折中最優(yōu)解。

圖2 近似Pareto前沿

求解上述實例共獲得29個Pareto解，從獲得的Pareto前沿可以看出，兩個優(yōu)化目標之間存在一定的沖突。圖中的兩個實心正方形分別表示兩個目標的近似下界和上界，實心三角形表示三階啟發(fā)式算法求得的解。顯然，ε-CTIH求得的部分解占優(yōu)于該三階啟發(fā)式算法求得的解。在訂單精準執(zhí)行率相同的情況下，ε-CTIH求得的解中成本降低了5.6%；在成本相同的情況下，ε-CTIH求得的解中訂單精準執(zhí)行率提高了近30%。

為幫助決策者根據偏好選擇一個折中最優(yōu)解，本文假設根據情況不同，決策者有3種不同的偏好：第一種情況下，決策者更注重總成本的控制，給第一個目標賦予的權重為ω1=0.7；第二種情況下，決策者同樣重視兩個目標，即ω1=0.5；第三種情況下，決策者更注重訂單精準執(zhí)行率，給總成本目標賦予的權重為ω1=0.3。圖1顯示了在上述3種不同的偏好下選擇的解，從中可以看出不同的權重設置導致了不同的Pareto解。

表2 偏好解的詳細信息

從表2可以看出，隸屬度的取值范圍從0.81到0.93，相對較高。如果決策者更注重成本的控制，選擇的解中成本會增長6.28%，訂單精準執(zhí)行率提高37%；如果決策者更注重訂單精準執(zhí)行率，選擇的解中成本會提高31.65%，訂單精準執(zhí)行率提高81%。從表中最后四列可以看出，訂單精準執(zhí)行率權重的增加會導致：(1)生產啟動次數增多，生產成本增長；(2)給部隊用戶交付器材的頻率更高，相應的運輸成本也會增長；(3)每階段結束時剩余的器材較少或無剩余，庫存成本降低。

3.3 算法性能評估

在單目標優(yōu)化中，可以利用下界或上界與獲得的解進行比較來直接評價解的質量，而在雙目標優(yōu)化中，評價近似Pareto解集AF的質量相對較復雜，通常需要參考另一個Pareto解集，記為RF。為評估ε-CTIH的性能，本文基于ε-約束法框架，設計了一個新的運用CPLEX求解每個單目標問題M(εm)的算法，記為ε-CC。ε-CC的基本框架與算法2類似，但在調用CPLEX進行求解時，計算時間限制在14400s內，且M(εm)和M(εm+1)之間只通過參數ε來鏈接。本文中的AF和RF分別由ε-CTIH和ε-CC提供。

表3 參數生成規(guī)則

對比實驗采用基數|Ar|、|RF|和計算時間T來評估算法性能，實驗結果如表4。表中，第5至第8列統計了算法在5個實例上運行后各個評估指標的均值，TC和TH列分別表示ε-CC和ε-CTIH的平均求解時間，TLC和TLH列分別表示ε-CC和ε-CTIH求解5個相同規(guī)模實例所用的最長計算時間。

圖3進一步給出了表中6個評估指標的詳細對比結果。

表4 小規(guī)模實例對比實驗結果

圖3 ε-CTIH和ε-CC對比實驗結果

比較表4和圖3中的實驗數據可以看出：

(1)從表4的基數列和圖3(a)可以觀察到，對包含10個部隊用戶和1輛車的實例，ε-CTIH與ε-CC生成的Pareto解的數量相差不大；在超過16個部隊用戶的實例上，ε-CTIH與ε-CC相比，能夠提供更多的Pareto解；在規(guī)定的求解時間內，ε-CC無法為包含25個部隊用戶和2輛車的實例提供Pareto解。

(2)在求解時間方面，表4顯示ε-CTIH和ε-CC求解的平均計算時間分別為159s和7546s，前者是后者2.1%，表明ε-CTIH的計算效率更高；從表4的最后一列可以看出，在所有實例上，ε-CTIH求解的最長計算時間的平均值比平均計算時間僅高出66s，表明ε-CTIH在求解時間上的穩(wěn)定性較強；ε-CC求解的最長計算時間的平均值與平均計算時間之間有很大差異。此外，從圖3(b)可以看出，隨著問題規(guī)模的增大，ε-CC的求解時間呈指數級增長，增幅明顯高于ε-CTIH。

4 結論

本文以經典的生產路徑優(yōu)化決策問題為基礎，研究了裝備維修器材PRP雙目標優(yōu)化決策問題。

(1)以總成本最小和訂單精準執(zhí)行率最大為優(yōu)化目標，構建了一個雙目標混合整數線性規(guī)劃模型。

(2)針對模型非線性有約束的特點，開發(fā)了一個基于ε-約束法的兩階迭代啟發(fā)式算法生成近似Pareto前沿，之后采用一種模糊邏輯決策方法幫助決策者根據偏好在諸多Pareto解中選擇折中最優(yōu)解。

(3)將提出的模型與算法應用于某次裝備保障的實例，結果表明本文提出的模型真實有效，開發(fā)的算法和偏好解選擇方法能夠很好地幫助決策者做出器材供應保障決策。基于不同規(guī)模測試問題的數值實驗表明，所設計的ε-CTIH求解雙目標問題的效果好、計算效率高。