基于遗传算法的通信基站维护车辆调度问题研究*

姚仲敏,沈玉会,卢艳阳

(齐齐哈尔大学通信与电子工程学院,黑龙江齐齐哈尔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 目标优化模型的遗传算法求解过程

文中采用整数排列编码。现举例说明:

假设代维公司调度中心下设有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)