Routing problems: constraints and optimality**This work was supported by Act 211 Government of the Russian Federation, contract N 02.A03.21.0006

We consider the issues of routing under constraints and formulate a mathematical problem of visiting megalopolises. The order of visits is subject to precedence constraints. In addition, the cost functions depend on the set of pending tasks. The quality criterion is a variety of the additive criterion. The problem is established within the dynamic programming framework, however, a heuristic is proposed and implemented to solve practical problems of large dimensionality.