A Model of 'Nonadditive' Routing Problem where the Costs Depend on the Set of Pending Tasks

А. G. Chentsov; Ya. V. Salii

doi:10.14529/mmp150102

Авторы

А. G. Chentsov Институт математики и механики им. Н.Н. Красовского УрО РАН
Ya. V. Salii Институт математики и механики им. Н.Н. Красовского УрО РАН

DOI:

https://doi.org/10.14529/mmp150102

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

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

Аннотация

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

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

А. G. Chentsov, Институт математики и механики им. Н.Н. Красовского УрО РАН

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

Ya. V. Salii, Институт математики и механики им. Н.Н. Красовского УрО РАН

старший математик

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

Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, W.H. Freeman and Company, 1979. 338 p.

Melamed I.I., Sergeev S.I., Sigal I.Kh. The Travelling 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.Kh. The Travelling Salesman Problem. Exact Methods. Automation and Remote Control, 1989, vol. 50, no. 10, pp. 1303-1324.

Melamed I.I., Sergeev S.I., Sigal I.Kh. The Travelling Salesman Problem. Approximate Algorithms. Automation and Remote Control, 1989, vol. 50, no. 11, pp. 1459-1479.

Bellman R. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM (JACM), 1962, vol. 9, no. 1, pp. 61-63. DOI: 10.1145/321105.321111

Held M., Karp R. A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial & Applied Mathematics, 1962, vol. 10, no. 1, pp. 196-210. DOI: 10.1137/0110015

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

The Travelling Salesman Problem and Its Variations (Combinatorial Optimization). Dordrecht, Kluwer Academic Publishers, 2002. 830 p.

Sergeev S.I. Algorithms for the Minimax Problem of the Travelling Salesman. I. An Approach Based on Dynamic Programming. Automation and Remote Control, 1995, vol. 56, no. 7, pp. 1027-1032.

Sesekin A.N., Chentsov A.A., Chentsov A.G. [Routing with an Abstract Function of Travel Cost Aggregation]. Trudy Inst. Mat. i Mekh. UrO RAN [Proceedings of the IMM UB RAS], 2010, vol. 16, no. 3, pp 240-264. (in Russian)

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

Dieudonn'e J. Foundations of Modern Analysis. N.Y., Academic Press, 1960. 361 p.

Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadaniy: voprosy teorii [A Theoretical Treatment of Extremal Problems in Routing and Scheduling]. Moscow, Izhevsk, Regular and Chaotic Dinamics, 2008. 240 p.

Chentsov A.A., Chentsov A.G. Extremal Bottleneck Routing Problem with Constraints in the Form of Precedence Conditions. Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2008, vol. 263, no. 2, pp. 23-36. DOI: 10.1134/S0081543808060047

Cheblokov I.B., Chentsov A.G. [About one Route Problem with Interior Tasks]. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye nauki [Journal of Udmurt University. Mathematics, Mechanics and Computer Science], 2012, no. 1, pp. 96-119. (in Russian)

Chentsov A.G. [To Question of Routing of Works Complexes]. Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye nauki [Journal of Udmurt University. Mathematics, Mechanics and Computer Science], 2013, no. 1, pp. 59-82. (in Russian)