Аннотация:В работе рассматривается задача построения сети магазинов/кафе в городе.
Считается, что в городе живет определенное количество жителей, каждый из которых может быть потребителем или заказчиком для сети магазинов/кафе.
Соответственно, чем ближе от места проживания конкретного жителя будет находиться кафе/магазин, тем больше вероятность того, что этот житель воспользуется их услугами.
Задача предпринимателя состоит в том, что разместить точки обслуживания (магазины или кафе) таким образом, чтобы минимизировать суммарное расстояние от всех жителей города (потенциальных потребителей) до ближайших к ним точек обслуживания.
При этом рассматривается 2 постановки задачи:
1. Количество пунктов обслуживания фиксировано и равно некоторому параметру K.
2. Предприниматель может сам выбирать, сколько пунктов обслуживания ему разместить на карте, но при этом содержание таких пунктов обслуживания будет стоить ему денег. Таким образом, потребуется найти баланс между сокращением расходов на содержание пунктов обслуживания и минимизацией суммарного расстояния до потребителей.
Для решения поставленной задачи предлагается использовать метод кластеризации, то есть множество всех потребителей кластеризуется и для каждого кластера размещается точка обслуживания в центре масс кластера.
В работе рассмотрено несколько алгоритмов кластеризации и проведено их сравнение по вычислительной сложности и качеству выдаваемого решения.