Статьи автора

Модификация метода пометок для задач многокритериальной оптимизации на графах

Номер 1 от 20.03.2020

Метод пометок (метод Дейкстры) позволяет найти кратчайший путь между двумя вершинами в графе с заданными длинами ребер. В статье предлагается модификация метода пометок для случая, когда каждое ребро графа характеризуется не одной, а несколькими характеристиками, например временем и стоимостью проезда по ребру. В задачах многокритериальной оптимизации разные лица, принимающие решения (ЛПР), могут выбирать различные решения. Но, как правило, ЛПР не может формализовать свои предпочтения. Поэтому необходимо уметь строить достаточно представительное множество оптимальных по Парето путей. Традиционно для решения подобных задач используются интерактивные человеко-машинные процедуры, формирующие Парето-оптимальные решения на основе выявленных предпочтений ЛПР. В статье рассмотрен один из возможных подходов к построению такой процедуры, основанный на оптимизации одного из критериев при заданных ЛПР ограничениях на остальные критерии. Построенные таким образом пути предъявляются ЛПР, которые анализируют их и уточняют свои требования, до тех пор пока не будет получен удовлетворяющий их путь. Для проверки эффективности предложенного подхода планируется провести серию вычислительных экспериментов.

1942 41