Генетический локальный поиск для задачи о $p$-медиане с предпочтениями клиентов

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