Maintaining Geographically Distributed Assets (GDA) requires complex team planning and scheduling decisions. Recently, many approaches have been introduced in the literature to solve this complex optimization problem. However, most of the introduced optimization models in the literature have considered this problem in its simplest form without involving realistic features such as precedence constraints, temporal dimension, and multiple depots. Therefore, the developed solutions are unlikely to be applicable in real-life systems. This study aims to determine the optimal number of teams and their schedules over a planning horizon to minimize the total cost associated with performing a group of maintenance activities in GDA. We formulated the problem as a Mixed Integer Linear Programming (MILP) model, which considers the release dates, due dates, interdependencies, teams working hours, and assets availability. The model is a more realistic variant of the multi-depot multi-period vehicle routing problem. As far as we know, this is the first study to consider all these features simultaneously. 

VRP is a well-known NP-Hard problem; therefore, we developed a novel hybrid metaheuristic algorithm to solve large practical instances of the problem. We combined Genetic Algorithm with a problem-specific solution encoding with a Simulated Annealing algorithm (GASA) to facilitate the search. We implemented the MILP model in IBM CPLEX OPL and coded GASA in Python. We performed an extensive computational study to test the performance of the proposed solution methods. The results over 600 instances revealed that GASA has a stable behavior dealing with different levels of the problem’s complexity, including the number of activities, assets, depots, days, teams, and interdependent activities. The MILP model is solved with a one-hour time limit. For the problem instances optimally solved by MILP, GASA provided solutions with an average error of 0.13%. Furthermore, when the MILP model was stopped due to the time limit, GASA produced an average of 4.4% better solutions than MILP. GASA was able to solve all instances in reasonable solution times. The performance of GASA was also demonstrated by real-life case studies of GDA maintenance systems of one of the leading companies in the energy sector in Oman. The results proved the effectiveness of GASA by generating solutions with an average of 39% less than the actual paid cost and 94% faster than the time spent on planning. The cost reductions in several instances reached up to 50%. The case study proved that the proposed GASA model is a promising tool to reduce the operational cost of the business and, accordingly, increase the company’s profits.