工业工程

工业工程 ›› 2020, Vol. 23 ›› Issue (6): 89-94,123.doi: 10.3969/j.issn.1007-7375.2020.06.012

• 专题论述 • 上一篇    下一篇

动态的可选择可重复取送货基站运维路径优化研究

刘广宇1, 陈志坚2, 於慧琳1, 陈明瑶2, 谢维1   

  1. 1. 华南理工大学 工商管理学院，广东 广州 510640;
    2. 中国铁塔股份有限公司黑龙江省分公司，黑龙江 哈尔滨 150010
  • 收稿日期:2019-12-25 发布日期:2020-12-18
  • 作者简介:刘广宇(1994-)，男，河南省人，硕士研究生，主要研究方向为运筹优化
  • 基金资助:
    国家自然科学基金青年科学基金资助项目(71601079)

A Research on Base Station Operation and Maintenance of Dynamic Selectable and Repeatable Pickup and Delivery Problem

LIU Guangyu1, CHEN Zhijian2, YU Huilin1, CHEN Mingyao2, XIE Wei1   

  1. 1. School of Business Administration, South China University of Technology, Guangzhou 510640, China;
    2. China Tower Co., Ltd. Heilongjiang Branch, Harbin 150010, China
  • Received:2019-12-25 Published:2020-12-18

RichHTML

6

PDF

5727

摘要： 为了解决动态的可选择可重复取送货车辆路径优化问题，建立了基于动态需求的VRP模型。对于实时到来的需求，将动态的问题分解成多个静态的问题来求解。每次求解时，用初始插入算法得到初始解，设计改进的变邻域搜索算法来改善初始解。为了准确计算车辆到达配送点的时间，从百度地图实时读取任意两点的交通时间。利用铁塔公司历史数据构造多个算例表明，所提算法在1 min内得到较优解，和公司现有经验相比平均提升了46.47%，与插入算法相比平均提升30.38%。目前该算法已应用在该公司实际的基站运维中，有效地降低了该公司运维成本。

关键词: 可选择可重复取送货, 动态需求, 插入算法, 变邻域搜索, 基站运维

Abstract: In order to solve the dynamic multi-vehicle selective and repeatable pick-up and delivery problem with time windows (DMVSRPDPTW), a dynamic vehicle routing model based on dynamic requirements is established. For the real-time arrival requirements, the dynamic problem is divided into several static problems. Each time a static problem is solved, the initial solution is constructed by the insertion algorithm, and the improved variable neighborhood search algorithm is designed to improve the initial solution. In order to accurately calculate the time when the vehicle arrives at each request, the traffic time of any two points is read from the Baidu map. Multiple instances are constructed based on the historical data from the China Tower Co., Ltd illustrate: the proposed algorithm could get better results in one minute, and it has an average improvement of 46.47% compared with the existing experience of the company, and an average improvement of 30.38% compared with the insertion algorithm. The algorithm has been applied by the company in actual base station operation and maintenance to reduce the maintenance costs efficiently.

Key words: selective and repeatable pickup and delivery, dynamic requirements, insert algorithm, variable neighborhood search, base station operation and maintenance

中图分类号: