大规模基站运维优化与车队规划研究

doi:10.3969/j.issn.1007-7375.2021.03.015

工业工程 ›› 2021, Vol. 24 ›› Issue (3): 115-120,160.doi: 10.3969/j.issn.1007-7375.2021.03.015

大规模基站运维优化与车队规划研究

周游, 朱文斌

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

收稿日期:2020-03-10 发布日期:2021-06-26
作者简介:周游(1994-)，男，广东省人，硕士研究生，主要研究方向为车辆路径规划、库存管理、排班优化、装箱问题
基金资助:
国家自然科学基金资助项目（71501075）；广东省自然科学基金杰出青年基金资助项目（2015A030306007）；中央高校基本科研业务费专项资金资助项目（2019ZD15）

A Research on Large-scale Base Station Maintenance Optimization and Fleet Planning

ZHOU You, ZHU Wenbin

School of Business Administration, South China University of Technology, Guangzhou 510641, China

Received:2020-03-10 Published:2021-06-26

摘要/Abstract

摘要： 研究了考虑充电量决策的大规模基站断电运维的多车辆路径规划问题。目标是在运维能力有限的条件下最小化基站断电产生的损失和车辆运行成本的加权总和。分析了该问题区别于传统取送货问题的差异与难点，利用图论模型建立了动态多阶段车辆路径的混合整数规划模型，利用库存理论辅助基站充电量的决策并通过软时间窗口对车辆服务与路径规划进行约束，最后设计了基于局部最优插入和变邻域搜索的动态算法框架进行求解。基于中国铁塔公司真实数据生成的多个算例验证了该算法可以显著降低运维成本，并协助公司进行运维车队规模的规划。

关键词: 动态取送货问题, 库存理论, 变邻域搜索, 基站运维

Abstract: The multi-vehicle routing problem of large-scale base station outage maintenance is studied, aiming to minimize the weighted sum of the loss caused by the outage of the base station and the vehicle travelling cost under the condition of limited operation and maintenance capacity. The differences and difficulties between this problem and the traditional pickup-and-delivery problem are analyzed, and a mixed integer programming model of dynamic multi-stage vehicle routing established by using graph theory model, the decision of base station charging volume assisted by using inventory theory and vehicles' service and routing constrained through soft time window, and finally a dynamic algorithm framework is designed based on local optimal insertion and variable neighborhood search for optimal solution. Several examples based on the real data generated by China Tower Corp. Ltd. show that the algorithm can significantly reduce the operation and maintenance cost and help the company to plan the scale of the fleet.

Key words: dynamic pickup-and-delivery problem, inventory theory, variable neighborhood search, base station maintenance

中图分类号:

U492.3

周游, 朱文斌. 大规模基站运维优化与车队规划研究[J]. 工业工程, 2021, 24(3): 115-120,160.

ZHOU You, ZHU Wenbin. A Research on Large-scale Base Station Maintenance Optimization and Fleet Planning[J]. Industrial Engineering Journal, 2021, 24(3): 115-120,160.

参考文献

[1] PARRAGH S N, DOERNER K F, HARTL R F. A survey on pickup and delivery problems—part II: transportation between pickup and delivery locations[J]. Journal für Betriebswirtschaft, 2008, 58: 81-117
[2] BERBEGLIA G, CORDEAU J F, GRIBKOVSKAIA I, et al. Static pickup and delivery problems: a classification scheme and survey[J]. TOP, 2007, 15(1): 1-31
[3] TING C K, LIAO X L. The selective pickup and delivery problem: formulation and a memetic algorithm[J]. International Journal of Production Economics, 2013, 141(1): 199-211
[4] TING C K, LIAO X L, HUANG Y H, et al. Multi-vehicle selective pickup and delivery using metaheuristic algorithms[J]. Information Sciences, 2017, 406–407: 146-169
[5] 潘立军, 符卓. 求解带时间窗取送货问题的遗传算法[J]. 系统工程理论与实践, 2012, 32(1): 120-126
PAN Lijun, FU Zhuo. Genetic algorithm for the pickup and delivery problem with time windows[J]. Systems Engineering—Theory & Practice, 2012, 32(1): 120-126
[6] VAN ANHOLT R G, COELHO L C, LAPORTE G, et al. An inventory-routing problem with pickups and deliveries arising in the replenishment of automated teller machines[J]. Transportation Science, 2016, 50(3): 1077-1091
[7] LARRAIN H, COELHO L C, CATALDO A. A variable MIP neighborhood descent algorithm for managing inventory and distribution of cash in automated teller machines[J]. Computers & Operations Research, 2017, 85: 22-31
[8] BARD J F, JARRAH A I. Large-scale constrained clustering for rationalizing pickup and delivery operations[J]. Transportation Research Part B: Methodological, 2009, 43(5): 542-561
[9] BERBEGLIA G., CORDEAU JF, LAPORTE G Dynamic pickup and delivery problems[J]. European Journal of Operational Research, 2010, 202(1): 8-15
[10] KIRCHLER D, WOLFLER CALVO R. A granular tabu search algorithm for the dial-a-ride problem[J]. Transportation Research Part B, 2013, 56: 120-135
[11] PAQUETTE J, CORDEAU J F, LAPORTE G, et al. Combining multicriteria analysis and tabu search for dial-a-ride problems[J]. Transportation Research Part B, 2013, 52: 1-16
[12] 贺冰倩, 李昆鹏, 成幸幸. 快递企业“最后一公里”快件收派优化方案研究[J]. 运筹与管理, 2019, 28(1): 27-34
HE Bingqian, LI Kunpeng, CHENG Xingxing. The research on the optimization of courier companies“last-mile”express pickup and Delivery Process[J]. Operations Research and Management Science, 2019, 28(1): 27-34
[13] FLEISCHMANN B, GNUTZNANN S, SANDVO? E. Dynamic vehicle routing based on online traffic information[J]. Transportation Science, 2004, 38(4): 420-433
[14] YANG J, JAILLET P, MAHMASSANI H S, 2004. Real-time multivehicle truckload pickup and delivery problems[J]. Transportation Science, 2004, 38(2): 135-148
[15] 孙宝凤, 史俊妍, 杨雪, 等. 基于实时信息的取送货动态车辆路径问题研究[J]. 宁波大学学报(理工版), 2019, 32(3): 87-94
SUN Baofeng, SHI Junyan, YANG Xue, et al. Solution for dynamic pickup and delivery problem based on real-time information[J]. Journal of Ningbo University (NSEE), 2019, 32(3): 87-94
[16] ATTANASIO A, BREGMAN J, GHIANI G, et al. Real-time fleet management at Ecourier Ltd. //ZEIMPEKIS V, GIAGLIS G M, MINIS I, et al(Eds.). Dynamic fleet management, operations research/computer science interfaces series[M]. Boston: Springer, 2007: 219–238.

大规模基站运维优化与车队规划研究

A Research on Large-scale Base Station Maintenance Optimization and Fleet Planning

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	刘广宇, 陈志坚, 於慧琳, 陈明瑶, 谢维. 动态的可选择可重复取送货基站运维路径优化研究[J]. 工业工程, 2020, 23(6): 89-94,123.
[2]	杨武成, 程文明. 求解考虑顺序相关调整时间的双边装配线平衡问题的变邻域搜索算法[J]. 工业工程, 2019, 22(5): 68-74.