Record Breaking Optimization Results Using the Ruin and Recreate Principle
✍ Scribed by Gerhard Schrimpf; Johannes Schneider; Hermann Stamm-Wilbrandt; Gunter Dueck
- Book ID
- 102970300
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 624 KB
- Volume
- 159
- Category
- Article
- ISSN
- 0021-9991
No coin nor oath required. For personal study only.
✦ Synopsis
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.