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