On One Routing Problem Oriented on the Problem of Dismantling Radiation-Hazardous Objects

We consider a problem of sequential visiting of megalopolises under the preceding conditions and costs functions depending on the list of tasks currently unfulfilled. Selection of a routing process involving index permutation, trajectory and starting point is optimized; point of finish is optimized also. We use additive criterion consisting in summary costs of external (as for megalopolises) movings, costs of works related to visiting of megalopolises and assessments of the terminal state. Procedure of construction of optimal solution based on widely understood dynamic programming is investigated. The statement is focused on the problem of dismantling the system of radiation-hazardous sources; at the same time, it is assumed that not all sources are dismantled (it is possible when workers receive maximum doses of radiation), which requires evacuation in conditions of radiation exposure of sources that remain undismantled. A specific variant of the criterion is reduced to the summary dose of radiation received by an employee both at the stage of dismantling and at the stage of evacuation. An algorithm based on the theoretical constructions is proposed and realized on personal computer; a computational experiment is completed.

Keywords

route; trace; preceding conditions; dynamic programming.

References

1. Chentsov A.A., Chentsov A.G. [A Model Variant of the Problem About Radiation Sources Utilization (Iterations Based on Optimization Insertions)]. Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 2017, no. 50, pp. 83-109. (in Russian) DOI: 10.20537/2226-3594-2017-50-08
2. Korobkin V.V., Sesekin A.N., Tashlikov O.L., Chentsov A.G. Metody marshrutizacii i ih prilozheniya v zadachah povysheniya bezopasnosti i ehffektivnosti ehkspluatacii atomnyh stanciy [Methods of Routing and Their Appendix in Problems of Increase of Efficiency and Safety of Operation of Nuclear Power Plants]. Moscow, Novye tekhnologii, 2012. (in Russian)
3. Chentsov A.A., Chentsov A.G., Grigor'ev A.M. Optimization "in Windows" for Routing Problems with Constraints. Communications in Computer and Information Science, 2019, vol. 1090, pp. 470-485. DOI: 10.1007/978-3-030-33394-2_36
4. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Berlin, Springer, 2002.
5. Cook, W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation. Princeton, Princeton University Press, 2012.
6. Gimadi Je.H., Khachay M.Yu. Ekstremal'nye zadachi na mnozhestvah perestanovok [Extremal Problems on Sets of Permutations]. Ekaterinburg, UMC UPI, 2016. (in Russian)
7. Liitle D, Murty K. Sweeney D., Karel C. An Algorithm for Traveling for the Traveling Salesman Problem. Economics and Mathematical Methods, 1965, vol. 1, no. 1, pp. 94-107. (in Russian)
8. Bellman R. [Application of Dynamic Programming to the Traveling Salesman Problem]. Kiberneticheskij sbornik, 1964, no. 9, pp. 219-228. (in Russian)
9. Held M., Karp M. [Application of Dynamic Programming to the Problem of Ordering]. Kiberneticheskij sbornik, 1964, no. 9, pp. 202-218. (in Russian)
10. Chentsov A.G. Jekstremal'nye zadachi marshrutizacii i raspredelenija zadanij: voprosy teorii [Extremal Problems of Routing and Distribution of Tasks: Questions of Theory]. Moscow, Izhevsk, RHD, 2008. (in Russian)
11. Kuratovskii K., Mostovskii A. Teoriya mnozhestv [Set Theory]. Moscow, Mir, 1970. (in Russian)
12. Dieudonne J. Osnovy sovremennogo analiza [Foundations of Modern Analysis]. Moscow, Mir, 1964. (in Russian)
13. Kormen T., Lejzerson Ch., Rivest R. Algoritmy: Postroenie i analiz [Introduction to Algorithms]. Moscow, MCNMO, 1999. (in Russian)
14. Warga J. Optimal'noe upravlenie differencial'nymi i funkcional'nymi uravneniyami [Optimal Control of Differential and Functional Equations]. Moscow, Nauka, 1977. (in Russian)
15. Chentsov A.G. [To Question of Routing of Works Complexes]. Bulletin of the Udmurt University. Mathematics. Mechanics. Computer Science, 2013, no. 1, pp. 59-82. (in Russian)
16. Chentsov A.G., Chentsov P.A. Routing under Constraints: Problem of Visit to Megalopolises. Automation and Remote Control, 2016, vol. 77, no. 11, pp. 1957-1974.
17. Chentsov A.G., Chentsov A.A., Sesekin A.N. On the Problem of Sequential Traversal of Megalopolises with Precedence Conditions and Cost Functions Depending on a List of Tasks. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2020, vol. 26, no. 3, pp. 219-234. (in Russian) DOI: 10.21538/0134-4889-2020-26-3-219-234
18. Petunin A.A, Chentsov A.G., Chentsov P.A. Optimal'naya marshrutizatsiya instrumenta mashin figurnoi rezki s chislovym programmnym upravleniem. Matematicheskie modeli i algoritmy [Optimal Tool Routing for CNC Shape Sheet Cutting Machines. Mathematical Models and Algoritms]. Ekaterinburg, Ural University, 2020. (in Russian)
19. Chentsov A.G., Chentsov A.A., Sesekin A.N. One Task of Routing Jobs in High Radiation Conditions. Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 2021, vol. 58, pp. 94-126. (in Russian) DOI: 10.35634/2226-3594-2021-58-06
20. Chentsov A.G., Chentsov P.A. The Routing Problems with Optimization of the Starting Point: Dynamic Programming. Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 2019, vol. 54, pp. 102-121. (in Russian) DOI: 10.20537/2226-3594-2019-54-08