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

[mirecl]

В этом году тоже решали подобную задачу и остановились на OR-Tools.

Для определения скорости и времени от точки А до точки B использовали Open Source Routing Machine (OSRM) - он используется на https://www.openstreetmap.org/.

Правда нам пришлось его поставить на отдельную машину, чтобы быстрее считать сразу большой набор данных за 1 запрос. Информацию по пробкам надо загружать отдельно и с OSRM есть свои нюансы)

При использовании OR-Tools наткнулись как минимум на 2 проблемы:

1. На момент нашего исследования - не умела работать в многопоточном режиме, что приводило к долгому обсчёту (обещают поправить в CP-SAT);

2. При добавлении новых ограничений в модель OR-Tools, она легко может сломаться или уйти искать решение в бесконечность (пришли к выводу - что ей надо помогать, см ниже).

В итоге пришли к такому сценарию:

1. Создали отдельную модель кластеризации и разбили N-точек на группы для каждой машины;

2. Прогоняем уже в параллель модель на для каждой машины;

3. Проверяем, что все точки машина успешно прошла. Если нет - анализируем загрузку каждой машины и делаем перебалансировку точек на другие маршруты и заново идем в п.2 (обычно за 2-3);

4. Написали в Jupyter визуализацию каждого маршрута на карте - чтобы просмотреть результат модели.

[klyusba]

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

В задаче с самокатами ограничения на количество самокатов в автомобиле заводили солвер в тупик, даже в мягкой форме. Мне кажется, это в первую очередь из-за количества таких ограничений. Как будто солвер в самом начале скатывался в локальный минимум и никак не мог из него выбраться. Только хорошее начальное решение позволяло продвинуться. Собственно для получения начального решения и решал без ограничений на вместимость.

[andrewgt]

А не пробовал, как OR-Tools в линейных и mixed-integer линейных задачах относительно грандов?

[klyusba]

Под грандами ты имеешь в виду пакеты типа cplex? Нет, не пробовал. Пробовал наоборот, с помощью cplex решить эту задачу. Но не удалось быстро разобраться в API. Решил лучше докрутить решение на or-tools, нежели начинать в третий раз заново.