基于蚁群算法的通信运营设备调度管理的研究

邢呈勇，刘 耘

（新疆大学 建筑工程学院，新疆 乌鲁木齐 830017）

0 引 言

随着通信技术的不断发展和进步，移动通信完成了由20世纪80年代1G模拟通信，向90年代2G语音和GPRS的更替，再迈向后期的3G语音数据业务的扩展，以及2010年开始的LTE数据业务+Volte技术。网络规模和覆盖不断得到提升和满足，为人民的生活提供了更多的便利性。现如今，5G新基建重要地位的确立，5G通信的应用和普及已经到来，使得5G网络建设和应用进入了快车道，使万物互联成为可能。对于网络建设初期阶段主要从无线网络的规划结合城市发展的角度，对通信设备进行安排部署。然而，随着城市化进程的发展，加之现阶段通信运营商多种网络制式共存，通信设备的能耗将持续增加，也成为各通信运营商关注的重点。基站功耗主要包括主设备功耗、空调等配套设施功耗以及配电和其他能耗等。现网中运行的2G、3G以及4G主设备大部分均采用BBU+RRU模式，主设备能耗也成为关注的重点。根据绿色和平、赛宝计量检测中心的相关研究分析，5G基站耗能主设备能耗（BBU和AAU）和空调能耗均占比46%，如图1所示。对于运营商而言，解决空调能耗及主设备相关的能耗问题成为了研究的重点。国内外对通信节能的研究均得到了长足的发展，各专家学者分别从规划站点数量、负荷分担、通信设备机房配套设备设施及智能关断算法等进行了相关研究。然而对于通信运营中设备的有效利用和合理调度的研究很少。本文拟从资源调度的角度，利用有限的现网资源，将空闲的运营设备调度至较忙站点，合理调度通信设备资源，既能提高设备资源的利用率，又能达到节能减排的目的。

图1 5G基站能耗分布（来源于网络）

1 调度问题相关的研究

基于调度路径问题的研究，文献[6]首先提出了如何解决配送路线优化的问题。相关行业的从业者和研究人员对提出的这个问题给予了极大的重视，很快成为组合优化、计算机应用技术、调度等复合学科研究的方向。许多专家不断发现新的配送路线选择问题并进行了大量的模拟仿真推理实验，各种解决方法和方案层出不穷。文献[7]对此问题进行了综述研究。文献[8]为了避免同一辆车配送不同产品混合的情况，提出了一种车辆车厢分割配送的遗传算法。文献[9]对LRP进行了详细的分类，提出物品流向、供/需特征、设施数量、运输车辆数量、车辆装载能力、设施容量、设施分级、计划期间、时间限制、目标数、模型数据类型。我国相应的概念虽然在20世纪90年代早期才逐渐出现，在配送路径优化研究领域有些落后，然而，在优化车辆运送路线方面已经取得了一些成果。各位专家学者应用禁忌搜索，粒子群优化和遗传算法等国际先进方法，解决了实际配送调度路径优化问题，在提高配送路径优化问题的便利性和结合性等方面并不逊色。文献[10]对具有多次访问的非配对接送车辆路径问题进行了相关的研究，为企业带来更大的降本增效空间。文献[11]运用改进蚁群算法，以车辆行驶里程最短和碳排放量最少为目标进行了相关研究。文献[12]运用改进遗传算法对时尚行业零售网点多品类取送货车辆整合拆分理论进行了研究。文献[13]基于顾客时间满意度的车辆路径问题，允许多次经过同一需求点的情况发生，而需求点只能被同一辆车服务一次的限制，验证了模型的有效性。文献[14]通过综述前人研究的VRPSPD（Vehicle Routing Problem with Simultaneous Pickup and Delivery）研究成果及方向，提出了同时最小化运输成本与最小化各路径间最大长度差的双目标模型对VRPSPD进行了相关研究。本文结合通信运营设备资源的特征，通过对国际国内资源调度的研究进行相关研学，将不同类型及不同厂家的通信运营设备的施工时间及运输时间综合考虑以适应客户满意度，制定适用于通信运营设备拆分的调度模型，同时运用计算机技术，应用蚁群算法进行寻优操作，对其综合调度进行研究。

2 问题描述和假设

2.1 问题的描述

对于现网运营的基站站点，其载频数量过大而处于闲置状态时，耗电量不会实质性降低，而会增加电能的资源消耗。如果能够合理地调度通信设备资源，将闲置通信运营设备应用于业务量需求大的站点，既能使其资源得到充分利用又节约其采购成本。基于此，提出对通信设备资源的调度以达到降本增效的目的。通信节能减排的调度问题，主要关注的是基站站点较长时段的业务量情况以及增长减少趋势分析。通过后台指标监控获取数据分析各个站点及其扇区业务量的增长情况，得出各站点对通信运营设备的需求量。对于通信设备站点的调度如图2所示。

图2 站点设备调度图示例

2.2 问题的假设

在考虑通信设备资源调度问题中，通信运营商网络维护人员拥有一定数量的相同车辆，假设车辆匀速行驶。车辆从公司驻地出发在一定行程的工作时间内完成各站点之间的设备调度。每个站点的拆装设备可由不同的车辆维护人员分批次完成，但同一站点的同类设备的需求不可拆分。在车辆最大工作时间内满足所有站点设备资源需求的情况下，实现车辆数量和行驶距离之和最小化。

假设站点区域内共用={0，1，2，…，}个顶点，其中0表示调度中心，其余顶点为各需求和提供设备站点。={1，2，…，}为设备类集合，={1，2，…，}为配送车辆集合。顶点与顶点之间的车辆行驶距离为D，配送车辆的最大载重量为Capacity，配送车辆的最大行程时间为。

此问题为考虑多目标的车辆调度问题，为便于模型的建立和求解，结合项目实地调研，将车辆数量和行驶距离以及施工人员作业转换为成本去求解。通过实地调研，通信设备运营调度数据如表1所示。

表1 通信运营设备调研数据

3 模型的建立

3.1 数据的初步处理

以往对于路径距离的研究都是考虑运用勾股定理计算任意2个节点距离的方法，但实际中应该运用实际驾驶距离计算更切合实际，因此，本文提出通过Python结合高德地图API获取道路的实际驾驶路线进行驾驶距离的选取。通过该改进，不仅可以提高运行速度，而且提高了系统的计算精度（高德地图API返回的数据精度达到米的级别）。

主要涉及到高德地图API的使用，该接口可以通过各站点的经纬度信息获取实际道路的驾驶距离，该接口的服务地址为：http://restapi.amap.com/v3/distance，接口请求包括origins（起点）、destination（终点）、out_lng（初始点经度），out_lat（初始点纬度），des_lng（目的站点经度），des_lat（目的站点纬度），用json读取Excel里各站点经纬度信息，返回驾驶距离新建Excel中，这里得到的任意两节点间的距离d是实际道路的驾驶距离，更有一定的实用性。表2为站点数据的输入信息，表3为获取到的路径数据信息。

表2 通信站点位置经纬度信息

表3 输出站点驾驶距离信息

3.2 模型的建立

根据上述对通信运营设备调度问题的描述及分析，运用站点间的实际驾驶距离进行通信设备调度优化，考虑不同通信运营设备的情形，建立了调用变量的通信运营设备调度问题模型。

目标函数：

约束条件：

其中:为公司驻地/调配中心；为站点集合；为设备型号集合；为车辆集合；，，，为索引；D为站点到站点的距离，∈⋃,∈⋃；Demand为需求站点对设备类型的需求或供给量，∈,∈；

为单车使用固定成本；为车辆单公里变动成本；Max为单车辆最大服务时间；为施工时间；Capacity为车辆最大装载量（经过调研已知信息）；为车辆行驶速度。

决策变量：

E=E+X*demand*w为车辆离开站点时的载重量，∈,∈；

式（1）考虑了车辆综合成本、运输路径油耗及磨损成本的总配送成本最小目标，隐含了使用调度车辆数最小、各站点间驾驶距离最短的两个子目标；式（2）约束了车辆必须被使用则必须服务需求站点；式（3）约束了每个需求站点的单个类型设备最多只能被同一车辆服务一次；式（4）约束了每辆调度车辆的行驶总时间的限制；式（5）约束了每辆调度车辆的载重设备数小于最大载重数；式（6）约束了每个站点只能被同一辆车服务一次；式（7）约束了运用于通信运营设备的调度，即各站点对于设备需求量可以被满足。

4 模型的求解

4.1 蚁群算法

蚁群算法（Ant Colony Optimization，ACO）是一种用来在图中寻找优化路径的机率型算法，也称“蚂蚁算法”。最早用于解决著名的旅行商问题（Traveling Salesman Problem，TSP）。蚁群优化算法已应用于许多组合优化问题，解决产生货郎担问题的拟最优解问题。同时，它在图表动态变化的情况下解决相似问题时，蚁群算法可以连续运行并适应实时变化，相比模拟退火和遗传算法方法有优势。在网络路由和城市交通系统中具有显著的优势。蚁群算法强调的是从始发点到回到始发点的路径最优问题，与通信节能减排中的通信运营设备调度起始站点和终止点具有相似和关联性。

4.2 解空间的构建

蚁群算法的特征是选择模型构造完全图=(,)。其中为顶点集合即为各站点或配送调度中心，为边集合即为各站点及配送调度中心之间距离的集合。在图中，蚂蚁通过随机选取一个顶点进行遍历搜索，通过轮盘赌概率算法进行寻优，通过各路径上的信息素浓度进行路径的选择。

轮盘赌算法是一种比例选择法，用以选择到站点的概率，个体被选中的概率与其适应度大小成正比产生一个随机数。

假设种群大小即蚂蚁数量为，首先蚂蚁从配送中心出发，在约束条件下，到可供站点取某类型通信设备，再对需求站点进行配送调度，出发点和之间的距离为d。在调度过程中，从出发站点到目的站点，会留下一定的信息，以供第二次或者其他蚂蚁寻求到信息，沿着信息素的路线寻找最优路径，此过程记为τ()，表示时刻蚂蚁由始发点到目的点的信息素浓度。蚂蚁在构建路径的每一步中，用轮盘赌法选择下一个要到达的城市。第只蚂蚁根据各站点信息素的浓度在满足约束条件下选择下一个站站点，假设P()表示蚂蚁在时刻从始发点行驶到目的点的概率，则计算公式为：

式中：，分别代表始发站点和目的站点；为信息素因子，反映了蚂蚁在运动过程中路径上积累的信息素的量，为指数函数因子指导蚁群搜索中相对重要程度；为启发函数因子，反映了启发式信息在指导蚁群搜索中的相对重要程度，蚁群寻优过程中先验性、确定性等因素的作用强度；η()=1 d是两站点，实际驾驶路径距离的倒数，表示蚂蚁从到的能见度；τ()为时刻由到的信息素浓度；两地距离越短，信息素浓度越大的路径被选择的概率越大；allowed为尚未访问过的站点集合。

信息素的更新规则为：

式中：为信息素常量，用以防止蚁群算法过早收敛陷入局部最优解的参数；为信息素挥发因子，反映了信息素消失的水平，相反的1-反映了信息素保持的水平；L为第只蚂蚁经过的路径长度；τ(+1)表示第+1次循环后始发点到目的点上的信息素含量的水平；τ()*(1-)表示保留的信息素浓度；Δτ为第只蚂蚁在本次循环中路径（,）上留下信息素的量；Δτ表示新增信息素量的和，即为只蚂蚁在始发点到目的点路径上留下的信息素总和。

4.3 算法步骤

如图3所示，首先初始化各参数（如蚂蚁数量、信息素因子、启发函数因子、信息素挥发因子、信息素常数、最大迭代次数itermax等），以保证随机放置只蚂蚁到各个站点。其次，对于每一只蚂蚁，需要在满足约束条件的前提下，根据概率转换公式，运用轮盘赌法选择下一个待访问站点，并更新循环次数，判断运营商设备是否均已调度，如果在约束条件下没有调度完成，继续进行选择调度，直到所有蚂蚁访问完所有站点满足取送要求，同时更新各站点间的信息素浓度。最后，判断是否达到最大迭代次数，如果未达到最大迭代次数，则迭代次数加1并清空蚂蚁经过路径的记录表，继续返回寻优；否则，输出最优路径做出各次迭代的可视化结果及配送方案。

图3 蚁群算法步骤

4.4 参数的分析

蚁群算法的主要参数有蚁群的大小、信息素启发因子指数、距离启发函数因子指数、信息素挥发系数、信息素增量强度常数。蚁群算法作为一种适应性很高的智能算法，参数设置没有固定的数值，一般是根据实际问题的要求实时设置，因此往往需要经过大量的模拟实验来确定参数的取值。就蚂蚁遍历模型而言，参数设置取值范围一般为：取值1～5之间；取值1～5之间；取值一般为0～1之间；取值一般在100～1 000之间。

文献[15]对超市配送运用蚁群算法进行了相关参数的分析。由于以往研究没有对通信设备调度的相关研究的算例数据，本文采取某市通信设备调度的10站点与50站点的算例数据进行参数的分析。

根据以往经验结合模型的实际验证，蚂蚁数量设置为目标数的1.5倍较为理想。因此，本算例中取值为站点数的1.5倍。由于与之间的关系比较紧密，因此在其他参数不变的情况下对与进行模拟实验，设置迭代次数为100次，观察其目标值。通过模拟实验分析，结合以往的经验，在取值为3，取值为1时，稳定性较好，能够取得较优解。因此，本文设置=3，=1。由于通信设备的调度主要考虑设备类型的匹配度，且各站点距离相对于用车综合成本较低，故应在保证设备类型匹配的情况下进行路径的选优，所以值不宜设置过高，本文选取配送路径优化模型的值为0.2。根据蚁群算法以往经验来设置参数，避免过早收敛，出现局部最优解，因此设置=100。

5 算例验证及结果分析

为验证模型及算法的寻优性能，选取20个站点进行寻优测试。算法采用Matlab 2018a编程语音实现，微机运行环境为：IntelCorei5-8265U CPU@1.60 GHz 1.80 GHz，内存8 GB的个人电脑上运行。

5.1 算例验证

通过实地调研分析，各站点对各类型设备需求及供给如表4所示。为了验证本模型的有效性，本文通过实地调研选取20个站点，对通信设备进行调度处理。首先将调研站点的数据进行初步处理，运用Python结合高德地图API获取到实际驾车距离，如表5所示。

表4 20个站点供需信息

表5 调度中心及20个站点之间实际驾驶距离 km

通过运行程序得到配送车辆为3辆，路线如下：

1）车辆1：0—2—1—12—3—15—8—6—17—14—0

描述如下：车辆1由公司驻地（调配中心）出发依次到达2号站点取走4类设备1台，然后到达1号站点取走1类设备2台，再到12号站点卸载并安装1类设备1台，再到3号站点卸载并安装1类设备1台并同时取走3类设备1台，然后再到15号站点取走3类设备1台，再到8号站点卸载并安装3类设备2台，再到6号站点取走2类设备1台，然后再到17号站点卸载并安装2类设备1台，再到14号站点卸载并安装4类设备1台，然后空载回到公司驻地（调配中心），用时482 min，满足约束条件。

2）车辆2：0—14—11—5—4—16—20—10—19—0

描述如下：车辆2由公司驻地（调配中心）出发依次到达14号站点取走2类设备2台，然后到达11号站点卸载并安装2类设备1台，再到达5号站点卸载并安装2类设备1台，再到4号站点取走1类设备1台，再到16号站点卸载并安装1类设备1台，再到20号站点取走4类设备1台，再到10号站点卸载并安装4类设备1台同时取走3类设备2台，然后到19号站点卸载并安装3类设备2台，然后空载回到公司驻地（调配中心），用时475 min，满足约束条件。

3）车辆3：0—9—19—7—18—13—0

描述如下：车辆3由公司驻地（调配中心）出发依次到达9号站点取走1类设备2台，然后到19号站点卸载并安装1类设备1台，再到7号站点取走4类设备2台和3类设备1台并卸载并安装1类设备1台，到18号站点卸载并安装4类设备2台，再到13号站点卸载并安装3类设备1台，然后空载回到公司驻地（调配中心），用时390 min，满足约束条件。

通过运行20站点算例数据，目标函数及程序迭代次数图如图4所示，收敛明显。通信设备具体调度路线如图5所示，其中黑色代表取设备，灰色代表配送需求，虚线代表返回公司驻地（配送中心）。通过对复杂的不同运行中的通信设备进行合理调度，其成本呈现下降趋势，需求车辆数为3辆，其调度总成本为742.6元。

图4 迭代图

图5 配送调度图

5.2 结果分析

通过对实地施工人员的调研，其调度采用先由近及远取设备再返回配送中心，再安排车辆进行通信设备的调度。由于需要取回设备17台超出车辆最大载量限制，选配2辆车进行取货操作，然后再安排车辆进行配送。

结合调度问题，通过实地调研及实际驾驶距离，某M市施工人员施工安排调度配送如下：

取设备车辆：

车辆1：0—2—7—14—20—10—3—0

车辆2：0—1—15—4—9—6—0

配送设备车辆：

车辆3：0—11—7—18—14—16—12—3—13—5—0

车辆4：0—8—10—17—19—0

根据调研数据及获取道路实际驾车距离，计算所花费时间及实际费用如下：

车辆1花费时间及费用：

车辆2花费时间及费用：

车辆3花费时间及费用：

车辆4花费时间及费用：

与模型算例总成本742.6元相比，调度成本节约148.3元。对于现阶段施工先取后送会增加调配中心的处理成本，造成资源的浪费和效率的降低。应用该模型及算法进行寻优操作，不仅不需要配送中心的处理成本，而且对各站点配送方案进行优化，现取现送，也很大程度上减少了设备型号配送错误导致的返工。对资产管理系统中资产的调配在施工之前就能够确定，减少了后期调整变更的工作量。因此，该模型可为通信运营设备调度提供理论指导，提高管理效率。

6 结 语

本文通过对当前通信发展的趋势分析，多网融合发展作为今后的发展趋势，初步分析了通信设备能耗的占比，从而引出通信运营设备调度管理的研究问题。多网融合共存的情况下，多类型通信运营设备的调度处理成为了今后管理研究的主要方向。结合通信设备的特点及调研数据进行分析，建立了通信运营设备的调度模型，并运用计算机技术进行算例的模拟求解。通过模型求解与现阶段施工人员所调度的方案进行对比分析，证明了模型的有效性。不仅节约了成本，也优化了资产调整的工作量。运用该模型用定量分析法输出调度路径，同时结合施工人员的施工经验确定路径，能够更好地为通信运营设备的调度进行指导。对现网运行设备能够充分利用，降低耗能，同时也减少了新设备的采购成本，实现降本增效的目的。由于通信运营设备调度，涉及到取送结合，复杂度较高。今后研究可以将其他因素考虑进来，如可以加入考虑路径拥堵时间窗的研究等。