On one routing problem modeling movement in radiation fields

A. G. Chentsov   ; A. A. Chentsov   ; A. M. Grigoryev

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 27 (2017) no. 4, pp. 540-557

Résumé

We consider a routing problem with constraints and complicated cost functions. The visited objects are assumed to be clusters, or megalopolises (nonempty finite sets), and the visit to each of them entails certain tasks, which we call interior jobs. The order of visits is subject to precedence constraints. The costs of movements depend on the set of pending tasks (not yet complete at the time of the movement), which is also referred to as “sequence dependence”, “position dependence”, and “state dependence”. Such a dependence arises, in particular, in routing problems concerning emergencies at nuclear power plants, similar to the Chernobyl and Fukushima Daiichi incidents. For example, one could consider a disaster recovery problem concerned with sequential dismantlement of radiation sources; in this case, the crew conducting the dismantlement is exposed to radiation from the sources that have not yet been dealt with. This gives rise to dependence on pending tasks in the cost functions that measure the crew's radiation exposure. The latter dependence reflects the “shutdown” operations for the corresponding radiation sources. This paper sets forth an approach to a parallel solution for this problem, which was implemented and run on the URAN supercomputer.

Détail

Keywords: dynamic programming, precedence constraints, parallel computation.
Mots-clés : route

Bibliographie

[1] Garey M. R., Johnson D. S., Computers and intractability: A guide to the theory of $NP$-completeness, W.H. Freeman, New York, 1979, 338 pp. | MR | Zbl

[2] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Springer US, New York, 2007 | DOI | MR | Zbl

[3] Cook W. J., In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton University Press, New Jersey, 2012, 248 pp. | MR | Zbl

[4] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. I: Theoretical issues”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[5] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. II: Exact methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[6] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Approximate algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | MR | Zbl

[7] Little J. D. C., Murty K. G., Sweeney D. W., Karel C., “An algorithm for the traveling salesman problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[8] Bellman R., “Dynamic programming treatment of the travelling salesman problem”, J. ACM, 9:1 (1962), 61–63 | DOI | MR | Zbl

[9] Held M., Karp R. M., “A dynamic programming approach to sequencing problems”, Journal of the Society for Industrial and Applied Mathematics, 10:1 (1962), 196–210 | DOI | MR | Zbl

[10] Gimadi E. Kh., Khachai M. Yu., Extremal problems on sets of permutations, UMC UPI, Yekaterinburg, 2016, 220 pp.

[11] Leon V. J., Peters B. A., “Replanning and analysis of partial setup strategies in printed circuit board assembly systems”, International Journal of Flexible Manufacturing Systems, 8:4 (1996), 389–411 | DOI

[12] Alkaya A. F., Duman E., “A new generalization of the traveling salesman problem”, Appl. Comput. Math., 9:2 (2010), 162–175 | MR | Zbl

[13] Kinable J., Cire A. A., van Hoeve W.-J., “Hybrid optimization methods for time-dependent sequencing problems”, European Journal of Operational Research, 259:3, 887–897 | DOI | MR

[14] Chentsov A. G., Extreme problems of routing and tasks distribution, Regular and Chaotic Dynamics, M.–Izhevsk, 2008, 240 pp.

[15] Korobkin V. V., Sesekin A. N., Tashlykov O. L., Chentsov A. G., Routing methods and their applications in problems of improving the safety and efficiency of operation of nuclear power plants, Novye Tekhnologii, M., 2012, 234 pp.

[16] Tashlykov O. L., Personnel dose costs in the nuclear industry. Analysis. Ways to decrease. Optimization, Lambert Academic Publishing, 2011

[17] Petunin A. A., “About some strategies of the programming of tool route by developing of control programs for thermal cutting machines”, Vestnik Ufimskogo Gosudarstvennogo Aviatsionnogo Tekhnicheskogo Universiteta. Seriya: Upravlenie, Vychislitel'naya Tekhnika i Informatika, 13:2(35) (2009), 280–286 (in Russian)

[18] Petunin A. A., Chentsov A. G., Chentsov P. A., “On routing tool motion on the sheet cutting NPC machines”, St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunication and Control Systems, 2013, no. 2(169), 103–111 (in Russian)

[19] Frolovskii V. D., “Computer-aided design of the control programs for thermal metal cutting on NPC machines”, Informatsionnye Tekhnologii v Proektirovanii i Proizvodstve, 2005, no. 4, 63–66 (in Russian)

[20] Wang G. G., Xie S. Q., “Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization”, International Journal of Production Research, 43:11 (2005), 2195–2216 | DOI

[21] Dewil R., Vansteenwegen P., Cattrysse D., “Construction heuristics for generating tool paths for laser cutters”, International Journal of Production Research, 52:20 (2014), 5965–5984 | DOI

[22] Chentsov A. G., “To question of routing of works complexes”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, no. 1, 59–82 | DOI

[23] Chentsov A. G., “On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs”, Automation and Remote Control, 73:3 (2012), 532–546 | DOI | MR | Zbl

[24] Chentsov A. G., “A parallel procedure of constructing Bellman function in the generalized courier problem with interior works”, Vestnik Yuzhno-Ural'skogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie, 2012, no. 12, 53–76

[25] Chentsov A. G., Grigoryev A. M., “Dynamic programming method in a routing problem: a scheme of independent computations”, Mekhatronika, Avtomatizatsiya, Upravlenie, 17:12 (2016), 834–846 (in Russian) | DOI

[26] Dieudonné J., Foundations of modern analysis, Academic Press Inc., New York, 1960, 361 pp. | MR | Zbl

[27] Cormen T. H., Leizerson C. E., Rivest R. L., Introduction to algorithms, MIT Press, Cambridge, 1990 | MR | Zbl

[28] Chentsov A. G., Chentsov A. A., “Route problem with constraints depending on a list of tasks”, Doklady Mathematics, 92:3 (2015), 685–688 | DOI | DOI | MR | Zbl

[29] Chentsov A. G., Chentsov P. A., “Routing under constraints: Problem of visit to megalopolises”, Autom. Remote Control, 77:11 (2016), 1957–1974 | DOI | MR | Zbl

[30] Chentsov A. G., Chentsov, A.A., “On the question of finding the value of routing problem with constraints”, Journal of Automation and Information Sciences, 48:2 (2016), 11–27 | DOI | MR

[31] Schmidt G., Ströhlein T., Relations and graphs. Discrete mathematics for computer scientists, Springer-Verlag, Berlin–Heidelberg, 1993, IX+301 pp. | DOI | MR | Zbl

[32] Steiner G., “On the complexity of dynamic programming for sequencing problems with precedence constraints”, Annals of Operations Research, 26:1 (1990), 103–123 | DOI | MR | Zbl