В роботі досліджено моделі та методи комбінаторної оптимізації, що
використовують властивості множини циклічних перестановок і їх
застосування для розв’язання наукових і прикладних задач, серед яких —
задачі транспортної маршрутизації.
Досліджено властивості циклічних перестановок при їх відображенні в
евклідів простір. Використовуються поліедральні властивості перестановок і
циклічних перестановок, що відповідають підмножині вершин
перестановочного багатогранника. Набув подальшого розвитку клас
транспозицій суміжності для перестановок різних елементів, представники
якого породжують перестановки, відповідні суміжним вершинам
перестановочного многогранника. Описано властивості суміжності і
особливості зміни циклічної структури перестановок при впливі транспозицій
суміжності. Проведено класифікацію циклічних перестановок в залежності від
впливу транспозицій суміжності на їх циклічну структуру. Доведено
відповідні твердження про властивості транспозицій суміжності.
Набули подальшого розвитку методи розв’язання задач оптимізації
лінійних функцій на множині циклічних перестановок, зокрема, з лінійними
обмеженнями. Для розв’язання задачі без обмежень запропоновано підхід,
20
заснований на комбінації методу гілок та меж і евристики. Запропоновано
метод пошуку наближеного розв’язку задачі без обмежень з використанням
властивостей транспозицій суміжності. Для розв’язання задачі оптимізації
лінійних функцій на множині циклічних перестановок з лінійними
обмеженнями запропоновано метод на основі випадкового пошуку, з
використанням транспозицій суміжності для розв’язання допоміжної задачі.
Набув подальшого розвитку метод комбінаторної оптимізації на основі
циклічних трансферів в частині генерації циклічних трансферів від’ємної
вартості. Метод застосовано для покращення розв’язків задач транспортної
маршрутизації, зокрема, задачі вивозу і доставки (Pickup and Delivery
Problem), отриманих за допомогою евристики.
Для розв’язання задач, досліджених в роботі, розроблено програмне
забезпечення, що реалізує запропоновані моделі та методи комбінаторної
оптимізації. Наведено результати обчислювальних експериментів, проведено
аналіз результатів, який підтверджує ефективність запропонованих підходів.
Отримані результати можуть бути використані при комп’ютерному
моделюванні і розв’язанні задач в областях архівації даних і криптографії,
квантових обчислень, біоінформатики.
Ключові слова: комбінаторна оптимізація, циклічні перестановки,
транспозиції, перестановочний багатогранник, транспозиції суміжності,
лінійна функція, метод гілок та меж, евристика, задача вивозу і доставки.
