帶時間窗的裝備維修器材生產路徑建模與優化

滕尚儒，何成銘，叢 彬

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

裝備維修器材供應保障是裝備保障工作的重要組成部分，其基本職能是彌補器材供需之間在空間上和時間上的不一致，以保證平時和戰時器材供應的不間斷[1]。其主要任務涉及生產和庫存計劃的制定、運輸方式和運輸工具的合理選擇以及配送路徑規劃等問題。研究合理地制定生產、庫存及配送計劃，使得供應鏈上總成本最低，該優化問題被稱為生產路徑問題(production routing problem，PRP)。

相對于傳統戰爭，信息化條件下的戰爭強度大，裝備損傷多，部隊用戶對器材的需求主要體現在器材供應的數、質、時、空四個方面，其中，“時”即時間。物流對配送時間上的要求主要體現在兩個方面：一是對配送運輸時間的有效性要求。從目前物流發展的現狀分析，這是一種時間段要求，即通常要求在規定的時間段內完成相應的配送運輸保障任務；二是對配送運輸時間的精確性要求。供應鏈對各個環節的銜接具有嚴格的時間要求，當這種要求達到較高水準時，配送運輸的送達時間就必須做到精確，也就是說配送與物流體系中其他環節在時間上要達到精確協接。

在器材供應保障過程中，給每個部隊用戶增添時間窗約束以進行配送服務，涉及的VRP就衍變成了VRPTW(vehicle routing problem with time windows，VRPTW)。VRPTW是基本VRP的擴展問題，是在VRP的基礎上考慮每個客戶對配送時間的具體要求，該時間窗是由客戶要求的最早服務時間和最晚服務時間所確定的一個服務時間區間。根據能不能違反時間限制這一標準，可以進一步將時間窗進行細分：能夠以一定懲罰為代價進行違反的時間限制為軟時間窗；必須嚴格執行的時間限制稱為硬時間窗。

國內外學者對于此類帶時間窗的優化問題已做出諸多的研究，Zografos等[2]提出了一個基于GIS決策支持系統的路徑構建算法，有效地解決了帶時間窗的雙目標車輛路徑優化問題。Shen等[3]探究在時變條件下多時間窗約束的危險品運輸網絡優化問題，并結合動態規劃法與灰色關聯分析法進行求解。趙達等[4]提出了一種修正的節約算法來求解帶硬時間窗的隨機需求庫存路徑優化問題，能夠在較短計算時間內最小化配送成本和用車數量。趙崇遠[5]針對有時間窗的車輛調度問題，建立了含有時間懲罰函數的數學模型，并用遺傳算法和節約啟發式算法求解。

論文研究了部隊用戶(需求)硬時間窗約束下的裝備維修器材PRP，各需求點只在指定時間窗內接受服務，同時還考慮了車輛最早離廠和最晚進廠時間。首先針對問題特征構建一個以總成本最小為目標的混合整數線性規劃(mixed integer linear programming，MILP)模型，同時提出3個有效不等式來改進該模型，之后在CPLEX平臺上求解隨機生成的45個算例，驗證了優化模型和不等式的有效性。

1 問題分析與建模

現代作戰戰場情況復雜，對器材供應的時效性要求較高，器材供應時間不能過早也不能過晚：過早可能暴露作戰企圖，還容易給部隊造成累贅；過晩可能造成供應間斷，影響部隊修復通用裝備，貽誤戰機。精確保障要求下的器材供應保障工作強調器材交付時間的準確性，即在一個合理的期限內將部隊所需的器材送達目的地，確保部隊用戶能夠及時得到器材保障。

因此研究裝備維修器材PRP，就必須充分考慮部隊用戶對器材交付時間的要求，同時也能夠反映器材供應保障工作的總體服務水平。

1.1 問題描述

假設用有向圖G=(N,A)表示配送網絡，其中，N={0,1,…,n}表示節點集，A為弧集。節點0表示器材承制單位，其庫存能力記為U0，最大生產能力記為C。器材承制單位可生產單品種器材，物流服務商可提供一組容量為V的同類型車輛K={1,2,…,|K|}。圖G中分布有一組部隊用戶R={1,2,…,n}，每個部隊用戶i∈R的最大庫存能力為Ui，在規劃周期T={1,2,…,|T|}內，對器材的需求具有時變性和確定性[6]。該生產路徑問題網狀結構可用圖1概略描述。

圖1 生產路徑問題網狀結構示意圖

所考慮的時間窗是一個部隊用戶與物流服務商協商好的、由部隊用戶的最早和最晚可接受服務的時間確定的一個時間區間[ET,LT]，ET表示最早可到達時間，LT表示最晚必須到達時間。當器材交付時間超出[ET,LT]時，其懲罰值等于一個非常大的正值，表示硬時間窗的限制，超出時間窗的服務視為無效服務，將其作為不可行解，從而每階段部隊用戶只能在該時間窗內接受服務。

綜上，帶時間窗的裝備維修器材PRP是指在規定時間窗內滿足各部隊用戶需求的前提下，對生產計劃、庫存計劃、配送計劃進行整合，以最小化生產、庫存和運輸總成本。每階段的主要決策內容包括：

1) 器材承制單位生產多少；

2) 給每個部隊用戶交付多少；

3) 如何為給定的交付計劃規劃運輸路徑。

為了簡化建模過程，在上述保障過程描述的基礎上，做出如下幾點假設和說明：

1) 器材承制單位在車輛離廠前已完當前階段成生產任務；

2) 每輛車在完成每次配送任務后返回器材承制單位；

3) 每階段每輛車至多執行一次配送任務；

4) 為節約卸貨時間，每階段每個部隊用戶僅能由同一車輛為其提供一次服務。

1.2 符號說明

引進參數如表1所示。

模型中的變量如表2所示。

表2 模型中的變量

1.3 模型構建

綜上所述，可用如下MILP模型表示帶時間窗的裝備維修器材PRP優化決策模型，記為P1。

(1)

約束條件：

(2)

(3)

(4)

pt≤Ytwt,?t∈T

(5)

(6)

(7)

(8)

(9)

(10)

(11)

?i∈R,j∈R{j},k∈K,t∈T

(12)

(13)

(14)

(15)

(16)

(17)

pt≥0,?t∈T

(18)

(19)

(20)

wt∈{0,1},t∈T

(21)

(22)

(23)

(24)

(25)

(26)

其中，目標函數(1)由生產、庫存和運輸成本3部分組成；式(2)-式(4)確保器材承制單位和部隊用戶之間的庫存守恒；式(5)確保器材承制單位每階段的生產量不超過其最大生產能力和部隊用戶未來階段的總需求量；式(6)限制了器材承制單位和部隊用戶的最大庫存；式(7)確保車輛在配送過程中的實際載貨量不超過其最大允許裝載量；式(8)表示如果車輛訪問了某部隊用戶，交付給該部隊用戶的器材量不能超過其未來階段的總需求量；式(9)表示每個部隊用戶至多被一輛車訪問；式(10)表示車流量守恒，即車輛到達一個節點后必須從該節點離開；式(11)確保每輛車每階段至多執行一次配送任務；式(12)確保了車輛訪問各部隊用戶時間的一致性；式(13)和(14)確保了車輛從器材承制單位出發時間和返回時間的一致性；式(15)-式(17)確保了部隊用戶在規定的時間窗內接受服務，并限制了車輛從器材承制單位出發和返回時刻；式(18)-式(26)界定了決策變量的取值范圍。

2 有效不等式

有效不等式是區別于原問題約束的，并且主問題中整數變量滿足的關系不等式。其加入可以對主問題的解空間進行有益的限制，能夠減少由主問題得出的整數解對于子問題不可行的情況，加速算法的收斂，并起到改進初始下界的作用。這些有效不等式通常是基于問題結構提出，對于不同的問題有不同形式的有效不等式。由于加入了時間窗約束，所構建的模型中包含了更多0-1變量和連續變量，可行域較大，通過CPLEX優化求解器可求得小規模實例最優解且求解的時間較長。

(27)

(28)

?i∈R,t∈T,t

(29)

式(27)表示在調用車輛k之前，車輛k+1不能離開器材承制單位，該不等式確保了編號靠前的車輛被優先調用；式(28)表示如果階段t部隊用戶i∈R由車輛k訪問，那么車輛k-1也一定訪問過同一階段編號在i之前的部隊用戶；式(29)表示如果某部隊用戶在區間[t+1,τ]內未被訪問，那么階段t結束時的該部隊用戶的庫存量足夠必須能夠滿足其在[t+1,τ]內的總需求量。

目標函數(1)和式(2)-式(29)構成了改進后的模型，記為模型P2。

3 模型求解

為檢驗提出模型和不等式的有效性，本章以隨機生成的45個實例來測試上述兩個模型。所有實例測試實驗均在Windows 10，CORE CPU 2.4 GHz，8 GB RAM下用Visual Studio 2010和CPLEX Version 12.6.0進行。

3.1 實例生成

表3 參數生成規則

3.2 結果分析

為驗證原模型P1和改進后的模型P2的求解效果，論文選定45個隨機實例進行實驗計算，其中包括9組不同規模問題，每組問題下生成5個實例。對比實驗采用表4的符號定義來評價模型P1和P2。

表4 對比實驗分析的符號定義

實驗結果如表5，其中，4-8列統計了CPLEX優化求解器在5個實例上運行后各個評價指標的均值，求解時間限制在7 200 s。這里需要注意的是，如果分支規模超出內存容量，計算便會終止。

分析表5中各列數據可以發現：

表5 小規模實例計算結果

1) 實例1，實例2，實例3和實例4表明，CPLEX可以求得包含10個部隊用戶、多至10個階段，和20個部隊用戶、多至3個階段的小規模實例的最優解，平均求解時間在105.32 s以內；

2) CPLEX在求解包含20個部隊用戶和6個階段的實例時，可獲得其中2個實例的最優解，但計算時間較長。隨著實例中部隊用戶數和階段數的增加，CPLEX計算時間的增幅較大；

3) 從包含30個部隊用戶和3個階段的實例7中可以看出，上下界的偏離程度平均達到了35.44%，說明求解此類帶時間窗約束的優化決策問題的復雜度較大；

4) 從LB2列可以看出，在測試實例上，改進后的模型P2提供的下界比起LB1列，平均有所增大，表明引入的不等式在求解此類問題時的有效性。

圖2給出了模型P1與P2提供的下界之間的差值，其中橫坐標x表示實例編號，縱坐標y表示差值，即LB2-LB1。

圖2 測試實例得出的下界差值曲線

從圖2可以看出，在45個測試實例中，有23個實例的最優值無法通過CPLEX獲得，其中有20個實例的差值為正，實例35的差值最大，達到了773。這主要是因為改進后模型的約束更緊，在線性松弛之后的多面體更接近原整數可行解的凸包，使用分支定界法時分枝和剪枝相比初始模型更加有效。綜上，所提出的有效不等式有助于CPLEX優化求解器生成更好的下界。

4 結論

為帶時間窗的裝備維修器材PRP提出了一個MILP模型，并引入3個有效不等式來改進該模型。通過數值仿真實驗發現，CPLEX優化求解器只能求得小規模實例的最優解，且求解的計算時間隨著部隊用戶數目和規劃周期的增加大幅增長，改進后的模型提供的下界比起初始模型平均有所增大，表明引入的不等式在求解此類問題時的有效性。

由于該問題的復雜性，CPLEX求解的計算時間隨著部隊用戶數目和計劃時域的長度的增加大幅增長。實際情況中，問題規模可能更大，需要進一步開發高效的求解算法求解該類問題。