I'm working on a paper that there is no previous paper for it to distinguish. its an old tool like ant colony optimization that is used on a new approach. I have sent the paper to a journal and they have said it doesn't have a good benchmark.
A benchmark is a standard or reference that will allow other authors compare their algorithms with yours. If the problem is known and other papers were published to solve it, follow the lead and compare your algorithm with them using the same parameters. If there are no other paper solving the problem, look for similar problems and check how they are described by certain variables.
The most basic parameter is the problem size, ie how many instances your problem has to deal with. For sorting algorithms, it is the number of items to sort. Usually, we start with quantities that could be easily handled in memory, increase to the limits of available memory, up to numbers that will need disk to store all items.
The second parameter is distribution. Are all instances equally probable and distributed along the possible spectrum? For sorting algorithms, if the set of items is partially sorted or totally random will impact the performance. In my thesis, I worked with geographical objects like cities, which are concentrated in some areas that were difficult to process, and other areas totally empty that could be easily recognized and discarded as not interesting.
Each problem might have multiple parameters, some are important, others are irrelevant. Your work is to identify them and choose values that are realistic and could show the strengths and weakness for different algorithms, not only yours.
Another set of parameters, very common when comparing software, is related to hardware, like the number of processors, total memory, network speed, etc...
Hope it helps, without reading your paper is hard to be specific.
As others have noted, it is very difficult to know how to act or suggest when we have no idea of the full picture. However, the problem seems to lie on the fact that you are attempting to use/adapt a method to apply on a particular problem, and there doesn't seem to be a benchmark solution to the problem you are trying to solve.
One way to gauge your work with respect to the literature is to also solve a well-known problem that has an established solution in addition to your problem. However, if you have already established that there is no benchmark, then there is nothing you can do about it.
Perhaps one of the reasons why they (the reviewers, I assume) want a benchmark is because they want you to prove that your paper is of value. Comparing the method to a benchmark is one of the ways that can be done. For instance, value can be proved by showing that your algorithm is faster/requires less computational power/finds better local optima/etc than someone else's. However, if there is no benchmark, you may want to look for other ways of displaying the value of your paper. For instance, one way to do that is to show that the method allows you to understand certain so far unknown features of the problem (there are other methods to accomplish this goal, but that utterly depends on your problem/field/goal). However, while I don't know your field nor the people nor the problem, simply applying a different method to solve a problem that has been solved by other methods may not provide sufficient novelty to yield publication, hence why they probably want you to show value.
On the other hand, maybe they want some sort of validation that your code/method is actually working properly, which is a very common supplement provided in many numerical papers. If that's what they want, you can apply your method to a different problem that has a benchmark, well-established solution, and show that you can reproduce the results.
Finally, it may just well be that you are trying to publish in the wrong venue. If you are trying to publish in the "Journal of Methods that Require Comparison to Benchmark Solutions", then you are probably out of scope.