姚仲敏,沈玉會(huì),盧艷陽(yáng)

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

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

姚仲敏,沈玉會(huì),盧艷陽(yáng)

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

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

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

0 引 言

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

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

1.1 調(diào)度思想

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

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

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

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

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

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

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

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

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

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

2.1 遺傳算法

基站維護(hù)車輛調(diào)度信息參數(shù)集稱GA,起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究,由美國(guó)Michigan大學(xué)的Hoolland教授及其學(xué)生率先提出,遺傳算法具有較高的搜索能力和極強(qiáng)的魯棒性,被廣泛應(yīng)用在生產(chǎn)調(diào)度問(wèn)題,如單件生產(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)化模型的遺傳算法求解過(guò)程

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

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

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

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

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

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

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

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

7)依次類推。

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

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

選取目標(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)解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 MATLAB仿真

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

本文利用遺傳算法研究調(diào)度中心從多駐點(diǎn)調(diào)度基站維護(hù)車輛的問(wèn)題。首先建立了一個(gè)由多個(gè)駐點(diǎn)發(fā)車,對(duì)多種任務(wù)需求的基站進(jìn)行服務(wù)的數(shù)學(xué)模型。模型秉承調(diào)度路徑最小的原則,能夠體現(xiàn)企業(yè)的節(jié)能減排,省時(shí)省力的經(jīng)濟(jì)意識(shí)。仿真實(shí)現(xiàn)了對(duì)5個(gè)駐點(diǎn)25個(gè)基站3種任務(wù)類型調(diào)度問(wèn)題的求解。結(jié)果表明,本文設(shè)計(jì)的算法和遺傳操作策略對(duì)于調(diào)度問(wèn)題的求解有很好的適應(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] 陳永紅.無(wú)線移動(dòng)通信基站巡檢的研究[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] 趙開(kāi)權(quán),施國(guó)梁.基于無(wú)線傳感網(wǎng)絡(luò)的車輛管理平臺(tái)[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] 陳著.移動(dòng)通信基站巡檢研究[J].中國(guó)新通信,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實(shí)現(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] 王少蕾,陳維義,周菲.艦艇編隊(duì)防空多平臺(tái)多類型武器火力分配優(yōu)化[J].計(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;

沈玉會(huì)(1987—)女,碩士研究生,主要研究方向?yàn)槲锫?lián)網(wǎng)技術(shù);

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

盧艷陽(yáng)(1988—)男,碩士研究生,主要研究方向?yàn)槲锫?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)師,主要研究方向?yàn)榻粨Q技術(shù)、信息傳輸處理;

2014-05-27;

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

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

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