An improved time-sensitive metaheuristic framework for combinatorial optimization

We introduce a metaheuristic framework for combinatorial optimization. Our framework is similar to many existing frameworks (e.g. [27]) in that it is modular enough that important components can be independently developed to create optimizers for a wide range of problems. Ours is different in many aspects. Among them are its combinatorial emphasis and the use of simulated annealing and incremental greedy heuristics. We describe several annealing schedules and a hybrid strategy combining incremental greedy and simulated annealing heuristics. Our experiments show that (1) a particular annealing schedule is best on average and (2) the hybrid strategy on average outperforms each individual search strategy. Additionally, our framework guarantees the feasibility of returned solutions for combinatorial problems that permit infeasible solutions. We, further, discuss a generic method of optimizing efficiently bottle-neck problems under the local-search framework. © Springer-Verlag 2004