Veeroute демонстрирует эффективность на публичных бенчмарках

Оптимизатор Veeroute показал лучшие результаты на публичных бенчмарках, приближенных к реальным условиям.

В таблице решений на 300 задач, предложенных владельцем репозитория cssartori, Veeroute занимает 214 строчек. Всё это — впервые зафиксированные лучшие решения, которые удалось получить с помощью оптимизатора Veeroute

Что это значит? Объясняем по порядку.

Как устроены соревнования на бенчмарках?

В марте 2019 года автор бенчмарков Carlo S. Sartori выложил задачи в публичный доступ, предложив всем желающим посоревноваться в их решении.

Данные бенчмарки представляют из себя транспортные задачи, не имеющие готового решения — по каждой из них известен только текущий лучший результат. В силу специфики задач проверить, является ли этот результат оптимальным, невозможно, однако при желании его можно попытаться улучшить.

Участники соревнования, которые первыми предоставят более эффективное решение той или иной задачи, попадают в итоговую таблицу, которая демонстрирует текущие лучшие результаты вместе с датами, когда они были получены. Если несколько участников предоставили одинаковые результаты, то в таблице указывается тот, кто предоставил своё решение раньше других.

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

Соревнования подобного плана проводят и крупные организации — так, например, регистрацией лучших решений академических бенчмарков занимается SINTEF, старейшая независимая исследовательская организация из Норвегии.

Успех на бенчмарках — доказательство эффективности?

Несмотря на то, что бенчмарки часто используются для сравнения программных продуктов, они редко позволяют получить приближенные к реальности результаты. Об этом мы подробно рассказываем в статье о сравнении планировщиков.

В соревнованиях преимущественно используются академические бенчмарки — абстрактные задачи, удалённые от реальности. Они сильно упрощены по сравнению с повседневными бизнес-задачами и используют фиксированные наборы данных, поэтому успех на бенчмарках вовсе не говорит о том, что планировщик будет эффективно решать задачи на практике.

Так, в классических бенчмарках — в том числе в тех, решения которых собирает SINTEF — используется евклидово расстояние: путь от точки до точки всегда рассчитывается по прямой. Поскольку в реальном мире такие условия встречаются редко, результаты, полученные на стандартных бенчмарках, не дадут чёткого представления о качестве работы оптимизатора.

Бенчмарки, приближенные к реальности

В отличие от бенчмарков, предлагаемых большинством популярных репозиториев, задачи, созданные Carlo S. Sartori, были сгенерированы с учётом реальных данных — расстояния между точками рассчитываются не по прямой, а по существующим дорогам.

Таким образом, автору бенчмарков удалось добиться большей реалистичности задач: в них используются неравные отрезки, где путь в точку отличается от пути из точки — например, в случае с дорогами с односторонним движением. Это одновременно усложняет расчёт маршрутов и приближает бенчмарки к условиям реального мира.

Приближенность к реальным условиям — причина, по которой наша команда обратила внимание на бенчмарки, предложенные Carlo S. Sartori: они больше подходят для демонстрации возможностей комбинаторного оптимизатора Veeroute, чем стандартные академические примеры.

Результаты Veeroute

В репозитории Carlo S. Sartori были представлены задачи разной размерности:
от 100 до 5000 локаций. На всех задачах от 1500 локаций и больше Veeroute удалось получить лучший результат.

Улучшения были зафиксированы на всех задачах, кроме самых небольших — 100 локаций. Это связано с тем, что на задачах малой размерности относительно легко достичь лучшего результата: вероятнее всего, его удалось получить большинству участников соревнования, но в таблицу был занесён только тот, кто получил его первым.

В общей сложности, впервые зафиксированный лучший результат принадлежит Veeroute в 214 из 300 предложенных задач.