Archive of Issues
Russia Yekaterinburg
Section  Mathematics 
Title  About one route problem with interior works 
Author(s)  Cheblokov I.B.^{a}, Chentsov A.G.^{ab} 
Affiliations  Ural Federal University^{a}, Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences^{b} 
Abstract  The route problem about visiting of multifunction sections with constraints of type of preceding conditions is considered. By setting of this problem the fulfilment of works on the abovementioned sections is provided. Any solution is defined in the form of the ordered pair for which components have the sense of the route (the index permutation) and the trace (trajectory) of the movements with respect to sections of multifunctions. The agreement of the trace and route is realized by procedures of the sequential choice of ordered pairs (the point of arrival and the starting point) of Descartes "squares" of the multifunction sections numbered in correspondence with a route. The cost aggregation is presupposed additive; the total criterion includes the costs of (exterior) movements between sections of multifunctions, interior works, and the final state. Under constructing of extension of the basic problem that realizes the used Bellman function, the equivalent transformation of constraints is applied: admissibility of routes by preceding is replaced onto admissibility by deletion of tasks (of the list) that corresponds to the constraints variant with respect to the current movements from one set onto another. An analog of the Bellman equation realized by procedure of the transformation of layers of Bellman function is obtained. The operation defining this transformation is further used for constructing of heuristic algorithms realized on PC. 
Keywords  route, permutation, trace, Bellman function 
UDC  517.977 
MSC  76D55, 90C27 
DOI  10.20537/vm120109 
Received  9 February 2011 
Language  Russian 
Citation  Cheblokov I.B., Chentsov A.G. About one route problem with interior works, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2012, issue 1, pp. 96119. 
References 

Full text 