Доработка алгоритма построения маршрутов на pythone (or-tools)

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

Решается классическая математическая задача маршрутизации транспортных средств (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. Вся необходимая сопутствующая документация находится там.

https://developers.google.com/optimization/routing?hl=ru

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

Поиск оптимальных маршрутов для перевозки самокатов

Статья: https://itnan.ru/post.php?c=1&p=705582

GitHub: https://github.com/klyusba/yandex_cup_2022/blob/master/algoritm_marathon/solvers/or_solver.py