基于遺傳算法的通信基站維護車輛調度問題研究*

姚仲敏,沈玉會,盧艷陽

(齊齊哈爾大學通信與電子工程學院,黑龍江齊齊哈爾161000)

基于遺傳算法的通信基站維護車輛調度問題研究*

姚仲敏,沈玉會,盧艷陽

(齊齊哈爾大學通信與電子工程學院,黑龍江齊齊哈爾161000)

通信行業基站維護車輛的傳統調度比較隨意,日常維護沒有全面的考慮到基站的次序和維護車輛行走路徑的最小化問題。針對上述情況,借助遺傳算法,提出一種由調度中心統一指揮,使代維公司多個駐點合理派發車輛,以最小路徑和最佳次序遍歷基站進行維護的方法。首先建立數學模型,然后根據模型的特點,采用整數排列編碼,引入遺傳算子,最后用MATLAB編程實現模型的求解。仿真結果驗證了算法的可行性。

車輛調度 遺傳算法 最小路徑 基站維護

0 引 言

基站是網絡通信的基礎,需要不斷的更新與維護來保障通信網絡的暢通[1]。通信基站分布廣泛,傳統的基站維護車輛的調度比較隨意,沒有全面的考慮到基站的服務次序和車輛行走路徑的最小化問題。目前通信行業的車輛管理大都實行外包,由代維公司隨機分配車輛,沒有完整的調度系統,管理也比較粗放。調查發現,運營商要求代維公司平均一個月要對基站全面巡檢一次,一個區的基站數在200個左右,一輛車一天能跑的基站數為10個左右,無序隨機發車巡檢所造成的油耗累積起來是不可忽視的。在促進節能減排已成為大風尚的今天,現有各駐點未能從經濟角度合理安排基站服務次序及車輛行走的路徑[2-4]。針對上述情況,根據待服務基站的經緯度,提出了一種基于遺傳算法的基站維護車輛調度辦法,使代維公司多個駐點合理派發車輛,以最小路徑和最佳次序遍歷各個基站進行服務。建立合適的數學模型來描述課題的思想,借助遺傳算法相關理論進行最短調度路徑的設計和實現,并用Matlab進行仿真[5]。仿真結果表明,本文提出的遺傳算法調度辦法可行,能夠滿足課題經濟高效的要求。

1 數學模型的建立

1.1 調度思想

本文調度內容描述如下:通過合理安排車輛和選擇行車路徑,確定從各駐點到基站的維護方案,使得出車路徑最小。該維護方案不但要確定如何調度車輛,還要明確每輛車從哪個駐點出發依次為哪些基站提供服務。

1.2 課題的數學模型

設I為代維公司駐點集合,i表示駐點;J為基站集合,j表示基站;K為調度類型的集合,即由調度中心指派的某個駐點執行特定的某種任務,k表示一次任務的調度,用路徑表示;qj表示基站j請求的服務;H為基站需求集合,h為任務碼,表示車輛k執行并勝任h任務處理,表示駐點i具備h類型的處理能力;dij表示駐點i到基站j的距離;Dijk= 1表示路徑k是從駐點i出發到基站j,否則Dijk=0;

式(1)為目標函數,表示車輛完成維護任務的總距離。

式(2)表示基站請求的處理業務不能超過調度能夠處理的范圍。

式(3)表示一個基站可以并且只能被服務一次。

式(4)表示一次調度最多只能從一個駐點發出并且只能被執行一次。

式(5)表示每個駐點的車輛派出后又回到該駐點,使調度形成一個閉環。

上述模型是建立在基站維護一個周期的范圍之內的,式(3)和式(4)都牽涉到一個月的巡檢任務,故設定時間期限不大于30天。

2 遺傳算法及實現方法

2.1 遺傳算法

基站維護車輛調度信息參數集稱GA,起源于對生物系統所進行的計算機模擬研究,由美國Michigan大學的Hoolland教授及其學生率先提出,遺傳算法具有較高的搜索能力和極強的魯棒性,被廣泛應用在生產調度問題,如單件生產車間調度、流水線生產車間調度、生產規劃、任務分配、物流運輸等方面[6-9]。遺傳算法的流程如圖1所示。

圖1 基于遺傳算法的基站維護車輛調度流程Fig.1 Flow chart of communication base stations maintenance vehicle scheduling strategy based on genetic algorithm

2.2 目標優化模型的遺傳算法求解過程

文中采用整數排列編碼?，F舉例說明:

假設代維公司調度中心下設有3個駐點(編號1,2,3),每個駐點都具備獨立完成A(巡檢),B(CQT撥測),C(日常故障處理)這3種任務的能力,需要為8個基站(編號為1～8)服務。設染色體的編碼為24536871通過下面編碼和解碼可以得到這個染色體對應的一個調度方案:

1)產生一個1～3的隨機數,表示由哪個駐點調度。如駐點1。

2)產生一個1～3的隨機數,表示出哪種類型的任務,如調度中心指派的任務A對應1,任務B對應2,任務C對應3。

3)將基站2作為第一個需要服務的對象加入到調度路徑a中。

4)確定基站2的需求信息是否與此次調度類型匹配,若匹配,將4作為第二個被服務對象加入路徑a然后再判斷,若還匹配,將5作為第三個對象加入路徑a進行判斷。

5)若基站5判斷結果為不匹配,則說明基站5不能加入路徑a。

6)繼續判斷基站3,匹配,加入路徑a。

7)依次類推。

得到第一條調度路徑a:A1a-2-4-3-Aa1表示調度中心從1號駐點發車依次為2,4,5號基站進行巡檢,并且完成工作后回到原駐點。其中A1a表示第1號駐點出調度中心指派的任務A,并且生成路徑a?？蓪φ{度中心下發的任務A/B/C同時進行判斷,重復上述步驟直到遍歷所有的待服務基站,假設得到一個完整的配送方案:A1a-2-4-3-C2b-5-6-7--B3c-8-1,它表示調度中心首先從駐點1派車執行任務A依次為2,4,3號基站服務,同時駐點2出車執行任務C依次對基站5,6,7服務,駐點3出車執行任務B依次對基站8,1服務,并生成三條行車路線,分別為a,b,c。每次調度從哪個駐點出發的車和員工完成任務后再回到原駐點。不難看出,本文選用的編碼和解碼方式能夠滿足數學模型的所有約束,表明用這種染色體編碼和解碼得到可行解的方式是可行的。

隨機生成M個個體作為初始群體P0,對其進行解碼可得每個個體對應的基站維護方案,前文染色體24536871即可看做一個初始群體。

選取目標函數的倒數作為適應度函數。課題遺傳算法優化的目標即為選擇適應度函數值盡可能大的染色體,fitness值越大就表示調度路徑越短,染色體越優質,反之越劣質。最終finesse值最大的染色體被選中,相應染色體即為最優解。

選擇操作即從群體中以一定的概率選擇個體到新的群體中,個體被選中的概率跟個體適應度值有關,個體適應度值越大,被選中的概率就越大[10]。

采用部分映射雜交,假定基站數為8,每組重復以下過程:

1)產生兩個[1,8]區間內的隨機整數X1=3,X2=5,染色體2 4|5 3 6|8 7 1

3 6|4 2 7|5 1 8

交叉操作**|4 2 7|8*1

**|5 3 6|*1 8

2)交叉后,同一個個體中,不重復的數字保留,沖突的基站編號采用部分映射的方法消除,利用中間的對應關系進行映射,交叉后結果為:

控制個體交叉數目的參數MC=PC·M,其中,PC為交叉概率,一般遺傳算法交叉概率為0.4～0. 9,M為群體的個體數[11]。

變異概率PM=B/ML,其中B表示每一代中突變基因的個數,且基因突變的位置隨機,L表示個體的基因個數,M表示群體中個體的數目,PM通常在0.01～0.1之間[12]。

比較簡單的終止方式為規定最大的迭代次數Gmax,當遺傳算法的迭代次數達到T時,停止操作,將結果輸出[13]。

以本文研究的30個點進行實驗,確定相對合適的遺傳算法初始種群和最大迭代次數。

當最大迭代次數為500時,比較不同初始種群對運算結果的影響,如表1所示。(表1～3的路徑總距離是在matlab仿真所得圖像的軌跡總線長基礎上借助谷歌地圖換算得來的。表中的時間表示的是本文遺傳算法的運算時間。)

由表1可以看出,初始種群大小為80的運算結果比較好并且相對穩定。當初始種群大小為80時,比較最大迭代次數不同對結果的影響,如表2所示。

表2 最大迭代次數不同時的運算結果Table 2 Operation results of different iterations number

表3 最大迭代次數不同時十次結果平均值Table 3 Average results of ten times when iterations number is different

由于遺傳算法是一種啟發式算法,用它能夠找出問題的較優解,但并不總是最優解,所以由上述表可以看出每次運行的結果不一定相同。所以,遺傳算法所謂的最優解都是相對的。

由表2和表3可以看出隨著迭代次數的增加,最小路徑呈現優化的趨勢,但并不是說迭代次數越大越好。如表2中Gmax=3 000時取得的線長9.856 2明顯優于Gmax=4 000時的結果。實驗中發現,當Gmax=5 000時,多次運算總線長落在9.726 6這個結果的比例達到了75%,運算結果的平均值為9.790 3,相對誤差為6.5‰,運行時間雖然較其他情況下長,但是結果的穩定性和優良性比較好,所以本文選擇的最大遺傳迭代次數為5 000。

選擇交叉率,變異率及選擇率的方法類似,保證其他基本參數不變,變換被測參數的數值,最終比較結果優劣選擇合適值。本文在參考其他文獻的基礎上對其進行設定和實驗比較,最終確定選用值,在此不再描述。

3 MATLAB仿真

為了節省仿真時間,本文沒有選用大量的基站數據,但仿真原理是相同的。而且所選基站數量對于日常調度一個駐點車輛進行基站維護的工作量來說更加適用。

假設已知某調度中心下屬的5個駐點(編號1～5)和所管轄的25個基站(編號6～30)的地理位置,并且假設出車后所行路線均為直線。

設置遺傳算法的參數:初始種群N=80,交叉率0.8,變異率0.02,選擇率0.2,最大遺傳迭代次數為5 000,通過Matlab7.0編程計算得到一個最優調度方案,如圖2所示,總線長=9.726 6,遺傳迭代次數=4 460。

圖2 車輛最優調度路徑Fig.2 Vehicle optimum scheduling path

遺傳進化曲線如圖3所示。

圖3 基站數為25時的遺傳進化曲線Fig.3 Genetic evolution curve when base stations number is 25

由圖2可知,當遺傳迭代次數為4 460時,得到最優路徑。由圖2的曲線可以看出,調度中心從5個駐點同時調度車輛分別為25個故障基站進行服務的最優調度方案為:

式(1)表示駐點1派車依次為基站15,25進行日常巡檢,然后對基站14,13進行CQT撥測,完成后對基站11,26進行故障處理。生成一條路徑a;式(2)～式(5)類同。上述順序是按照順時針排列的,逆時針結果是一樣的。從圖3的遺傳進化曲線可以看出,隨著遺傳代數的增加,最優個體適應度的值很快下降并逐漸趨于穩定。

圖4是基站數為45時,第3次獨立運算得到的一條進化曲線。

圖4 基站數為45時的遺傳進化曲線Fig.4 Genetic evolution curve when base stations number is 45

從圖3和圖4可以看出,對不同的目標數量和初始種群,利用本文遺傳算法,曲線總能夠收斂,即總能得到問題的最優解,所以,本文的遺傳算法是可行的、有效的。

4 結 語

本文利用遺傳算法研究調度中心從多駐點調度基站維護車輛的問題。首先建立了一個由多個駐點發車,對多種任務需求的基站進行服務的數學模型。模型秉承調度路徑最小的原則,能夠體現企業的節能減排,省時省力的經濟意識。仿真實現了對5個駐點25個基站3種任務類型調度問題的求解。結果表明,本文設計的算法和遺傳操作策略對于調度問題的求解有很好的適應性。

[1] 代平.淺談通信基站的巡檢及其重要性[J].通信管理與技術,2013,35(03):47-48.

DAIPing.The Maintenance And Importance of Communication Base Station[J].Communication Management& Technology,2013,35(3):47-48.

[2] 陳永紅.無線移動通信基站巡檢的研究[D].河北:華北電力大學,2012.

CHEN Yong-hong.The Maintenance of The Wireless Mobile Communication Base Station[D].Journal of North China Electric Power University,2012.

[3] 趙開權,施國梁.基于無線傳感網絡的車輛管理平臺[J].通信技術,2011,44(11):59-62.

ZHAO Kai-quan,SHI Guo-liang.Vehicle Management Platform Based on Wireless Sensor Network[J].Communication Technique,2011,44(11):59-62.

[4] 陳著.移動通信基站巡檢研究[J].中國新通信,2014, 16(02):17-18.

CHEN Zhu.The Maintenance of Mobile Communication Base Station[J].China New Communication,2014,16 (2):17-18.

[5] 王娟.遺傳算法的Matlab實現及應用[J].信息與電腦:理論版,2012,24(06):103-104.

WANG Juan.The Implementation and Application of Matlab Based on Genetic Algorithm[J].Information&Computer (THEORY EDITION),2012,24(6):103-104.

[6] ZEGORDI S H,Abadi I N,Nia M A.A Novel Genetic Algorithm forSolvingProductionandTransportation Scheduling In A Two-stage Supply Chain[J].Computers &Industrial Engineering,2010,58(03):373-381.

[7] VIDAL T,Crainic T G,Gendreau M,et al.A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems[J].Operations Research,2012, 60(03):611-624.

[8] ATHANASIOS C.Spanos,STAVROS T.Ponis,ILIAS P.Tatsiopoulos,IOANNIS T.Christou,ELENA Rokou. A New Hybrid Parallel Genetic Algorithm for The Jobshop Scheduling Problem[J].International Transactions In Operational Research,2014,21(03):479-499.

[9] 羅勇,陳治亞.基于改進遺傳算法的物流配送路徑優化[J].系統工程,2012,30(08):118-122.

LUO Yong,CHEN Georgia.The Optimization of Logistics Distribution Routing Based on Improved Genetic Algorithm[J].Systems Engineering,2012,30(008):118-122.

[10] TASAN A S,GEN M.A Genetic Algorithm Based Approach to Vehicle Routing Problem With Simultaneous Pick-up And Deliveries[J].Computers&Industrial Engineering,2012,62(03):755-761.

[11] NAZIF H,LEE L S.Optimized Crossover Genetic Algorithm for Vehicle Routing Problem With Time Windows [J].American Journal of Applied Sciences,2010, 7(01):95-101.

[12] EDISON E,SHIMA T.Integrated Task Assignment And Path Optimization for Cooperating Uninhabited Aerial Vehicles Using Genetic Algorithms[J].Computers& Operations Research,2011,38(01):340-356.

[13] 王少蕾,陳維義,周菲.艦艇編隊防空多平臺多類型武器火力分配優化[J].計算機仿真,2014,31(01): 18-21.

WANG Shao-lei,CHEN Wei-yi,ZHOU Fei.The Optimization of Multi Platform and Multi Types of Naval Fleet Air Defense Weapons Fire Distribution[J].Computer Simulation,2014,31(1):18-21.

YAO Zhong-min(1959-),female,B. Sci.,professor,M.Sci.tutor,majoring in the exchange of technology and information transfer process;

沈玉會(1987—)女,碩士研究生,主要研究方向為物聯網技術;

SHEN Yu-hui(1987-)female,graduate student,mainly engaged in IOT networking technology;

盧艷陽(1988—)男,碩士研究生,主要研究方向為物聯網技術。

LU Yan-yang(1988-)male,graduate student,mainly working at IOT technology.

Vehicle Scheduling for Base Stations Maintenance based on Genetic Algorithms

YAO Zhong-min,SHEN Yu-hui,LU yan-yang
(Communications and Electronics Engineering,Qiqihar University,Qiqihar Heilongjiang 161000,China)

The traditional vehicle scheduling for base-station maintenance is fairly casual in the communications industry,and not fully takes into account the order of base-station maintenance and the minimization of vehicle route.For the above,with the help of genetic algorithm,a maintenance method uniformly commanded by the dispatch center is proposed,thus enabling the multiple branches of communications to send vehicles reasonably,the vehicle to take the shortest path with optimal order,to traverse around all the alarm stations and provide service successfully.A mathematical model is firstly established,and based on the characteristics of the model,the genetic operator is introduced by integer arrangement code.Finally, the solution of the model is implemented by MATLAB programming.The simulation result indicates the feasibility of this algorithm.

base maintenance;vehicle scheduling;genetic algorithm;minimum path

TN918

A

1002-0802(2014)09-1053-05

10.3969/j.issn.1002-0802.2014.09.015

姚仲敏(1959—),女,學士,教授,碩士生導師,主要研究方向為交換技術、信息傳輸處理;

2014-05-27;

2014-06-27 Received date：2014-05-27;Revised date：2014-06-27

齊齊哈爾市科技攻關項目(No.GYGG-201106)

Foundation Item：Qiqihar Scientific and Technical Project(No.GYGG-201106)