Об одной нестационарной задаче маршрутизации с ограничениями
https://doi.org/10.18255/1818-1015-2012-4-5-24
Аннотация
Исследуется экстремальная задача маршрутизации перемещений при ограничениях в виде условий предшествования. Предполагается, что исполнитель покидает начальный пункт (базу), после чего посещает систему мегаполисов (конечных целевых множеств), на каждом из которых выполняет некоторую работу. Функции стоимости внешних перемещений и (внутренних) работ зависят от "момента посещения" , который может отвечать фактическому времени, а может соответствовать естественной очередности (первое посещение, второе, третье и т. д. ). Построены экономичный вариант широко понимаемого метода динамического программирования (МДП) и, на его основе, оптимальный алгоритм, реализованный на ПЭВМ. Предложен вариант жадного алгоритма.
Об авторах
Александр Георгиевич Ченцов
Институт математики и механики УрО РАН
Россия
д-р физ.-мат. наук, чл.-корр. РАН, зав. отделом
Россия
д-р физ.-мат. наук, чл.-корр. РАН, зав. отделом
Павел Александрович Ченцов
Институт математики и механики УрО РАН
Россия
канд. физ.-мат. наук, научный сотрудник
Россия
канд. физ.-мат. наук, научный сотрудник
Список литературы
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 с.
Рецензия
При поддержке: РФФИ
Для цитирования:
Ченцов А.Г., Ченцов П.А. Об одной нестационарной задаче маршрутизации с ограничениями. Моделирование и анализ информационных систем. 2012;19(4):5-24. https://doi.org/10.18255/1818-1015-2012-4-5-24
For citation:
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
Просмотров: 723
Послать статью по эл. почте 