Abstract: Network maintenance by service engineers (SE) involves a range of activities to ensure that the network is functioning optimally and providing reliable service to users. To optimize the network maintenance process, company need to find suitable places for service offices, decide how to distribute engineers between them, and find a partition of sites into office responsibility zones. These decisions should take into account multiple factors: routes from offices and sites, fair workload distribution, zone topologies, etc. Such a problem can be considered as a generalization of a well-known facility location problem with additional geometric and workload constraints. In this study, we consider the following formulation of the network maintenance optimization problem. There is a set of sites, a set of potential service office locations, and a limited number of engineers. The site workload is defined by a vector of integers. The objective is to decide which offices should be open, distribute engineers between offices, and find a site partition. With respect to the referenced industrial scenarios, different types of zone topologies are considered. Two criteria are considered to be minimized: total traveling time between offices and sites in a related zone and minimal deviation of workload per worker. An original multi-stage heuristic, which includes greedy and Tabu-search approaches, is proposed. The algorithm includes geometry-based search steps to obtain solutions with star and convex zone topologies. Numerical experiments on industrial instances with up to 10000 sites and 20 offices demonstrate the efficiency of the proposed approach. The obtained results outperformed the CPLEX solver and demonstrated algorithm scalability and obtained solution quality.

Cite: Davydov I. , Gabdullina A. , Shevtsova M. , Arkhipov D.
Tabu Search for a service zone clustering problem
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 Jun - 6 Jul 2024