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

Рассматривается задача построения маршрутов для транспортных средств на конечном временном интервале. Компания имеет множество транспортных средств ограниченной грузоподъёмности, находящихся в разных депо. Требуется построить такие маршруты посещения всех клиентов, чтобы суммарное пройденное расстояние было минимальным, а рабочее время водителей укладывалось в рабочую смену. Задана частота посещений каждого клиента, которые должны проходить через равные промежутки времени. Обслуживание клиента должно производиться одним и тем же транспортным средством.
Построена модель частично-целочисленного линейного программирования. Разработан метод локального поиска с чередующимися окрестностями, усиленный методом поиска с запретами. Для расширения пространства решений ограничение на длительность рабочей смены и грузоподъёмность заносятся в целевую функцию со штрафами, изменяемыми в ходе поиска. Процедуры интенсификации и диверсификации применяются для повышения эффективности метода. Приводятся результаты расчётов на реальных исходных данных. Табл. 6, ил. 1, библиогр. 28.