Оптимизация маршрутов и расписания выездных сотрудников
Алгоритм, который оптимизирует маршруты и расписание выездных сотрудников с учётом времени встреч, географии и дорожной обстановки.
Контекст
Расписание выездов составлялось вручную и по интуиции: часть времени уходила на переезды, которых можно было избежать.
Маршрут, оптимальный по расстоянию, часто невыполним по времени. Время в пути берётся из прогноза пробок на тот час, когда сотрудник реально поедет на встречу: утренний и вечерний маршрут по одним и тем же адресам – это два разных маршрута.
Вторая половина задачи – сотрудник выезжает из дома и возвращается домой. Место жительства входит в расчёт наравне с адресами встреч: без него алгоритм экономит на переездах между клиентами и теряет сэкономленное на дороге до первой точки и обратно с последней.
Как перестраивается маршрут
Время в пути на момент поездки
Результат планирования
Что входило в задачи
- Прогноз пробокЯндекс Карты дают время в пути на тот час, когда сотрудник реально поедет
- Дом сотрудникамаршрут строится от дома и до дома: дорога до первой точки тоже стоит времени
- Задачи и окналокации, длительность встреч, временные ограничения
- Жадное решениебыстрый допустимый вариант как отправная точка
- Муравьиный алгоритмперебор порядка обхода, в который помещается больше встреч
- Рабочее времядоступность сотрудников как ограничение расписания
- Оценка качествасчитаем по числу задач, которые удалось выполнить за день