Details

Работа посвящена созданию программного модуля для оптимизации маршрутов доставки в условиях крупного города (на примере Санкт-Петербурга), учитывающего реальное время проезда по дорогам и прогнозируемую загруженность улично-дорожной сети. Основные задачи, решённые в работе: – Анализ существующих подходов к решению задачи маршрутизации транспортных средств (VRP) с учётом временнозависимых факторов; – Математическая постановка задачи time-dependent vehicle routing problem (TD-VRP) для одного курьера; – Реализация жадного алгоритма Nearest Neighbor как базового (эталонного) метода; – Разработка и программная реализация муравьиного алгоритма (ACO) с классической эвристикой по расстоянию; – Модификация ACO для работы с динамическими весами рёбер на основе предсказания скорости движения моделью CatBoost; – Интеграция с сервисом OSRM для получения реальной геометрии и времени проезда по дорогам; – Создание backend-модуля на Laravel с API-эндпоинтами для базовой и ML-оптимизации; – Разработка фронтенд-визуализации (React + Leaflet) с анимацией работы алгоритмов и сравнением результатов; – Проведение вычислительных экспериментов на реальных данных дорожной сети Санкт-Петербурга; – Оценка экономической эффективности внедрения разработанного модуля. Основные результаты работы: – Реализована информационная система, включающая: сбор координат точек доставки, построение матрицы времени проезда через OSRM, предсказание скорости на рёбрах с помощью модели CatBoost, оптимизацию маршрута муравьиным алгоритмом с динамическими весами; – Проведены эксперименты на 14 узлах (склад + 13 точек в разных районах СПб). Получено сокращение длины маршрута на 25–26 % и времени доставки на 19–20 % по сравнению с жадным алгоритмом (при погодных условиях «дождь»); – Разработан интерактивный визуализатор работы алгоритмов (жадный vs ACO) с пошаговой и итерационной анимацией, отображением феромонов и таблицы сравнительных метрик; – Проведена экономическая оценка: при парке из 10 автомобилей годовая экономия составляет ≈ 1,55 млн руб. Использованные информационные технологии и программное обеспечение: – Языки программирования и фреймворки: PHP 8 (Laravel), Python (FastAPI), JavaScript (React, Leaflet); – Алгоритмы и библиотеки: Ant Colony Optimization (собственная реализация), CatBoost (модель предсказания трафика), OSRM (маршрутизация по дорогам); – Базы данных и хранилища: PostgreSQL (Laravel), JSON-файлы для кэширования edge_lookup; – Инструменты разработки и визуализации: PHPSTORM, PyCharm, Docker, Git, Postman. Работа подтверждает возможность и высокую эффективность применения метаэвристических методов в сочетании с машинным обучением для решения задач городской логистики и многоточечной доставки в условиях нестационарной дорожной обстановки.

The thesis is devoted to the creation of a software module for optimizing delivery routes in a large city (using Saint Petersburg as an example), taking into account real road travel times and predicted traffic congestion on the street–road network. Main tasks solved in the work: – Analysis of existing approaches to solving the vehicle routing problem (VRP) with time-dependent factors; – Mathematical formulation of the time-dependent vehicle routing problem (TD-VRP) for a single courier; – Implementation of the Nearest Neighbor greedy algorithm as a baseline (reference) method; – Development and software implementation of the ant colony optimization algorithm (ACO) with classical distance-based heuristic; – Modification of ACO to work with dynamic edge weights based on speed prediction using the CatBoost model; – Integration with the OSRM service to obtain real road geometry and travel times; – Creation of a Laravel backend module with API endpoints for basic and ML-based optimization; – Development of a frontend visualization (React + Leaflet) with algorithm animation and result comparison; – Conducting computational experiments on real road network data of Saint Petersburg; – Evaluation of the economic efficiency of implementing the developed module. Main results of the work: – An information system was implemented that includes: collection of delivery point coordinates, construction of a travel time matrix via OSRM, edge speed prediction using the CatBoost model, and route optimization using the ant colony algorithm with dynamic weights; – Experiments were conducted on 14 nodes (warehouse + 13 delivery points across different districts of Saint Petersburg). A reduction in route length by 25–26% and delivery time by 19–20% was achieved compared to the greedy algorithm (under “rain” weather conditions); – An interactive visualizer of algorithm operation (greedy vs ACO) was developed, featuring step-by-step and iterative animation, pheromone visualization, and a comparative metrics table; – An economic assessment was performed: with a fleet of 10 vehicles, the annual savings amount to approximately 1.55 million RUB. Information technologies and software used: – Programming languages and frameworks: PHP 8 (Laravel), Python (FastAPI), JavaScript (React, Leaflet); – Algorithms and libraries: Ant Colony Optimization (custom implementation), CatBoost (traffic prediction model), OSRM (road routing); – Databases and storage: PostgreSQL (Laravel), JSON files for edge_lookup caching; – Development and visualization tools: PhpStorm, PyCharm, Docker, Git, Postman. The work confirms the feasibility and high efficiency of applying metaheuristic methods in combination with machine learning for solving urban logistics and multi-point delivery tasks under non-stationary road conditions.

• РЕФЕРАТ
• ABSTRACT
• ВВЕДЕНИЕ
• ГЛАВА 1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ И ПОСТАНОВКА ЗАДАЧИ
• 1.1. Современное состояние городской логистики в России
  • Основные вызовы городской логистики в мегаполисе:
• 1.2. Проблемы оптимизации маршрутов доставки
• 1.3. Обзор методов оптимизации маршрутов
• 1.4. Анализ существующих решений
• 1.5. Постановка задачи
• ГЛАВА 2. ПРОЕКТИРОВАНИЕ ИНФОРМАЦИОННОЙ СИСТЕМЫ
• 2.1. Функциональные требования
• 2.2. Информационно–логическая модель
• 2.3. Архитектура системы
• 2.4. Моделирование дорожной сети Санкт-Петербурга
• 2.5. Выводы по главе
• ГЛАВА 3. РАЗРАБОТКА МОДЕЛИ ПРЕДСКАЗАНИЯ ТРАФИКА
• 3.1. Сбор и генерация данных
• 3.2. Анализ паттернов трафика
• 3.3. Обучение и сравнение моделей
• 3.4. Выбор и оценка лучшей модели (CatBoost)
• 3.5. Выводы по главе
• ГЛАВА 4. АЛГОРИТМ ДИНАМИЧЕСКОЙ ОПТИМИЗАЦИИ МАРШРУТОВ
• 4.1. Математическая постановка задачи
• 4.2. Классический алгоритм муравьиной колонии
• 4.3. Модификация ACO для временнозависимых весов
• 4.5. Результаты экспериментального исследования
  • Проедем сравнение жадного алгоритма с ML-оптимизацией (Greedy + CatBoost). Для полноты сравнения был также протестирован жадный алгоритм с динамическими весами (время проезда вместо расстояния).
• 4.6. Выводы по главе
• ГЛАВА 5. РЕАЛИЗАЦИЯ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
• 5.1. Архитектура backend
• 5.2. Интеграция модели предсказания трафика
• 5.3. REST API
• 5.4. Тестирование и производительность
• 5.5. Выводы по главе
• ГЛАВА 6. ЭКОНОМИЧЕСКАЯ ЧАСТЬ
• 6.1. Цель и исходные данные для экономического расчёта
  • Выводы по экономической части следующие:
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• ПРИЛОЖЕНИЕ А. КОД НА PYTHON
• ПРИЛОЖЕНИЕ Б. КОД НА LARAVEL