АЛГОРИТМ BRANCH-CUT-AND-PRICE ДЛЯ ТОЧНОГО РОЗВ’ЯЗАННЯ ЗАДАЧІ МАРШРУТИЗАЦІЇ ТРАНСПОРТНИХ ЗАСОБІВ З ОБМЕЖЕННЯМИ НА ВАНТАЖОПІДЙОМНІСТЬ
DOI:
https://doi.org/10.34185/1991-7848.itmm.2026.01.044Ключові слова:
CVRP, маршрутизація транспортних засобів, branch-cut-and-price, генерація стовпців, розбиття множини, комбінаторна оптимізація, цілочисельне програмування, лінійна релаксація, точні та евристичні методи, логістикаАнотація
У роботі подано реалізацію алгоритму branch-cut-and-price для точного розв’язання задачі маршрутизації транспортних засобів з обмеженнями на вантажопідйомність (Capacitated Vehicle Routing Problem, CVRP). Метод поєднує модель розбиття множини (set partitioning formulation), стартову евристику на основі алгоритму Кларка-Райта, породження маршрутів із від’ємною зведеною вартістю (reduced cost) та округлені ємнісні нерівності (rounded capacity inequalities). У межах генерації стовпців алгоритм спочатку намагається знайти нові маршрути швидшим евристичним способом; за певних налаштувань під час такого пошуку застосовується спрощена перевірка того, що маршрут не містить повторних відвідувань клієнтів. Якщо таким способом нових маршрутів не знайдено, алгоритм переходить до точного пошуку маршрутів без повторних відвідувань клієнтів і лише після цього завершує генерацію стовпців. На стандартних екземплярах CVRP розмірності від 16 до 60 вершин включно з депо реалізація алгоритму відтворила відомі оптимуми.
Посилання
Archetti C., Coelho L.C., Speranza M.G., Vansteenwegen P. Beyond fifty years of vehicle routing: Insights into the history and the future. European Journal of Operational Research. 2026. Vol. 330, No. 2. P. 355-372. DOI: 10.1016/j.ejor.2025.06.014.
Costa L., Contardo C., Desaulniers G. Exact Branch-Price-and-Cut Algorithms for Vehicle Routing. Transportation Science. 2019. Vol. 53, No. 4. P. 946-985. DOI: 10.1287/trsc.2018.0878.
Feillet D., Dejax P., Gendreau M., Gueguen C. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks. 2004. Vol. 44, No. 3. P. 216-229. DOI: 10.1002/net.20033.
Fukasawa R., Longo H., Lysgaard J., Poggi de Aragao M., Reis M., Uchoa E., Werneck R.F. Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem. Mathematical Programming. 2006. Vol. 106, No. 3. P. 491-511. DOI: 10.1007/s10107-005-0644-x.
Baldacci R., Christofides N., Mingozzi A. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming. 2008. Vol. 115, No. 2. P. 351-385. DOI: 10.1007/s10107-007-0178-5.
Pecin D., Pessoa A., Poggi M., Uchoa E. Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation. 2017. Vol. 9, No. 1. P. 61-100. DOI: 10.1007/s12532-016-0108-8.
All Instances – CVRPLIB. GALGOS – Algorithms, Optimization and Simulation Group. URL: https://galgos.inf.puc-rio.br/cvrplib/index.php/en/instances (date of access: 02.04.2026).
