Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования

Александр Георгиевич Ченцов; Павел Александрович Ченцов

doi:10.14529/mmp180207

Авторы

Александр Георгиевич Ченцов Уральский федеральный университет
Павел Александрович Ченцов Уральский федеральный университет

DOI:

https://doi.org/10.14529/mmp180207

Ключевые слова:

маршрутная задача, ограничения, точка старта.

Аннотация

Рассматривается задача маршрутизации перемещений с ограничениями и функциями стоимости, допускающими зависмость от списка заданий. Предполагается, что начальное условие процесса с дискретным временем может выбираться в пределах метрического пространства, удовлетворяющего условию полной ограниченности. По постановке задачи предполагается посещение конечной системы мегаполисов (непустых конечных множеств) с выполнением тех или иных работ, стоимости которых зависят всякий раз от пункта прибытия и пункта отправления. Стоимости перемещений и выполняемых работ агрегируются аддитивно. Для решения используется вариант широко понимаемого динамического программирования, обеспечивающий нахождение epsilon-оптимального решения при любом значении epsilon>0.

Биографии авторов

Александр Георгиевич Ченцов, Уральский федеральный университет

Член-корреспондент РАН

Павел Александрович Ченцов, Уральский федеральный университет

Кандидат физико-математических наук

Библиографические ссылки

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 the 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.

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 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

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.

Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G. Routing Methods and Their Applications to the Enhancement of Safety and Efficiency of Nuclear Plant Operation. Moscow, Novye tekhnologii, 2012. (in Russian)

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

Little J., Murty K., Sweeney D., Karel C. An Algorithm for the Traveling Salesman Problem, Operations Research, 1963, vol. 11, no. 6, pp. 972-989. DOI: 10.1287/opre.11.6.972

Kuratowski K., Mostowski A. Set Theory. Amsterdam, North-Holland Publishing Company, 1967.

Dieudonne J. Foundations of Modern Analysis. New York, Academic Press, 1960.

Cormen T., Leiserson C., Rivest R. Introduction to Algorithms. MIT Press and McGraw-Hill, 1990.

Engelking R. General Topology. Polish Scientic Publishers, 1977.

Chentsov A.G. Ekstremalnye zadachi marshrutizacii i raspredeleniya zadaniy voprosy teorii [Extreme Routing and Task Distribution Problems: Theory Questions]. Izhevsk, NITs

"Regulyarnaya i Khaoticheskaya Dinamika", 2008. (in Russian)

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. Efficient 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. To Question of Routing of Works Complexes. Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 1, pp. 59-82. (in Russian)