Алгоритмизация перезарядки самокатов

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

Максимизируем величину $$\sum_{i} val_i - T \cdot penalty$$ где $T$ - общее затраченное время, $penalty$ - штраф за секунду в пути. При этом должны выполняться ограничения на количество перевозимых аккумуляторов (в нашем случае 50) и на длительность смены

Один исполнитель

Начнем с генерации пути для одного исполнителя. Разобьем на 2 этапа: начальная генерация и локальная оптимизация

Начальная генерация

Из 500 точек нужно выбрать 50. Выбираем случайно, переходя в следующую вершину с вероятностью, пропорциональной расстоянию до нее

Локальная оптимизация

Задача коммивояжера для 50 вершин. Используем алгоритм имитации отжига и муравьиный алгоритм. Была взята и адаптирована open source реализация этих алгоритмов на Python, в дальнейшем планируется переписать на C++ в целях оптимизации

Несколько исполнителей

Для нескольких исполнителей локальная оптимизация будет той же, но начальное разбиение на пути будет отличаться. Самый простой, но неоптимальный вариант, это сгенерировать несколько путей последовательно. Более разумным выглядит разбиение вершин на батчи, и затем для каждого батча отдельно генерируется путь и затем оптимизируется. Будет реализованно в этом семестре. Также в планах сравнить результаты при разных параметрах (например насколько будет улучшение качества при времени работы 2 минуты против 10 секунд)