Efficiency in logistics is often affected by the fair distribution of the customers along the routes and the available depots for goods delivery. From this perspective, in this study, the Multi-depot Vehicle Routing Problem (MDVRP), by considering two objectives, is addressed. The two objectives in conflict for MDVRP are the distance traveled by vehicles and the standard deviation of the routes’ length. A significant standard deviation value provides a small distance traveled by vehicles, translated into unbalanced routes. We have used a weighted average objective function involving the two objectives. A Variable Neighborhood Search algorithm within a Chu-Beasley Genetic Algorithm has been proposed to solve the problem. For decision-making purposes, several values are chosen for the weight factors multiplying the terms at the objective function to build up a non-dominated front of solutions. The methodology is tested in large-size instances for the MDVRP, reporting noticeable results for managerial insights.