Combinatorial optimization problems involve finding the best solution from a wide set of possibilities, often arising in logistics, scheduling, and resource allocation. These problems, such as the Traveling Salesman Problem (TSP) and the Multi-Depot Vehicle Routing Problem (MDVRP), are typically NP-hard, with solution spaces growing exponentially, making systematic search methods impractical. We address a particular application of the MDVRP: the Electricity Technician Dispatch Problem (ETDP), which focuses on planning and optimizing routes for technicians providing maintenance services to customers located at various geographical points. In order to find the optimal travel routes, we propose a variant of the Genetic Algorithm (GA). In the initial population, customers are assigned to the nearest depot and routes are generated randomly for each technician. Then, during the improvement phase, our algorithm proceeds with its standard evolution process to explore better solutions. To evaluate the performance of our proposed method, we conducted experiments on several instances of the Cordeau benchmarking dataset and compared the results with those obtained from other methods, such as the Stochastic Local Search (SLS) and the Nearest-Neighbor Algorithm (NNA). The results show the effectiveness of our method in terms of both solution quality and computational efficiency.