Гибридный алгоритм локального поиска для задачи маршрутизации разнородного ограниченного автопарка

Рассматривается задача оптимизации маршрутов разнородных транспортных средств для обслуживания заданного множества клиентов. Предполагается, что клиенты представлены точками на плоскости, а число транспортных средств каждого типа ограничено. Для решения задачи разработан гибридный алгоритм локального поиска с кодировкой решений в виде последовательности клиентов. Для декодирования последовательности соответствующая NP-трудная задача решается методом лагранжевых релаксаций. Предложены новые процедуры интенсификации и диверсификации поиска, а также новая окрестность экспоненциальной мощности. Приводятся результаты численных экспериментов на известных тестовых примерах с числом клиентов до 255. Для 15 примеров получены новые рекордные значения целевой функции. Табл. 7, ил. 5, библиогр. 26.