鄧 佳，譚代倫

風(fēng)能是一種具有無污染、分布廣泛、可循環(huán)利用等優(yōu)點(diǎn)的可再生資源［1］，風(fēng)能發(fā)電在我國發(fā)電系統(tǒng)的占比呈逐年上升趨勢［2］.其中，維護(hù)風(fēng)力發(fā)電設(shè)備正常運(yùn)行、保持較高的日均發(fā)電效率［3?4］，是風(fēng)力發(fā)電運(yùn)營公司日常需要解決的重要問題.

當(dāng)風(fēng)力發(fā)電設(shè)備數(shù)量較多時(shí)，電力運(yùn)營公司不得不組織一定數(shù)量的檢修小組，依靠合適的運(yùn)輸工具將檢修小組送達(dá)故障設(shè)備處完成檢修任務(wù).對(duì)一批待檢修的風(fēng)機(jī)故障任務(wù)，是否能及時(shí)有效地完成，對(duì)公司降低成本、提高效益具有重要作用.為此，在風(fēng)力發(fā)電設(shè)備的故障檢修過程中，存在著運(yùn)籌學(xué)領(lǐng)域中的優(yōu)化問題，對(duì)其進(jìn)行研究，對(duì)電力公司的高效運(yùn)營和維修具有較強(qiáng)的理論與實(shí)踐意義.

該類問題不僅包含了沿某種路徑完成維修小組的運(yùn)送，還包括了根據(jù)人員特性和故障需求進(jìn)行合理的任務(wù)指派，前者更具有TSP問題［5］的特征，后者則比較符合運(yùn)籌學(xué)中的AP 問題的特征［6］，因此它屬于這兩類基本運(yùn)籌學(xué)問題復(fù)合而成的組合優(yōu)化問題.由于設(shè)備數(shù)量多、場地面積大，這類復(fù)合型問題尤為突出，在其他領(lǐng)域也有類似情況.

對(duì)此，國內(nèi)外學(xué)者展開了相關(guān)研究.在國外，TANG 等［7］于2007 年利用禁忌搜索算法求解了一類帶時(shí)間依賴的計(jì)劃調(diào)度問題.BAYS等［8?9］利用運(yùn)籌學(xué)知識(shí)研究了一艘母艦攜帶一定數(shù)量的、帶有不同特定任務(wù)的無人小艇在某一片海域進(jìn)行施放或回收作業(yè)問題.RASHIDNEJAD 等［10］研究了將維護(hù)調(diào)度與車輛路由相結(jié)合問題并利用遺傳算法求解.MOSAYEBI 等［11］提出了帶工作時(shí)間的TSP 問題，給出了數(shù)學(xué)模型并設(shè)計(jì)了啟發(fā)式搜索算法進(jìn)行求解.目前，國內(nèi)對(duì)該類問題的研究還較少.陳峰［12］研究了運(yùn)籌學(xué)在整車物流智能調(diào)度決策支持系統(tǒng)的應(yīng)用.袁瑋等［13］研究了運(yùn)籌學(xué)在海上油田直升機(jī)智能航線規(guī)劃中的應(yīng)用.周忠彬等［14］研究了運(yùn)輸排程優(yōu)化模型在海上批量傷員運(yùn)送中的應(yīng)用.

本文基于風(fēng)力發(fā)電設(shè)備檢修場景，研究基于TSP 路徑與任務(wù)指派的MWPEP 問題，分析并建立數(shù)學(xué)模型，既拓寬了運(yùn)籌學(xué)知識(shí)的應(yīng)用，也對(duì)企業(yè)的經(jīng)營管理具有較強(qiáng)的借鑒意義.

1 問題提出

在風(fēng)力發(fā)電運(yùn)營與管理的全過程，即使只考慮設(shè)備檢修環(huán)節(jié)，需要考慮的因素也比較多，為此需要對(duì)問題作一些必要的簡化，使問題具有基礎(chǔ)性和代表性.

①只考慮有一輛運(yùn)輸工具的情形，它從固定的檢修中心出發(fā)，裝載上全部檢修小組及物資后，沿一定路線依次經(jīng)過每一個(gè)待檢修的故障設(shè)備點(diǎn)，到達(dá)故障點(diǎn)后被指定的檢修小組馬上開始檢修工作，運(yùn)輸工具則繼續(xù)前往下一個(gè)故障點(diǎn)，完成全部運(yùn)送任務(wù)后回到起點(diǎn).對(duì)每一個(gè)故障點(diǎn)，過且只過一次，以保證不遺漏也不重復(fù).合理地規(guī)劃路線，將有利于盡早把檢修人員送達(dá)現(xiàn)場.

②對(duì)于檢修人員與故障設(shè)備，假設(shè)每一個(gè)設(shè)備點(diǎn)所出現(xiàn)的故障現(xiàn)象并不完全相同，成功檢修故障所需的時(shí)間也因而不同；另外，不同檢修人員對(duì)不同類別故障現(xiàn)象的檢修水平也各有不同，相應(yīng)的每個(gè)檢修小組完成每一個(gè)故障設(shè)備的檢修時(shí)間也不完全相同.任務(wù)的指派規(guī)則是每一個(gè)檢修小組只承擔(dān)一個(gè)故障點(diǎn)的檢修任務(wù)，反之每一個(gè)故障點(diǎn)的檢修任務(wù)只被一個(gè)檢修小組完成.合理地進(jìn)行故障檢修任務(wù)的指派，將有利于盡早完成全部的檢修任務(wù).

綜合考慮運(yùn)送與任務(wù)指派，問題的總體目標(biāo)是規(guī)劃一條最優(yōu)的運(yùn)送路線和檢修小組的最優(yōu)指派，使得全部檢修任務(wù)能盡早結(jié)束.其中，運(yùn)輸工具的行進(jìn)速度視為勻速，檢修小組對(duì)每一類故障現(xiàn)象的檢修時(shí)間可經(jīng)統(tǒng)計(jì)或測試獲得.

基于以上問題描述，為完成風(fēng)力發(fā)電設(shè)備的檢修任務(wù)，需要綜合運(yùn)用基于TSP 問題的路徑規(guī)劃方法和AP 問題的任務(wù)指派方法，本文將其稱為基于TSP 路徑與任務(wù)指派的一類MWPEP 問題.

2 建立MWPEP 問題的數(shù)學(xué)模型

根據(jù)問題提出，MWPEP 問題的目標(biāo)是要求盡早完成全部檢修任務(wù)，即使整體完工時(shí)間最短.容易發(fā)現(xiàn)，對(duì)任意一個(gè)檢修小組，它的檢修任務(wù)完工時(shí)間由兩個(gè)部分組成：一是運(yùn)輸工具從檢修中心（即TSP 中0 號(hào)路徑點(diǎn)）出發(fā)將此檢修小組運(yùn)送到達(dá)某個(gè)故障點(diǎn)所需的時(shí)間；二是到達(dá)故障點(diǎn)后檢修小組完成該故障任務(wù)檢修所花的時(shí)間.由于到達(dá)時(shí)間有先后，各個(gè)故障點(diǎn)檢修任務(wù)的完工時(shí)間有所不同，因此要使整體完工時(shí)間最短，則需使所有檢修小組的到達(dá)時(shí)間和檢修時(shí)間之和中的最大者盡量小.其中，到達(dá)時(shí)間由按TSP 問題特征進(jìn)行路徑規(guī)劃的結(jié)果所決定，檢修時(shí)間由按AP 問題特征進(jìn)行任務(wù)指派的結(jié)果所決定.

鑒于此，下面先給出必要的數(shù)學(xué)符號(hào)和變量，再基于TSP 問題和AP 問題分別從兩個(gè)方面進(jìn)行分析和建模.

2.1 符號(hào)與變量

不妨設(shè)共有n個(gè)故障點(diǎn)，依次記為1，2，…，n，檢修中心記為0 號(hào)點(diǎn)，任意第i個(gè)點(diǎn)的坐標(biāo)記為pi(xi，yi)，i=0，1，2，…，n，這里假設(shè)所有點(diǎn)均在一個(gè)平面內(nèi)，而不考慮具體的山區(qū)或海上情形.運(yùn)輸工具以勻速行駛，速度記為V0.共有n個(gè)檢修小組，任意第j個(gè)檢修小組完成第i個(gè)故障檢修任務(wù)的時(shí)間記為cij.

對(duì)所有路徑節(jié)點(diǎn)（包括設(shè)備故障點(diǎn)和檢修中心），設(shè)任意兩點(diǎn)之間的距離為dij，按歐式距離公式計(jì)算，公式為：

式中：i，j=0，1，2，…，n.

經(jīng)過該段路程dij所花的時(shí)間為：

2.2 基于TSP 路徑與任務(wù)指派的建模

對(duì)MWPEP 問題，基于TSP 路徑與任務(wù)指派進(jìn)行建模，主要是指在TSP 行走路徑基礎(chǔ)上考慮任務(wù)指派所形成的設(shè)備檢修時(shí)間的疊加.為此，不妨設(shè)任意一輪檢修設(shè)備及人員運(yùn)送形成的TSP 路徑及任務(wù)指派的檢修小組如下：

式中：v0為0 號(hào)檢修中心，vi，ui∈{1，2，…，n}分別為不重復(fù)的任意一個(gè)設(shè)備故障點(diǎn)和任意一個(gè)檢修小組.

因此，各檢修小組被運(yùn)送到設(shè)備故障點(diǎn)的到達(dá)時(shí)間和完成檢修任務(wù)的完工時(shí)間可沿路徑點(diǎn)依次計(jì)算，結(jié)果如表1 所示.

表1 基于TSP 路徑與任務(wù)指派的變量構(gòu)造

借鑒基于路徑構(gòu)建的TSP 問題的數(shù)學(xué)模型，記任意一條運(yùn)送路徑為V={v0，v1，…，vi，…，vj，…，vn}，對(duì)應(yīng)檢修小組的任意一個(gè)指派為U={u1，u2，…，ui，…，uj，…，un}，則MWPEP問題的數(shù)學(xué)模型（記為模型Ⅰ）可表示為：

上述模型的目標(biāo)是使各個(gè)檢修小組的完工時(shí)間最大最小化，它依賴于運(yùn)送路徑，也依賴于指派方案.此外由表1 可知，模型中運(yùn)送到每一個(gè)路徑節(jié)點(diǎn)的到達(dá)時(shí)間TVi與前一個(gè)節(jié)點(diǎn)的到達(dá)時(shí)間TVi?1形成累加關(guān)系，在模型中也可以由遞推關(guān)系式表示為：

2.3 基于0-1 型決策變量的建模

TSP 問題的0?1 規(guī)劃模型 和AP 問題的模型均基于0?1 型決策變量進(jìn)行建模，其優(yōu)點(diǎn)是比較容易刻畫路徑節(jié)點(diǎn)被唯一經(jīng)過、維修任務(wù)與檢修小組的唯一分配等對(duì)應(yīng)關(guān)系，但這種對(duì)應(yīng)關(guān)系無法體現(xiàn)出路徑節(jié)點(diǎn)被經(jīng)過的先后順序，因此無法按表1 刻畫出每一個(gè)節(jié)點(diǎn)的到達(dá)時(shí)間，相應(yīng)的檢修時(shí)間也無法累加進(jìn)去.

基于此，除繼續(xù)采用關(guān)于TSP 路徑和任務(wù)指派的兩種0?1 型決策變量外，還將運(yùn)送到達(dá)任意一個(gè)節(jié)點(diǎn)的到達(dá)時(shí)間也作為一組決策變量，并對(duì)其進(jìn)行約束.

為此，設(shè)TSP 的路徑節(jié)點(diǎn)集為V={1，2，…，n}，待分配的任務(wù)集為U={1，2，…，n}.在節(jié)點(diǎn)集V中，0 為檢修中心，是出發(fā)的起始點(diǎn)，不分配檢修小組.問題的主要決策變量及定義如下：

Ti：運(yùn)送到第i個(gè)故障點(diǎn)的到達(dá)時(shí)間.式中：i，j，k=1，2，…，n.

決策變量xij，yik仍然分別用于約束運(yùn)送路徑和任務(wù)指派關(guān)系的生成，結(jié)合變量Ti可表示檢修任意第i個(gè)設(shè)備故障點(diǎn)處的完工時(shí)間為：

式中：cik為第k個(gè)檢修小組對(duì)第i個(gè)設(shè)備故障點(diǎn)的檢修時(shí)間.

根據(jù)AP 問題的基本約束，對(duì)于任意i，決策變量組{yi1，yi2，…，yin}必只有一個(gè)取值為1，因此式（1）就是任意第i個(gè)設(shè)備故障點(diǎn)處的到達(dá)時(shí)間和檢修時(shí)間之和，即第i點(diǎn)的完工時(shí)間.

于是，MWPEP 問題要使運(yùn)送與檢修總體完工時(shí)間最短的目標(biāo)可以表示為：

下面對(duì)Ti構(gòu)建必要的約束，運(yùn)送到第j個(gè)設(shè)備故障點(diǎn)的兩種情形如圖1 所示.

圖1 運(yùn)送到達(dá)第j 點(diǎn)的兩種情形

由圖1（a）可知，當(dāng)起點(diǎn)從0 號(hào)點(diǎn)出發(fā)時(shí)，必有

類似地，當(dāng)最終從任意第i個(gè)設(shè)備故障點(diǎn)返回0 號(hào)起點(diǎn)時(shí)，必有

由圖1（b）可知，當(dāng)從任意第i點(diǎn)向第j點(diǎn)運(yùn)送時(shí)，必有

綜合TSP 問題、AP 問題的0?1 規(guī)劃模型，以及式（1）～式（4），可建立MWPEP 問題基于0?1 型決策變量的數(shù)學(xué)模型（記為模型Ⅱ）如下：

3 MWPEP 問題算例與模型分析

前面已經(jīng)建立了MWPEP 問題的兩個(gè)數(shù)學(xué)模型，其中，模型Ⅰ的建模過程簡單直觀，可以通過列舉一個(gè)方案，描述清楚模型Ⅰ的可行解和目標(biāo)函數(shù)值的形成過程.而對(duì)模型Ⅱ直接構(gòu)建可行解，其目標(biāo)函數(shù)值計(jì)算過程與模型Ⅰ相似，在此不再對(duì)模型Ⅱ進(jìn)行舉例計(jì)算.在模型Ⅱ中，為刻畫到達(dá)節(jié)點(diǎn)的先后順序，構(gòu)造了一組運(yùn)送到第i個(gè)故障點(diǎn)的到達(dá)時(shí)間作為決策變量，下面對(duì)模型Ⅱ中構(gòu)造的決策變量做詳細(xì)分析.

3.1 MWPEP 問題算例

現(xiàn)設(shè)需要維修的設(shè)備故障點(diǎn)有5 個(gè)，編號(hào)為1，2，3，4，5，起點(diǎn)記為0.為簡化計(jì)算，直接給出任意兩點(diǎn)之間的運(yùn)送時(shí)間，不再給出距離矩陣和速度.相應(yīng)地，檢修小組有5 個(gè)，編號(hào)記為A，B，C，D，E，給出任意設(shè)備故障點(diǎn)對(duì)應(yīng)檢修小組的檢修時(shí)間，相關(guān)數(shù)據(jù)如表2 所示.

表2 MWPEP 問題算例的運(yùn)送時(shí)間和檢修時(shí)間數(shù)據(jù)

注：表2 中任意兩路徑點(diǎn)之間的運(yùn)送時(shí)間即為模型Ⅰ中的矩陣T=(tij)，指派給任意路徑點(diǎn)的檢修小組所對(duì)應(yīng)的檢修時(shí)間即為模型Ⅰ中的矩陣C=(cik)，且表中時(shí)間數(shù)據(jù)的單位均為分.

3.2 基于算例對(duì)模型Ⅰ的分析

在模型Ⅰ中，首先規(guī)劃了一條TSP 運(yùn)送路徑，然后在路徑的基礎(chǔ)上分配任務(wù)指派的檢修小組.其中，運(yùn)送到達(dá)每個(gè)路徑點(diǎn)的時(shí)間與檢修小組完成工作需要的檢修時(shí)間之和，就是檢修此路徑點(diǎn)的完工時(shí)間.所有路徑點(diǎn)的檢修完工時(shí)間中最大值為最大完工時(shí)間，最大完工時(shí)間與運(yùn)輸返回起點(diǎn)時(shí)間中較大者，即為目標(biāo)函數(shù)值.

假設(shè)一輪運(yùn)送路徑及任務(wù)指派的檢修小組為：0 →2(D) →1(C) →4(A) →5(E)→3(B)→0 記為方案1，參照表1 的計(jì)算公式可得出方案1 任意路徑點(diǎn)的到達(dá)時(shí)間、檢修時(shí)間和完工時(shí)間，如表3 所示.

表3 方案1 對(duì)應(yīng)的變量取值

為更直觀理解表3 中數(shù)字的含義，繪制方案1 的運(yùn)輸路線、指派方案及相應(yīng)的時(shí)間，如圖2 所示.其中圓中數(shù)字為對(duì)應(yīng)路徑點(diǎn)，長方形中字母和數(shù)字分別代表分配給對(duì)應(yīng)路徑點(diǎn)的檢修小組及檢修時(shí)間，帶箭頭的線上數(shù)字為兩相鄰路徑點(diǎn)的運(yùn)輸時(shí)間，圓形外面的數(shù)字為對(duì)應(yīng)路徑點(diǎn)的到達(dá)時(shí)間.

圖2 方案1 的旅行路徑和檢修小組指派

從圖2 可以看出，從起點(diǎn)到路徑點(diǎn)3，需要依次經(jīng)過路徑點(diǎn)2，1，4，5，到達(dá)路徑點(diǎn)3 的時(shí)間為41，此時(shí)檢修小組B 在路徑點(diǎn)3 執(zhí)行檢修任務(wù)，所需檢修時(shí)間為11.所以，在路徑點(diǎn)3的檢修任務(wù)完工時(shí)間為到達(dá)路徑點(diǎn)3 的時(shí)間與檢修小組B 完成檢修任務(wù)所需時(shí)間之和為52.同理，在路徑點(diǎn)1，2，4，5 的檢修完工時(shí)間分別為26，19，35，46.運(yùn)輸工具完成運(yùn)送返回到起點(diǎn)花費(fèi)的時(shí)間為51.所以，在這個(gè)方案中，所有路徑點(diǎn)的檢修完工時(shí)間和運(yùn)輸返回起點(diǎn)所需時(shí)間中最大值為52，則方案1 的函數(shù)值為52.

通過對(duì)模型Ⅰ進(jìn)行舉例說明，對(duì)MWPEP問題的決策變量和目標(biāo)函數(shù)形成有了更清楚的認(rèn)識(shí).

3.3 基于算例對(duì)模型Ⅱ進(jìn)行分析

在模型Ⅱ中，為了刻畫到達(dá)路徑點(diǎn)的順序，特別使用了運(yùn)送到達(dá)任意一個(gè)節(jié)點(diǎn)的到達(dá)時(shí)間Ti作為一組決策變量，并對(duì)Ti的取值范圍進(jìn)行約束，下面對(duì)方案1 中到達(dá)時(shí)間的約束作進(jìn)一步分析，現(xiàn)設(shè)變量xij的取值如表4所示.

表4 MWPEP 問題方案1 對(duì)應(yīng)變量xij 的取值

從表4 可以看出，當(dāng)從0 號(hào)點(diǎn)出發(fā)到達(dá)第一個(gè)路徑點(diǎn)為2 號(hào)路徑點(diǎn)，此時(shí)

從起點(diǎn)出發(fā)到達(dá)除路徑點(diǎn)2 的任意節(jié)點(diǎn)都會(huì)經(jīng)過路徑點(diǎn)2，則對(duì)除路徑點(diǎn)2 的任意路徑點(diǎn)滿足Ti>T2，i≠2.所以，對(duì)除起點(diǎn)外任意路徑點(diǎn)滿足式（2），當(dāng)且僅當(dāng)i為從0 號(hào)點(diǎn)出發(fā)到達(dá)的第一個(gè)路徑點(diǎn)時(shí)取等.

同理，返回0 號(hào)點(diǎn)有兩種情況.返回0 號(hào)點(diǎn)前到達(dá)的最后一個(gè)路徑點(diǎn)為3 號(hào)點(diǎn)，那么到達(dá)3 號(hào)點(diǎn)的時(shí)間為運(yùn)送花費(fèi)總時(shí)間與從i點(diǎn)到0 號(hào)點(diǎn)所需時(shí)間之差，即

對(duì)除3 號(hào)點(diǎn)的任意路徑點(diǎn)，需要經(jīng)過路徑點(diǎn)3 才能返回起點(diǎn)，故Ti

綜上，對(duì)除起點(diǎn)外任意路徑點(diǎn)i的到達(dá)時(shí)間的取值范圍滿足8 ≤Ti≤41，i=1，2，3，4，5，即

經(jīng)過路徑點(diǎn)i到達(dá)路徑點(diǎn)j有兩種情況，第一種情況是從路徑點(diǎn)i可直接到達(dá)路徑點(diǎn)j，第二種情況是從路徑點(diǎn)i需要經(jīng)過若干個(gè)路徑點(diǎn)才能到達(dá)路徑點(diǎn)j.若j點(diǎn)為4 號(hào)點(diǎn)，i點(diǎn)為1 號(hào)點(diǎn)，則從1 號(hào)點(diǎn)可直接到達(dá)4 號(hào)點(diǎn)，滿足

若i點(diǎn)為2 號(hào)點(diǎn)，從2 號(hào)點(diǎn)需要經(jīng)過1 號(hào)點(diǎn)才能到達(dá)4 號(hào)點(diǎn)，此時(shí)T2=T1?t21

通過對(duì)模型Ⅱ到達(dá)時(shí)間變量的約束條件進(jìn)行分析，對(duì)約束條件的構(gòu)造過程更加容易理解.

4 結(jié)語

本文研究了風(fēng)力發(fā)電設(shè)備檢修場景內(nèi)的一類設(shè)備檢修問題.通過對(duì)問題做適當(dāng)簡化，給出了基于TSP 路徑與任務(wù)指派的MWPEP 問題.同時(shí)以TSP 問題和AP 問題的數(shù)學(xué)模型為基礎(chǔ)，一方面，在TSP 路徑的基礎(chǔ)上，把指派所形成的檢修時(shí)間疊加，構(gòu)造目標(biāo)函數(shù)值，建立數(shù)學(xué)模型；另一方面，借鑒TSP 問題和AP 問題的0?1 規(guī)劃模型，刻畫到達(dá)每個(gè)節(jié)點(diǎn)時(shí)間作為一組決策變量，并限制其取值范圍進(jìn)行建模.MWPEP 問題的提出，擴(kuò)寬了運(yùn)籌學(xué)知識(shí)的應(yīng)用，同時(shí)，MWPEP 問題數(shù)學(xué)模型的建立，為今后使用智能算法求解此類問題奠定了基礎(chǔ).