Как Альфа-Банк делал собственную систему маршрутизации для доставки в 1300 городов

Буквально каждый день решая «задачу коммивояжёра».

Как Альфа-Банк делал собственную систему маршрутизации для доставки в 1300 городов
5454

Решить задачу коммивояжера на 4-10 "городов" это, конечно, не rocket science, но все равно приятно, что коммерческие предприятия занимаются этим.

С промежуточной кластеризацией решение все равно получается эвристическим, так что я бы лучше сразу использовал эвристику для решения множественной задачи коммивояжера. Например, для вашей задачи можно использовать алгоритм муравьиных колоний (Ant Colony Optimization). Количество муравьев на каждой итерации соответствует числу сотрудников, муравьи стартуют с места жительства сотрудников и пытаются обойти "города" в соответствии с теми ограничениями, что вы наложили. При этом помимо ограничений на граф, вы можете динамически поддерживать ограничения такие как максимальное число "городов" у каждого сотрудника, или задать набор навыков у сотрудника и набор навыков требуемого для каждого "города", тогда "муравьи"-сотрудники смогут выбирать только те, "города" которые соответствуют их навыкам.

1
Ответить

Как на это ответит Альфа банк? 😅

1
Ответить