Abstract. In this paper we consider one of the variants of the routing problem on a plane integer lattice. It is shown that this problem can be represented as a problem of searching for words with certain properties over a finite alphabet. In turn, the problem of finding optimal words can be considered as a problem with fragmentary structure. A combinatorial estimate for set of feasible words was derived and the lower bound of the density was established for the problem of finding optimal line density. An evolutionary-fragmentary model of the routing problem is constructed. Optimal and near-optimal solutions are obtained for this problem for small sizes.

Keywords: routing problem, routing density, combinatorial optimization, fragmentary structure, evolutionary model.