Об одной нестационарной задаче маршрутизации с ограничениями


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

Просмотров: 228

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


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