Алгоритмічне дослідження та програмна реалізація оптимізації маршрутів доставки з обмеженням вантажопідйомності

Abstract

The paper investigates heuristic approaches to solving the capacitated vehicle routing problem (CVRP) for delivery route optimization under vehicle capacity constraints. A comparative analysis of the K-means, Sweep, and Clarke–Wright algorithms was conducted using simulated datasets with different spatial distributions. The evaluation was performed based on the total route length and the number of vehicles required. The results demonstrate that the efficiency of the algorithms depends on the spatial structure of customer locations. A web-based application implementing the studied methods and providing interactive visualization of the results was developed. Experimental testing confirms the practical applicability of the proposed approach to logistics optimization tasks.

У роботі досліджено евристичні підходи до розв’язання задачі оптимізації маршрутів доставки з обмеженням вантажопідйомності транспортних засобів. Проведено порівняльний аналіз алгоритмів K-means, Sweep та Clarke–Wright на імітаційних наборах даних із різною просторовою структурою. Оцінювання здійснювалося за критеріями сумарної довжини маршрутів та кількості транспортних засобів. Встановлено залежність ефективності алгоритмів від характеру розподілу пунктів доставки. Розроблено WEB-застосунок, що реалізує досліджені методи та забезпечує інтерактивну візуалізацію результатів. Проведене тестування підтверджує практичну придатність запропонованого підходу для задач логістичної оптимізації.