Dynamic programming in the routing problem: decomposition variant

Abstract

The questions of applying the dynamic programming (DP) apparatus to the routing problem with constraints and cost functions with the tasks list dependence are investigated. It is supposed that binary partition of the task set is given; tasks of the first task group must be fulfilled before the fulfillment of the task of the second group begins. In each of the groups, precedence conditions may be present. This setting can be applied in the case of sheet cutting on CNC machines, where two above-mentioned groups form zones planned at the cutting stage. In general case, for the optimal solution construction, the two-stage variant of DP is used. Linking two versions of DP is realized by identification of the criterion terminal component for service problem of the first group with extremum function connected with the second group. The connection of optimal solutions for above-mentioned two problems allows to construct an optimal solution for the initial joint problem. Based on the theoretical constructions algorithm realized on personal computer is constructed; computing experiment is realized.