Закажите услуги фрилансеров для вашего проекта прямо сейчас!

Размещение заказа на фриланс бирже бесплатно.

1 месяц назад
Гость
1 месяц в сервисе
Был онлайн 1 месяц назад
1 месяц назад

В рамках задачи требуется доработать алгоритм распределения заказов между курьерами.
Решается классическая математическая задача маршрутизации транспортных средств (VRP). Так же задача дополняется различными усложнениями алгоритма:
*Транспортное средство – здесь и далее подразумевается курьер.
1) У каждого заказа есть временные рамки для посещений - время забора и время доставки. Проблема маршрутизации транспортных средств с временными окнами (VRPTW).
*У каждого заказа есть несколько точек со статусами посещений: «Не посетил -> Выехал -> Прибыл на точку -> Посетил точку и забрал/доставил товар”
2) Задача маршрутизации транспортных средств с вместимостью (CVRP) — это задача VRP, в которой транспортные средства с ограниченной грузоподъемностью должны забирать или доставлять предметы в разных местах. Предметы имеют количество, такое как вес или объем, а транспортные средства имеют максимальную грузоподъемность, которую они могут перевозить. Проблема состоит в том, чтобы забрать или доставить товар с наименьшими затратами, не превышая вместимость транспортных средств.

Что необходимо сделать/доработать/улучшить:
1) После первичного распределения заказов и после того, как курьер начал выполнять заказы по маршруту - в алгоритм может попасть новый заказ. Необходимо найти новый оптимальный маршрут с учётом текущих заказов на курьере (и статусы точке заказов). Нюанс состоит в том, что курьер может выехать на какой-то заказ и при обнаружении нового оптимального маршрута желательно учесть, что курьер должен завершить текущий заказ (т.е. за текущее местоположение курьера можно считать координаты точки доставки). Противоположный исход - курьер успел выполнить все назначенные на него заказы, а время его работы еще осталось (условно, работает он с 9:00 до 17:00, алгоритм сперва нашёл оптимальное решение построения маршрута и назначил 3 заказа на курьера, которые он завершил в 15:00. Соответственно, предполагается, что алгоритм должен пытаться найти маршрут с учётом оставшегося свободного времени - с 15:00 до 17:00, если таковые имеются).
*Вероятно - задача коммивояжёра (TSP).

2) Рефакторинг ныне действующего алгоритма, а так же, желательно, комментирование и документирование кода.
Алгоритм учитывает:
- Количество курьеров
- Количество точек (точек заказа. 1 заказ - минимум, две точки. Максимум - 1 + N)
- Скорость курьера
- Время обслуживания одной точки
- Временные рамки посещения точки
- Временные рамки графика работы курьера (его активности)
- Максимально допустимый переносимый вес заказов для каждого курьера
- Текущие заказы на курьере
3) Более детальное описание различных сценариев ошибок/исключений для дальнейшего дебага при тестировании и эксплуатации алгоритма
Текущая версия алгоритма использует официальные библиотеки Google OR-Tools. Вся необходимая сопутствующая документация находится там.

Возможно, при решении данной задачи помогут некоторые статьи и открытый исходный код сторонних проектов:
Поиск оптимальных маршрутов для перевозки самокатов
Статья:
GitHub:

  1. Прием заявок
  2. Выбор исполнителя
  3. Выполнение заказа
  4. Обмен отзывами
Анна С.
Анна С. 
39 лет, Казахстан
5 месяцев в сервисе
Была онлайн 1 час назад
1 месяц назад
Тимофей Казаков
19 лет, Россия
4 месяца в сервисе
Был онлайн 1 неделю назад
1 месяц назад

Безопасный платеж

Луша М.
Луша М. 
25 лет, Россия
1 месяц в сервисе
Был онлайн 1 месяц назад
1 месяц назад

Безопасный платеж

Другие заказы в категории «Прикладное ПО»

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