Local search for the Steiner tree problem in the Euclidean plane. (English) Zbl 0933.90065
Summary: Most heuristics for the Steiner tree problem in the Euclidean plane perform a series of iterative improvements using the minimum spanning tree as an initial solution. We may therefore characterize them as local search heuristics. In this paper, we first give a survey of existing heuristic approaches from a local search perspective, by setting up solution spaces and neighbourhood structures. Secondly, we present a new general local search approach which is based on a list of full Steiner trees constructed in a preprocessing phase. This list defines a solution space on which three neighbourhood structures are proposed and evaluated. Computational results show that this new approach is very competitive from a cost-benefit point of view. Furthermore, it has the advantage of being easy to apply to the Steiner tree problem in other metric spaces and to obstacle avoiding variants.
MSC:
| 90C35 | Programming involving graphs or networks |
References:
| [1] | E.H.L. Aarts, J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization, Wiley, New York, 1997; E.H.L. Aarts, J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization, Wiley, New York, 1997 · Zbl 0869.00019 |
| [2] | A. Armillotta, G. Mummolo, A heuristic algorithm for the Steiner problem with obstacles. Technical report, Dipt. di Pregettazione e Produzione Industriale, Univ. degli Studi di Bari, Bari, 1988; A. Armillotta, G. Mummolo, A heuristic algorithm for the Steiner problem with obstacles. Technical report, Dipt. di Pregettazione e Produzione Industriale, Univ. degli Studi di Bari, Bari, 1988 |
| [3] | S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, in: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996, p. 2-13; S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, in: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996, p. 2-13 |
| [4] | Beasley, J. E., OR-library: Distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1069-1072 (1990) |
| [5] | Beasley, J. E., A heuristic for Euclidean and rectilinear Steiner problems, European Journal of Operational Research, 58, 284-292 (1992) · Zbl 0757.90080 |
| [6] | Beasley, J. E.; Goffinet, F., A delaunay triangulation-based heuristic for the Euclidean Steiner problem, Networks, 24, 215-224 (1994) · Zbl 0807.90115 |
| [7] | Berman, P.; Ramaiyer, V., Improved approximations for the Steiner tree problem, Journal of Algorithms, 17, 3, 381-408 (1994) · Zbl 0820.68049 |
| [8] | Chang, S. K., The generation of minimal trees with a Steiner topology, J. ACM, 19, 699-711 (1972) · Zbl 0251.94031 |
| [9] | Chapeau-Blondeau, F.; Janez, F.; Ferrier, J.-L., A dynamic adaptive relaxation scheme applied to the Euclidean Steiner minimal tree problem, SIAM Journal on Optimization, 7, 4, 1037-1053 (1997) · Zbl 0890.90173 |
| [10] | Chung, F. R.K.; Graham, R. L., Steiner trees for ladders, Annals of Discrete Mathematics, 2, 173-200 (1978) · Zbl 0384.05030 |
| [11] | D.R. Dreyer, M.L. Overton, Two heuristics for the Steiner tree problem, Technical Report 724, Computer Science Department, New York University, 1996; D.R. Dreyer, M.L. Overton, Two heuristics for the Steiner tree problem, Technical Report 724, Computer Science Department, New York University, 1996 · Zbl 0909.90199 |
| [12] | Du, D.-Z.; Zhang, Y., On better heuristics for Steiner minimum trees, Mathematical Programming, 57, 193-202 (1992) · Zbl 0784.90094 |
| [13] | Gilbert, E. N.; Pollak, H. O., Steiner minimal trees, SIAM Journal on Applied Mathematics, 16, 1, 1-29 (1968) · Zbl 0159.22001 |
| [14] | G.R. Grimwood, The Euclidean Steiner Tree Problem: Simulated Annealing and Other Heuristics. Master’s thesis, Institute of Statistics and Operations Research, Victoria University of Wellington, New Zealand, 1994; G.R. Grimwood, The Euclidean Steiner Tree Problem: Simulated Annealing and Other Heuristics. Master’s thesis, Institute of Statistics and Operations Research, Victoria University of Wellington, New Zealand, 1994 |
| [15] | J. Hesser, R. Männer, O. Stucky. Optimization of Steiner trees using genetic algorithms, in: Proceedings of the Third International Conference on Genetic Algorithm, 1989, p. 231-236; J. Hesser, R. Männer, O. Stucky. Optimization of Steiner trees using genetic algorithms, in: Proceedings of the Third International Conference on Genetic Algorithm, 1989, p. 231-236 |
| [16] | T. Hürlimann, The Euclidean Steiner tree problem, implementation of a heuristic, Technical Report 94-14, Institute of Informatics, University of Fribourg, 1994; T. Hürlimann, The Euclidean Steiner tree problem, implementation of a heuristic, Technical Report 94-14, Institute of Informatics, University of Fribourg, 1994 |
| [17] | Hwang, F. K., A linear time algorithm for full Steiner trees, Operations Research Letters, 4, 5, 235-237 (1986) · Zbl 0582.05022 |
| [18] | F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem, Annals of Discrete Mathematics 53, Elsevier, Amsterdam, 1992; F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem, Annals of Discrete Mathematics 53, Elsevier, Amsterdam, 1992 · Zbl 0774.05001 |
| [19] | Hwang, F. K.; Weng, J. F., The shortest network under a given topology, Journal of Algorithms, 13, 468-488 (1992) · Zbl 0764.68119 |
| [20] | Jayadeva; Bhaumik, B., A neural network for the Steiner minimal tree problem, Biological Cybernetics, 70, 485-494 (1994) · Zbl 0805.68107 |
| [21] | Johnson, D. S.; Aragon, C. R.; McGeoch, L. A.; Schevon, C., Optimization by simulated annealing: An experimental evaluation; Part I, graph partitioning, Operations Research, 37, 6, 865-892 (1989) · Zbl 0698.90065 |
| [22] | Karp, R., Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane, Mathematics of Operations Research, 2, 209-224 (1977) · Zbl 0391.90091 |
| [23] | P. Korhonen, An algorithm for transforming a spanning tree into a Steiner tree, in: Survey of Math. Programming, Proceedings of the Ninth International Math. Program. Symp., vol. 2, North-Holland, Amsterdam, 1974, p. 349-357; P. Korhonen, An algorithm for transforming a spanning tree into a Steiner tree, in: Survey of Math. Programming, Proceedings of the Ninth International Math. Program. Symp., vol. 2, North-Holland, Amsterdam, 1974, p. 349-357 · Zbl 0445.05043 |
| [24] | Lundy, M., Applications of the annealing algorithm to combinatorial problems in statistics, Biometrika, 72, 191-198 (1985) |
| [25] | K. Mehlhorn, S. Näher, LEDA - A Platform for Combinatorial and Geometric Computing. Max-Planck-Institut für Informatik, Saarbrücken, Germany, http://www.mpi-sb.mpg.de/LEDA/leda.html, 1996; K. Mehlhorn, S. Näher, LEDA - A Platform for Combinatorial and Geometric Computing. Max-Planck-Institut für Informatik, Saarbrücken, Germany, http://www.mpi-sb.mpg.de/LEDA/leda.html, 1996 |
| [26] | Melzak, Z. A., On the problem of Steiner, Canadian Mathematical Bulletin, 4, 2, 143-148 (1961) · Zbl 0101.13201 |
| [27] | M. Nielsen, Abstakte Voronoi-diagrammer i ESTPO-heuristikker, Master’s thesis, DIKU, Department of Computer Science, University of Copenhagen, 1994; M. Nielsen, Abstakte Voronoi-diagrammer i ESTPO-heuristikker, Master’s thesis, DIKU, Department of Computer Science, University of Copenhagen, 1994 |
| [28] | F.P. Preparata, M.I. Shamos, Computational Geometry: An Introduction, 2nd ed., Springer, New York, 1988; F.P. Preparata, M.I. Shamos, Computational Geometry: An Introduction, 2nd ed., Springer, New York, 1988 · Zbl 0759.68037 |
| [29] | Provan, J. S., An approximation scheme for finding Steiner trees with obstacles, SIAM Journal on Computing, 17, 5, 920-934 (1988) · Zbl 0665.68053 |
| [30] | Ravada, S.; Sherman, A. T., Experimental evaluation of a partitioning algorithm for the Steiner tree problem in \(R^2\) and \(R^3\), Networks, 24, 409-415 (1994) · Zbl 0820.90118 |
| [31] | Sleator, D. D.; Tarjan, R. E., A data structure for dynamic trees, Journal of Computer and System Sciences, 26, 362-391 (1983) · Zbl 0509.68058 |
| [32] | J.M. Smith, Generalized Steiner network problems in engineering design, In: Design Optimization, Academic Press, New York, 1985; J.M. Smith, Generalized Steiner network problems in engineering design, In: Design Optimization, Academic Press, New York, 1985 |
| [33] | Smith, J. M.; Lee, D. T.; Liebman, J. S., An \(O(n logn)\) heuristic for the rectilinear Steiner minimal tree problem, Engineering Optimization, 4, 179-192 (1980) |
| [34] | Smith, J. M.; Lee, D. T.; Liebman, J. S., An \(O(n logn)\) heuristic for Steiner minimal tree problems on the Euclidean metric, Networks, 11, 23-29 (1981) · Zbl 0459.68032 |
| [35] | Smith, J. M.; Liebman, J. S., Steiner trees, Steiner circuits and the interference problem in building design, Engineering Optimization, 4, 15-36 (1979) |
| [36] | Smith, J. M.; Weiss, R.; Patel, M., An \(O(N^2)\) heuristic for Steiner minimal trees in \(E^3\), Networks, 25, 273-289 (1995) · Zbl 0856.90120 |
| [37] | Smith, W. D., How to find Steiner minimal trees in Euclidean \(d\)-space?, Algorithmica, 7, 2/3, 137-177 (1992) · Zbl 0751.05028 |
| [38] | Soukup, J., Minimum Steiner trees, roots of a polynomial and other magic, ACM/SIGMAP Newsletter, 22, 37-51 (1977) |
| [39] | Soukup, J.; Chow, W. F., Set of test problems for the minimum length connection networks, ACM/SIGMAP Newsletter, 15, 48-51 (1973) |
| [40] | Suzuki, A.; Iri, M., A heuristic method for the Euclidean Steiner problem as a geometrical optimization problem, Asia-Pacific Journal of Operational Research, 3, 2, 109-122 (1986) · Zbl 0625.90019 |
| [41] | Thompson, E. A., The method of minimum evolution, Annals of Human Genetics, 36, 333-340 (1973) · Zbl 0245.92012 |
| [42] | Voß, S., Steiner’s problem in graphs: Heuristic methods, Discrete Applied Mathematics, 40, 45-72 (1992) · Zbl 0758.68032 |
| [43] | D.M. Warme, Personal communication, 1997; D.M. Warme, Personal communication, 1997 |
| [44] | Winter, P.; Smith, J. M., Steiner minimal trees for three points with one convex polygonal obstacle, Annals of Operations Research, 33, 577-599 (1991) · Zbl 0748.90073 |
| [45] | Winter, P.; Zachariasen, M., Euclidean Steiner minimum trees: An improved exact algorithm, Networks, 30, 149-166 (1997) · Zbl 0893.90170 |
| [46] | M. Zachariasen, P. Winter, Concatenation-based greedy heuristics for the euclidean steiner tree problem, Algorithmica (to appear); M. Zachariasen, P. Winter, Concatenation-based greedy heuristics for the euclidean steiner tree problem, Algorithmica (to appear) · Zbl 0944.68146 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
