基于遺傳算法的通信基站維護(hù)車輛調(diào)度問題研究*

姚仲敏,沈玉會,盧艷陽

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

基于遺傳算法的通信基站維護(hù)車輛調(diào)度問題研究*

姚仲敏,沈玉會,盧艷陽

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

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

車輛調(diào)度 遺傳算法 最小路徑 基站維護(hù)

0 引 言

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

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

1.1 調(diào)度思想

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

1.2 課題的數(shù)學(xué)模型

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

式(1)為目標(biāo)函數(shù),表示車輛完成維護(hù)任務(wù)的總距離。

式(2)表示基站請求的處理業(yè)務(wù)不能超過調(diào)度能夠處理的范圍。

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

式(4)表示一次調(diào)度最多只能從一個駐點發(fā)出并且只能被執(zhí)行一次。

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

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

2 遺傳算法及實現(xiàn)方法

2.1 遺傳算法

基站維護(hù)車輛調(diào)度信息參數(shù)集稱GA,起源于對生物系統(tǒng)所進(jìn)行的計算機(jī)模擬研究,由美國Michigan大學(xué)的Hoolland教授及其學(xué)生率先提出,遺傳算法具有較高的搜索能力和極強(qiáng)的魯棒性,被廣泛應(yīng)用在生產(chǎn)調(diào)度問題,如單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配、物流運(yùn)輸?shù)确矫鎇6-9]。遺傳算法的流程如圖1所示。

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

2.2 目標(biāo)優(yōu)化模型的遺傳算法求解過程

文中采用整數(shù)排列編碼?，F(xiàn)舉例說明:

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

1)產(chǎn)生一個1～3的隨機(jī)數(shù),表示由哪個駐點調(diào)度。如駐點1。

2)產(chǎn)生一個1～3的隨機(jī)數(shù),表示出哪種類型的任務(wù),如調(diào)度中心指派的任務(wù)A對應(yīng)1,任務(wù)B對應(yīng)2,任務(wù)C對應(yīng)3。

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

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

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

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

7)依次類推。

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

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

選取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。課題遺傳算法優(yōu)化的目標(biāo)即為選擇適應(yīng)度函數(shù)值盡可能大的染色體,fitness值越大就表示調(diào)度路徑越短,染色體越優(yōu)質(zhì),反之越劣質(zhì)。最終finesse值最大的染色體被選中,相應(yīng)染色體即為最優(yōu)解。

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

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

1)產(chǎn)生兩個[1,8]區(qū)間內(nèi)的隨機(jī)整數(shù)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)交叉后,同一個個體中,不重復(fù)的數(shù)字保留,沖突的基站編號采用部分映射的方法消除,利用中間的對應(yīng)關(guān)系進(jìn)行映射,交叉后結(jié)果為:

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

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

比較簡單的終止方式為規(guī)定最大的迭代次數(shù)Gmax,當(dāng)遺傳算法的迭代次數(shù)達(dá)到T時,停止操作,將結(jié)果輸出[13]。

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

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

由表1可以看出,初始種群大小為80的運(yùn)算結(jié)果比較好并且相對穩(wěn)定。當(dāng)初始種群大小為80時,比較最大迭代次數(shù)不同對結(jié)果的影響,如表2所示。

表2 最大迭代次數(shù)不同時的運(yùn)算結(jié)果Table 2 Operation results of different iterations number

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

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

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

選擇交叉率,變異率及選擇率的方法類似,保證其他基本參數(shù)不變,變換被測參數(shù)的數(shù)值,最終比較結(jié)果優(yōu)劣選擇合適值。本文在參考其他文獻(xiàn)的基礎(chǔ)上對其進(jìn)行設(shè)定和實驗比較,最終確定選用值,在此不再描述。

3 MATLAB仿真

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

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

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

圖2 車輛最優(yōu)調(diào)度路徑Fig.2 Vehicle optimum scheduling path

遺傳進(jìn)化曲線如圖3所示。

圖3 基站數(shù)為25時的遺傳進(jìn)化曲線Fig.3 Genetic evolution curve when base stations number is 25

由圖2可知,當(dāng)遺傳迭代次數(shù)為4 460時,得到最優(yōu)路徑。由圖2的曲線可以看出,調(diào)度中心從5個駐點同時調(diào)度車輛分別為25個故障基站進(jìn)行服務(wù)的最優(yōu)調(diào)度方案為:

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

圖4是基站數(shù)為45時,第3次獨(dú)立運(yùn)算得到的一條進(jìn)化曲線。

圖4 基站數(shù)為45時的遺傳進(jìn)化曲線Fig.4 Genetic evolution curve when base stations number is 45

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

4 結(jié) 語

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

[1] 代平.淺談通信基站的巡檢及其重要性[J].通信管理與技術(shù),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].河北:華北電力大學(xué),2012.

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

[3] 趙開權(quán),施國梁.基于無線傳感網(wǎng)絡(luò)的車輛管理平臺[J].通信技術(shù),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實現(xiàn)及應(yīng)用[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ìn)遺傳算法的物流配送路徑優(yōu)化[J].系統(tǒng)工程,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] 王少蕾,陳維義,周菲.艦艇編隊防空多平臺多類型武器火力分配優(yōu)化[J].計算機(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—)女,碩士研究生,主要研究方向為物聯(lián)網(wǎng)技術(shù);

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

盧艷陽(1988—)男,碩士研究生,主要研究方向為物聯(lián)網(wǎng)技術(shù)。

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—),女,學(xué)士,教授,碩士生導(dǎo)師,主要研究方向為交換技術(shù)、信息傳輸處理;

2014-05-27;

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

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

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