This paper presents the investigation of an evolutionary multi-objective simulated annealing algorithm with variable neighborhoods to solve the multi-objective multicast routing problems in telecommunications. The hybrid algorithm aims to carry out a more flexible and adaptive exploration in the complex search space by using features of the variable neighborhood search to find more non-dominated solutions in the Pareto front. Different neighborhood strictures have been designed with regard to the set of objectives, aiming to drive the search towards optimising all objectives simultaneously. A large number of simulations have been carried out on benchmark instances and random networks with real world features including cost, delay and link utilisations. Experimental results demonstrate that the proposed evolutionary multi-objective simulated annealing algorithm with variable neighborhoods is able to find high quality non-dominated solutions for the problems tested. In particular, the variable neighborhood structures which are specifically designed for each objective significantly improved the performance of the proposed algorithm compared with variants of the algorithm with a single neighborhood.