The multi-objective problem of multi-depot vehicle routing (MOMDVRP) is proposed by considering the minimization of the traveled arc costs and the balance of routes. Seven mathematical models were reviewed to determine the route balance equation and the best-performing model is selected for this purpose. The solution methodology consists of three stages; in the first one, beginning solutions are built up by means of a constructive heuristic. In the second stage, fronts are constructed from each starting solution using the iterated local search multi-objective metaheuristics (ILSMO). In the third stage, we obtain a single front by using concepts of dominance, taking as a base the fronts of the previous stage. Thus, the first two fronts are taken and a single front is formed that corresponds to the current solution of the problem; next the third front is added to the current Pareto front of the problem, the procedure is repeated until exhaustion of the list of the fronts initially obtained. The resulting front is the solution to the problem. To validate the methodology we use instances from the specialized literature, which have been used for the multi-depot routing problem (MDVRP). The results obtained provide very good quality. Finally, decision criteria are used to select the most appropriate solution for the front, both from the point of view of the balance and the route cost.