Привет, меня зовут Абай Баймуканов, я работают алгоритмистом в ИТ-компании Relog, разрабатывающей облачный сервис для оптимизации городской доставки.

Для решения транспортных задач в логистике нужны лучшие алгоритмы, поэтому мы решили провести собственное исследование и выбрали для него два самых популярных открытых алгоритма - Vroom и Jsprit.

Нужно было понять какой из них лучше не только по качеству, но и выдает решение (построение маршрутов с учетом различных транспортных задач) за короткое время.

Какую задачу решали

Есть разные виды VRP-задач, например, CVRP (учет весогабаритных параметров), VRPTW (учет временных окон), MDVRP (задача с несколькими складами) и PDVRP(задача с забор-доставка). Для теста мы взяли CVRPTW (CVRP+VRPTW), поскольку это самая актуальная для наших клиентов задача.

Про сами алгоритмы. В чем их разница и преимущества

Для решения задач мы использовали два солвера Vroom и Jsprit. Оба они являются движками с открытым исходным кодом и решают CVRPTW, а также имеют много звезд Github.

VROOM

Vroom — это движок оптимизации с открытым исходным кодом, написанный на C++17, предназначенный для поиска эффективных решений разных реальных задач маршрутизации транспортных средств (VRP) за небольшое вычислительное время. Он решает задачу в 2 этапа:

Меня зовут Абай Баймуканов, я – разработчик-алгоритмист международной IT-компании Relog. Уже несколько лет увлекаюсь олимпиадными программированием, поэтому в этой статье хотел бы поделиться своим видением по этому поводу.

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

Здесь есть свой нюанс: программа может работать настолько долго, сколько не существует даже вселенная, а может сработать за долю секунды. Причем в обоих случаях результат будет один и тот же. Любой олимпиадник стремится к тому, чтобы его программа была как можно эффективнее. Для этого существуют алгоритмы и структуры данных - методы, позволяющие сделать определенные программы более эффективными с точки зрения необходимого времени или памяти компьютера.

Спектр сложности у задач по спортивному программированию достаточно широкий: от задач для новичков до задач мирового уровня для вундеркиндов. Большинство соревнований проводится практически одном и том же формате, то есть дается несколько задач, на их решение 5 часов и за это время нужно решить как можно больше.

На школьных олимпиадах обычно за каждую задачу можно получить от 0 до 100 баллов и общим результатом будет суммарный балл за все задачи, у студентов в результат идет просто количество решенных задач, а если есть участники, решившие одно и то же количество задач, то они группируют по убыванию штрафа. Чем дольше решаешь задачу или чем больше на них нужно попыток решить, тем больше штрафов за нее получишь.