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

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

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