基于Benders分解的煤炭供應(yīng)鏈網(wǎng)絡(luò)維護(hù)調(diào)度優(yōu)化

高吉冰，鄭瀾波

(武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063)

煤炭行業(yè)作為我國國民經(jīng)濟(jì)的重要支柱，每年我國有數(shù)十億噸的煤炭消費(fèi)總量，但大部分煤炭都不是本地直接消費(fèi)的，而是經(jīng)過長途運(yùn)輸才能從生產(chǎn)地到達(dá)使用地，整個(gè)運(yùn)輸過程涉及到煤礦、鐵路、船公司、港口和煤炭用戶等眾多企業(yè)。這些企業(yè)之間相互協(xié)作，構(gòu)成了一個(gè)龐大的煤炭供應(yīng)鏈網(wǎng)絡(luò)。煤炭供應(yīng)鏈網(wǎng)絡(luò)的作業(yè)設(shè)備必須經(jīng)常進(jìn)行預(yù)防性維護(hù)，但傳統(tǒng)的人工調(diào)度方法效率低、可處理時(shí)間區(qū)間有限，已不能滿足當(dāng)下的需求，于是作業(yè)設(shè)備預(yù)防性維護(hù)時(shí)如何更加科學(xué)有效地調(diào)度成為當(dāng)下煤炭供應(yīng)鏈亟需解決的問題。BOLAND等[1]提出的帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問題為解決此問題提供了新的研究方向，首次提出使用網(wǎng)絡(luò)流的理論來解決維護(hù)調(diào)度問題。

目前對設(shè)備維護(hù)的定量研究，主要集中在制造業(yè)生產(chǎn)研究，很少涉及煤炭供應(yīng)鏈。VATN等[2]提出了一種確定生產(chǎn)系統(tǒng)部件最優(yōu)維修計(jì)劃的方法，將安全健康環(huán)境目標(biāo)、維修費(fèi)用和損失生產(chǎn)成本考慮在內(nèi)，對多個(gè)目標(biāo)進(jìn)行了優(yōu)化。葉培釩[3]基于狀態(tài)維修策略研究了針對系統(tǒng)維修的優(yōu)化問題。李有堂等[4]考慮多設(shè)備混聯(lián)系統(tǒng)，提出了一種以作業(yè)計(jì)劃為約束的動(dòng)態(tài)維護(hù)策略模型。SOUSA等[5]提出了一種選擇和確定關(guān)鍵設(shè)備維修任務(wù)的方法，并將該方法應(yīng)用于案例工廠，取得了不錯(cuò)的效果。門峰等[6]為了有效降低汽車質(zhì)保期內(nèi)制造商的維修成本，提出了基于汽車固定使用里程的預(yù)防性維修方法，能有效降低汽車的整體維修成本。

針對煤炭供應(yīng)鏈網(wǎng)絡(luò)設(shè)計(jì)的研究，CONRADIE等[7]研究了煤炭的開采、堆垛和回收的作業(yè)調(diào)度問題，提出的模擬退火算法在求解大規(guī)模實(shí)例問題時(shí)取得了不錯(cuò)的效果。PENG等[8]將原煤的生產(chǎn)、洗選、加工、運(yùn)輸、銷售整合為一個(gè)模型進(jìn)行分析，并將其應(yīng)用于煤礦生產(chǎn)。范志強(qiáng)[9-10]加入新的配煤加工和流量平衡等約束，構(gòu)建了煤炭供應(yīng)鏈網(wǎng)絡(luò)混合整數(shù)規(guī)劃模型，此后又針對復(fù)雜產(chǎn)品需求特性，在以上基礎(chǔ)上規(guī)劃了新的四級煤炭供應(yīng)鏈網(wǎng)絡(luò)模型，并設(shè)計(jì)了遺傳算法進(jìn)行求解。袁旭梅等[11]考慮整個(gè)煤炭供應(yīng)鏈，以煤礦、鐵路裝載點(diǎn)、港口和煤炭消費(fèi)客戶構(gòu)成的海運(yùn)煤炭供應(yīng)鏈為研究對象，提出了考慮港口物流能力的供應(yīng)鏈網(wǎng)絡(luò)優(yōu)化問題。

目前的研究傾向于合理規(guī)劃整個(gè)煤炭供應(yīng)鏈網(wǎng)絡(luò)，并未考慮維護(hù)問題，且相對于普通制造業(yè)供應(yīng)鏈，煤炭行業(yè)供應(yīng)鏈涉及的流通環(huán)節(jié)和相關(guān)企業(yè)多，運(yùn)輸過程復(fù)雜，對整個(gè)煤炭供應(yīng)鏈進(jìn)行優(yōu)化尤其困難，所以制造業(yè)的維護(hù)模型很難適用于煤炭供應(yīng)鏈。因此，BOLAND等針對獵人谷煤炭供應(yīng)鏈網(wǎng)絡(luò)設(shè)計(jì)問題，抽象出帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問題，設(shè)計(jì)了貪婪啟發(fā)式算法對問題進(jìn)行求解。由于該網(wǎng)絡(luò)設(shè)計(jì)問題為NP-hard問題，具有調(diào)度和網(wǎng)絡(luò)流相結(jié)合的特性，因此使用Benders分解求解十分有效。劉茜[12]設(shè)計(jì)了一種基于重復(fù)求解主問題的Benders分解算法(classical benders decomposition,CBD)，研究顯示與Gurobi相比，CBD算法求解此類問題十分有效。PEARCE等[13]則設(shè)計(jì)了一種基于分支定界樹的Benders分解算法(branch and benders cut,B&BC)，發(fā)現(xiàn)與Boland相比，B&BC算法求得最優(yōu)解的算例大幅提升。雖然上述兩位學(xué)者使用了CBD算法和B&BC算法對問題求解，但無論是算法的結(jié)構(gòu)還是終止條件，以及對于求解結(jié)果的處理均存在諸多不同，因此無法進(jìn)行有效比較。B&BC算法作為近幾年才流行起來的Benders分解，其在求解器分支定界過程加入Benders cut的思路為Benders分解提供了一種新的研究方向。目前國內(nèi)外很少有文獻(xiàn)針對CBD算法和B&BC算法的求解優(yōu)劣進(jìn)行對比，因此從煤炭供應(yīng)鏈網(wǎng)絡(luò)維護(hù)調(diào)度的角度探討兩種算法各自適合應(yīng)用的工業(yè)問題規(guī)模是很有必要的。

筆者從整個(gè)煤炭供應(yīng)鏈設(shè)備維護(hù)的運(yùn)營角度出發(fā)，描述帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問題的構(gòu)建過程，基于問題特殊的網(wǎng)絡(luò)流和調(diào)度特征，分別設(shè)計(jì)CBD和B&BC兩種Benders分解算法，并針對這兩種算法在不同規(guī)模算例下的求解效率進(jìn)行對比分析。其中，對于B&BC算法，從子問題和主問題兩個(gè)方向，分別使用預(yù)流推進(jìn)算法、加入有效不等式的方式對算法進(jìn)行了改進(jìn)，以使得問題的求解效率得到提升。

1 問題描述及模型

1.1 問題描述

煤炭在礦山被開采出來經(jīng)過鐵路的運(yùn)輸?shù)竭_(dá)港口，在港口經(jīng)過翻車機(jī)、堆料機(jī)、取料機(jī)、裝船機(jī)等輪番作業(yè)后到達(dá)船舶。無論鐵路還是港口，都對應(yīng)著多條煤炭運(yùn)輸線路，這些線路互相連接形成了一個(gè)龐大的煤炭供應(yīng)鏈網(wǎng)絡(luò)，如圖1所示。其中，有向箭頭表示煤炭在鐵路和港口各設(shè)備間的流動(dòng)方向。每個(gè)設(shè)備都有固定的單位時(shí)間處理能力，且設(shè)備都要定期進(jìn)行預(yù)防性維護(hù)。對于每一個(gè)維護(hù)工作，都存在最早開始時(shí)間、最遲截止時(shí)間和處理時(shí)間，且維護(hù)工作一旦開始就必須完成。因此當(dāng)同時(shí)出現(xiàn)多個(gè)維護(hù)工作時(shí)，合理調(diào)度這些維護(hù)工作對于保障整個(gè)網(wǎng)絡(luò)的高效運(yùn)行就變得至關(guān)重要。

圖1 煤炭供應(yīng)鏈網(wǎng)絡(luò)

由于煤炭供應(yīng)鏈網(wǎng)絡(luò)具有環(huán)節(jié)多、結(jié)構(gòu)復(fù)雜、動(dòng)態(tài)變化的特點(diǎn)，普通的數(shù)學(xué)模型難以精確描述整個(gè)問題，而網(wǎng)絡(luò)流模型具有靈活、可擴(kuò)展性強(qiáng)的特性，非常適合刻畫煤炭供應(yīng)鏈網(wǎng)絡(luò)。建模時(shí)，鐵路網(wǎng)和碼頭裝卸、運(yùn)輸設(shè)備網(wǎng)的組合被表示為一個(gè)數(shù)學(xué)網(wǎng)絡(luò)G=(V,A)，煤炭則被表示為流經(jīng)網(wǎng)絡(luò)中弧的流，每條弧對應(yīng)一定的容量，表示設(shè)備單位時(shí)間的處理能力。在這個(gè)網(wǎng)絡(luò)中，如果設(shè)備停止運(yùn)行進(jìn)行維護(hù)工作，則代表弧中斷即容量為零，此時(shí)煤炭無法流經(jīng)此弧。

1.2 參數(shù)設(shè)置

定義網(wǎng)絡(luò)G=(V,A)，V為網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，s為源點(diǎn)，s′為匯點(diǎn)，A為網(wǎng)絡(luò)中弧的集合；離散時(shí)間變量t∈[T]={1,2,…,T}，[k,l]={k,k+1,…,l}；Ca為每一條弧a∈A對應(yīng)的容量；δ+(v)為流出每一個(gè)節(jié)點(diǎn)v∈V的弧集；δ-(v)為流入每一個(gè)節(jié)點(diǎn)v∈V的弧集；J為所有維護(hù)工作的集合；Ja為弧a上維護(hù)工作的集合；pj∈Ν為每一個(gè)維護(hù)工作j∈J的處理時(shí)間；rj∈[T]為每一個(gè)維護(hù)工作j∈J的最早開始時(shí)間；dj∈[T]為每一個(gè)維護(hù)工作j∈J的最遲截止時(shí)間；若給定一個(gè)調(diào)度計(jì)劃，弧a維護(hù)工作開始時(shí)間為sj(j∈Ja)，那么弧a在t∈[sj,sj+pj-1]內(nèi)流量為0。

1.3 數(shù)學(xué)模型

(1)決策變量：φat∈R+表示時(shí)間t上流經(jīng)弧a的流量,a∈A,t∈[T]；xat={0,1}，若時(shí)間t上弧a是連通的，則xat的取值為1，否則為0；yjt={0,1}，若維護(hù)工作在j時(shí)間開始，則yjt的取值為1，否則為0,j∈J,t∈[rj,dj-pj+1]。

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

(1)

s.t.

∑dj-pj+1t=rjyjt=1，j∈J

(4)

(5)

目標(biāo)函數(shù)式(1)表示最大化時(shí)間T內(nèi)整個(gè)網(wǎng)絡(luò)的流量；約束條件式(2)保證了每一個(gè)節(jié)點(diǎn)的流量守恒；約束條件式(3)確保每一條弧的流量都不超過弧的容量；約束條件式(4)要求每項(xiàng)維護(hù)工作在規(guī)定時(shí)間窗內(nèi)被維護(hù)一次；約束條件式(5)保證了當(dāng)維護(hù)工作在時(shí)間t進(jìn)行時(shí)，弧a是中斷的，且弧上的流量為0。

式(2)和式(3)組成了一個(gè)網(wǎng)絡(luò)最大流問題，準(zhǔn)確描述了整個(gè)煤炭供應(yīng)鏈網(wǎng)絡(luò)的結(jié)構(gòu)；式(4)和式(5)描述了一個(gè)調(diào)度問題，將決定維護(hù)工作所有的計(jì)劃方案。兩個(gè)問題通過弧中斷變量xat連接，即調(diào)度問題將維護(hù)計(jì)劃通過xat傳遞給網(wǎng)絡(luò)最大流問題完成整個(gè)問題的求解。

2 Benders分解算法設(shè)計(jì)

2.1 Benders模型分解設(shè)計(jì)

(6)

2.2 CBD與B&BC算法設(shè)計(jì)

與CBD重復(fù)求解主問題不同，B&BC算法只需求解一次主問題，利用求解器的callback函數(shù)在分支定界框架下對其中可行的分支節(jié)點(diǎn)進(jìn)行探索，從而產(chǎn)生Benders cut。在B&BC算法中，Benders cut是以松弛約束的形式加入模型，這種約束的優(yōu)點(diǎn)是只有當(dāng)這種約束被違反時(shí)才會(huì)被加入模型，但是這種約束會(huì)使得模型在一開始的預(yù)求解階段對于模型的縮減變得十分小心。

2.3 融合預(yù)流推進(jìn)算法

由于Benders分解算法的求解效率主要受到主問題和子問題求解效率的影響，因此針對主問題和子問題特殊的結(jié)構(gòu)進(jìn)行改進(jìn)是加快求解的一種有效方式。帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問題的子問題是一個(gè)網(wǎng)絡(luò)流問題，傳統(tǒng)的Gurobi建模默認(rèn)使用單純形法對子問題進(jìn)行求解，并未有效利用子問題的結(jié)構(gòu)。

2.4 加入有效不等式

雖然改進(jìn)子問題的求解算法在理論上能加快問題的求解速度，但是經(jīng)過研究證實(shí)，主問題在整個(gè)求解過程占時(shí)能夠達(dá)到90%,甚至更多。因此,從優(yōu)化的角度來看，改進(jìn)主問題的求解將是提升求解效率的一個(gè)更加有效的方法。

由于經(jīng)過映射和松弛以后，主問題已經(jīng)沒有子問題的相關(guān)信息，因此在搜索過程中將會(huì)產(chǎn)生不穩(wěn)定的邊界和很多無效的分支，解決這個(gè)問題的有效方法是在主問題中加入有效不等式，即縮小主問題的上界。文獻(xiàn)[13]采用主問題的線性松弛產(chǎn)生多組有效不等式，但這種方式不能保證cut的有效性，還使得問題的求解規(guī)模變大，改進(jìn)效果并不明顯。為了保證問題的規(guī)模盡可能小和加入的不等式盡可能有效，設(shè)計(jì)基于加入有效不等式的B&BC，即LR-B&BC，選取含有子問題信息的整個(gè)MIP問題的松弛解生成一組有效不等式并加入到主問題中，由于整個(gè)MIP問題的松弛解含有更多子問題的信息，因此，與主問題的線性松弛相比，其生成的不等式更有效。

3 算例實(shí)驗(yàn)分析

3.1 算例測試集

基于文獻(xiàn)[1]的算例集對所設(shè)計(jì)的算法進(jìn)行測試，算例集包含兩個(gè)部分：網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)和與每個(gè)網(wǎng)絡(luò)對應(yīng)的維護(hù)工作數(shù)據(jù)，算例集對應(yīng)的時(shí)間范圍為T=1 000。根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量、弧數(shù)量、平均作業(yè)數(shù)量，網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)可以分為8個(gè)不同規(guī)模的網(wǎng)絡(luò)，其中1，2，3，4為小網(wǎng)絡(luò)，5，6，7，8為大網(wǎng)絡(luò)。

維護(hù)工作數(shù)據(jù)設(shè)置了兩個(gè)時(shí)間窗區(qū)間，分別為小規(guī)模的[1,35]和大規(guī)模的[25,35]，即維護(hù)作業(yè)時(shí)間窗分別在兩個(gè)區(qū)間隨意選擇，每個(gè)網(wǎng)絡(luò)根據(jù)[1,35]對應(yīng)產(chǎn)生10個(gè)小規(guī)模算例，根據(jù)[25,35]對應(yīng)產(chǎn)生10個(gè)大規(guī)模算例，其中8個(gè)網(wǎng)絡(luò)對應(yīng)的80個(gè)小規(guī)模算例稱為算例集1，8個(gè)網(wǎng)絡(luò)對應(yīng)的80個(gè)大規(guī)模算例稱為算例集2，共計(jì)160個(gè)算例。

3.2 算法性能對比

實(shí)驗(yàn)設(shè)定單個(gè)算例最大運(yùn)行時(shí)間為1 800 s，單個(gè)算例的運(yùn)行停止條件為Abs(gap)=0.999，即主問題上下界的差值為0.999，此時(shí)算例求得最優(yōu)解。實(shí)驗(yàn)程序以Python 3.6作為編程語言，Gurobi 8.0為模型求解工具，處理器為Intel Core i7-4710MQ，內(nèi)存為4GB，操作系統(tǒng)為Windows 10 Professional(64-bit)。兩個(gè)算例集在1 800 s內(nèi)小于gap的解的比例分別如圖2和圖3所示，兩個(gè)算例集在1 800 s內(nèi)的詳細(xì)運(yùn)行結(jié)果分別如表1和表2所示。

表2 算例集2在1 800 s內(nèi)的運(yùn)行結(jié)果

圖2 算例集1在1 800 s內(nèi)小于gap的解的比例

圖3 算例集2在1 800 s內(nèi)小于gap的解的比例

(1)比較CBD算法與B&BC算法。由圖2可知，對于算例集1的小規(guī)模算例，其求解相對容易，B&BC算法與CBD算法均取得了不錯(cuò)的求解結(jié)果，兩種算法對于小網(wǎng)絡(luò)1、2、3均求得最優(yōu)解，且平均解時(shí)間大致相同，最優(yōu)解求取比例均超過60%。但從表1可以看到，在最難求解的網(wǎng)絡(luò)5中，B&BC算法的平均gap為0.145%，遠(yuǎn)小于CBD算法的1.803%。在所有80個(gè)算例中，CBD算法的最大gap的最大值為6.263%，B&BC算法的最大gap的最大值僅為0.222%，但在第4個(gè)網(wǎng)絡(luò)上CBD算法求得的最優(yōu)解個(gè)數(shù)比B&BC算法多2個(gè)。對于算例集2中的大規(guī)模算例，B&BC算法所有算例求得最優(yōu)解的比例為35%，高于CBD算法的26%。B&BC算法的求解優(yōu)勢明顯，8個(gè)網(wǎng)絡(luò)的平均gap的最大值為1.584%，小于CBD算法的18.319%。

表1 算例集1在1 800 s內(nèi)的運(yùn)行結(jié)果

(2)比較B&BC算法與Pre-B&BC算法。相比于B&BC算法，Pre-B&BC算法在求解算例集1的小網(wǎng)絡(luò)1、2、3時(shí)，3個(gè)網(wǎng)絡(luò)的總體平均解時(shí)間比B&BC算法減少了48%；對于算例集2中的網(wǎng)絡(luò)1、3，Pre-B&BC算法的平均解時(shí)間比B&BC算法分別減少56%和70%。此外，Pre-B&BC算法所有算例的最大gap的最大值為3.104%，較B&BC算法的4.046%下降了23.3%，在算例集2中最難求解的第6個(gè)網(wǎng)絡(luò)，平均gap由B&BC算法的1.584%下降到Pre-B&BC算法的1.207%。

(3)比較B&BC算法與LR-B&BC算法。相比于B&BC算法，LR-B&BC算法在求解小網(wǎng)絡(luò)時(shí)表現(xiàn)出非常大的優(yōu)勢，求解時(shí)間明顯降低。LR-B&BC算法最大的優(yōu)勢在于求解算例集2的大規(guī)模網(wǎng)絡(luò), 對算例集2的網(wǎng)絡(luò)5和網(wǎng)絡(luò)7分別求出一個(gè)最優(yōu)解，實(shí)現(xiàn)最優(yōu)解求取數(shù)量為零的突破。同樣對于算例集2中最難求解的網(wǎng)絡(luò)6，最大gap由B&BC算法的4.046%下降到LR-B&BC算法的1.808%，解的收斂效果提升了59%。

綜上所述，整體上B&BC算法比CBD算法在求解結(jié)果和求解速度上表現(xiàn)得更好。但是根據(jù)算例規(guī)模的不同，B&BC算法與CBD算法的求解效果表現(xiàn)出較大的差異，對于小規(guī)模算例，此時(shí)主問題的規(guī)模也相對較小，兩者求解差距很小，甚至CBD算法有時(shí)會(huì)求出更多的最優(yōu)解。但是當(dāng)主問題規(guī)模較大時(shí)，B&BC算法的求解優(yōu)勢則更加明顯。此外，相對于B&BC算法，LR-B&BC算法、Pre-B&BC算法在解的收斂速度方面均有一定提升，Pre-B&BC算法在求解小規(guī)模網(wǎng)絡(luò)時(shí)，求解時(shí)間的提升尤其明顯，LR-B&BC算法則在求解大規(guī)模問題上表現(xiàn)出顯著的求解優(yōu)勢。

4 結(jié)論

針對煤炭供應(yīng)鏈網(wǎng)絡(luò)設(shè)備維護(hù)調(diào)度問題，考慮其特殊的網(wǎng)絡(luò)流與調(diào)度相結(jié)合的結(jié)構(gòu)，設(shè)計(jì)了CBD、B&BC兩種Benders分解算法。通過算例求解發(fā)現(xiàn)B&BC算法在總體上表現(xiàn)出更好的求解效果?；谶@一研究結(jié)果，在原有B&BC算法基礎(chǔ)上，使用預(yù)流推進(jìn)算法對子問題的求解進(jìn)行改進(jìn)，重點(diǎn)針對主問題的求解設(shè)計(jì)了一種改進(jìn)方案即加入一組有效不等式。最終通過算例實(shí)驗(yàn)分析，得到以下結(jié)論：

(1)通過具體分析160個(gè)算例的求解數(shù)據(jù)，認(rèn)為在煤炭供應(yīng)鏈的實(shí)際工業(yè)應(yīng)用中，CBD算法可能更適合求解子問題相對規(guī)模較大的網(wǎng)絡(luò)，而B&BC算法更適合求解主問題規(guī)模較大的網(wǎng)絡(luò)，即維護(hù)調(diào)度情況更為復(fù)雜的網(wǎng)絡(luò)，因此建議根據(jù)調(diào)度問題規(guī)模選擇合適的算法。

(2)使用預(yù)流推進(jìn)算法對子問題的求解進(jìn)行改進(jìn)，發(fā)現(xiàn)其更適合加速小規(guī)模網(wǎng)絡(luò)的求解，對大規(guī)模網(wǎng)絡(luò)提升較有限。

(3)通過加速主問題的求解，即加入一組有效不等式，發(fā)現(xiàn)此改進(jìn)適合加速大規(guī)模問題的求解，在求解時(shí)間充足且希望獲得最優(yōu)解的情形下能取得很好的效果。

但是，由于B&BC算法在Benders分解過程中加入了過多的Benders cut，主問題的規(guī)模變得越來越大，導(dǎo)致解的收斂性逐漸變慢。因此在未來的研究中，可以考慮針對加入的Benders cut設(shè)計(jì)有效的篩選方案，以達(dá)到更高的求解效率。此外，B&BC主問題的分支與節(jié)點(diǎn)選擇策略、解生成策略的智能化研究略有不足，使用機(jī)器學(xué)習(xí)算法對主問題的求解過程進(jìn)行有效干預(yù)也會(huì)成為未來研究的重點(diǎn)。