During any natural disaster, significant damage may occur to the power grid, disconnecting thousands of customers from the supply of electricity. The power utility companies need to deal with the after effects of such calamity in an efficient manner. A certain number of Power Line Technicians (PLT) are normally present across all the depots in a region, each responsible to maintain the grid for a specific geographic area. After a disaster hits a region, the utility companies will need to reallocate the PLTs to the depots depending on the number of outages in each area and to schedule the sequence in which PLTs will visit and fix the outages. The goal is to restore the service of all the customers as soon as possible while reducing the total wait times across all the customers. Although these objectives can be contradictory, one of the several mathematical models in the literature of Multi Depot Multi Vehicle Routing Problem (MDMVRP) with some modification can aim at finding an optimum schedule minimizing a weighted combination of the objectives. Such mathematical model cannot realistically be solved for medium or large scale problems.

In this research, we have introduced a Meta-Heuristic algorithm to solve the problem that optimizes both objective functions iteratively. The outages are clustered using K-means clustering and Linear Programming (LP) to minimize the overall initial restoration time. Then, each cluster is considered as a single Vehicle Routing Problem (VRP) which is solved to minimize the total weighted wait time. Tabu Search metaheuristics is used to improve the overall restoration time of the current solution. The two stages (clustering and routing optimizations) are executed iteratively until no further improvement is possible.

We have applied the algorithm to several simulated problems and tested the performance of the approach by taking into account the optimality of the solutions.