Article ID: | iaor19981863 |
Country: | Netherlands |
Volume: | 86 |
Issue: | 3 |
Start Page Number: | 565 |
End Page Number: | 579 |
Publication Date: | Nov 1995 |
Journal: | European Journal of Operational Research |
Authors: | Sutter Alain, Chardaire Pierre, Lutton Jean Luc |
Keywords: | programming: travelling salesman |
We propose a new heuristic method to solve 0–1 optimisation problems. Basically, the method is an extension of the simulated annealing algorithm. At a given temperature, approximations of the variable value expectations are computed. This information allows us to fix the variables as the temperature decreases, so that the size of the problem is progressively reduced. It follows a significant improvement compared with pure simulated annealing: we obtain better solutions in less CPU time. Variable value expectations can be estimated by simulation procedures. In the special case of unconstrained 0–1 optimisation problems, estimates can be obtained by solving an analytic system. Two problems are examined: the travelling salesman problem and the minimisation of an unconstrained 0–1 quadratic function.