Preview

Modeling and Analysis of Information Systems

Advanced search

On a Nonstationary Route Problem with Constraints

https://doi.org/10.18255/1818-1015-2012-4-5-24

Abstract

The extremal route problem of permutations under constraints in the form of preceding conditions is investigated. It is supposed that an executer leaves the initial point (the base) after which he visits a system of megalopolises (finite goal sets) and performs some work on each megalopolis. The cost functions for executor permutations and interior works depend on the “visiting moment” that can correspond to the real time or can also correspond to the natural regular succession (the first visiting, the second visiting, and so on). An economic variant of the widely interpreted dynamic programming method (DPM) is constructed. On this basis an optimal computer realized algorithm is constructed. A variant of a greed algorithm is proposed.

About the Authors

A. G. Chentsov
Институт математики и механики УрО РАН
Russian Federation
д-р физ.-мат. наук, чл.-корр. РАН, зав. отделом


P. A. Chentsov
Институт математики и механики УрО РАН
Russian Federation
канд. физ.-мат. наук, научный сотрудник


References

1. Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации с внутренними потерями // Труды Института математики и механики УрО РАН. 2008. Т. 14. № 3. С. 183–201.

2. Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями // Известия вузов. Математика. 2010. № 6. C. 64–81.

3. Ченцов А.Г. Об оптимальной маршрутизации в условиях ограничений // Доклады РАН. 2008. Т. 423. № 3. C. 303–307.

4. Ченцов А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями // Изв.РАН. Теория и системы управления. 2010. № 3. C. 52–66.

5. Ченцов А.А., Ченцов А.Г., Ченцов П.А. Метод итераций в задаче маршрутизации с внутренними потерями // Труды Института математики и механики УрО РАН. 2009. Т. 15. № 4. C. 270–289.

6. Ченцов А.А., Ченцов А.Г., Ченцов П.А. Условия предшествования в одной задаче экстремальной маршрутизации с внутренними работами // Сб. научных трудов "Алгоритмы и программные средства параллельных вычислений". Екатеринбург: Ин-т математики и механики УрО РАН. 2010. Вып. 10. C. 60–76.

7. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Москва; Ижевск: РХД. 2008. 238 с.

8. Тонков Л.В., Ченцов А.Г. К вопросу оптимального выбора маршрута в условиях временного дисконтирования // Кибернетика и систем. анализ. 1999. №1. С. 95–106.

9. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 c.

10. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964. 430 с.

11. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦ-НМО. 2002. 960 с.

12. Григорьев А.М., Иванко Е.Е., Ченцов А.Г. Динамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структуры // Моделирование и анализ информационных систем. 2011. Т. 18. №3. C. 101–124.

13. Красовский Н.Н. Игровые задачи о встрече движений. М.: Наука, 1970. 420 с.

14. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Наука, 1985. 518 с.


Review

For citations:


Chentsov A.G., Chentsov P.A. On a Nonstationary Route Problem with Constraints. Modeling and Analysis of Information Systems. 2012;19(4):5-24. (In Russ.) https://doi.org/10.18255/1818-1015-2012-4-5-24

Views: 866


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)