A tabu search approach to automated map generalisation

ABSTRACT

Displaying map data at scales smaller than its source can result in objects that are either too small to be seen or too close to each other to be distinguishable. Furthermore, graphic conflicts become more likely when certain map symbols are no longer a true scale representation of the feature they represent. Map generalisation includes the processes by which such conflicts are resolved. The map generalisation technique presented here is exponential in the problem size and is, as such, combinatorially large (NP-hard). We show how the tabu search metaheuristic was used to resolve spatial conflict between objects after scaling, achieving near optimal solutions within practical time constraints.

REFERENCES

• 1: Brassel, K.E. and R. Weibel. (1988). "A review and conceptual framework of automated map generalisation", International Journal of Geographical Information Systems 2(3), 229--244.
• 2: Buttenfield, B.P. and R.B. McMaster. (1991). Map Generalisation: Making Rules for Knowledge Representation. Longman.
• 3: Fleurent, C. and J. A. Ferland (1996), "Genetic and Hybrid Algorithms for Graph Coloring", Annals of Operations Research, 63.
• 4: Glover, F. (1989). "Tabu Search-Part I", Operations Research Society of America Journal on Computing 1(3), 190--206.
• 5: Glover, F. (1990). "Tabu Search: A Tutorial", Interfaces 20, 74--94.
• 6: Fred Glover , Eric Taillard , Dominique de Werra, A user's guide to tabu search, Annals of Operations Research, v.41 n.1-4, p.3-28, 1993
• 7: Jin-Kao Hao , Raphaël Dorne , Philippe Galinier, Tabu Search for Frequency Assignment in Mobile Radio Networks, Journal of Heuristics, v.4 n.1, p.47-62, June 1998 [doi>10.1023/A:1009690321348]
• 8: Jones, C.B. and J.M. Ware. 1998. "Proximity relations with triangulated spatial models", The Computer Journal, 41(2), 71--83.
• 9: Jones, C.B., J.M. Ware and C.D. Eynon. (1999). "Triangulated Spatial Models and Neighbourhood Search: An Experimental Comparison with Quadtrees", The Visual Computer 15(5), 235--248.
• 10: Morley, G.D. and W.D. Grover. (2001). "Tabu Search Optimization of Optical Ring Transport Networks", Proceedings of IEEE Globecom2001.
• 11: Muller, J.C., J.P. Lagrange and R. Weibel. (1995). GIS and Generalisation Methodology and Practice. Taylor and Francis.
• 12: Robinson, A.H., J.L. Morrison, A.J. Muehrcke, S.C. Guptill and A.J. Kimerling. (1995). Elements of Cartography. John Wiley.
• 13: Shea, K.S. and R. B. McMaster. (1989). "Cartographic generalisation in a digital environment: When and how to generalise", Proceedings of 9th International Symposium on Computer-Assisted Cartography, 56--67.
• 14: Missae Yamamoto , Gilberto Camara , Luiz Antonio Nogueira Lorena, Tabu Search Heuristic for Point-Feature Cartographic Label Placement, Geoinformatica, v.6 n.1, p.77-90, March 2002 [doi>10.1023/A:1013720231747]
• 15: J. Mark Ware , Christopher B. Jones, Conflict Reduction in Map Generalization Using Iterative Improvement, Geoinformatica, v.2 n.4, p.383-407, December 1998 [doi>10.1023/A:1009713606524]
• 16: Ware, J.M., Wilson, I.D. and Ware, J.A., 2003, "A Knowledge-Based Genetic Algorithm Approach to Automating Cartographic Generalisation", to appear in Knowledge-based Systems.
• 17: Weibel, R. (1995). Cartography and GIS, Special Issue: Automated Map Generalisation, 22(4).
• 18: Robert Weibel , Christopher B. Jones, Computational Perspectives on Map Generalization, Geoinformatica, v.2 n.4, p.307-314, December 1998 [doi>10.1023/A:1009748903798]
• 19: Zoraster, S. (1997). "Practical results using simulated annealing for point feature label placement", Cartography and Geographical Information Systems, 24(4), 228--238.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
cartography, displacement, graphic conflict resolution