论文部分内容阅读
随着5G网络在现实中的推广和应用,将进一步提高人们的生活质量。而5G网络的顺利推广则离不开基站网络的基础建设与维护,负责全国移动通信基础设施网络的建设与维护的单位为中国铁塔公司,目前公司仅凭员工经验进行基站设施网络维护,运维效率低下,导致每年其运维成本高达100亿人民币。基于此,本文研究了该公司亟需解决的一类取货和送货问题。对于公司日常基站维护问题,该问题属于动态的可选择可重复取送货车辆路径优化问题,我们建立了基于动态需求的VRP模型。对于实时到来的需求,将动态的问题分解成多个静态的问题来求解。每次求解时,采用初始插入算法得到初始解,并设计改进的变邻域搜索算法来改善初始解。为了准确计算车辆到达每个配送点的时间,从百度地图实时读取任意两点的交通时间。基于铁塔公司历史数据构造多个算例表明:本文所提的算法在1min内得到较优解,和公司现有经验比解的质量平均提升46.47%,与插入算法相比平均提升30.38%。目前该算法已应用在该公司实际的基站日常运维中,帮助公司有效地降低了运维成本。对于基站大规模维护问题,该问题属于可选择可重复取送货可变时间窗车辆路径优化问题。对于需求点,每次访问后,该点的服务类型发生变化,该点的时间窗也发生变化,通过估算需求点访问次数的最大值来刻画每个基站的多次访问,并基于此建立线性规划模型。本文根据基站每次访问后时间窗的变化设计插入算法。为进一步提高解的质量,设计基于变邻域搜索算法的求解框架。根据公司历史数据构造的多个算例表明,该算法得到结果比插入算法得到的结果节约成本27.13%,证明了本文所提出算法的高效性,表明该算法可以应用于基站大规模实际运维中。最后,本文对公司各个资源以及权重参数进行了灵敏度分析,为公司相关参数设置和资源配置提供了指导。本文的研究问题不但提高了铁塔公司运维效率,降低了掉线成本,推动5G网络的普及,从而更好地为用户提供移动互联服务,而且具有创新性地提出了取货和送货问题的新变种,对于解决该类问题具有一定的借鉴意义。