时变路网下动态可选路线可重复取送货基站运维路径优化

谢 维，於慧琳，陈宇航，傅咔妮

（华南理工大学，广东广州 510641）

1 问题提出

随着5G 技术的蓬勃发展，越来越多的行业接入5G 网络并开始多领域的推广及应用，我国基站建设及维护工作越显重要。据工信部发布的《2020 年通信业统计公报》数据显示，2020 年我国新建5G 基站超60 万个，全部已开通5G 基站超71.8 万个，其中中国铁塔新建5G 基站超33 万个，5G 网络已覆盖全国地级以上城市及重点县市。5G 基站和现有基站大量共同建设，给基站的配套电力与运维任务带来了极大的挑战。

国内移动通信基础设计网络的建设和维护均由中国铁塔公司负责，其主要的工作包括规划基站网络的建设以及通过基站运行监控系统时刻保持基站的正常运作。基站运作依靠电网的电力供应，而由于恶劣天气、道路施工等因素导致基站的电力供应中断（称之为“掉线”），掉线后备用蓄电池将短暂地维持基站的电力供应。铁塔公司收到报警信息后需在蓄电池电量耗尽前将柴油发电机送往基站，否则基站将停止服务，造成经济损失。如图1 为齐齐哈尔地区单月掉线基站情况，每日掉线基站数量从几个到几十个不等。铁塔公司每年的基站运维费用高昂，如何通过优化理论和算法设计进行有效的运维工作、减少掉线成本，是当前亟待解决的重要问题。

图1 齐齐哈尔地区基站单月掉线情况

基站运维的研究问题实际上是属于取货与配送问题（pick-up and delivery problem,PDP），应用场景主要集中在采购补货等场景，要求车辆必须满足所有顾客的需求且供给与需求必须相等。如Ting 等［1］根据现实情况提出了可选的取送货问题（multi-vehicle selective pick-up and delivery problem,MVSPDP），车辆在若干个取货点中选择前往，对顾客节点进行时间约束，并利用启发式算法求解了多车辆的配送路径方案和取货量决策；Al Chami 等［2］基于带时间窗的取送货问题提出了词典方法进行求解，但该方法要求取货点仅可访问一次，不可多次访问；Fleischmann 等［3］考虑顾客的需求会随时产生，每个需求均有软时间窗约束，决策目标是最小化服务延迟和运输成本；Attanasio 等［4］基于动态取送货问题（dynamic pick and delivery problem,DPDP）问题，综合考虑顾客需求到来和行程时间的不确定性，提出能够动态优化客户服务满意度的实时系统；Gendreau 等［5］针对快递服务问题设计了插入算法，将新旧需求一并重新优化并求解当前最优路线；Mitrović-Minić［6］针对快速处理动态问题提出了根据滚动时间水平法，即将调度时间等分地分割成若干个小块，每个小块内按静态问题的方法求解，并通过启发式算法求解问题；葛显龙等［7］在研究动态需求的多配送中心问题时放松了车辆与单个配送中心捆绑的约束，并引入时间轴将动态需求转换为时间轴上的静态需求；张婷等［8］考虑需求量、需求点、突发状况等的动态因素，通过引入虚拟节点的方法将问题转化为静态后利用遗传算法求解；王仁民等［9］在处理动态车辆路径规划问题（dynamic vehicle routing problem,DVRP）时，将时间看成一个个小段，并对每个时间段进行规划处理，并分别利用变邻域搜索算法和遗传算法进行局部搜索和全局搜索，寻找最佳的路线安排。目前在动态取送货问题上的研究已有较多成果，但相关的研究在计算顾客节点间的距离仅考虑静态的交通状况，且以节点间的欧氏距离代替实际行驶距离，但该计算方式无法刻画现实生活中多变的城市交通状况。

由于基站密集地分布在城市的各个角落，基站运维人员前往存放柴油发电机的节点取货后送往各个报警基站点。在配送过程中，行驶时间也随着时空的改变而发生剧烈的变化，图2 为广州市2021 年6 月全市的交通情况，由于早晚高峰以及突发事故等影响，一天不同时间段下的路网平均速度相差甚远。在随时间变化的交通状况下，传统路径规划方案的优化效果将受影响，于是越来越多学者开始研究具有时间依赖性的车辆路径问题（time-dependent vehicle routing problem,TDVRP）。时间依赖性指的是随着时间推移而发生变化的交通状况，而TDVRP则是考虑随着时间变化的交通状况的车辆路径规划问题。如Malandraki 等［10］将时间分割为多段，每一段均有不同的行驶时间，但该理论不符合“先进先出（first in first out,FIFO）”原则；Ichoua［11］通过分段刻画行驶速度，通过路径长度和行驶速度来计算时间，该模型符合FIFO 原则，后续很多研究在此研究基础上开展；Eglese 等［12］基于真实的路网结构和对应的车辆行驶数据，刻画出随时间变化的最短路径表；Maden 等［13］在解决英国西南部电力运营的车队运作时，考虑了早晚高峰的交通拥堵，目标是最小化总行驶时间，他们提出禁忌搜索的启发式算法来求解问题，实证分析后发现考虑时变网络下的规划方案能减少7%的二氧化碳排放；马华伟等［14］就时间依赖性的路径规划问题的求解提出了两阶段启发式算法，考虑采用分阶段的策略来设计模拟退火算法，并通过算例验证了该算法性能较好；Kok等［15］首先构建随时间变化的最短路径，之后利用启发式算法求解出配送方案，并证实考虑时变网络对行程时间的减少是显著的；Jabali 等［16］在研究车辆的二氧化碳排放时，由于汽车的行驶速度将影响二氧化碳的排放，文中根据这一特性将车速的限制作为优化的一部分，并构建碳排放与车辆行驶速度的函数，进而通过实证分析证明该方法对于控制成本是有效的；吴瑶等［17］针对易腐品集配问题的生产与配送环节设计了一种混合遗传算法进行问题求解，该模型的优化目标是总配送成本最小；刘长石等［18］考虑时变路网的配送问题时，放松了出发时间、车辆必须返回驻点等约束，根据油耗、碳排放等建立起与时间关联的目标函数，并设计了蚁群算法求解问题；范厚明等［19］考采用三角函数近似表示行驶速度的方法来刻画动态的交通状况，并使用动态调整和周期调整两种策略来处理动态需求，最后设计了遗传算法来求解问题。

图2 广州市6 月城市路网交通状况

以上的文献均是利用顾客节点刻画出节点网络，每条节点弧线代表一条道路，简单地刻画在该弧线上的交通状况变化，然而这种刻画方式仅仅考虑了交通网络的动态变化性，并没有达到躲避交通拥堵、提升配送效率的目的。因为在实际的交通网络中，两顾客节点间可存在多种行驶路线，不同路线由于具有时空性，花费的时间也不尽相同，通常司机会采用不同路线来躲避交通拥堵。若能够在路径规划中考虑决策多种路线以躲避交通拥堵路段，可以实现减少行驶时间，提高配送效率的目的。

综上所述，交通状况会影响车辆路径规划方案的质量，然而现有研究大多采用顾客节点构成的弧线来代表道路，此方法无法达到躲避交通拥堵、提高配送效率的目的。本文根据真实的城市路网构建两两节点间的道路，对顾客节点网络与交通路网进行分别刻画并建立模型，节点间存在多种路线组合，模型除了决策车辆服务顺序、取货量等传统路径规划因素外，增加使用何种路径来构成最佳的路线方案的决策，以此达到躲避交通拥堵、减少行驶时间的目的。另外，基站运维属于企业实际面临的问题，本文需要设计高效的算法以保证路径规划问题的求解速度。本研究可为基站运维管理提供参考，对于当前车辆路径规划问题以及考虑时变网络的车辆路径规划问题也有一定的借鉴意义。

2 问题描述和模型

2.1 问题描述

现铁塔基站运维公司有一支车队负责G 地区的基站运维工作，该车队拥有数台同质的车辆，分布在该地区的各个驻点。基站发出报警信息时，车辆需从驻点出发，前往存放着油机的地点取油机，每次取货需决策取油机数量，同一个取油机点可以被多次访问，车辆取油机后再配送至报警基站，每个报警基站的油机需求均为1。车辆按服务顺序配送完所有的报警基站后，返回驻点待命。由于基站报警的随机性，车辆需动态地规划实时到来的新报警信息。对于正在执行任务的车辆，当新的报警产生时，车辆即将服务的报警基站与新产生的报警基站需要合并重新优化，同时取油机点也需要被重新优化，决策出新的服务路线方案。

车辆行驶在城市路网中，交通状况随着时空发生变化，车辆在决策服务基站及顺序时，也需要决策何时行驶何种路线。而基站的备用蓄电池电量各异，每个报警基站都有不同的最晚服务时间，若车辆到达报警基站并完成装卸货工作后晚于报警基站的最晚服务时间，则会因断电产生惩罚成本。本文的优化目标是最小化基站掉线的个数以及基站总掉线时间。

2.2 参数描述

为了读者方便理解，表1 汇总了本文所涉及到的符号。

表1 符号

2.3 问题建模

2.3.1 模型预处理

如何建立函数描述不同时间段下的行程时间是时变网络的研究中的难点，学者们针对该难点开展了很多研究，如Hill 等［20］、Malandraki 等［10］均不满足FIFO 原则。直至Ichoua 提出通过速度构造分段函数描述旅行时间，FIFO 才被满足。本节将参考Gendreau 等［21］提及的方法对时变网络下的行驶时间进行建模。

2.3.2 模型建立

目标函数（由掉线基站个数和基站的总掉线时间组成）模型构建如式（1）至（27）。

其中，式（1）为目标函数，其中第一部分是掉线基站个数，第二部分是基站的总掉线时间；式（2）表示并非所有车辆都需要被使用；式（3）表示车辆从驻点出发后必须回到驻点；式（4）表示可使用车辆数量约束；式（5）表示需求点必须被服务，且仅能被一辆车服务；式（6）表示车辆服务完一个需求点后必须离开；式（7）表示车辆行驶在节点间时，仅可选择某一条路线；式（8）和式（9）共同规定了车辆从i点前往j点的离开时间有且仅有一个；式（10）和式（11）表示车辆的实际行驶时间计算；式（12）节点的离开时间需大于前一个服务节点离开时间加上行驶时间再加上节点服务时间；式（13）表示车辆在服务节点时是否延误；式（14）和式（15）表示若车辆在服务节点时的延误时长；式（16）和式（17）表示车辆经过服务节点后的载货量变化；式（18）表示任何时候车辆的载货量不得超过载荷；式（19）表示取货点并非必须前往的；式（19）表示取货量不得超过取货点的总货物数量；式（21）至（27）是变量约束。

3 基站网络运维路径优化的仿真研究

3.1 动态算法设计

一天内交通网络与基站的运行状态会动态地发生变化，我们将通过切割时间，将动态问题转换为一个个的静态问题进行求解。每当新的报警基站出现时，所有车辆或在驻点待命，或在城市路网的某一处，均有若干个即将执行的服务需求，这些需求与新的报警基站共同组成了一个该时刻下的需求集合，本节的算法将结合车辆所处的位置以及当时的路网状况，对该时刻下的进行优化，重新安排该t时刻下的服务路线。

3.1.1 最短路算法

Dijkstra 算法是求解最短路的经典方法之一，其中心思想是从中心点出发，层层向外迭代，探索最短路。原始的Dijkstra 算法仅考虑在某时刻出发的最短路，并不适用于本文的时变网络，因此本文基于Dijkstra 算法进行了一定的改进，求解出每个m时间段下的最短路，改进的Dijkstra算法伪代码如表2所示。

表2 改进的最短路算法伪代码

通过上述的Dijkstra 算法，我们可以根据车辆的行驶进程以及路网的实时交通状况，找到t时刻下的最佳路线，使车辆能以最短的时间行驶至服务节点。Dijkstra 算法将穿插在算法优化的每一个计算环节中，当出现新的报警基站时，车辆需决策服务节点的分配以及服务顺序，此时决策的依据是Dijkstra 算法根据实时t时刻下的交通状况计算出最佳路线的行驶时间。

3.1.2 遍历插入算法

当新的报警基站出现时，需要动态地规划新的路径，将新的报警基站安排进服务计划内。我们考虑在加权目标值最小增量的情况下，基于报警基站的断电时间窗遍历插入。遍历插入算法如表3所示。

表3 遍历插入算法伪代码

遍历插入算法可以在较短时间内获得针对新出现的报警基站的初始解，该初始解是基于新报警基站的位置、时间窗信息进行简单的插入，寻找使目标函数增量最小的方案。该插入算法是基于贪心原则的，其构成的解空间有限，容易陷入局部最优解。需要进一步优化。

3.1.3 变邻域搜索算法

变邻域搜索（variable neighborhood search,VNS）属于一种元启发式算法，其核心的思路是设计若干个具有不同结构的算子应用于求解过程中，具有不同结构的算子能使解空间变大，算法在若干个算子中循环，在单个算子构成的解空间中寻找到最优解后，邻域被重新构造，算法进一步探索新的解空间，帮助算法跳出局部最优解一步步逼近最优解。

变邻域搜索算法的关键在于算子的设计，算子构成的邻域越大，越有可能逼近全局最优解。算子需要根据问题的特性进行设计，否则可能影响算法的运行速度，进而影响求解效率。如表4 所示，本节根据问题设计了以下5 个算子：

表4 变邻域搜索算法伪代码

（1）Two_option_swap: 交换两条服务路线的某个需求；

（2）Transfer: 将某路线的某个需求迁移至另一条路线上；

（3）Two_exchange_one: 选取A 路线上的两个相邻服务节点，将其与B 路线上的某个节点交换；

（4）Reverse: 选取某条路线，将相邻的两个服务节点的服务顺序调换；

（5）Three_exchange_one: 选取某三条路线，相互交换路线中某个需求。

3.2 数据实验与结果分析

3.2.1 算例生成

图3 交通路网示意

表5 报警基站信息

在基站运维工作中，工作人员的运维流程是先开车前往取油机地点取货，然后将油机送至报警基站为其充电，最后开车返回驻点。在实际运维中，由于服务的随机性，工作人员可能会在服务完最后一个节点后，将车辆驾驶至家中，由此导致工作车辆并非全部在仓库点待命。为了更贴近现实，在设计算例时，车辆的位置将随机产生，车辆位置可能是任意节点。

3.2.2 参数设置

现该地区共有三辆负责基站运维的车辆，每辆车的最大载货量是3 台柴油机。油机个数共有50个，分布在仓库与部分基站站点中。基站掉线个数的权重值，基站总掉线时间的权重值（参数设定从铁塔公司获得）。算法采用Java 编程，计算机设备为16 GB 内存，处理器为AMD Ryzen 54 600U 2.10 GHz。所有程序的运行时间均不超过1 min，所有算例都能在1 s 内完成并输出结果。为了更好判断本文提出的方法的有效性，本文基于CVRP 模型设计了对比实验。对比实验是基于距离的传统VRP 模型，距离矩阵通过基站间的欧氏距离与城区的平均速度 相除得到，城区的平均速度设定依据广州市交通运输局提供的《交通运输月报》。

3.2.3 算法实施效果总结

为了保证真实性与可复现性，本文共生成100个算例，实验组（TDVRP-PF）与对比组（CVRP）在同一个情景下，即在相同的报警基站、相同的运维车辆、相同的取油机信息下进行。运行结果如表6 所示。

表6 算例总体效果

对100 个算例汇总分析的结果如下。在考虑时变网络下，可选路段地进行车辆路径优化所得的效果要远好于以往不考虑时变网络的模型。总加权目标值提升71.47%，平均掉线基站个数减少63.38%，平均每个算例减少约3 个掉线基站，同时均掉线时间减少了72.22%，本文提出的方法对基站运维的效率和效果都有较大的提升。表7 的算例具体效果显示本文提出的方法在各种算例中表现稳定且均好于对比组。

表7 算例具体效果

3.2.4 优化方法效果分析

为了更好探究本文提出的优化方法是否可以达到躲避交通拥堵的目的，我们选取共有16 个报警基站的算例，将油机和车辆均设置在点57 处。使用本文优化方法（以下简称“TDVRP-PF”）的实验组掉线基站个数为4 个，掉线时间为82.53 分钟，而传统的以CVRP 为基础的对照组掉线基站个数为8 个，掉线时间为177.73 分钟。具体数值表现如表8 所示。

表8 算法效果对比

结果显示，当考虑了时间依赖性进行车辆路径规划的求解时，求解生成的优化方案与传统CVRP方法相比，在服务需求分配、需求服务顺序以及节点间路线选择都会有不同程度的差异，这些差异使得两种方法在掉线个数与掉线时间上有不同的表现。摘取TDVRP-PF 和CVRP 优化方案中部分的路线规划如表9 和表10 所示。对08、42、63 需求节点，TDVRP-PF与CVRP的需求分配、需求服务顺序一致，出发时间均为08:05:21。然而，在TDVRP-PF 方法下，车辆选择了不同的行驶路线。对于需求节点08，08号节点在08:06:56 发出报警，由于基站内蓄电池无电量储备，基站立即断线，需要基站运维人员尽快赶到并安装好柴油发电机。TDVRP-PF 的行驶路线如 图4，为57 →62 →63 →64 →08，而CVRP 的行驶路线如图为57 →56 →55 →07 →08。

表9 TDVRP-PF 优化方案路线

表10 CVRP 优化方案路线

图4 TDVRP-PF 与CVRP 方案的车辆路径规划

从结果来看，TDVRP-PF 方案中，车辆在08:19:03 就已经到达08 号节点，基站总计断电12 分钟。而CVRP 方案中，车辆在08:24:55 到达08 号节点，基站断电18 分钟，较TDVRP-PF 方案晚了6 分钟。原因在于二者采用了不同的行驶路线，如图4 黑色的线表示车辆服务第一个需求节点08 的行驶路线，虽然CVRP 方案下选择的路线长度比TDVRP-PF 方案下选择的路线长度短了2 600 米，但是62-63-64-08 路段属于一级公路，行驶速度较快，而8 点正值早高峰时期，56-57 路段的行驶速度较正常缓慢25%，56-55 路段的行驶速度较正常缓慢55%，而62-63、63-64 路段的行驶速度仅较非高峰下降了5%～10%。以距离最短为原则的CVRP 下优化方案忽略了交通的因素，花费了更多的时间。而考虑时间依赖性的TDVPR-PF 下，充分考虑到不同道路类型的通行速度差异以及早高峰带来的行驶速度上的影响，选择了时间最短的道路，最大程度减少基站断电时间。

相同的情况也发生在42 节点上，虽然二者所选的道路均为三级公路，道路基本情况相似，但是由于53-56 路段的交通长期处于高压状态，在早高峰拥堵情况则更为严重。而服务前序节点08 时进入了拥堵路段，耽误了时间，使得CVRP 方案下42节点基站断，断电时间达21 分钟。相较之下，在TDVPR-PF 的方案中，42 节点在基站断电前9 分钟即完成任务。综上所述，本文所提方法能够根据变化的交通状况决策最佳的行驶路线来躲避交通拥堵，以更短的时间到达目的地，并且随着服务进程的推移和交通拥堵的加剧，该方案的优势将更加显著，如表11 所示。

表11 TDVRP-PF 与CVRP 方案到达节点的时间对比

4 结论

本文针对中国铁塔公司基站运维管理成本较高和效率低下的困境，提炼出基站运维问题属于动态的带软时间窗约束的多车辆可重复取货和配送问题。在此基础上，针对基站运维工作中城市交通路网的动态性，创新地将时间依赖性考虑进基站运维车辆路径规划中，通过分段刻画城市交通路网，考虑取货点、取货量、车辆分配与容量约束，采用速度来计算行驶时间，构造出发时间与总行驶时间的关系，构建速度-行程时间函数用于决策行驶路线、取货量和服务路线，设计了改进的最短路算法与变邻域搜索算法相结合的混合算法来求解问题，数值试验结果表明本文所提出的方法可以实现基站运维的成本降低和效率提升。