Dynamic programming in multi-level routing problems with constraints

The problem of sequential bypassing megacities (non-empty finite sets) under decomposition conditions is investigated: a set of tasks is specified by a system of clusters, the order of service of which is set. Each cluster defines a partial routing task with precedence conditions and cost functions allowing task list dependence. The statement is oriented towards engineering applications connected with sheet cutting on CNC-machines; this refers to the task of cutting in zones that are determined by technological requirements. The procedure of compositional solutions optimization is constructed, which is based on the separate application of a broadly understood dynamic programming and a specific rule linking the conditions of partial problems by assigning terminal components of additive criteria based on the extremum functions of these partial problems. The constructed algorithm implemented on a multi-core PC; computational experiment in solving problems of appreciable dimension (hundreds of megacities) showed the possibility of solving the problem at time acceptable for engineering practice.