Abstract: Hybrid evolutionary metaheuristics tend to enhance search capabilities, by improving intensication and diversication, through incorporating dierent cooperative metaheuristics. In this paper, an improved version of the Hybrid Evolutionary Metaheuristics (HEMH) [7] is presented. Unlike HEMH, HEMH2 uses simple inverse greedy algorithm to construct its initial population. Then, the search eorts is directed to improve these solutions by exploring the search space using binary differential evolution. After a certain number of evaluations, path-relinking is applied on high quality solutions to investigate the non-visited regions in the search space. During evaluations, the dynamic-sized neighborhood structure is adopted to shrink/extend the mating/updating range. Furthermore, the Pareto adaptive epsilon concept is used to control the archiving process with preserving the extreme solutions. HEMH2 is verified against its predecessor HEMH and the MOEA/D [13], using a set of MOKSP instances from the literature. The experimental results indicate that the HEMH2 is highly competitive and can achieve better results.