Record Breaking Optimization Results Using the Ruin and Recreate Principle

A new optimization principle is presented. Solutions of problems are partly, but significantly, ruined and rebuilt or recreated afterwards. Performing this type of change frequently, one can obtain astounding results for classical optimization problems. The new method is particularly suited for more complex optimization problems (“discontinuous” ones, problems with hard-to-find admissible solutions, problems with complex objectives or many constraints). The method is an all-purpose-heuristic. Numerical results are given for the Traveling Salesman Problem, for the Vehicle Routing Problem with time windows, and for network optimization. Numerical evidence for the quality of the proposed principle is given. For most of the instances of a research library of problems, the ruin and recreate (R&R) implementation achieved the best published results. For many instances, better or much better solutions could be found.