Справка - Route Optimizer

⚡ Быстрый старт

1

Загрузите GPX файл

Контрольные пункты с обязательной стартовой точкой 0-0

2

Настройте параметры

Бюджет (90000м или 720мин), выберите решатели ("Быстрый" + "Обычный")

3

Запустите оптимизацию

Нажмите "🚀 Оптимизировать" и дождитесь результата (~30-60 сек)

💡 Для новичков: Оставьте все настройки по умолчанию, измените только бюджет под свои цели и загрузите GPX файл. Система подберет оптимальный маршрут автоматически!

📖 Что это за сервис?

Route Optimizer — это веб-приложение для оптимизации маршрутов в соревнованиях по трейлраннингу (бег по пересеченной местности), таких как "Кольцо24".

Система решает Orienteering Problem — задачу поиска оптимального маршрута через контрольные пункты (КП) с максимизацией суммы призов при ограничении по времени или расстоянию.

💡 Ключевая особенность: В отличие от обычных оптимизаторов, наша система учитывает рельеф местности, перепады высот и возможность прямого движения через лес (что может быть быстрее обхода по дорогам).

Основные возможности:

📁 Загрузка маршрутов из GPX файлов
🚀 Несколько алгоритмов оптимизации (от быстрого до максимально качественного)
⛰️ Учет рельефа и набора высоты
🗺️ Интерактивные карты с результатами
📊 Сравнение различных вариантов маршрутов
💾 История всех расчетов

🚀 Быстрый старт

Шаг 1: Загрузите GPX файл

Загрузите файл с контрольными пунктами одним из способов:

Drag & Drop: Перетащите GPX файл в зону загрузки
Выбор файла: Нажмите на зону загрузки и выберите файл через диалог

⚠️ Важно: Стартовый контрольный пункт (депо) должен иметь имя 0-0 в GPX файле. Это обязательное требование!

Шаг 2: Настройте параметры

Имя задачи: Введите описательное название или оставьте пустым для автогенерации.

Бюджет:

Дистанционный бюджет (по умолчанию): Укажите максимальное расстояние в метрах (например, 90000 м = 90 км)
Временной бюджет: Включите чекбокс "Временной бюджет" и укажите время в минутах (например, 720 = 12 часов)

Шаг 3: Выберите варианты решений

Вы можете выбрать один или несколько вариантов для сравнения:

Вариант	Алгоритм	Время расчета	Качество
Быстрый	Greedy + 2-opt	~5 сек	60-80% от оптимума
Обычный	OR-Tools (30s)	~30 сек/вариант	85-95% от оптимума
Качественный	OR-Tools (120s)	~2 мин/вариант	90-98% от оптимума
Супер качество	OR-Tools (настраиваемое)	5-30 мин	95-100% от оптимума

💡 Рекомендация: Для первого расчета выберите "Быстрый" и "Обычный", чтобы быстро получить результат. Затем можно пересчитать с "Качественным" для улучшения маршрута.

Шаг 4: Настройте коэффициенты высоты

Коэффициент штрафа за набор высоты определяет, насколько "дороже" становится движение в гору. Укажите один или несколько коэффициентов через запятую (например: 1.0,1.3,1.5).

1.0 — не учитывать набор высоты
1.3 — умеренный учет (рекомендуется для равнинного трейла)
1.5 — сильный учет (рекомендуется для горного трейла)

Шаг 4а: Задайте ограничения маршрута (опционально)

Вы можете указать обязательные КП или цепочки КП, которые должны быть посещены в определенной последовательности.

Формат ввода:

В поле "Цепочки КП" каждая цепочка указывается с новой строки. Поддерживаются два формата идентификации узлов:

По ID: 28 или 51,20,21
По полному имени: 5-28 или 3-51,4-20,8-21 (рекомендуется)

Примеры:

Формат	Значение	Описание
`31`	Обязательный узел	КП с ID 31 обязательно будет включен в маршрут
`5-31`	Обязательный узел	КП с полным именем "5-31" (рекомендуется для избежания конфликтов)
`5,2,14`	Цепочка узлов	КП 5, 2 и 14 должны быть посещены в указанном порядке
`5-05,4-02,3-14`	Цепочка узлов	КП "5-05", "4-02" и "3-14" в указанном порядке (рекомендуется)

💡 Важно: Между узлами цепочки могут быть другие КП. Ограничение требует только соблюдения порядка указанных узлов.

✅ Рекомендация: Используйте полные имена узлов (формат "prize-id"), чтобы избежать потенциальных конфликтов при одинаковых ID у разных КП.

Шаг 5: Запустите оптимизацию

Нажмите кнопку "🚀 Оптимизировать маршруты" и дождитесь завершения расчета.

Система покажет прогресс в реальном времени и уведомит о завершении.

Шаг 6: Изучите результаты

После завершения вы увидите:

Интерактивные карты для каждого варианта
Статистику: количество посещенных КП, общий приз, дистанция, время расчета
Возможность открыть карту в полном размере

⚙️ Подробное описание параметров

Имя задачи

Произвольное название для идентификации расчета в истории. Если не указано, генерируется автоматически в формате: Задача YYYY-MM-DD HH:MM

Бюджет

Максимальное ограничение на маршрут. Может быть дистанционным (в метрах) или временным (в минутах).

Дистанционный: Ограничение по расстоянию (например, 90000 м)
Временной: Ограничение по времени прохождения (например, 720 мин = 12 часов)

📝 Примечание: При временном бюджете система учитывает скорость движения по разным типам местности и рельеф.

Варианты решений

1. Быстрый (Greedy + 2-opt)

Жадный алгоритм, который на каждом шаге выбирает ближайший КП с лучшим соотношением "приз/расстояние". После построения маршрута применяется локальная оптимизация 2-opt.

Когда использовать: Для быстрой оценки или большого количества КП (>200).

2. Обычный (OR-Tools, 30 секунд)

Использует Google OR-Tools с метаэвристикой Guided Local Search. Лимит времени: 30 секунд на каждый вариант коэффициента высоты.

Когда использовать: Оптимальный выбор для большинства задач.

3. Качественный (OR-Tools, 120 секунд)

Тот же алгоритм, но с увеличенным временем расчета (2 минуты на вариант).

Когда использовать: Когда нужно улучшить результат "Обычного" варианта.

4. Супер качество (OR-Tools, настраиваемое)

Позволяет задать собственное время расчета (от 1 до 30 минут). Рекомендуется 5-10 минут для максимального качества.

Когда использовать: Для финального расчета перед соревнованием.

Коэффициенты высоты

Система может построить несколько маршрутов с разными коэффициентами учета набора высоты. Это позволяет сравнить "плоские" маршруты с маршрутами, которые избегают подъемов.

Формула расчета:

effective_distance = base_distance + (elevation_gain × coefficient)

Примеры:

1.0: Не учитывать высоту (100м подъема = 100м дистанции)
1.3: Умеренный штраф (100м подъема = 130м дистанции)
1.5: Сильный штраф (100м подъема = 150м дистанции)
2.0: Очень сильный штраф (100м подъема = 200м дистанции)

💡 Совет: Для горных соревнований рекомендуется использовать коэффициенты 1.3-1.5. Для равнинных можно использовать 1.0-1.2.

🎯 Ограничения маршрута

Вы можете задать обязательные контрольные пункты или последовательности КП, которые система должна обязательно включить в маршрут в указанном порядке.

Типы ограничений

1. Обязательный узел (одиночный)

КП, который обязательно должен быть включен в маршрут, но позиция в маршруте не важна.

Пример: 31 или 5-31

2. Цепочка узлов (последовательность)

Несколько КП, которые должны быть посещены в строгом порядке. Между элементами цепочки могут быть другие КП.

Пример: 5,2,14 или 5-05,4-02,3-14

Форматы идентификации узлов

Формат	Пример	Описание	Рекомендуется?
По ID	`28`	Числовой идентификатор узла	⚠️ Может быть неоднозначным
Полное имя	`5-28`	Формат "prize-id"	✅ Рекомендуется

💡 Почему полные имена лучше?
В GPX файле узлы имеют имена вида "prize-id" (например, "5-28"). Если использовать только ID (28), то в случае существования узлов "3-28" и "5-28" будет неоднозначность. Система сначала ищет по полному имени, затем по ID.

Синтаксис

В поле "Цепочки КП" каждое ограничение указывается с новой строки:

Запятая (,): разделяет узлы внутри одной цепочки
Новая строка: разделяет разные ограничения
Пробелы: допускаются и автоматически удаляются (можно писать 3-51,4-20 или 3-51, 4-20)

💡 Гибкий ввод: Система корректно обрабатывает пробелы в последовательностях. Можно вводить как 3-51,4-20,8-21, так и 3-51, 4-20, 8-21 — оба формата работают одинаково.

Примеры использования

Пример 1: Один обязательный КП

5-28

Результат: КП "5-28" обязательно будет в маршруте.

Пример 2: Несколько обязательных КП

5-28
3-51
8-22

Результат: Все три КП будут включены в маршрут.

Пример 3: Одна цепочка

3-51,4-20,8-21

или

3-51, 4-20, 8-21

Результат: КП будут посещены в порядке: "3-51" → "4-20" → "8-21". Между ними могут быть другие КП. Оба формата (с пробелами и без) работают одинаково.

Пример 4: Комбинация обязательных узлов и цепочек

5-28
3-51,4-20,8-21,8-22
7-15

Результат: КП "5-28" обязателен, цепочка "3-51→4-20→8-21→8-22" в указанном порядке, КП "7-15" обязателен.

Как это работает?

Greedy решатель

Приоритизирует узлы из ограничений, умножая их "ценность" на большой коэффициент (1000x). Это заставляет алгоритм выбирать их в первую очередь.

OR-Tools решатель

Использует два механизма:

Обязательность: Узлы из ограничений исключаются из "опциональных" (disjunctions)
Precedence constraints: Для цепочек добавляются ограничения порядка через dimension constraints

Валидация и проверки

Система автоматически проверяет:

✅ Все указанные узлы существуют в GPX файле
✅ Не указано депо (id=0) в ограничениях
✅ Финальный маршрут содержит все обязательные узлы
✅ Цепочки соблюдают указанный порядок

⚠️ Важно: Если указанные ограничения невозможно выполнить в рамках бюджета, решатель может не найти решение. В этом случае попробуйте:

Увеличить бюджет
Уменьшить количество обязательных узлов
Упростить цепочки (сделать их короче)

Статус ограничений в результатах

После оптимизации вы увидите статус "Constraints" в таблице результатов:

✅ Satisfied: Все ограничения выполнены
❌ Not satisfied: Некоторые ограничения нарушены (обычно у Greedy решателя)

💡 Совет: Для критически важных ограничений используйте OR-Tools решатель ("Обычный" или "Качественный"), так как он гарантирует соблюдение ограничений.

📊 Понимание результатов

Статистика маршрута

Параметр	Описание
Посещено узлов	Количество КП в маршруте (включая стартовый)
Общий приз	Сумма призов всех посещенных КП
Дистанция	Общая длина маршрута в километрах
Время расчета	Сколько времени потребовалось на вычисление (не время прохождения!)
Решатель	Использованный алгоритм (GREEDY или ORTOOLS)
Набор высоты	Коэффициент учета высоты для этого варианта

Интерактивная карта

На карте отображаются:

🟢 Зеленый маркер: Стартовая точка (депо)
🔵 Синие маркеры: Посещенные КП (в порядке прохождения)
⚪ Серые маркеры: Непосещенные КП
Синяя линия: Оптимальный маршрут

💡 Совет: Кликните на маркер, чтобы увидеть подробную информацию о КП (имя, приз, высота).

📚 История задач

Все расчеты автоматически сохраняются в разделе "История задач" в нижней части страницы.

Операции с историей:

👁 Просмотр: Открыть результаты предыдущего расчета
🗑 Удалить: Удалить задачу и все связанные файлы
🔄 Обновить: Обновить список задач

Информация в истории:

Имя задачи: Название, заданное при создании
Дата создания: Когда был выполнен расчет
Количество узлов: Сколько КП было в исходном файле
Количество вариантов: Сколько маршрутов было построено
Дистанция: Длина первого варианта маршрута

📁 Формат GPX файла

Требования к файлу:

Формат: GPX (GPS Exchange Format)
Кодировка: UTF-8
Должен содержать waypoints (точки интереса)
Обязательно: Точка с именем 0-0 (стартовая точка)

Структура waypoint:

lat, lon: Координаты (обязательно)
ele: Высота в метрах (опционально, можно загрузить автоматически)
name: Имя КП в формате "X-Y" где Y — это очки (приз)

Пример waypoint:


<wpt lat="55.7558" lon="37.6173">
    <ele>150</ele>
    <name>31-10</name>
</wpt>

Здесь КП номер 31 с призом 10 баллов на высоте 150 метров.

⚠️ Важно: Если высота не указана в GPX, система попытается загрузить её автоматически из внешних источников. Это может увеличить время обработки.

💡 Советы и рекомендации

Оптимизация производительности

Для первого расчета используйте "Быстрый" вариант для оценки
Большое количество КП (>100) требует больше времени
Временной бюджет вычисляется медленнее дистанционного
Множественные коэффициенты высоты умножают время расчета

Выбор параметров

Начните с коэффициента 1.3, затем сравните с 1.0 и 1.5
Для соревнований на 12 часов используйте бюджет ~720 минут
Для соревнований на 24 часа используйте бюджет ~1440 минут
Временной бюджет более точен, чем дистанционный

Анализ результатов

Сравните варианты с разными коэффициентами высоты
Обратите внимание на соотношение "приз/расстояние"
Проверьте логичность маршрута на карте (нет ли петель)
Учтите, что система не знает о препятствиях (реки, заборы и т.д.)

❓ Часто задаваемые вопросы (FAQ)

Почему расчет долго выполняется?

Время расчета зависит от количества КП, выбранных вариантов и алгоритмов. "Супер качество" может работать до 30 минут — это нормально.

Можно ли прервать расчет?

Да, просто обновите страницу. Расчет будет остановлен, но уже завершенные варианты сохранятся.

Где хранятся результаты?

Результаты хранятся на сервере в директории results/. Каждая задача имеет уникальный ID сессии.

Как экспортировать маршрут в GPS устройство?

В текущей версии экспорт в GPX не реализован. Используйте интерактивную карту для планирования. (Эта функция запланирована в будущих версиях)

Учитывается ли тип местности?

В текущей версии используется прямолинейное расстояние с учетом рельефа. Типы местности (лес, дорога, болото) пока не учитываются напрямую, но это в планах развития.

Что делать если API недоступен?

Проверьте что Docker контейнеры запущены: docker-compose ps
Если нет, запустите: make web-up

🔧 Технические детали

Используемые технологии

Backend: Python 3.13, FastAPI, Google OR-Tools
Frontend: Vanilla JavaScript, HTML5, CSS3
Визуализация: Folium (Leaflet.js)
Деплой: Docker, Nginx

Алгоритмы оптимизации

OR-Tools: Использует комбинацию методов: constraint programming, local search (Guided Local Search), и различные эвристики для решения Vehicle Routing Problem with Prizes.

Greedy: Жадный алгоритм с последующей оптимизацией через 2-opt swap.

📞 Поддержка и контакты

GitHub: github.com/IgorGots/route

Документация: Смотрите файлы в директории docs/

Вопросы и предложения: Создайте Issue на GitHub