On the Nonstationary Variant of Generalized Courier Problem with Interior Works

Abstract

The problem of the sequential circuit of megalopolises with preceding conditions and necessity of the interior works in megalopolises is considered in the article. It is supposed that the costs of permutations depend on the parameter having the sense of a discrete time. The above-mentioned dependence can reflect priorities of clients connected with served megalopolises and partially compensating inputs of executers. The constructed method corresponds to dynamic programming in a broad sense which is applied to solve the route problem with constraints. The extension of the problem, which use equivalent transformation of the system of constraints as a result of which route admissibility by precedence is changed into admissibility by deletion (the task from the list), introduced in the article. Therefore route constraints are reduced to the system of constraints by current interchange that allows us to obtain Bellman equations. To apply the later in the computational procedure of layers construction of Bellman equation we use the approach which implies the construction of the whole array of the values for the function mentioned; this approach is based on the use of essential lists of tasks (by precedence), which the saving of computations is achieved by.