煤炭港口設備維護調(diào)度優(yōu)化研究

劉華琳 王 瀟 李軍偉

(國能黃驊港務有限責任公司1) 滄州 061113) (武漢理工大學交通與物流工程學院2) 武漢 430063)

0 引 言

Boland等[1-2]在研究澳大利亞獵人谷煤炭供應鏈年度維護問題時發(fā)現(xiàn),將規(guī)劃期內(nèi)所有設備的維護檢修任務作為一個整體考慮,協(xié)調(diào)起來制定檢修計劃,才能保證系統(tǒng)的總中斷時間最短,從而達到在計劃時間段內(nèi)最大化系統(tǒng)通貨能力的效果.該問題被抽象為一個帶邊中斷動態(tài)網(wǎng)絡最大流(MAXTFAO)問題,并被證明是強NP難的.同時還提出了多種基于智能搜索的優(yōu)化算法有效解決了該問題,成功替代了以往需要20多人兩個月完成的工作,并應用到了紐卡斯爾港NCIG碼頭的日常運營管理中,取得了顯著的經(jīng)濟效益.

帶邊中斷的動態(tài)網(wǎng)絡最大流問題自然地混合了網(wǎng)絡流和調(diào)度問題的特征.系統(tǒng)組件維護期間是不可用的,相應的抽象網(wǎng)絡中對應的弧容量為0.每個維護任務的維護時間窗是相對固定的,其取決于設施設備的運行狀態(tài).這意味著弧容量是隨著時間的推移而變化,即不同時間段內(nèi)流量的相互依賴性和流量網(wǎng)絡是動態(tài)的,這是典型的時間依賴動態(tài)容量網(wǎng)絡問題.此外,網(wǎng)絡中的弧是否中斷取決于何時執(zhí)行維護任務,這意味著網(wǎng)絡在一定時間范圍包含的時間段內(nèi)的性能將在很大程度上取決于之前的時間段所做的決策,是調(diào)度的結(jié)果.

Pearce等[3]針對該問題特征設計了基于Branch and Benders cut(B&BC)的精確算法并提出三種有效的改進措施對該問題進行求解.相較于商業(yè)求解器,該算法均有不錯的改進和表現(xiàn).與Pearce算法不同,劉茜等[4]采用傳統(tǒng)的Benders分解算法對該問題進行了算法實驗.高吉冰等[5]將兩位學者的算法進行了求解性能對比,其結(jié)果表明B&BC算法的性能更加優(yōu)越,并基于該算法框架提出了多種有效的改進措施.徐齊鵬[6]設計了以禁忌搜索算法為主體,結(jié)合整數(shù)規(guī)劃的混合算法,實驗結(jié)果表明該算法在大網(wǎng)絡大規(guī)模的算例中表現(xiàn)最好.

上述研究中均是假設網(wǎng)絡中維護資源無限的情況下進行的.然而,在現(xiàn)實世界中維護計劃通常受到資源可用性的限制.根據(jù)文獻[7]可知:當多個組件通過共享備件、工具或維護人員連接時,就會出現(xiàn)資源依賴性.例如,如果系統(tǒng)由于工人的可用性有限而顯示出資源依賴性,那么維護活動的同步調(diào)度將受到可用維護人員數(shù)量的限制.Charkhgard等[8]對MaxTFFAO進行了拓展,其基于使用的預防維護以網(wǎng)絡路徑的角度對該問題重新建模并進行了深入研究,探討了在一條路徑上的維護設備有限且唯一,同時該維護設備在單位時間段內(nèi)可到達的弧的范圍為有限的情況.在其研究中驗證了即使只有一個設備需要維護,該問題仍是NP難的.

針對基于網(wǎng)絡優(yōu)化模型研究系統(tǒng)的設備維護調(diào)度問題,Urbani等[9]研究了將多組件系統(tǒng)建模為網(wǎng)絡化的有向圖,在其網(wǎng)絡中節(jié)點表示機器或工人,邊表示這些節(jié)點之間的材料、信息或工作交換.制定了一個雙目標優(yōu)化問題,該問題考慮了維修人員的有限可用性,目的是尋求最佳維護計劃.馮樂樂[10]提出了一種基于設備健康指數(shù)的多設備生產(chǎn)線預防性機會維護方法.謝志強等[11]提出了基于動態(tài)規(guī)劃調(diào)整設備維護開始時間的綜合調(diào)度算法.

文中結(jié)合黃驊港作業(yè)實際場景的需求,考慮了維護資源配備組(維護人員和其他資源)的限制,構(gòu)建了資源限制下的網(wǎng)絡維護調(diào)度優(yōu)化的混合整數(shù)規(guī)劃模型,涉及維護作業(yè)的分配和時間表設計.該模型在MaxTFFAO問題結(jié)構(gòu)上,增加了維護資源到維護任務的分配,具有帶時間窗車輛路徑問題的特征.通過基于問題結(jié)構(gòu)的分解,提高了精確算法的求解能力,并在實際數(shù)據(jù)和測試算例中驗證了方法的有效性.

1 問題描述及模型

1.1 問題描述

在黃驊港的生產(chǎn)場景中,火車將煤炭運送到港口后需要經(jīng)過翻車機、堆料機、取料機、裝船機以及設備間輸送煤炭的皮帶等運送到船舶,見圖1.由于使用和暴露于環(huán)境的原因,港口的設備通常隨著時間的推移會退化.這將導致設備的質(zhì)量下降,最終導致設備故障.為了避免在設備突然發(fā)生故障后進行成本更高的事后維護,企業(yè)會對設備進行定期檢查和保養(yǎng)措施的預防性維護.這也是確保了設備運轉(zhuǎn)的性能和可靠性水平.

圖1 煤炭港口裝卸設備關聯(lián)示意圖

相互關聯(lián)的港口設備組成了設備網(wǎng)絡,可以抽象為圖2的有向圖來描述,其中V表示設備連接關系節(jié)點.網(wǎng)絡中的弧a∈A分為設備弧和關系弧,其中設備弧代表的是一個設備.由于部分設備之間的相互關系復雜,因此需用關系弧進行表示.每個設備的單位運行效率為每條設備弧上的容量.對于關系弧的容量則等于其出發(fā)節(jié)點所連接的設備弧的容量.

圖2 設備網(wǎng)絡有向圖示意圖

在港口日常運作時,維護計劃通常受到資源可用性的限制.港口設備共享備件、工具和維護人員.因此維護活動的同步調(diào)度將受到可用維護人員數(shù)量的限制.此外,在開始執(zhí)行維護作業(yè)之前,維護人員需申請流動機械和備件,以及一定的到達維修點的時間[12].因此同一維護人員的多個維護作業(yè)之間需要一定大小的時間間隔.

1.2 參數(shù)設置

定義設備網(wǎng)絡G=(V,A),其中V為節(jié)點集合,A為有向的弧集.虛擬一個源點s和一個匯點v.其他具體的參數(shù)說明如下.

1) 參數(shù)集合δ+(v)為流出每個節(jié)點v∈V的弧集;δ-(v)為流入每個節(jié)點v∈V的弧集;J為所有維護作業(yè)的集合;Ja為單個弧上維護作業(yè)的集合.

2) 參數(shù)T為設備網(wǎng)絡G的總規(guī)劃期;Ca為每個弧上的容量;pj為每個維護作業(yè)的處理時間;rj為每個維護作業(yè)的最早開始時間;dj為每個維護作業(yè)的最遲截止時間;[rj,dj-pj+1]為每個維護作業(yè)的可以開始執(zhí)行的時間窗;Tij為維護作業(yè)之間的維護人員到達時間間隔;K為維護人員的數(shù)量.

1.3 數(shù)學模型

將資源限制下的網(wǎng)絡維護問題表述為MIP問題.該問題中要最大化的目標函數(shù)是在總規(guī)劃期內(nèi)設備網(wǎng)絡的吞吐能力,即經(jīng)過的流量最大.

(1)

該問題的可行方案由以下一組約束條件定義.

(2)

(3)

(4)

(5)

(6)

?i∈J,k=1,2,…,K

(7)

(8)

startik+pi+Tij-M(1-wijk)≤

startjk,i≠j∈[J],k∈K

(9)

(10)

wijk∈{0,1},startjk≥0

(11)

式(2)和式(3)分別為t時段對應的每個弧流量出入平衡,且流經(jīng)的流量小于弧的容量.式(4)為每個維護作業(yè)執(zhí)行時相對應的弧會中斷,且同一個弧上的多個維護作業(yè)不能同時進行.式(5)為每個維護作業(yè)只能有一個維護人員執(zhí)行且每個維護作業(yè)的開始時間唯一.式(6)虛擬一個出發(fā)作業(yè)節(jié)點0.每個維護人員都會經(jīng)過虛擬節(jié)點一次.式(7)限定了每個作業(yè)節(jié)點只能被一個維護人員訪問一次.即如果維護作業(yè)j被維護人員k在其時間窗內(nèi)執(zhí)行,則等于1,否則為0.式(8)定義了每個維護作業(yè)的時間戳.式(9)為一個維護人員執(zhí)行的維護作業(yè)之間必須有一個準備和到達所需的間隔時間Tij,該約束同為消除子回路約束.式(10)為資源約束.即同一時間網(wǎng)絡中中斷的弧的數(shù)量不能大于維護人員的數(shù)量.

2 Benders分解算法設計

2.1 Benders模型分解設計

Benders Decomposition與傳統(tǒng)的Benders算法在子問題和主問題之間循環(huán)迭代求解不同,采用Branch and Benders Cut(B&BC)算法框架,是只需求解一次主問題的Benders分解算法.

該問題可以分解為兩個問題,子問題為網(wǎng)絡最大流問題,主問題為一個具有VRP特征的調(diào)度問題.

(12)

(14)

φat≥0

(15)

當子問題求解完后獲取其對偶變量uat,并引入一個θt變量用以表示主問題的上界.

(16)

將式(16)加入主問題后主問題模型為

(17)

(18)

(19)

算法步驟為:

步驟1初始化參數(shù)G,A,T,C,J,Ja,K.

步驟2構(gòu)建子問題模型和主問題模型,設置xat=1(?a∈A,t∈[T]).

步驟3獲取子問題目標值x0,構(gòu)造約束θt≤x0加入主問題中.

步驟4設置主問題參數(shù)MipGapAbs=0.999,MipGap=1×10-6.

步驟5求解主問題,求解過程中利用求解器的Callback函數(shù)向主問題中加入Benders割.

2.2 網(wǎng)絡最小割

因為關閉任意的弧都不可能增加網(wǎng)絡總流量,所以當網(wǎng)絡中的弧都處于連通狀態(tài),即xat=1(?a∈A,t∈[T])時,網(wǎng)絡可以通過的最大流量為網(wǎng)絡流量的上界.與容量約束相關的非零對偶變量的弧集是來自最大流最小割定理的“最小割集”,最小割集是網(wǎng)絡的瓶頸.因為最小割集中的任意弧的中斷,都會直接影響通過網(wǎng)絡的總流量.圖3為分層結(jié)構(gòu)示意圖.

圖3 分層結(jié)構(gòu)示意圖

除去虛擬的源匯點,該網(wǎng)絡有兩層,其中弧1～2的容量之和為10,弧3～4的容量之總和為15.在這種情況下,初始割集將為弧1～2.組成了最小割集即為網(wǎng)絡的瓶頸,故可以在模型中增加約束.

θt≤4x1t+6x2t?t∈T

(20)

由于這些弧為最大流量最小切割定理中定義的最小切割集,所以其是該網(wǎng)絡的瓶頸所在.假設增加這些弧的容量,使其大于弧3～4的容量之和.然后我們再次求解這一最大流量問題時,發(fā)現(xiàn)第二個最小割集為弧3～4.然后只需在模型中添加瓶頸約束:

θt≤8x3t+7x4t?t∈T

(21)

這些約束都是有效的.通過這些網(wǎng)絡流瓶頸約束,可以找到滿足調(diào)度約束的主問題的解決方案.當遇到分支和定界樹的節(jié)點時,檢查是否需要更多的網(wǎng)絡流瓶頸割,以惰性約束的方式添加到模型中.該實施將被記為為網(wǎng)絡最小割(Net-cuts).

算法步驟為:

步驟1檢查子問題的對偶變量ua,?a∈A.

步驟3重置Ca,?a∈A的值.

該算法步驟用于Benders算法步驟的3～4.

3 算例實驗分析

3.1 算例測試集

實驗數(shù)據(jù)由維護作業(yè)信息數(shù)據(jù)和網(wǎng)絡結(jié)構(gòu)數(shù)據(jù)兩部分組成.網(wǎng)絡結(jié)構(gòu)數(shù)據(jù)是由黃驊港一期項目的現(xiàn)實場景抽象而來,關于場景包含的設備詳情見表1.

表1 網(wǎng)絡結(jié)構(gòu)數(shù)據(jù)詳情

維護數(shù)據(jù)主要的參數(shù)有維護任務可選開始時間窗、維護任務的處理時間.在生成測試數(shù)據(jù)時主要關注兩點:時間窗的大小和處理時間的長短.很容易知道時間窗的大小對模型的求解規(guī)模影響極大.因此在生成測試數(shù)據(jù)時,生成了三種規(guī)模的時間窗.而處理時間的長短決定了網(wǎng)絡中斷的總規(guī)模.除了測試算例集,還依據(jù)港口生產(chǎn)的現(xiàn)實維護狀態(tài)進行設計實例數(shù)據(jù)C進行測試.現(xiàn)實場景中維護任務往往會因為生產(chǎn)壓力而推遲執(zhí)行,因此每個維護任務的時間窗的規(guī)模往往較大.具體參數(shù)見表2.

表2 維護作業(yè)數(shù)據(jù)詳情

3.2 算法性能對比分析

設定了以下對比指標.F-time為模型在迭代求解的過程中發(fā)現(xiàn)第一個可行解的時間;S-time為程序運行時間,采用此指標用以觀察算法在尋優(yōu)的表現(xiàn).gap為每個資源下網(wǎng)絡相應的求解gap值.

小規(guī)模時間窗下,模型整體規(guī)模較小.見表3算例A1的結(jié)果顯示,Gurobi和B&BC都可以在極短的時間尋找到可行解.但在尋找最優(yōu)解上,Gurobi明顯優(yōu)于B&BC.這是由于B&BC分解原模型的同時,喪失了相應的信息,從而B&BC在主問題獲得的松弛解的質(zhì)量比原問題差.這意味著B&BC的上界很差且產(chǎn)生了很多無效分支,增加搜索成本.算例B1相較于A1,增大了作業(yè)處理時間,這樣會導致維護資源的需求增大,因此在資源為1時無解.

表3 算法運行1 800 s結(jié)果對比詳情

中規(guī)模時間窗下,問題規(guī)模增大.通過算例A2和B2發(fā)現(xiàn)B&BC尋找可行解的優(yōu)勢更加明顯.算例B2中,在資源為3和4時B&BC都尋到了可行解而Gurobi沒有.特別在資源為5時,B&BC在找可行解和尋優(yōu)上都優(yōu)于Gurobi.這是因為B&BC將規(guī)模變大的原問題分解后,主問題的規(guī)模相較于原問題會小很多,在探尋節(jié)點的速度上更快.雖然其松弛解質(zhì)量要比原問題差很多,但利用Callback加入有效Benders割可以對主問題的規(guī)模進行有效的消減.

大規(guī)模時間窗下,進一步驗證了之前算法的表現(xiàn).除此之外,在算例B3時發(fā)現(xiàn)資源為4時B&BC找不到可行解,而Gurobi可以尋到最優(yōu)解.這和其它算例中B&BC在特定資源下尋找可行解不如Gurobi的原因相同.隨著資源的增大,問題規(guī)模也隨之增大.但是不同資源下的Benders割的有效性可能是相同的,對于效果一樣的Benders割,問題規(guī)模卻倍增下,尋找可行解的難度自然增大很多.

3.3 算法改進對比

從網(wǎng)絡的分層結(jié)構(gòu)出發(fā),構(gòu)造了網(wǎng)絡最小割用以提高松弛解的質(zhì)量.

在實際運用場景中,數(shù)據(jù)規(guī)模往往偏大.在表4實例數(shù)據(jù)C的求解結(jié)果看,B&BC和其改進在尋優(yōu)和發(fā)現(xiàn)可行解方面的表現(xiàn)都遠遠強于Gurobi,符合3.2中分析的不同數(shù)據(jù)算法求解規(guī)律.在資源為1時Net-B&BC算法表現(xiàn)的非常優(yōu)秀.其不僅在117.3 s內(nèi)就求得了最優(yōu)解,且在發(fā)現(xiàn)最優(yōu)解的時間花費也是最少的.

表4 實例數(shù)據(jù)C算法運行1800s結(jié)果對比詳情

表5列出了Root松弛解、添加cut數(shù)量和搜索節(jié)點數(shù)量的詳細信息來說明B&BC和Net-B&BC兩者的優(yōu)劣.Net-B&BC的松弛解的質(zhì)量明顯全部優(yōu)于B&BC,這意味著網(wǎng)絡最小割十分有效.且在算法運行中Net-B&BC向主問題中添加的benders割的數(shù)目大量減少,這意味著網(wǎng)絡最小割的加入有效的排除了大量的無效benders割的加入.而且分支定界樹的規(guī)模相對變小,這在node數(shù)量的對比上可以有效體現(xiàn).

表5 B&BC和Pre-B&BC算法運行信息詳情

4 結(jié) 論

1) 建立資源約束下的網(wǎng)絡維護問題整數(shù)規(guī)劃模型,可以同時處理維護人員配置和任務調(diào)度兩個維度的問題,更貼近工程實際需求.

2) 可以在規(guī)劃期內(nèi)同步為港口范圍內(nèi)所有部門的預防性維護任務制定統(tǒng)一的調(diào)度時刻表,相較于傳統(tǒng)的分部門分時段的人工決策更有助于提升系統(tǒng)整體的作業(yè)效率,有利于洞察港口作業(yè)系統(tǒng)生產(chǎn)運營的薄弱環(huán)節(jié).

3) 設計了基于網(wǎng)絡數(shù)據(jù)結(jié)構(gòu)的網(wǎng)絡最小割進行算法改進.通過對真實作業(yè)數(shù)據(jù)和測試用例的計算實驗分析了不同的維護任務數(shù)據(jù)對于問題求解難度的影響,驗證了所提出的算法的有效性,尤其在某些算例中有非常優(yōu)秀的表現(xiàn).

后續(xù)研究將會考慮與啟發(fā)式算法結(jié)合去改進算法以適用于更大規(guī)模的工業(yè)數(shù)據(jù).除此之外,也會圍繞該問題的本質(zhì)結(jié)構(gòu)進行更深入的探索,尋找更多有效的不等式以提升MIP模型線性松弛解的下界.