Discrete optimization by optimal control methods. III. The dynamic traveling salesman problem

For one of the basic variants of the dynamic minisum traveling salesman problem, a decomposition scheme is designed, which in general gives a new approximate solution algorithm. This algorithm is exact if certain conditions are imposed on the distance matrix. The problem is solved with the sufficient optimality conditions known in optimal control theory.