в статье излагаются результаты вычислительных экспери¬ментов по сравнению эффективности различных алгоритмов поиска множе¬ства Парето-оптимальных путей в ориентированном графе.
многокритериальная оптимизация, Парето - оптимальные пути, вычислительная сложность алгоритма.
УДК: 519.81
ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ ПО ТЕСТИРОВАНИЮ
АЛГОРИТМОВ ПОСТРОЕНИЯ СЕТИ ПАРЕТО-ОПТИМАЛЬНЫХ МАРШРУТОВ НА ГРАФАХ
TEST SIMULATION EXPERIMENTS OF MESH ALGORITHM OF PARETO EFFICIENCY ROUTES IN GRAPHS
Ткачёв А.Ю., магистрант
ФГБОУ ВО «Воронежский государственный университет
инженерных технологий» г. Воронеж, Россия
DOI: 10.12737/16242
Аннотация: в статье излагаются результаты вычислительных экспериментов по сравнению эффективности различных алгоритмов поиска множества Парето-оптимальных путей в ориентированном графе.
Summary: This article states the results of simulation experiments
in comparison with algorithm efficiency of set's search of Pareto efficiency routes in direct graph.
Ключевые слова: многокритериальная оптимизация, Парето - оптимальные пути, вычислительная сложность алгоритма.
Keywords: multicriteria optimization, Pareto efficiency routes , algorithm computational complexity.
Задача построения транспортной сети, соединяющей несколько пунктов назначения, удовлетворяющей определённым оптимальным требованиям и организации на её основе системы оптимальных маршрутов актуальна для многих отраслей промышленности и сельского хозяйства, в том числе и для проблем управления лесным комплексом.
Для её решения требуется знание маршрутов объезда всех пунктов назначения и количественных характеристик этих маршрутов: протяженность, время проезда, степень загруженности, качество дороги и пр. Иными словами, в общем случае данная задача является многокритериальной.
1. Поиск оптимальных путей на графах с векторными весами. Методи-ческие указания к выполнению лабораторной работы по курсу "Методы оп-тимизации" / Сост. С. Ю. Городецкий. Н.Новгород: Нижегородский государ¬ственный университет, 1996. 28 с.
2. Бугаев, Ю. В. Применение прямого обобщения скалярных алгорит-мов в векторной оптимизации на графах / Ю. В. Бугаев // Дискретная математика. - 2001. Т. 13. Вып. 3. - c.110 - 124.
3. Бугаев, Ю. В. Применение векторной оптимизации на графах для мо-делирования раскроя лесоматериалов / Ю. В. Бугаев // Изв. ВУЗов. Лесной журнал, 2001, № 3. С. 84 - 87.
4. Блинов, И. В.Обобщение алгоритма Флойда-Уоршалла на случай не-скольких критериев / И. В. Блинов, Ю. В. Бугаев, С. В. Чикунов // Вестник Тамбовского государственного технического университета. 2009. Т.15. №4 С. 885 - 892.
