Schrimpf, Gerhard and Schneider, Johannes and Stamm-Wilbrandt, Hermann and Dueck, Gunter (2000) Record breaking optimization results using the ruin and recreate principle. JOURNAL OF COMPUTATIONAL PHYSICS, 159 (2). pp. 139-171. ISSN 0021-9991
Full text not available from this repository. (Request a copy)Abstract
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. (C) 2000 Academic Press.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | ALGORITHM; combinatorial optimization; Monte Carlo; threshold accepting; global optimization; Traveling Salesman Problem; Vehicle Routing Problem; network optimization |
| Subjects: | 500 Science > 530 Physics |
| Divisions: | Physics > Institute of Theroretical Physics |
| Depositing User: | Dr. Gernot Deinzer |
| Date Deposited: | 16 May 2022 09:30 |
| Last Modified: | 16 May 2022 09:30 |
| URI: | https://pred.uni-regensburg.de/id/eprint/42586 |
Actions (login required)
 |
View Item |
