Abstract: The metric dimension problem (MDP) of graphs is a kind of combinatorial optimization problem which has important applications in the fields such as machine navigation, sonar system layout, chemistry, and data classification. To solve this problem, we establish a non-linear model by introducing a resolving table storage structure for the considered graphs; simultaneously, an improved ant colony algorithm for solving the proposed model is established, by improving the parameters design of existing ant colony algorithms and leveraging the strategy of global search and local search. Numerical comparison analysis verifies the efficiency of the new algorithm: the combination of global search and local search improves the solution quality of the proposed algorithm to a large extent; it is a great challenge to improve the solution quality of the algorithm on regular graphs; compared with the results of genetic algorithm on MDP, the algorithm proposed in this paper not only improves the solution quality, but also provides the minimal resolving set for graphs in the worst case. Furthermore, we examine the influences of some parameters on the solution quality of the algorithm, and propose a further research topic.

Key words: distance, metric dimension, resolving set, ant colony algorithm, resolving table, resolving neighbour, resolving degree, 0-1 coloring