Быстрые метаэвристики для дискретной задачи о $(r|p)$-центроиде

Два игрока, лидер и его конкурент, открывают предприятия, стараясь захватить как можно большую долю рынка. Лидер открывает $p$ предприятий. Затем конкурент открывает $r$ предприятий. Каждый клиент выбирает ближайшее предприятие в качестве поставщика. Требуется так выбрать $p$ предприятий лидера, чтобы максимизировать его долю рынка. Эта задача может быть представлена в виде задачи двухуровневого программирования. Опираясь на это представление, в работе предлагаются два численных метода: локальный поиск с чередующимися окрестностями и стохастический поиск с запретами. Основное внимание уделяется сокращению трудоемкости методов без ущерба качеству получаемых решений. Результаты численных экспериментов подтверждают возможность быстрого нахождения точного решения задачи и решений с малой погрешностью.

Статья представлена к публикации членом редколлегии: А. И. Кибзун