On the Nonstationary Variant of Generalized Courier Problem with Interior Works

A. G. Chentsov ; P. A. Chentsov

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 6 (2013) no. 2, pp. 88-107

Résumé

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. The use of the theory developed can be connected with the problems dealing with the reduction of radioactive influence on employees of atomic power plants at work under emergency conditions as well as the problems of transport service for a great number of clients under conditions of priority influencing the choice of service discipline.

Détail

Mots-clés : route
Keywords: preceding conditions, dynamic programming.