Metaheuristics are one of the most widespread solutions in the literature to address optimization problems. This application of metaheuristics makes them suitable for many problems in different fields of knowledge. However, the constant increase of new metaheuristics proposals has a problem; the comparison between different metaheuristics to determine which one to use is a very complex task for which it does not help that each author uses his way of evaluating his metaheuristics. In this work, we analyze and study different techniques used by authors of metaheuristics and evaluate their problems to propose a testing methodology that is objective, neutral, and fair for all metaheuristics evaluated. This methodology will also consider how to set the parameter optimization so that it is the same for all metaheuristics and problem instances to get as close as possible to an actual application of the metaheuristics. This new methodology will be tested in the experimentation by evaluating five metaheuristics widely known and extended in the literature.