Corresponding author: Chentsov Aleksandr G., D. Sc., Professor, N. N. Krasovskii Institute of Mathematics and Mechanics, 620990, Ekaterinburg, Russian Federation; Ural Federal University, 620002, Ekaterinburg, Russian Federation

E-mail: chentsov@imm.uran.ru
Received on July 7, 2016
Accepted on July 14, 2016

The article is devoted to an implementation of the scheme of independent computations for solving the routing problem with precedence constraints and (in the theoretical part) with the cost functions depending on the list of tasks. The prototype of the considered statement is the well-known intractable traveling salesman problem, however, the considered statement is distinguished by the above-mentioned qualitative features. The problem is solved by the dynamic programming method. It is not necessary to construct the whole array of the values of the Bellman function, which is motivated by a desire to decrease the computational complexity. The parallel algorithm for determining the value of the problem value (the global extremum) and the "complete" solution algorithm, which includes the construction of an optimal route, are treated separately. The latter algorithm was realized on the Uran supercomputer; it made use of the (finite) nodes system. Every node had multiple processors, and the totality of the nodes formed the computational cluster. It was possible for certain values of the Bellman function to be (independently) computed by different processors. The developed methods may be applied to certain problems of the nuclear power generation, including the problem of minimization of the radiation exposure of the staff during the emergency situations, similar to Chernobyl and Fukushima. Another possible application may be connected with machine engineering problems, such as routing of a cutting tool of CNC cutting machines. And the last but not the least, this statement may be used to model many problems in the sea and air transportation, and also certain problems in the airborne wildfire detection.
Keywords: dynamic programming, route, precedence constraints, feasible sets (of tasks), state space layers, independent computations, Bellman function

For citation:

Chentsov A. G., Grigoryev A. M. Dynamic Programming Method in a Routing Problem: a Scheme of Independent Computations, Mekhatronika, Avtomatizatsiya, Upravlenie, 2016, vol. 17, no. 12, pp. 834—846.

DOI: 10.17587/mau.17.834-846

To the contents