maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2012-4-5-24mais-37Research ArticleОригинальные статьиArticlesОб одной нестационарной задаче маршрутизации с ограничениямиOn a Nonstationary Route Problem with ConstraintsЧенцовАлександр ГеоргиевичChentsovA. G.

д-р физ.-мат. наук, чл.-корр. РАН, зав. отделом

д-р физ.-мат. наук, чл.-корр. РАН, зав. отделом

chentsov@imm.uran.ruЧенцовПавел АлександровичChentsovP. A.

канд. физ.-мат. наук, научный сотрудник

канд. физ.-мат. наук, научный сотрудник

chentsov.p@mail.ruИнститут математики и механики УрО РАНРоссияИнститут математики и механики УрО РАНRussian Federation201228022015194524Copyright © Ченцов А.Г., Ченцов П.А., 20152015Ченцов А.Г., Ченцов П.А.Chentsov A.G., Chentsov P.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/37

Исследуется экстремальная задача маршрутизации перемещений при ограничениях в виде условий предшествования. Предполагается, что исполнитель покидает начальный пункт (базу), после чего посещает систему мегаполисов (конечных целевых множеств), на каждом из которых выполняет некоторую работу. Функции стоимости внешних перемещений и (внутренних) работ зависят от "момента посещения" , который может отвечать фактическому времени, а может соответствовать естественной очередности (первое посещение, второе, третье и т. д. ). Построены экономичный вариант широко понимаемого метода динамического программирования (МДП) и, на его основе, оптимальный алгоритм, реализованный на ПЭВМ. Предложен вариант жадного алгоритма.

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.

маршруттрассадинамическое программированиеусловия предшествованияroutetracedynamic programmingpreceding conditionsРФФИReferencesЧенцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации с внутренними потерями // Труды Института математики и механики УрО РАН. 2008. Т. 14. № 3. С. 183–201.Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации с внутренними потерями // Труды Института математики и механики УрО РАН. 2008. Т. 14. № 3. С. 183–201.Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями // Известия вузов. Математика. 2010. № 6. C. 64–81.Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями // Известия вузов. Математика. 2010. № 6. C. 64–81.Ченцов А.Г. Об оптимальной маршрутизации в условиях ограничений // Доклады РАН. 2008. Т. 423. № 3. C. 303–307.Ченцов А.Г. Об оптимальной маршрутизации в условиях ограничений // Доклады РАН. 2008. Т. 423. № 3. C. 303–307.Ченцов А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями // Изв.РАН. Теория и системы управления. 2010. № 3. C. 52–66.Ченцов А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями // Изв.РАН. Теория и системы управления. 2010. № 3. C. 52–66.Ченцов А.А., Ченцов А.Г., Ченцов П.А. Метод итераций в задаче маршрутизации с внутренними потерями // Труды Института математики и механики УрО РАН. 2009. Т. 15. № 4. C. 270–289.Ченцов А.А., Ченцов А.Г., Ченцов П.А. Метод итераций в задаче маршрутизации с внутренними потерями // Труды Института математики и механики УрО РАН. 2009. Т. 15. № 4. C. 270–289.Ченцов А.А., Ченцов А.Г., Ченцов П.А. Условия предшествования в одной задаче экстремальной маршрутизации с внутренними работами // Сб. научных трудов "Алгоритмы и программные средства параллельных вычислений". Екатеринбург: Ин-т математики и механики УрО РАН. 2010. Вып. 10. C. 60–76.Ченцов А.А., Ченцов А.Г., Ченцов П.А. Условия предшествования в одной задаче экстремальной маршрутизации с внутренними работами // Сб. научных трудов "Алгоритмы и программные средства параллельных вычислений". Екатеринбург: Ин-т математики и механики УрО РАН. 2010. Вып. 10. C. 60–76.Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Москва; Ижевск: РХД. 2008. 238 с.Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. Москва; Ижевск: РХД. 2008. 238 с.Тонков Л.В., Ченцов А.Г. К вопросу оптимального выбора маршрута в условиях временного дисконтирования // Кибернетика и систем. анализ. 1999. №1. С. 95–106.Тонков Л.В., Ченцов А.Г. К вопросу оптимального выбора маршрута в условиях временного дисконтирования // Кибернетика и систем. анализ. 1999. №1. С. 95–106.Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 c.Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 c.Дьедонне Ж. Основы современного анализа. М.: Мир, 1964. 430 с.Дьедонне Ж. Основы современного анализа. М.: Мир, 1964. 430 с.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦ-НМО. 2002. 960 с.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦ-НМО. 2002. 960 с.Григорьев А.М., Иванко Е.Е., Ченцов А.Г. Динамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структуры // Моделирование и анализ информационных систем. 2011. Т. 18. №3. C. 101–124.Григорьев А.М., Иванко Е.Е., Ченцов А.Г. Динамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структуры // Моделирование и анализ информационных систем. 2011. Т. 18. №3. C. 101–124.Красовский Н.Н. Игровые задачи о встрече движений. М.: Наука, 1970. 420 с.Красовский Н.Н. Игровые задачи о встрече движений. М.: Наука, 1970. 420 с.Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Наука, 1985. 518 с.Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Наука, 1985. 518 с.

The authors declare that there are no conflicts of interest present.