基于Benders 分解的煤炭供應(yīng)鏈設(shè)備維護(hù)計(jì)劃決策

劉 茜，鄭瀾波

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

1 引言

我國(guó)是世界上最大的煤炭生產(chǎn)與消費(fèi)國(guó)，由于煤炭生產(chǎn)與消費(fèi)地理的不平衡，煤炭行業(yè)形成了煤炭生產(chǎn)、輸送、消費(fèi)的供應(yīng)鏈，煤炭供應(yīng)鏈的可持續(xù)發(fā)展對(duì)國(guó)民經(jīng)濟(jì)具有重大影響，而煤炭行業(yè)的均衡、穩(wěn)健發(fā)展依賴于設(shè)備的安全、可靠運(yùn)轉(zhuǎn)。隨著設(shè)備向大型化、專業(yè)化及自動(dòng)化方向發(fā)展，設(shè)備的維護(hù)管理問題日益突出。當(dāng)前煤炭行業(yè)內(nèi)的企業(yè)各自獨(dú)立的由經(jīng)驗(yàn)豐富的維修工人根據(jù)生產(chǎn)計(jì)劃制定維護(hù)計(jì)劃，這種分散的維護(hù)計(jì)劃使得供應(yīng)鏈上各企業(yè)的生產(chǎn)運(yùn)作不均衡，造成了供應(yīng)鏈整體效率較大的損失。

工業(yè)領(lǐng)域和學(xué)術(shù)界針對(duì)設(shè)備維護(hù)管理展開了研究。國(guó)內(nèi)對(duì)煤炭行業(yè)設(shè)備維護(hù)的研究主要集中在：（1）設(shè)備管理制度和管理信息系統(tǒng)的探討；（2）狀態(tài)監(jiān)測(cè)和故障診斷技術(shù)[1]。陳文靜[2]、劉藝杰[3]介紹了維修管理理論，自修、外包等維修組織形式，指出現(xiàn)有設(shè)備維修體制存在的缺陷、維修決策水平不足、設(shè)備維護(hù)信息系統(tǒng)不完善等問題，并提出基于可靠性理論的設(shè)備預(yù)防性維護(hù)策略。范體軍[4]提出設(shè)備維護(hù)外包的三種外包策略，并分析了不同策略對(duì)設(shè)備維護(hù)計(jì)劃組織的影響。設(shè)備維護(hù)計(jì)劃的決策研究已有部分成果。崔維偉[5]考慮生產(chǎn)與設(shè)備維護(hù)的集成調(diào)度問題，認(rèn)為工件生產(chǎn)與設(shè)備維護(hù)相互關(guān)聯(lián)、共同影響車間的生產(chǎn)效率，構(gòu)建了以工件流程時(shí)間最短、維修成本最小的多目標(biāo)模型，并設(shè)計(jì)出一種改進(jìn)的遺傳算法進(jìn)行求解，實(shí)現(xiàn)了車間生產(chǎn)調(diào)度與設(shè)備維護(hù)計(jì)劃的有效協(xié)調(diào)。然而上述研究沒有考慮維修設(shè)備的關(guān)聯(lián)性，對(duì)此，王紅等人[6]提出故障鏈的概念對(duì)維修部件間的關(guān)系進(jìn)行描述，建立了具有故障相關(guān)關(guān)系的復(fù)雜機(jī)械系統(tǒng)中各部件的可靠度模型。當(dāng)前國(guó)內(nèi)對(duì)煤炭行業(yè)的設(shè)備維護(hù)管理的研究還停留在維護(hù)管理模式及組織形式的探討上，少數(shù)關(guān)于維護(hù)計(jì)劃的決策研究對(duì)象或者局限于系統(tǒng)的一部分，或者沒有考慮預(yù)防性維護(hù)的動(dòng)態(tài)性，沒有成果刻畫制定的設(shè)備維護(hù)計(jì)劃對(duì)持續(xù)生產(chǎn)的影響，更沒有研究煤炭供應(yīng)鏈上多個(gè)企業(yè)從宏觀層面結(jié)成維護(hù)的戰(zhàn)略聯(lián)盟，協(xié)同制定預(yù)防性維護(hù)計(jì)劃以降低維護(hù)中斷對(duì)持續(xù)生產(chǎn)系統(tǒng)造成的影響的成果。本文從設(shè)備維護(hù)計(jì)劃對(duì)降低煤炭供應(yīng)鏈吞吐量影響的角度展開研究，揭示其中規(guī)律，為系統(tǒng)設(shè)備維護(hù)規(guī)劃與管理提供科學(xué)決策。

獵人谷煤炭供應(yīng)鏈協(xié)調(diào)機(jī)構(gòu)數(shù)據(jù)顯示，設(shè)備年度停機(jī)維護(hù)造成的系統(tǒng)中斷會(huì)導(dǎo)致年吞吐量約15%的損失。獵人谷煤炭供應(yīng)鏈協(xié)調(diào)機(jī)構(gòu)協(xié)調(diào)供應(yīng)鏈中各環(huán)節(jié)設(shè)備的維護(hù)窗口，分配容量，以使得計(jì)劃期內(nèi)因維護(hù)造成的吞吐量損失最少。Natashia Boland等人[7]利用“帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流（簡(jiǎn)稱MaxTFFAO）”模型來(lái)研究煤炭供應(yīng)鏈中設(shè)備維護(hù)的計(jì)劃，清晰地闡明了帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問題的結(jié)構(gòu)特點(diǎn)。由于該問題的強(qiáng)NP難性，已有的多數(shù)方法均為啟發(fā)式算法。Benders分解算法（以下簡(jiǎn)稱BD算法）是一種運(yùn)用分解思想求解混合變量規(guī)劃問題的巧妙方法[9]，將原問題分解為主問題（Master Problem，簡(jiǎn)稱MP）和子問題（Sub-problem，簡(jiǎn)稱SP），它適用于MaxTFFAO問題的求解，實(shí)驗(yàn)證明了BD算法的可行性和有效性。

2 問題概述

2.1 動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)及最大流

圖1表示一個(gè)煤炭供應(yīng)鏈網(wǎng)絡(luò)G=(V,A,C)，左側(cè)為鐵路網(wǎng)絡(luò)，右側(cè)橢圓內(nèi)為煤碼頭作業(yè)網(wǎng)絡(luò)。左側(cè)圓圈表示裝煤點(diǎn)，方框表示煤炭匯集的鐵路站點(diǎn)。碼頭中的大圓圈表示堆場(chǎng)。A為有向弧集，表示煤炭在設(shè)施設(shè)備間的流動(dòng)軌跡：煤炭裝載流、鐵路輸送流以及傾貨、堆料、取料、裝船和離泊作業(yè)流。煤炭需求量、鐵路運(yùn)煤能力、碼頭機(jī)械設(shè)備的工作能力分別表示相應(yīng)弧的容量C。煤礦裝煤中斷、鐵路因維護(hù)而中斷、煤碼頭中機(jī)械設(shè)備停機(jī)維護(hù)都會(huì)使得煤炭供應(yīng)網(wǎng)絡(luò)的弧斷開，弧容量降為零，造成該段時(shí)間內(nèi)網(wǎng)絡(luò)煤吞吐量減少；而維護(hù)結(jié)束后，弧容量恢復(fù)，即網(wǎng)絡(luò)中弧的容量隨維護(hù)的實(shí)施而變動(dòng)。選擇碼頭一段時(shí)期內(nèi)輸出煤炭量這一指標(biāo)來(lái)評(píng)估供應(yīng)鏈的效率，可見獵人谷煤炭供應(yīng)鏈優(yōu)化問題本質(zhì)上是一個(gè)帶邊中斷的動(dòng)態(tài)網(wǎng)絡(luò)最大流問題。

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

2.2 設(shè)施設(shè)備維護(hù)調(diào)度

煤炭供應(yīng)鏈設(shè)備的預(yù)防性維護(hù)都有一個(gè)維護(hù)時(shí)間窗，調(diào)度維護(hù)工作的計(jì)劃表會(huì)對(duì)計(jì)劃期內(nèi)網(wǎng)絡(luò)總輸出流量產(chǎn)生不同的影響。待維修設(shè)備的故障相關(guān)關(guān)系使得其預(yù)防性維護(hù)計(jì)劃必須協(xié)調(diào)起來(lái)制定。因此，煤炭供應(yīng)鏈設(shè)備維護(hù)調(diào)度問題可抽象為帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流問題，它研究如何調(diào)度容量網(wǎng)絡(luò)邊的中斷時(shí)刻，動(dòng)態(tài)性地分配容量，以最大化計(jì)劃期內(nèi)網(wǎng)絡(luò)的總吞吐量。

3 模型構(gòu)建及求解

3.1 參數(shù)及變量定義

定義[m,n]={m,m+1,...,n}，[m]={1,2,...,m}，m,n∈Z+。G=(V,A,s,s',C)表示一個(gè)網(wǎng)絡(luò)，其中[V]為節(jié)點(diǎn)集合，[A]為網(wǎng)絡(luò)中弧的集合，s為源點(diǎn)，s'為匯點(diǎn)，[C]為弧容量集合，Ca表示弧a的容量。節(jié)點(diǎn)v∈[V]，δ-(V)和δ+(V)分別表示進(jìn)出節(jié)點(diǎn)v的弧集。設(shè)置網(wǎng)絡(luò)總時(shí)間跨度為T。

網(wǎng)絡(luò)G中散布著一系列維護(hù)作業(yè)j∈[J]，其中[J]為作業(yè)集，作業(yè)j∈[J]有一系列屬性：處理時(shí)間pj∈[T]，最早開始維護(hù)時(shí)間rj∈[T]，最遲維護(hù)截止時(shí)間dj∈[T]，作業(yè)一旦開始就不能提前終止，在其處理時(shí)間段內(nèi)，與作業(yè)j相關(guān)聯(lián)的弧aj上通過(guò)的流量為零。[Ja]是弧a上作業(yè)集合，假設(shè)a上任意兩作業(yè)的時(shí)間窗不重合。作業(yè)j∈[J]，維護(hù)開始時(shí)間，sj∈[rj,dj-pj+1]其中[rj,dj-pj+1]稱為該作業(yè)的維護(hù)時(shí)間窗，當(dāng)j∈[Ja]，t∈[sj,sj-pj+1]時(shí)，弧a的容量在t時(shí)刻為零，即當(dāng)弧a上有作業(yè)在處理時(shí)，弧a斷開，途徑a的流量為零。

設(shè)置變量：φat為時(shí)間t內(nèi)流經(jīng)a的流量；xat∈{0,1}表示a是否在時(shí)間t內(nèi)中斷，中斷為0，否則為1；yjt∈{0,1},j∈[J]表示作業(yè)j是否開始于時(shí)間t，是則為1，否則為0。

3.2 建立數(shù)學(xué)模型

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

約束條件：

目標(biāo)（1）最大化時(shí)間跨度內(nèi)總流量。約束條件（2）和（3）是流量守恒和容量限制約束，（4）要求每一項(xiàng)設(shè)備維護(hù)作業(yè)j在其時(shí)間窗內(nèi)恰好被完成一次，（5）確保當(dāng)維護(hù)作業(yè)j正在處理中時(shí)，路徑弧a容量為零，（6）是非負(fù)約束和0-1約束。

4 BD算法

4.1 BD轉(zhuǎn)化模型

將變量xat與φat分離到兩個(gè)問題中，分別構(gòu)成具有調(diào)度元素的MP與最大流SP。又因?yàn)槿我粫r(shí)刻網(wǎng)絡(luò)最大流僅與該時(shí)刻網(wǎng)絡(luò)各邊的中斷情況xat有關(guān)，因此可以將一段時(shí)間內(nèi)的動(dòng)態(tài)最大流分解為該時(shí)間段內(nèi)每一時(shí)刻靜態(tài)最大流的和，分解后的這類單位時(shí)刻靜態(tài)最大流問題，可以利用線性規(guī)劃求解器快速求解，這種分解的BD算法能有效提高模型求解效率。

給定xat,t∈[T]的一個(gè)可行解為xat，則對(duì)?t∈[T]，SP的模型為：

S.t.

式（11）是加入到MP模型中的割平面。因此以單位時(shí)間t劃分后的MP模型如下：

S.t.

4.2 求解步驟

BD算法的求解步驟如下：

Step1：初始化。G=(V,A,s,s',C)，總時(shí)間跨度T，=+∞,=-∞,ε =0.09% ；

Step2：創(chuàng)建空Python字典Y，構(gòu)建SP和MP的模型；

Step3：初始化 xat=1,?a∈[A],?t∈[T]，求解SP得到最優(yōu)解x0、容量約束的對(duì)偶變量(ua|a∈[A])，將 xat作為字典Y的鍵，值為(x0,ua|a∈[A])，在MP中增加約束 θt≤x0,?t∈[T]；

Step4：求解 MP，得新的當(dāng)前解值、θt及 yjt，；若，轉(zhuǎn)Step5，否則轉(zhuǎn)Step7；

Step5：檢索 xat',t'∈[T]，如果 xat'是Y的鍵，取Y中xat'鍵對(duì)應(yīng)的值(x0,ua|a∈[A]) ，否則，求解SP，將結(jié)果置于Y中；

Step6：如果 θt'≥x0,?t'∈[T]，在MP中增加約束θt'≤∑a∈[A]Caxat'uat'(?t'∈[T]) ；否 則 t'←t'+1 ；若t'=T ，則，轉(zhuǎn)Step4，否則，轉(zhuǎn)Step5；

Step7：算法終止，輸出最優(yōu)解。

5 算例分析

通過(guò)數(shù)據(jù)實(shí)驗(yàn)對(duì)所設(shè)計(jì)的BD算法的求解效果進(jìn)行分析評(píng)價(jià)。計(jì)算實(shí)驗(yàn)的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)來(lái)源于文獻(xiàn)[7]，包括8個(gè)規(guī)模不一的網(wǎng)絡(luò)結(jié)構(gòu)、2組可選的維護(hù)時(shí)間窗口大小不同的數(shù)據(jù)集，每組數(shù)據(jù)集中，對(duì)應(yīng)每一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)都有10個(gè)單獨(dú)的實(shí)例，那么總共運(yùn)行的數(shù)據(jù)實(shí)例有160個(gè)。通過(guò)比較BD算法及Gurobi求解器在1 800s內(nèi)給出實(shí)例的結(jié)果來(lái)分析算法的優(yōu)劣。采用Python2.7語(yǔ)言編程，Gurobi6.5建立模型，在Intel Core i7處理器（2.5GHz）、12GB內(nèi)存的計(jì)算機(jī)上測(cè)試。通過(guò)分析BD算法上、下界的gap，運(yùn)行時(shí)間以及算例能被求得最優(yōu)的個(gè)數(shù)等指標(biāo)，分析三種方法的特點(diǎn)，實(shí)驗(yàn)結(jié)果見表1、表2。

表1 數(shù)據(jù)集1運(yùn)行1 800s的結(jié)果數(shù)據(jù)

表2 數(shù)據(jù)集2運(yùn)行1 800s的結(jié)果數(shù)據(jù)

觀察以上兩組實(shí)驗(yàn)結(jié)果數(shù)據(jù)，得到如下結(jié)論：

（1）通過(guò)比較兩種算法能求解出實(shí)例的平均個(gè)數(shù)，可知分解算法的求解效率顯著高于Gurobi求解器的效率，尤其是在數(shù)據(jù)集合1中，BD算法得到的最優(yōu)解的個(gè)數(shù)在多數(shù)網(wǎng)絡(luò)中更加突出。

（2）在平均gap方面，BD算法與Gurobi求解的結(jié)果相差不大，但是在數(shù)據(jù)集合1中，BD算法表現(xiàn)更好，時(shí)間上，在大多數(shù)算例中，BD算法消耗的時(shí)間成本也較Gurobi更好。結(jié)果表明使用Benders分解，將原始模型分割成主問題和子問題的求解技術(shù)性能更好。

6 實(shí)際案例分析

當(dāng)前，國(guó)內(nèi)煤炭行業(yè)水平方向企業(yè)之間的競(jìng)爭(zhēng)仍然是投資、資源體量之間的競(jìng)爭(zhēng)。煤礦資源被進(jìn)一步開發(fā)，鐵路、煤碼頭吞吐量的設(shè)計(jì)呈井噴增長(zhǎng)趨勢(shì)，這些粗放的資源開發(fā)與利用行為造成了嚴(yán)重的產(chǎn)能過(guò)剩和資源浪費(fèi)，煤炭行業(yè)急需精細(xì)的資源管理來(lái)提高效率，降低浪費(fèi)。

一般的，設(shè)備維護(hù)資源主要是維護(hù)工人、維護(hù)器具等，維護(hù)資源過(guò)少會(huì)引起維修不及時(shí)，而維護(hù)資源過(guò)多，又增加企業(yè)的成本。上文的MaxTFFAO模型假設(shè)，任意時(shí)刻都有足夠的維護(hù)資源對(duì)設(shè)備進(jìn)行維護(hù)，即同一時(shí)刻處于維護(hù)狀態(tài)的設(shè)備數(shù)量不受資源限制，這就需要企業(yè)具備足夠的維護(hù)資源。當(dāng)資源閑置時(shí)，產(chǎn)生浪費(fèi)。假設(shè)G中每條邊上散布著數(shù)量不等的待維護(hù)作業(yè)，且每條邊上待維護(hù)作業(yè)的時(shí)間窗不重疊，考慮帶資源約束的煤炭供應(yīng)鏈設(shè)備維護(hù)計(jì)劃決策，在MaxTFFAO模型中添加資源約束（17）。

|A|表示G中弧的總數(shù)，K是維護(hù)資源總數(shù)。

煤炭供應(yīng)鏈上各環(huán)節(jié)的設(shè)備維護(hù)資源類型不同，各環(huán)節(jié)的維護(hù)資源僅僅維護(hù)自身環(huán)節(jié)的設(shè)備，如鐵軌維修工人檢修列車軌道，不會(huì)維修碼頭的堆料機(jī)，因此煤炭供應(yīng)鏈上各環(huán)節(jié)維護(hù)資源的數(shù)量需要分開進(jìn)行決策。考慮多資源約束，對(duì)MaxTFFAO模型進(jìn)行修正：

其中|Ai|表示G中第i環(huán)節(jié)邊的數(shù)量，Ki為第i環(huán)節(jié)的維護(hù)資源數(shù)量，i=[q]則表示G中的某一個(gè)環(huán)節(jié)，整個(gè)供應(yīng)鏈分為q個(gè)環(huán)節(jié)。上述兩個(gè)模型分別對(duì)應(yīng)于單資源約束與多資源約束的情形。在資源不受限情形下，由MaxTFFAO模型計(jì)算網(wǎng)絡(luò)最大流及最大資源需求量K。隨后，在修正后的模型中，逐漸減少K值，網(wǎng)絡(luò)最大流保持不變，直到K=K1時(shí)，網(wǎng)絡(luò)最大流開始減少；當(dāng)K繼續(xù)減少到某一臨界值時(shí)，修正模型無(wú)可行解，此時(shí)可推算出最小資源數(shù)K2。修正后的模型可找到保持最大流不變情形下的最少資源需求量K1、設(shè)備維護(hù)作業(yè)能及時(shí)被處理的最少資源需求量K2以及煤炭供應(yīng)鏈設(shè)備維護(hù)計(jì)劃表。同理，可求出帶約束（18）模型的最少資源需求量組合及設(shè)備維護(hù)計(jì)劃表。

表3 單資源約束下數(shù)據(jù)集1網(wǎng)絡(luò)1的資源與最大流

表4 多資源約束下數(shù)據(jù)集1網(wǎng)絡(luò)1的資源組合與最大流

表3、4給出了文獻(xiàn)[7]中數(shù)據(jù)集合1對(duì)應(yīng)于10組不同維護(hù)作業(yè)下的網(wǎng)絡(luò)1在資源受限情形下的網(wǎng)絡(luò)最大流，可見對(duì)于每組維護(hù)作業(yè)，網(wǎng)絡(luò)1都有一個(gè)最小的維護(hù)資源量，使得計(jì)劃期內(nèi)的網(wǎng)絡(luò)最大流達(dá)到最大，同時(shí)也有最小的維護(hù)資源量數(shù)使得維護(hù)作業(yè)能及時(shí)得到處理。

7 結(jié)論與展望

本文針對(duì)煤炭供應(yīng)鏈中設(shè)備維護(hù)計(jì)劃問題，研究了帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流模型及其算法，取得了以下成果：（1）從供應(yīng)鏈管理的角度，對(duì)設(shè)備維護(hù)管理展開研究，建模并設(shè)計(jì)算法求解，對(duì)實(shí)際煤炭供應(yīng)鏈中設(shè)備維護(hù)作業(yè)計(jì)劃的調(diào)度問題有一定的指導(dǎo)意義；（2）詳述了BD算法，設(shè)計(jì)了該算法解決該問題及模型的具體步驟；（3）實(shí)驗(yàn)結(jié)果表明BD算法是有效的，且在處理大規(guī)模網(wǎng)絡(luò)難題時(shí)，能比精確算法更有效提高解的質(zhì)量。此問題之后的研究方向：（1）考慮具有不確定性因素的“帶邊中斷動(dòng)態(tài)網(wǎng)絡(luò)最大流”問題，如考慮弧容量隨不確定因素改變，利用BD算法設(shè)計(jì)具有穩(wěn)健性的作業(yè)中斷調(diào)度表；（2）本文BD算法中，未談?wù)搶?shí)驗(yàn)中參數(shù)設(shè)置的規(guī)則，可進(jìn)一步改進(jìn)。

[1]宋之杰,陳文靜,侯貴賓,等.港口設(shè)備維修優(yōu)化模型及實(shí)例研究[J].物流技術(shù),2013,32(9):172-175.

[2]陳文靜.基于時(shí)間延遲模型的港口設(shè)備維修管理研究[D].秦皇島:燕山大學(xué),2012.

[3]劉藝杰.基于可靠性理論的退化設(shè)備預(yù)防維修策略研究[D].秦皇島:燕山大學(xué),2013.

[4]范體軍,許淑君,李宏余,等.設(shè)備維護(hù)外包策略及其對(duì)維護(hù)計(jì)劃組織的影響[J].工業(yè)工程與管理,2006,11(3):15-18.

[5]崔維偉,陸志強(qiáng),潘爾順.基于多目標(biāo)優(yōu)化的生產(chǎn)調(diào)度與設(shè)備維護(hù)集成研究[J].計(jì)算機(jī)集成制造系統(tǒng),2014,20(6):1 398-1 404.

[6]王紅,杜維鑫,劉志龍,等.聯(lián)合故障與經(jīng)濟(jì)相關(guān)性的動(dòng)車組多部件系統(tǒng)維護(hù)[J].上海交通大學(xué)學(xué)報(bào),2016,50(5):660-667.

[7]Boland N,Kalinowski T,Waterer H,et al.Scheduling arc maintenance jobs in a network to maximize total flow over time[J].Discrete Applied Mathematics,2014,163(1):34-52.

[8]Boland N,Kalinowski T,Kapoor R,et al.Scheduling unit processing time arc shutdown jobs to maximize network flow over time:complexity results[J].Computer Science,2013,63(2):196-202.

[9]J F Benders.Partitioning procedures for solving mixed-variables programming problems[J].Computational Management Science,2005,2(1):3-19.

[10]Fischetti Lodi.Local branching[J].Mathematical Programming,2003,98(1):23-47.