Abstract This paper states a novel hybrid-metaheuristic based on deterministic swapping, evolutionary algorithms and simulated annealing inspired algorithms for the multi-objective optimization of combinatorial problems. The proposed algorithm is named EMSA. It is an improvement of MODS algorithm. Unlike MODS, EMSA works using a search direction given by the assignation of weights to each objective function of the combinatorial problem to optimize. Lastly, EMSA is tested using well know instances of the Bi-Objective Traveling Salesman Problem (BTSP) from TSPLIB. Its results were compared with MODS metaheuristic (its predecessor). The comparison was made using metrics from the specialized literature such as Spacing, Generational Distance, Inverse Generational Distance and Non-Dominated Generation Vectors. In every case, the EMSA results on the metrics were always better and in some of those cases, the superiority was 100%.