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

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

Тип публикации: Статья в журнале

Тип материала: Текст

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

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

Язык публикации: russian

Том: 14

Номера страниц: 43-58

Количество страниц: 16

Номер: 1

Год публикации: 2007

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

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

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

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

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

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

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

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