Тестовое задание от компании Drivee

Стек технологий

Backend: golang Frontend: vite, react, TypeScript, react-yandex-maps

Запуск

Для запуска потребуется:

• убрать example у example.env
• установленный golang
• установленный make (можно установить через choco install make)

Далее нужно ввести команду make run - линукс, а для windows - make run-windows

Для запуска фронтенда нужно:

• nodejs
• npm
• npm install (в папке frontend)
• npm run dev

Задача

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

Решение

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

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

Для решения данной проблемы я выбрал Генетический алгоритм для нахождения кратчайшего пути между заказами одного курьера, а для распределения курьеров будем использовать Венгерский алгоритм. Значение будем брать исходя из расстояния между точками (координаты), приблизительная скорость курьера. Можно взять также такие параметры, как рейтинг курьера, чп, пробки, погодные условия, но я думаю, что не успею выполнить это всё в срок, поэтому пренебрегу такими параметрами. Я лучше воспользую "штрафом", который будет уменьшать или увеличивать значения исходя из коэффициента штрафа. Скорость, рейтинг курьера и т.д. будут являться каким-то коэффициентом у курьера, который будет замедлять его и увеличивать искусственно расстояния, чтобы он не мог брать слишком далекие от него заказы. Можно также этот штраф добавлять и для заказов, у которых по пути могут быть пробки, гололед и прочие уличные проблемы.

Почему именно венгерский алгоритм?

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

Как это работает?

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