On One Routing Problem with Non-Additive Cost Aggregation

We investigate the problem on sequential round of megalopolises (nonempty finite sets) with preceding conditions and nonadditive aggregation of costs. We suppose that a variant of aggregation with respect to 'external' phase (by the estimation of the system of cycles, which are determined every time by the 'external' movement and internal jobs) corresponds to the 'bottleneck' problem with the correction parameter. At the 'internal' phase (within the cycle), an aggregation of costs with respect to external movement and carrying out works can be arbitrary. We construct nonadditive variant of the procedure of dynamic programming (DP) including economical variant, which uses preceding conditions. In the form of a program for a personal computer, we realize the optimal algorithm based on DP for the statement oriented to the problem on control of an autonomous system, which works in aggressive environment and implements a sequential process of dismantling of the sources of exposures (of this environment) to the system. Such a statement can correspond to the engineering problem on sequential dismantling of the sources of radiation under emergency situations on the nuclear power plants in the case of application of the robotic system with electronic equipment, which can work only if tolerances are complied with respect to influence of radiation during entire time interval. For this variant of the general statement, we implement a calculation experiment by means of a personal computer.

Keywords

dynamic programming; route; preceding conditions.

References

1. Melamed I.I., Sergeev S.I, Sigal I.Kh. The Travelling Salesman Problem. Automation and Remote Control, 1989, vol. 50, pp. 1147-1173.
2. Gareу R., Johnson D. Vichislitilnye mashiny i trudnoreshaemye zadachi [Computers and Intractabilitу]. Moscow, Mir, 1982.
3. Gutin G. Punnen A.P. The Traveling Salesman Problem and Its Variations. Berlin, Springer, 2002.
4. Gimadi E.H., Khachay M.Yu. Ektremalnye zadachi na mnogestvah perestanovok [ Extreme Permutation Problems]. Ekaterinburg, UMC UPI, 2016.
5. Bellman R. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the Association for Computing Machinery, 1962, vol. 9, pp. 61-63. DOI: 10.1145/321105.321111
6. Held M., Karp R.M. A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial and Applied Mathematics, 1962, vol. 10, no. 1, pp. 196-210.
7. Serveev S.I. Algorithms for the Minimax Problem of the Traveling Salesman. I. An Approach Based on Dynamic Programming. Automation and Remote Control, 1995, vol. 56, pp. 1027-1032.
8. Little J., Murthy K., Sweeny D., Karel C. An Algorithm for the Travelling Salesman Problem. Operation Research, 1963, vol. 11, no. 6, pp. 972-989. DOI: 10.1287/oper.11.6.972.
9. Chentsov A.G., Chentsov A.A. Routing of Displacements with Dynamic Constraints: 'Bottleneck Problem'. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2016, vol. 26, no. 1, pp. 121-140. (in Russian) DOI: 10.20537/vm160110
10. Sesekin A.N., Chentsov A.A., Chentsov A.G. [Routing with an Abstract Function of Travel Cost Aggregation]. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2010, vol. 16, no. 3, pp. 240-264. (in Russian)
11. Chentsov A.G., Saliy Ya.V. [A Problem on a Narrow Place]. Vserrossiiskya nauchno-prakticheskoy konferentsii 'Statistika. Modelirovanie. Optimizatsiya'. Chelyabinsk, Publishing center of SUSU, 2011, pp. 85-91. (in Russian)
12. Chentsov A.G., Chentsov A.A., Sesekin A.N. Dynamic Programming in the Generalized Bottleneck Problem and the Start Point Optimization. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2018. vol. 28, no. 3, pp. 348-363. (in Russian) DOI: 10.20537/vm180306
13. Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G. Metody marshrutizatsii i ikh prilogeniya v zadachakh povysheniay bezopasnosti i effektivnosti ekspluatatsii atomnykh stantsii [Routing Methods and Their Applications in Improving the Safety and Efficiency of Operation of Nuclear Power Plants]. Moscow, Noviye tekhnologii, 2012. (in Russian)
14. Chentsov A.G., Chentsov A.A. A Model Variant of the Problem about Radiation Sources Utilization (Iterations Based on Optimization Insertions). Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 2017, vol. 50, pp. 83-109. (in Russian) DOI: 10.20537/2226-3594-2017-50-08
15. Chentsov A.G. Extremalnie zadachi marshrutizatsiyi i raspredeleniya zadanii: voprosy teorii [Extremal Problems of Routing and Assignment of Tasks: Questions Theories]. Izhevsk, Regularnaya i khaoticheskaya dinamika, 2008. (in Russian)
16. Dieudonne J. Foundations of Modern Analysis. New York, Academic Press, 1960.
17. Kuratowski K, Mostowski A. Sets Theory. North-Holland Publishing Company, 1967.
18. Cormen T., Leiserson Ch., Rivest R. Introduction to Algorithms. London, The MIT Press, 1990.
19. Chentsov A.G., Chentsov P.A. Оptimization of the Start Point in the GTSP with the Precedence Conditions. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2018, vol. 11, no. 2, pp. 83-95. (in Russian) DOI: 10.14529/mmp180207
20. Chentsov A.G., Chentsov A.A. [Extremal Bottleneck Routing Problem with Constraints in the Form of Precedence Conditions]. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2008, vol. 14, no. 2, pp. 129-142. (in Russian)
21. Cheblokov I.B., Chentsov A.G. [About One Route Problem with Interior Works]. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2012, no. 1, pp. 96-119. (in Russian) DOI: 10.20537/vm120109
22. Chentsov A.G. [To Question of Routing of Works Complexes]. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, no. 1, pp. 59-82. (in Russian) DOI: 10.20537/vm130107
23. Lawler E.L. Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems. Stichting Mathematisch Centrum, 1979, pp. 1-16.
24. Chentsov A.G., Chentsov A.A. [To the Question of Finding the Value of a Route Problem with Restrictions]. Problemy upravleniya i informatiki, 2016, no. 1, pp. 41-54. (in Russian)