Страница публикации

Метод декомпозиции для задачи о P-медиане на несвязном графе.

Авторы: Васильев И.Л.

Журнал: Дискретный анализ и исследование операций. Сер. 2

Том: 14

Номер: 1

Год: 2007

Отчётный год: 2007

Издательство:

Местоположение издательства:

URL:

Проекты:

DOI:

Аннотация: Рассматривается задача оптимального замещения, которая формулируется как задача о p-медиане. Практическое приложение данной задачи возникает в автомобильной промышленности, где существуют примеры, которые определяются на графах, состоящих из нескольких десятков тысяч вершин и нескольких миллионов дуг. Отличительной особенностью любой такой задачи является то, что граф состоит из нескольких компонент связности. Эта структура графа используется для декомпозиции исходной задачи в серию подзадач о p-медиане меньшей размерности. Предложенная декомпозиция естественным образом позволяет использовать параллельные вычисления при программной реализации метода. Эффективность предложенного подхода иллюстрируется численными экспериментами на практических примерах.

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет

Публикация в печати: 0