Probably the first thing to try is to implement a random solution generator, which gives the possibility to get things tested and running. The assessment of an random solution requires the understanding of all constraints in the problem and consequently the definition of an evaluation function.

Then, improve the random solution generator starting introducing heuristics (e.g. variable-values heuristics)

Randomize the heuristic.

To design a local search algorithm for an optimization problem you have to define the following components:

1. candidate solution representation
2. evaluation function
3. initial solution
4. a neighborhood operator
5. step function
6. stopping criterion

After implementation and test of the above components, improvements in efficiency (ie, computation time) can be achieved by:

A. fast delta evaluation
B. neighborhood pruning
C. clever use of data structures

Improvements in quality can be achieved by:

A. application of a metaheuristic
B. definition of a larger neighborhood

Metaheuristics

• start introducing random non-improving moves in the search (stochastic local search)
• iterated local search with a random perturbation is quite easy to obtain and should be checked (works well in TSP). Alternatively try GRASP.
• if a best improvements can be implemented to be very fast consider applying tabu search
• variable neighborhood search should be the next trial. It is more time demanding in the implementation since it requires more than one local search (each one implemented efficently)