Automatic metro map layout using multicriteria optimization.
This paper describes an automatic mechanism for drawing metro maps. We apply multicriteria optimization to find effective placement of stations with a good line layout and to label the map unambiguously. A number of metrics are defined, which are used in a weighted sum to find a fitness value for a layout of the map. A hill climbing optimizer is used to reduce the fitness value, and find improved map layouts. To avoid local minima, we apply clustering techniques to the map-the hill climber moves both stations and clusters when finding improved layouts. We show the method applied to a number of metro maps, and describe an empirical study that provides some quantitative evidence that automatically-drawn metro maps can help users to find routes more efficiently than either published maps or undistorted maps. Moreover, we have found that, in these cases, study subjects indicate a preference for automatically-drawn maps over the alternatives.
School of Computing, University of Kent, Canterbury, Kent CT2 7NF, UK. jonathan.stott@axonuk.com
Jonathan
J
Stott
Peter
P
Rodgers
Juan Carlos
JC
Martínez-Ovando
Stephen G
SG
Walker
D000465:Algorithms; D003196:Computer Graphics; D003198:Computer Simulation; D017076:Computer-Aided Design; D006801:Humans; D016247:Information Storage and Retrieval / Q000379:methods*; D008377:Maps as Topic; D010363:Pattern Recognition, Automated / Q000379:methods; D012984:Software; D014584:User-Computer Interface