The first step to choosing a heuristic is some basic problem analysis. How well does greedy/local search work, and what is its efficiency? Specifically, how much more computational effort can you afford? After you've answered this question, the next baseline is a set of random restarts that uses this allowed time.

In addition to being a benchmark on performance, having a large set of local optima can allow you to analyze several characteristics of the search space -- are the local optima clustered/concentrated in the search space (e.g. does your search space have global convexity)?, are there structures or features that are common to these clusters (i.e. what are the key schema to target/preserve in the change operators of your future heuristic)?, what is the variability in fitness among local optima?, etc

After that, you have a long path of subtle decisions as to whether you want to pursue iterated local search techniques, memetic algorithms (and the key design of the embedded genetic operators), and/or more constructive approaches like ant colony optimization. (Note: the "and" is there because most of these techniques can be hybridized to involve multiple components from multiple heuristic paradigms.)

Hope that helps, and good luck!

What is the problem? That is the first thing you should ALWAYS ask when it comes to combinatorial optimization. Without more, I can't provide much resources as algorithmic results relate to problems, very rarely whole disciplines. I'd have to recommend a list the size of maybe a large indoor pool otherwise.

Your question is very general to understand correctly. Please give any mathematical model in order to give you any constrictive advice. Give to us any link to understand your problem exactly.

At this current time I need to formalize some details before describing it in more detail. Thank you Stephen, Daniel and Gennady for taking the time to answer my question, however vague it was.