РЕАЛІЗАЦІЯ ТА ДОСЛІДЖЕННЯ АЛГОРИТМУ BRANCH-CUT-AND-PRICE ДЛЯ ЗАДАЧІ МАРШРУТИЗАЦІЇ ТРАНСПОРТНИХ ЗАСОБІВ З ОБМЕЖЕННЯМИ НА ВАНТАЖОПІДЙОМНІСТЬ

Анотація

Ефективність транспортних перевезень істотно залежить від якості маршрутного планування. Тому для задач маршрутизації поряд із швидкими наближеними підходами зберігають значення точні методи, які дають змогу не лише побудувати план перевезень, а й підтвердити його оптимальність. У статті розглянуто реалізацію алгоритму branch-cut-and-price для точного розв’язання задачі маршрутизації транспортних засобів з обмеженнями на вантажопідйомність (Capacitated Vehicle Routing Problem, CVRP). Метою дослідження є опис реалізації, пояснення основних принципів її побудови та перевірка працездатності на стандартних тестових екземплярах. Метод поєднує модель розбиття множини (set partitioning formulation), генерацію стовпців, стартову евристику на основі алгоритму Кларка-Райта, округлені ємнісні нерівності (Rounded Capacity Inequalities) та точне розв’язання підзадачі маршруту. Щоб скоротити час обчислень, у межах генерації стовпців спочатку застосовується швидший евристичний пошук нових маршрутів, а якщо нових маршрутів не знайдено, виконується точний сертифікуючий етап. У результаті обчислювального експерименту на одинадцяти стандартних екземплярах розмірності від 16 до 60 вершин включно з депо в усіх випадках відтворено відомі оптимуми. Отримані результати підтверджують коректність реалізації та практичну придатність обраної організації обчислень у дослідженому діапазоні розмірностей.