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

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