Справка - Route Optimizer

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

1

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

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

2

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

Задайте бюджет и выберите «Быстрый» или «Оптимум»

3

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

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

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

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

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

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

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

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

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

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

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

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

GPX-файл автоматически сжимается в браузере перед отправкой.

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

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

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

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

Бюджет:

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

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

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

Вариант	Алгоритм	Время расчета	Качество
Быстрый	Greedy	~1 сек	Предварительный маршрут
Оптимум	CP-SAT (до 60s)	до 60 сек	Показывает верхнюю границу и gap; может доказать оптимум
OR-Tools	Routing solver (30s)	до 30 сек	Резерв для больших наборов (>150 КП)

💡 Рекомендация: Сравните «Быстрый» с «Оптимум». Если CP-SAT не доказывает оптимум для большого числа КП, попробуйте OR-Tools.

Шаг 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 часов)

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

Персональный профиль скорости

Загрузите тренировочный GPX с высотой и временем в track points. Трек разбивается на сегменты 150 м, остановки и участки со скоростью ниже 1 км/ч исключаются. Методом наименьших квадратов подбираются темп на ровном и фактор подъёма; сохранённый JSON-профиль можно выбрать для следующих расчётов.

Время на отметку КП

По умолчанию на поиск и отметку каждого посещённого КП закладывается 90 секунд. Время начисляется при входе в КП (не в депо): оно учитывается в расчётном времени и временном бюджете, но не увеличивает дистанционный бюджет.

Время старта, ночь и усталость

Выберите дату и местное время старта; браузер передаёт часовой пояс как ISO offset. По времени заката/рассвета и заданным коэффициентам система оценивает ночное замедление и усталость после шестого часа. Время прохода КП и ночные плечи показываются в таблице. Стоимость маршрута пересчитывается не более четырёх раз и останавливается, когда маршрут перестаёт меняться.

Запас времени и план «Б»

По умолчанию 10% указанного бюджета остаётся резервом для погрешности оценки скорости. Для временного бюджета на маршруте формируются до 12 CP-SAT сценариев: приход на 10 минут раньше или на 10, 20 и 30 минут позже в точках решения. Таблица показывает, какие выбранные КП стоит пропустить и сколько очков при этом теряется. Штраф за перерасход применяется только в этих сценариях; значение 0 запрещает плану Б превышать оставшееся время.

Маршрутизация

По прямым: плечи оцениваются напрямую между КП.
По местности: поиск идёт по подготовленному растру, обходит водоёмы и препятствия; длина, время и набор высоты считаются по найденным полилиниям.

Сервер выбирает подготовленный локальный растр, покрывающий все КП и буферную зону. Если подходящего растра нет, маршрут считается по прямым и в результат добавляется предупреждение; во время solve сетевые источники не запрашиваются.

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

Быстрый (Greedy)

Строит маршрут эвристически для быстрой предварительной оценки.

Оптимум (CP-SAT, до 60 секунд)

Максимизирует сумму призов и показывает верхнюю границу. Если статус — OPTIMAL и разрыв равен нулю, найденный результат доказанно оптимален.

OR-Tools (резерв)

Альтернативный решатель для больших наборов КП, где CP-SAT может не успеть доказать оптимум.

Модель времени и высот будет уточняться: текущие варианты отличаются алгоритмом, а не коэффициентами высоты.

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

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

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

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 решателя)

💡 Совет: Для критически важных ограничений используйте CP-SAT или OR-Tools — оба решателя поддерживают обязательные КП и цепочки.

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

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

Параметр	Описание
Посещено узлов	Количество КП в маршруте (включая стартовый)
Общий приз	Сумма призов всех посещенных КП
Дистанция	Общая длина маршрута в километрах
Время расчета	Сколько времени потребовалось на вычисление (не время прохождения!)
Решатель	Использованный алгоритм (GREEDY, CP-SAT или OR-Tools)
Статус оптимума	CP-SAT показывает верхнюю границу и разрыв; OPTIMAL означает доказанный оптимум

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура waypoint:

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

Пример waypoint:


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

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

⚠️ Важно: Загрузка GPX сама по себе не обращается к внешним сервисам. Чтобы запросить недостающие высоты, включите «Учитывать рельеф» перед запуском. Координаты КП будут отправлены в OpenTopoData, а при необходимости — в Open-Elevation; число узлов с высотой будет показано в результате. Без загруженных или указанных высот рельеф не учитывается.

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

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

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

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

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

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

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

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

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

Время расчета зависит от количества КП, выбранных вариантов и алгоритмов. CP-SAT работает до 60 секунд; OR-Tools доступен как резерв для больших наборов КП.

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

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

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

Результаты хранятся на сервере в директории 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