Циклічні перестановки в методах комбінаторної оптимізації на основі циклічних трансферів

Abstract

Дана стаття присвячена стратегії розв’язання задач комбінаторної оптимізації, основаній на циклічних трансферах та властивостях множини циклічних перестановок. Циклічні трансфери – це один із відомих методів пошуку в околі, що дозволяє отримувати наближене рішення задач комбінаторної оптимізації. Існує загальний метод для пошуку в околі за допомогою циклічних трансферів. Він заснований на пошуку циклічного трансфера у допоміжному графі. Але особливості задачі, що розв’язується, деколи не дозволяють побудувати допоміжний граф та скористатися вже існуючими методами пошуку. У такому випадку ми пропонуємо використовувати множину циклічних перестановок та її властивості для побудови циклічних трансферів. Для демонстрації застосування, описаної у статті стратегії розв’язку задач комбінаторної оптимізації, було розв’язано задачу маршрутизації транспорту. Обчислювальні експерименти та їх результати наведені у статті.