Solving a Routing Problem with the Aid of an Independent Computations Scheme
DOI:
https://doi.org/10.14529/mmp180106Ключевые слова:
динамическое программирование, маршрут, условия предшествования, параллельный алгоритм.Аннотация
Статья посвящена вопросам построения и реализации параллельных алгоритмов для решения прикладных задач. Рассматривается задача маршрутизации перемещений с ограничениями и усложненными функциями стоимости. Предполагается, что объекты посещения - суть мегаполисы (непустые конечные множества), при посещении которых должны выполнятся некоторые работы, именуемые далее внутренними. По постановке задачи имеются ограничения в виде условий предшествования. Стоимости перемещений зависят от списка заданий, которые не выполнены на момент перемещения. Ситуация такого рода возникает, в частности, при аварийных ситуациях, связанных с работой АЭС и подобных происходящим в Чернобыле и Фукусиме. Речь идет об утилизации источников радиоактивного излучения, осуществляемой последовательно во времени; в этом случае исполнитель находится под воздействием источников, которые не были демонтированы на момент соответствующего перемещения. За счет этого в функциях стоимости, оценивающих воздействие радиации на исполнителя, возникает зависимость от списка невыполненных заданий. Последние состоят в том или ином варианте ' выключения' соответствующего источника. В настоящем исследовании излагается подход к решению данной задачи параллельным алгоритмом, реализуемым на суперкомпьютере УРАН. Приведены результаты вычислительного эксперимента.Библиографические ссылки
Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NPCompleteness, N.Y., W.H. Freeman, 1979.
Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations, N.Y., Springer, 2002.
Cook W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation, New Jersey, Princeton University Press, 2012.
Melamed I.I., Sergeev S.I., Sigal I. The Traveling Salesman Problem. Issues in Theory. Automation and Remote Control, 1989, vol. 50, no. 9, pp. 1147-1173.
Melamed I.I., Sergeev S.I., Sigal I. The Traveling Salesman Problem. Exact Methods. Automation and Remote Control, 1989, vol. 50, no. 10, pp. 1303-1324.
Melamed I.I., Sergeev S.I., Sigal I. The Traveling Salesman Problem. Approximate Algorithms. Automation and Remote Control, 1989, vol. 50, no. 11, pp. 1459-1479.
Little L.D.C., Murty K.G., Sweeney D.W., Karel C. An Algorithm for the Travelling Salesman Problem. Operations Research, 1963, vol. 11, no. 6, pp. 972990. DOI: 10.1287/opre.11.6.972
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
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.
DOI: 10.1137/0110015
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, 1996, vol. 8, pp. 389-411. DOI: 10.1007/BF00170019
Alkaya A.F., Duman E. A New Generalization of the Traveling Salesman Problem. Applied and Computational Mathematics, 2010, vol. 9, no. 2, pp. 162-175.
Kinable J., Cire A., van Hoeve W.J. Hybrid Optimization Methods for Time-Dependent Sequencing Problems. European Journal of Operational Research, 2017, vol. 259, no. 3, pp. 887-897. DOI: 10.1016/j.ejor.2016.11.035
Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii [Extreme Problems of Routing and Tasks Distribution: Regular and Chaotic Dynamics]. Izhevsk, Izhevsk Institute of Computer Research, 2008. (in Russian)
Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G. Routing Methods and Their Applications to the Enhancement of Safety and Eficiency of Nuclear Plant Operation. Moscow, Novye tekhnologii, 2012. (in Russian)
Tashlykov O.L. Personnel Dose Costs in the Nuclear Industry. Analysis. Ways to Decrease. Optimization. Saarbruke, LAP LAMBERT Academic Publishing GmbH & Co. RG., 2011.
Petunin A.A. About Some Strategies of the Tool Path Modelling at the Control Programs Generation for the Flame Cutting Machines. Vestnik UGATU, 2009, vol. 13, no. 2, pp. 280-286. (in Russian)
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, pp. 103-111. (in Russian)
Frolovskii V.D. Computer-Aided Design of the Control Programs for Thermal Metal Cutting on NPC Machines. The scientic and technical journal "Information Technology of Cad/Cam/Cae" (ITDP), 2005, no. 4, pp. 63-66. (in Russian)
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, 2005, vol. 43, no. 11, pp. 2195-2216. DOI: 10.1080/00207540500070376
Dewil R., Vansteenwegen P., Cattrysse D. Construction Heuristics for Generating Tool Paths for Laser Cutters. International Journal of Production Research, 2014, vol. 52, no. 20, pp. 1-20. DOI: 10.1080/00207543.2014.895064
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. DOI: 10.1134/S0005117916110060
Dieudonne J. Foundations of Modern Analysis. N.Y., Academic, 1960.
Cormen T.H., Leizerson C.E., Rivest R.L. Introduction to Algorithms. Cambridge, MIT Press, 1990.
Chentsov A.G. To Question of Routing of Works Complexes. Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 1, pp. 59-82. (in Russian)
Chentsov A.G., Chentsov A.A. Route Problem with Constraints Depending on a List of Tasks. Doklady Mathematics, 2015, vol. 92, no. 3, pp. 685-688. DOI: 10.1134/S1064562415060083
Chentsov A.G., Chentsov A.A. On the Problem of Obtaining the Value of Routing Problem with Constraints. Journal of Automation and Information Sciences, 2016, vol. 6, pp. 41-54.
Lawler E.L. Eficient Implementation of Dynamic Programming Algorithms for Sequencing Problems. CWI Technical report. Stichting Mathematisch Centrum. Mathematische Besliskunde-BW, 1979, vol. 106, no. 79, pp. 1-16.
Chentsov A.G. One Parallel Procedure for the Construction of the Bellman Function in the Generalized Problem of the Courier with the Inner Workings. Automation and Remote Control, 2012, vol. 3, pp. 134-149.
Chentsov A.G. One Parallel Procedure for the Construction of the Bellman Function in the Generalized Problem of the Courier with the Inner Workings. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software,
, no. 18 (277), pp. 53-76. (in Russian)
Chentsov A.G., Grigoryev A.M. Dynamic Programming Method in the Route Problem: the Scheme of Independent Calculations. Mekhatronika, avtomatizatsiya, upravlenie, 2016, vol. 17,
no. 12, pp. 834-846.
Schmidt G., Strohlein T. Relations and Graphs: Discrete Mathematics for Computer Scientists. London, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1993.
Steiner G. On the Complexity of Dynamic Programming for Sequencing Problems with Precedence Constraints. Annals of Operations Research, 1990, vol. 26, no. 1, pp. 103-123.
DOI: 10.1007/BF02248587
