В 2020 году Saint HighLoad++ проводиться не будет.
В Санкт-Петербурге мы с вами встретимся в июне 2021

Алгоритмы в Яндекс.Маршрутизации: 100000 дейкстр в секунду на ядро, или Как получить хайлоад от одного запроса Бэкенд, теория программирования

Доклад принят в программу конференции
Тихон Рощупкин
Яндекс

9 лет в Яндексе, из них 6 лет в Яндекс.Поиске. Руководил службой базового ранжирования, растил метрику качества выдачи.
3 года в Яндекс.Картах. С нуля участвовал в создании проекта Яндекс.Маршрутизации и сейчас руководит всей его технической частью.

Почта: tuxxon@yandex-team.ru
Telegram: tuxxon
Тезисы

Ежедневная проблема крупной службы доставки: как развести 5000 заказов с помощью 200 водителей. Чтобы начать решать такую задачу, нужно за 2 минуты посчитать 300 млн маршрутов. Затем за 10 минут нужно найти оптимальное размещение этих заказов по водителям. Хорошая новость в том, что у вас есть вычислительный кластер. Плохая новость в том, что даже с одним водителем вариантов объехать все заказы 5000! — это число с 16327 знаками. Хорошая новость в том, что самое оптимальное решение искать не нужно, достаточно решить эту задачу лучше человека (логиста). Логист находит решение этой задачи на 1 млн рублей логистических расходов. Если вы найдёте решение на 10% лучше, то сэкономите клиенту 100 тыс. рублей. И это за 12+ минут вы обработали только один запрос.

В докладе будут рассмотрены быстрые алгоритмы поиска оптимального пути на графе и дискретной оптимизации на вычислительном кластере в приложении к логистической задаче, используемые в Яндекс.Маршрутизации.

Другие доклады секции Бэкенд, теория программирования