周 游，朱文斌

(华南理工大学 工商管理学院，广东 广州 510641)

随着5G网络的发展，其应用将大大提升人们的生活水平，增强各行各业的发展潜力。在5G网络的建设中最重要的环节就是基站的覆盖和维护，国内移动通信基础设施网络的建设与维护均由中国铁塔公司负责。目前全国有约200万个基站，铁塔公司建立了完备的基站状态监控系统。由于台风、暴雪或电网故障等原因，会出现大面积断电情况，此时基站会切换到备用电池供电，并向系统发出断电报警。每个基站的备用电池容量有限，运维人员须在电池电量耗尽之前将给电池充电的柴油发电机(以下简称为“油机”)配送到位，否则基站将会断电，对铁塔公司造成重大损失。同时，雇佣运维人员、购买和储备车辆与油机也会产生相应的成本。因此如何利用优化理论和算法规划车队规模并优化有限资源的分配与调度，提高服务保障率，并达到最小化总成本的目标，成为运维优化中亟需解决的问题。

本文研究的优化问题本质上属于取送货问题(pick-up and delivery problem,PDP)。目前国内外关于取送货问题的研究非常丰富[1]，但大部分文献都基于总的取货量与送货量相等这一条件，其所解决的问题一般集中于采购补货等场景，隐含了所有客户点均需要被访问的约束[2]。Ting等[3-4]提出了可选择的取送货问题，放松了访问约束，加入了收货点的时间窗口约束，并利用启发式算法求解了多车辆的最优取送路径与取送货量的决策。潘立军等[5]利用基于时差的插入算法和遗传算法的框架求解了带时间窗口的问题。还有一类相似的问题是库存路径问题(inventory routing problem,IRP)，其典型的应用是银行ATM机的现金取钞、加钞的场景，但是这类文献一般利用库存理论计算出确定的需求量并转化为确定性需求的问题进行求解。Anholt等[6]使用分支定界算法求解了荷兰ATM的提货和补货的库存路径问题。Larrain等[7]利用混合整数规划对智利ATM网络配送问题进行建模，考虑多个车辆的路径规划，采用可变MIP邻域下降算法进行求解。这些研究基本属于静态问题，即假设需求已经确定且通行时间等不发生变化[8]。

本文的研究问题与传统静态问题具有如下的差别。1）充电量的决策与路径的规划相互依赖，在本问题中，基站备用电池的电量决定了服务需求的时间窗口，电池电量的补充量又取决于油机实际到达和取走的时间差，而传统问题中一般是在已知各点的供给和需求量的条件下进行路径规划。2）取货、送货点的状态会发生多次转换。当一个基站安装油机进行充电后，该基站就会从需求点变为供给点，需要决策何时取走该点的油机送往其他需要充电的基站，而传统问题中的取货、送货点是固定的。

同时国内外越来越多的研究也开始关注动态问题，其特点是问题中的相关信息会随着时间不断变化更新，更加符合实际需求[9]。其主要应用场景为动态乘车请求问题、快递配送服务等[10-12]。Fleischmann等[13]研究了顾客请求不断产生且通行时间不断变化的动态问题，目标是最小化请求满足的延迟和交通成本。Yang等[14]考虑了具有软时间窗的多车辆动态问题，但所有出现的顾客请求必须被服务。孙宝凤等[15]使用禁忌搜索求解了基于实时信息的动态取送货问题。Attanasio等[16]提出了一个考虑需求动态到达及行程时间随机的实时系统，目标是最大化客户服务总体满意度。这些研究中虽然需求点是不断动态产生的，但需求量仍然是互相独立且固定的，无法解决本文的难点。

1 问题描述和建模

1.1 问题描述

在铁塔公司接到基站断电警报后，系统会迅速根据基站的位置信息、道路通行时间规划运维部门对于各基站的取送油机方案，即每一辆车应按照什么顺序访问哪些基站。运维部门拥有多辆装备油机的车辆，每辆车有容量限制，车辆均从唯一的车库出发，依照系统指示进行顺序服务。每辆车给需要充电的基站送油机，到正在充电的基站取油机，每个基站需要的油机均为1台，车辆在取送油机过程中不得超过其容量限制。另外，车辆在装卸和启动油机时均需要服务时间，本文假定取送油机服务时间相同且对于各个基站是固定的。一个完整的规划周期从断电开始直到电网电力恢复为止，一般持续数个小时，因此假定所有车辆均可一直行驶。同时作出如下定义。

定义1掉线。若油机送达基站开始充电时间晚于备用电池电量耗尽时间，基站无法正常工作，称之为掉线。

定义2掉线时长。发生基站掉线时，油机开始充电时间减去电池耗尽的时间即为该基站的掉线时长。

基站掉线将会对基站服务覆盖范围内的用户产生巨大影响。掉线基站的个数越多且掉线时长越长，带给铁塔公司的损失就越大，同时使用更多的车辆和油机也会产生更多的成本。因此，公司的目标是最小化一个周期内出现掉线的基站数目、基站掉线时长及车辆交通时间的加权总和。

1.2 问题建模

虽然原问题是一个需求确定的问题，但由于其充电量决策与路径规划的相互依赖性以及取货、送货点状态的转换性，对于实际问题不能按照简单静态问题进行建模。本文通过转化为多阶段动态决策问题进行处理，对于每一阶段的决策建立混合整数规划模型。

1.2.1 符号含义

对于t时刻的决策，问题已知的常量如下。

K：车辆的集合；

V：基站点、车辆位置点的集合；

P：该次决策可取油机的点集；

D：该次决策需要送油机的点集；

Δti：点i装卸油机的服务时间；

Tij：点i到点j的通行时间；

Ck：车辆k的最大容量；

Nk：车量k的初始油机数量；

Ei：点i电池电量耗尽的时间，i∈D；

M：一个足够大的正数；

w1：基站掉线个数在目标中的权重系数；

w2：基站掉线总时长在目标中的权重系数；

w3：车辆交通总时长在目标中的权重系数。

模型中的决策变量如下。

xkij：车辆k经过边(i,j)则取1，否则为0；

rki≥0：车辆k到达点i的时间；

nki∈Z ：车辆k离开点i时的油机数量，为整数变量；

fi：点i发生掉线则取1，否则为0，i∈D；

σki≥0：若点i发生掉线则表示掉线时长，否则为0。

1.2.2 模型建立

模型的目标为在该阶段决策中最小化基站掉线个数、掉线时长和所有车辆的交通时间的加权之和。其中，权重参数由铁塔公司提前确定。

使用图论模型对路径规划问题建模，图上的流量需要保持均衡。

约束(1)确保所有出发的车辆最终都会抵达该阶段的终止位置；约束(2)表示每个送货点在该次决策有且仅有一辆车服务；约束(3)表示取货点是可选的；约束(4)表示每个中间节点的流入车辆和流出车辆均衡。

同时，基站送货的到达时间由于时间窗口约束，基站掉线会在目标函数中产生惩罚，利用开关变量法将约束均写为线性约束。

约束(5)表示如果车辆k经过边(i,j)，则到达点j的时间至少等于到达点i的时间加上在点i的服务时间；若不经过该边，则约束失效。同理，约束(6)为软时间窗约束，表示车辆k在送货点i安装油机完毕的时间应不晚于该基站电池耗尽时间，否则会出现惩罚。约束(7)和(8)为一组，表示若掉线，则掉线时长等于安装油机完毕的时间减去电池耗尽的时间。

最后关于车辆运输油机的容量约束为

约束(9)～(12)确保了车辆在取送油机时车上油机数量的增减，约束(13)表示车辆所携带的油机数量必须符合容量限制，且初始位置时的数量已知。

2 模型求解

虽然上述模型是线性的整数规划模型，可以使用Cplex、Gurobi等商业规划器直接求解，但其为NP难问题，实际应用中问题规模较大且具有严格的时间要求。因此本文设计了一种高效的启发式算法架构进行求解，在短时间内得到满意的解决方案。

由于每当车辆在一个基站取、送油机后，原问题的取货、送货点集合将发生变化，因此需要重新进行规划。

2.1 时间窗口的计算

虽然充电量由油机送达和取走的时间差决定，但是其可以通过时间窗口约束对路径规划的调控来保证其充电量符合预计的规划量。在人工决策中一般将电池耗尽的时间作为送油机的最迟时间窗口，且对于取油机点没有时间约束。但是由于采用软时间窗口的约束，会导致有较大风险出现基站掉线的损失。如果出现基站电量已满但油机仍在该基站充电的情况，由于油机对于基站是稀缺的，这样的过充现象会对全局目标产生损失。因此考虑引入库存理论对于基站取送油机的最迟时间窗口进行修正。

不同于传统的库存问题，本模型不仅需要计算电量的下限，还需要计算防止过充的电量上限。对于电量的取、送油机问题，电池电量的消耗和补充速度即需求是恒定的，而车辆来取、送油机的提前期是不确定的。因此，设显著性水平α，一般取0.05，安全电量的计算公式为SS=，其中，Z取1.65，即为充放电的速率，而提前期(lead time,LT)的分布用该基站和全部其他基站的通行时间近似代替。对于每个基站，令schar表示充电速度且scon表示耗电速度，均用单位时间百分比表示。提前计算出其取油机的电量上限(UB)和送油机的电量下限(LB)，并根据t时刻的电量ct分别计算其时间窗口

2.2 动态算法框架

对于每一次规划，保持正在执行的当前任务不变，同时更新取、送货点集和各基站的时间窗口，然后再利用变邻域搜索(variable neighborhood search，VNS)搜索本阶段的较优解，直到电力恢复。具体框架如图1所示。

图1 动态算法框架图Figure 1 Dynamic algorithm framework

2.2.1 初始解生成

步骤1对于该阶段的取、送货集合和各基站的时间窗口，将基站按照时间窗口排序，按前后顺序插入。

步骤2对于每个待插入基站，遍历车辆集合，计算插入队尾的到达时间，选择最早到达且油机数量符合要求的车辆插入。

步骤3若没有车辆符合油机数量要求，则选择时间窗口最早的相反状态的基站插入。

步骤4重复步骤1～3，直到所有基站均被插入，生成初始解。

2.2.2 VNS优化

将初始解S0按照一定规则操作得到的全部合法解称为S0的邻域，对应的操作称为算子。本文主要使用交换和迁移2种算子，如图2所示。

图2 交换和迁移算子示意图Figure 2 Diagram of exchange and relocate operators

步骤1对于当前解，利用交换算子找到所有合法的邻域，记录最优局部解并将其与全局最优解比较，若改善则转到步骤2，若没有改善则转到步骤3。

步骤2将最优的交换操作应用于当前解，得到新的解并更新全局最优解，若迭代次数超过上限则转到步骤4，否则重复步骤1。

步骤3利用迁移算子找到所有合法的邻域，记录最优局部解并将其与全局最优解比较，若改善则转到步骤2，若没有改善则转到步骤4。

步骤4输出当前决策阶段的全局最优解。

3 数值实验

利用铁塔公司真实数据进行数值实验。从2018年1～8月份的数据中随机生成不同规模的数据集，并与公司现有系统的安排结果比较。每辆车均从唯一的车库出发，车辆容量均为3台油机，每阶段迭代上限为200。为方便对比，数据集的停电时间均设为4 h。所有算例目标函数权重参数均与铁塔公司协商后确定，为w1=0.7，w2=0.2，w3=0.1，其衡量的目的如下。1) 对于公司运维成本影响最大的为基站掉线个数，无论时间长短均会带来重大损失，因此在目标中占较大比重；2) 在掉线个数相同的情况下，公司希望掉线的总时长更小，可使基站掉线产生的持续影响较小；3) 公司也需要考虑车辆通行成本，在目标函数中需要一定比重的体现。

3.1 实验结果

为了比较了不同规模的问题，基站数量设定为50～300个，同时为了方便铁塔公司确定运维车队的规模，车辆数设定为10～30辆。比较结果如表1所示。

由表1可知，本文算法的结果显著优于铁塔公司目前系统得到的方案，除11号外，优化率＞0。通过观察还可以发现：1) 当车辆数远小于基站数时，由于服务能力过低，必然导致很多掉线损失，2个方案的效果无明显差异；2) 算例规模变大且车辆数量合理时，本文算法优势很大，优化率＞10%，如，序号14、15；3) 车辆数并非越多越好，在中小规模算例中，反而出现目标值变差的情况，公司应根据各种规模问题出现的概率进行规划。

表1 数值实验结果Table 1 Numerical experiment results

3.2 算法特性分析

本文主要从最优解的搜索能力和收敛速度来分析算法的有效性。通过对比单个阶段算法求解结果与Cplex直接求解整数规划模型最优解来验证算法的最优性。由于问题的复杂性，Cplex在5 min内仅能求得基站数为10以内的问题最优解。从表2可以看出，在小规模的算例中，本文算法用时均为毫秒级，且随问题规模的增长，求解时间变化较小，而Cplex求解时间随问题规模增长而迅速增加。同时，本文算法的目标值与最优解差距平均＜20%，说明算法符合实时决策要求下依然具有较好的最优解搜索能力。本文用算法目标值及总通行时间随迭代次数的改变情况表示算法搜索的收敛速度。图3展示了基站数为200、车辆数为30的单个阶段算法的目标值随迭代次数的变化。在100次迭代内，算法目标值先迅速降低，随后趋于平缓，同时，算法优先减少掉线基站个数，随后优化掉线时间和通行时间，符合目标函数各部分的权重分配。

图3 目标函数迭代变化图Figure 3 Diagram of objective function change with iteration

表2 算法最优性对比分析Table 2 Comparative analysis of algorithm optimality

4 结语

本文以中国铁塔公司基站运维问题为背景，深入分析了该问题与传统取送货问题的差异性，将静态问题转化为动态多阶段决策，并利用图论模型建立整数规划模型，利用库存理论修正各基站取送油机电量的上下限，设计了基于VNS的动态算法进行求解。通过公司实际数据生成的算例验证了本文的算法的优越性。该模型可以辅助公司决策运维车队的规模。进一步的研究将寻找更精准的充电量决策方式和车辆之间任务均衡性的优化。