遺傳算法在電力維護人員調度問題中的應用

王柏根，汪　勛，張子臻

遺傳算法在電力維護人員調度問題中的應用

王柏根1，汪勛2，張子臻2

（1.東莞供電局，東莞523000；2.中山大學移動信息工程學院，珠海519000）

隨著電力設備的不斷發展和電力需求的不斷增加，電力維護問題日益突出。如何合理安排電力維護人員的行程成為一個亟待解決的問題。將該問題建模為累積時間的帶容量的車輛路徑問題的模型。CCVRP是傳統車輛路徑規劃問題的一個變種，但與一般VRP不同的是，它以最小化客戶的總等待時間為目標。針對該問題，我們利用遺傳算法的框架，并結合模擬退火算法進行局部搜索對問題進行求解。實驗部分證明該方法能有效地解決該類優化問題。

累計時間；車輛路徑規劃問題；遺傳算法；模擬退火

中央高校基本科研業務費專項資金（No.15lgpy37）

0　引言

電力工業是國民經濟的重要基礎產業，電力設施是電能生產、輸送、供應的載體，是重要的社會公用設施。電力設施的日常維護是保障供用電安全和維護社會公共安全的基礎性工作。在電力發展日益迅猛的今天，電力系統網絡越來越復雜，電力系統的安全性問題也逐漸突出。面對成百上千個分布在城市各處的電力設備，需要考慮維護人員工作的優化問題。本文的問題正是源于某市供電局的實際情況。其問題可以描述為，假設A供電局有n個分布在各地的電力設備（用集合N={1,…,n}表示）和m個維護人員，每個電力設備在得到維護前的等待時間為該問題就是如何安排這m個維護人員的工作路徑，使得在滿足維護人員最大工作量的前提下讓最小。其中等待時間主要與維護人員行走的路程有關。

這個問題我們可以把它抽象為以最小化客戶的總等待時間為目標的“累積時間的帶容量的車輛路徑問題”（The Cumulative Capacitated Vehicle Routing Problem）問題，該問題是VRP（Vehicle Routing Problem）問題的延伸。VRP最早是由Dantzig和Ramser于1959年首次提出，它是指一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是在滿足所有客戶的需求且在滿足一定的約束下，達到路程最短、成本最小、耗時最少等目的。VRP已被證明是一個NP難問題。

CCVRP也是一個NP難問題，傳統的精確求解方法例如分支定界法難以解決大規模的數據，因此一般采用啟發式算法。例如文獻[1]就采取了一種Memetic Algorithm的進化算法，由于解決CCVRP的案例不多，所以本文的實驗結果也主要與[1]對比；文獻[2]采取了一種變鄰域搜索的方式；文獻[3]采用了大鄰域搜索方法；文獻[6]則主要是一種加入了貪心的禁忌搜索。本文的求解方法是前期利用遺傳算法[10]的快速收斂性，查找最優解集空間，后期再結合用模擬退火[4]，進行細致的局部搜索，從而找到較優的問題的解。

1　數學模型的建立

我們把n個分布在各地的電力設備看作CCVRP問題中的服務點,m個維護人員看作CCVRP中的車輛，可描述如下：在圖G=（V，E）中，服務點集合為{0，1，2，…，n}，R表示安排的車輛集合，Q表示車輛的容量限制，表示從i到j的花費，tik表示第k輛車到達i的時間花費，xkij是一個布爾值，如果它是1，說明第k輛車經過了（i，j）這條邊，反之則表示沒有經過，有如下整數規劃模型：

其中（1）是保證得到最小目標函數值，（2）保證派出去的車都能回來，（3）保證每個客戶都只被服務一次，（4）保證每條路線上車的運輸量都不超過容量限制，（5）跟（6）保證每條路徑都以0為起點和終點，（7）保證當j在i后被車輛k服務，則比大，M是一個足夠大的值，目的是防止出現環路。

2　算法的實現

2.1設計思路

文獻[1]中采取的Memetic Algorithm算法是每次遺傳迭代后都采用一次局部搜索。為了找到全局最優解，在初期需要有較大的概率接受差解。這樣一來，初期與單純使用遺傳算法所得到的種群質量差別并不是很大，可是時間花費卻加大了。所以我們在前期只是單純使用遺傳算法，利用它的快速收斂性，找到較優的解集，而在后期遺傳算法效率下降的時候，我們采用一邊迭代一般局部搜索（模擬退火[4]）的方式。對于何時該加入局部搜索，程序每次用遺傳算法迭代都記錄下種群的最優解，當出現連續多次最優解沒有明顯提高的時候，就進入算法的下一步（本文是用連續四次的方差來衡量）。

實驗結果表明，采用這種方式可以得到較好的結果，在時間開銷上也有了較好的表現。

2.2遺傳算法

遺傳算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。它采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳算法的這些性質，已被人們廣泛地應用于組合優化、機器學習、信號處理、自適應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。其基本運算過程如下：

（1）初始化種群：設置進化代數計數器N=0，設置最大進化代數M，產生M個個體作為初始化種群P（0）。

（2）個體評價：計算群體P（N）中各個個體的適應度。

（3）選擇運算：對當代種群群體進行選擇。選擇的目的是把適應度更高的個體遺傳到下一代或選擇它們進行交配從而產生適應度較高的子代遺傳到下一代。

（4）交叉運算：選取兩個或者多個種群內的個體進行交叉運算。這是遺傳算法的核心步驟。

（5）變異運算：對種群內的每個個體以一定的幾率進行變異，以達到跳出局部最優解的作用。

經過選擇、交叉、變異后得到下一代種群P（N+1）。

（6）如果N==M，程序終止，否則N=N+1，返回步驟（2）。

本文中采用的遺傳算法和上述步驟基本一致，但在初始化種群，算子概率的確定以及選擇策略上有所改進，使效果更好。

其中，初始化過程沒有采取隨機化，而是帶有一定的策略，獲得較為優秀的初始群體，算子概率的確定則是采取了自適應的動態變化方式，選擇策略也放棄了傳統的輪盤賭，采取了競爭選擇的方式。下文還會詳細論述。

2.3基因編碼

采用整數編碼的形式對它進行編碼，不同的排列方式代表不同的路徑安排，再設計適應度函數對不同的路徑進行劃分。假設有n個客戶，那么（1，2，…，n）表示順序服務客戶1~客戶n。

2.4計算適應度

根據編碼方式，我們在滿足限制條件的前提下采用文獻[10]介紹的一種劃分路徑方式，運用動態規劃的思想，每次增加一輛車后，都對每個節點進行一次松弛，該算法的復雜度為O（n2）。

以車輛的最大數目為3，最大服務量為10為例。

①如圖1所示，小括號中數字表示該點需要的服務量。

圖1　

②當只有一輛車的時候，最多只能到達b節點，用Pki記錄在第k次迭代過程中0~i節點的最優路徑，方框內表示到當前節點的最短距離。

圖2　

③繼續增加車輛，對以上一輪經過的節點進行更新（如b節點的值被更新為45）。

圖3　

④重復上述步驟，直到結束。

圖4　

得出最優路徑。

圖5　

2.5種群初始化

由經驗可知，一輛車集中訪問一片區域往往可以得到較優的解集，如下圖所示：

圖6　

以笛卡爾坐標系為例，我們把每個坐標點按照x坐標由小到大排序，將排序后的數列作為種群的初始解，以此獲得質量較高的第一代種群。

2.6交叉

在交叉與變異的概率的確定上，我們采取了自適應的概率計算方式，公式如下：

Pc表示交叉概率，其中Pc1=0.9，Pc2=0.6

Pm表示變異概率，其中Pm1=0.1，Pm2=0.001

favg表示種群的平均適應度

fmax表示需要交叉的兩個個體中適應度較大的那個值

f表示被選擇個體的適應度

這樣，我們可以保證適應度較大的個體有較小的交叉和變異概率，從而在競爭選擇的過程中被很好地保存下來。

交叉方式選擇了比較經典的匹配交叉（PMX），我們先隨機產生兩個交叉點，定義這兩點間的區域為匹配區域，并用交換兩個父代的匹配區域。

父代A：872|130|9546

父代B：983|567|1420變為：

TEMP A:872|567|9546

TEMP B:983|130|1420

對于TEMP A、TEMP B中匹配區域以外出現的數碼重復，要依據匹配區域內的位置逐一進行替換。匹配關系：1〈—〉5，3〈—〉6，7〈—〉0。得到匹配后的結果如下所示：

子代A：802|567|9143

子代B：986|130|5427

2.7種群選擇

實驗初期采用的是傳統的輪盤賭策略，結果發現這種策略的效果并不理想。所以我們采取了競爭選擇的策略，主旨思想就是每次從種群里任意選擇兩個種群，選擇當中較大的那個代入下一次迭代過程（假如遇到相同的則都不選擇），然后再將其全部放回，重復這一步驟直到選擇完成。

2.8局部搜索和變異

局部搜索我們采用的是文獻[4]中的模擬退火方式，選擇了較低的初始溫度t0=30以及L=1000的馬爾可夫鏈長，以e（-ΔE/kt）的概率接受新解（ΔE為新解與原始解的適應度大小的差值），其產生新解的方式和變異的方式一致，都有下面兩種：

（1）2-opt

隨機選取兩點i和j，將i之前的路徑和j之后的路徑不變地添加到新路徑中，將i到j之間的路徑翻轉其編號后添加到新路徑中。例如原路徑為ABCDEFG，若我們隨機選取的區間為（CDEF），則進行2-opt操作后得到的新路徑為ABFEDCG。

（2）隨機產生三個位點，將1，2位點間的基因與2，3位點間的基因左右交換。例如對于路徑ABCDFE，我們選擇了ACF這三個位點，執行交換后得到新路徑ADCBF。

實驗初期還采取了隨機交換兩個點位置的這種變化策略，但實驗過程中發現這并沒有提高解的質量。

3　程序框架

程序的大體框架如下：generation〈—0

initial（）//初始化種群

while（generation〈maxgeneration）C

hoose（）//選擇交叉的子代C

rossover（）//子代交叉產生新的子代Mutation（）//子代變異產生新的子代

If（judge（））//根據前幾次方差判斷遺傳算法的收斂速度，如果速度較慢，就開始調用局部搜索

Localsearch（）//用模擬退火進行局部搜索，更新子代

endIf

Preservethebest（）//保存最優解

endwhile

4　實驗及運行結果

我們使用C編程，程序運行環境為i3處理器，2.30GHz，4GB內存，64位Win7操作系統，而文獻[1]中也是用C編程，程序運行環境為3.4GHz，1GB內存，WinXP操作系統。測試了文獻[1]中的數據。

文獻[1]中Table 1作者的數據是從文獻[6]中獲得。其解決的主要是TRP問題，TRP問題則是在TSP問題上求解最小路徑和的變式，也就是本文所求的CCVRP問題的特例（其車輛數為1）。

文獻[1]中的作者是用實驗數據的下界與實際實驗數據來計算相差的百分比，從而進行度量，而且只考慮用一種車的情況。其下界的計算方法是構建n個點的最小生成樹。那么有：

其中，wi是將這棵最小生成樹的邊按照升序方式排序后第i條邊的權值。其中，作者給出了范圍為10~ 500這6種規模的數據，每個數據規模又有20個算例。實驗結果如表1所示，注意相差的比例是20個算例的平均值與下界的差距，可以看出，我們的結果與文獻[1]的結果差距不大。

表2是與文獻[1]中的Table 3做的比較，文獻采取的方法是利用TSP問題的數據（數據來源：http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/），不考慮容量限制，給出固定車輛數生出CCVRP的算例。由該表同樣看出我們的算法表現同樣較好。

表1　TRP實驗對比結果

表2　CCVRP結果

另外，我們還利用某市供電局的變壓器分布數據，隨機選取41個點，對5個工作人員進行任務指派。得出的效果圖如圖7所示。

圖7　實際效果圖

5　結語

本文研究了電力維護人員調度問題，并把它建模為累積時間的帶容量的車輛路徑問題（CCVRP）。我們給出了一種用利用遺傳算法對CCVRP進行求解的方法，并結合模擬退火算法對局部解進行了優化。實驗表明我們的求解結果與對比文獻差距不大。同時，我們用實際電力維護的數據對算法進行測試，因此該方法具有較強的實際意義。

[1]Ngueveu S U，Prins C，Calvo R W.An Effective Memetic Algorithm for the Cumulative Capacitated Vehicle Routing Problem[J]. Computers&Operations Research，2010，37（11）:1877~1885

[2]Croes G A.A Method for Solving Traveling-Salesman Problems[J].Operations Research，1958，6（6）:791~812

[3]Ribeiro G M，Laporte G.An Adaptive Large Neighborhood Search Heuristic for the Cumulative Capacitated Vehicle Routing Problem [J].Computers&Operations Research，2012，39（3）:728~735

[4]Osman I H.Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem[J].Annals of Operations Research，1993，41（4）:421~451

[5]Gendreau M，Hertz A，Laporte G.A Tabu Search Heuristic for the Vehicle Routing Problem[J].Management Science，1994，40（10）: 1276~1290

[6]Salehipour A，S?rensen K，Goos P，BRAYSY，O.An Efficient GRASP+VND Metaheuristic for the Traveling Repairman Problem[R]. University of Antwerp，Faculty of Applied Economics，2008

[7]Campbell A M，Vandenbussche D，Hermann W.Routing for Relief Efforts[J].Transportation Science，2008，42（2）:127~145

[8]Barbarosoglu G，Ozgur D.A Tabu Search Algorithm for the Vehicle Routing Problem[J].Computers&Operations Research，1999，26（3）:255~270

[9]Hiquebran D T，Alfa A S，Shapiro J A，et al.A Revised Simulated Annealing and Cluster-First Route-Second Algorithm Applied to the Vehicle Routing Problem[J].Engineering Optimization，1993，22（2）:77~107

[10]Prins C.A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem[J].Computers&Operations Research，2004，31（12）:1985~2002

[11]Croes G A.A Method for Solving Traveling-Salesman Problems[J].Operations Research，1958，6（6）:791~812

[12]李寧馨.采用不同算法求解車輛路徑問題的對比分析[J].重慶工商大學學報（自然科學版），2014，5:016

王柏根，男，工程師，工學學士，研究方向為計算機應用與工程管理

汪勛，男，本科，研究方向為算法設計與分析

張子臻，男，講師，研究方向為最優化理論、人工智能

Cumulative Time;Capacitated Vehicle Routing Problem;Genetic Algorithm;Simulated Annealing

Application of Genetic Algorithm in Scheduling Problem of Maintaining Electric Metering Devices

WANG Bo-gen1，WANG Xun2，ZHANG Zi-zhen2

（1.Power Grid Co.，Guangdong Dongguan Power Supply Bureau，Dongguan 523000）（2.School of Mobile Information Engineering，Sun Yat-Sen University，Zhuhai 519000）

With the rapid development of the power equipment and demand,electricity maintenance issues become increasingly prominent.How to arrange the maintenaners into a timely power optimization problem needs to be solved.Aiming at this problem,proposes a model called the Cumulative Capacitated Vehicle Routing Problem.CCVRP is a variation of the classical Capacitated Vehicle Routing Problem in which the objective is to minimize the sum of waiting times at customers.Establishes a genetic algorithm combined with a simulated annealing algorithm for local search.Experiments indicate that the algorithm is able to solve the problem effectively.

1007-1423（2015）12-0003-06

10.3969/j.issn.1007-1423.2015.12.001

2015-03-17

2015-04-09