10.23683/2311-3103-2017-9-169-181
DYNAMIC PROGRAMMING AND HEURISTIC METHODS IN ROUTING PROBLEMS
Chentsov , P.A.
P.A.
Chentsov
Ural Federal University
Chentsov, A.G.
A.G.
Chentsov
Ural Federal University
Southern Federal University
2017
Article
Routing problems
precedence conditions
metal cut optimization
17-01-2018
2311-3103
The "additive" route problems with constraints and possible dependence of cost functions on
tasks list are considered. Such settings are natural under investigation of engineering problems
arising in nuclear power and mechanical engineering. In first case, decrease in dose rate for the
worker of the nuclear power plant under dismantling radiation elements of equipment is discussed.
In second case, procedures are connected with sheet cutting on machines with a numerical control.
In article, an issue connected with employment of dynamic programming for solution of problems
with constraints and above-mentioned dependence of cost functions from task list is considered.
Procedures of testing and local improvements of heuristics are borne in mind. In both versions
realized for sub-problems of moderate dimension apparatus of the widely understood dynamic
programming is used. But, it is supposed that the above-mentioned sub-problems are complicated
by the same conditions as in original “big” problem (constraints, cost functions with
dependency on tasks list). For implementation of the “local” dynamic programming, the scheme
with using of precedence constraints to reduce of the computational complexity is realized (precedence
conditions are available practically in all variants of above-mentioned applied problems);
wherein, the construction of total array of Bellman function is not required. For the accounting of
emerging under performance of tasks dynamic constraints, special (threshold) cost functions with
role of palpable penalties for violation of constraints are used. Results of computing experiment
both for testing of above-mentioned heuristics and under solution of problems with palpable dimension
are given. The article is based on a lecture one of authors in conference MKPU-10
ru