Проблемы с маршрутизацией с большим количеством точек и одним ограничением

Question

В настоящее время я занимаюсь проблемой маршрутизации, когда мне приходится составлять ежедневное расписание для работников по ремонту некоторых установок. Там 200 000 установок и рабочий может работать только 8 часов за фей. Цель состоит в том, чтобы делать оптимальные маршруты ежедневно; Таким образом, оптимизируя расстояние между различными точками, которые он должен посещать ежедневно, также существует ограничение на приоритет каждой установки. Действительно, каждая установка имеет приоритет от 0 до 1, и точкам с более высоким приоритетом должны быть присвоены более высокие веса.

Я просто искал некоторые предложения, поскольку я пытался реализовать некоторые решения (https://developers.google.com/optimization/routing/tsp), но из-за множества моментов, которые у меня есть, это приводит к слишком большому времени вычислений.

Спасибо.

С уважением,

Charles

Answer 1

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

Что вы должны попробовать, по крайней мере, на мой взгляд, это эвристические подходы для решения TSP / VRP: поиск по табу , имитация отжига , восхождение на гору . При наличии достаточного количества времени и правильного набора ограничений один из этих методов даст «достаточно хорошие» решения, которые намного лучше, чем случайное предположение. Взгляните на что-то вроде Google OR-Tools

Answer 2

Это огромная проблема. Вам нужно будет разбить его на более мелкие подзадачи, прежде чем заняться этим. Мы применили сложные методы нечеткой кластеризации, чтобы экспериментально решить проблему с 20000 местоположений. Для 200 000 вам, вероятно, потребуется агрегировать данные по географическим регионам (например, почтовый индекс / почтовый индекс), прежде чем вы сможете попытаться запустить какую-то кластеризацию, чтобы разделить ее. В качестве альтернативы вы, возможно, просто захотите попробовать жесткий сплит, основанный в первую очередь на географии.

Answer 3

Как вы знаете, не существует идеального ответа на ваш вопрос, но, возможно, я смогу направить ваше исследование:

• Альфа-бета-обрезка : я использовал его, чтобы уменьшить количество возможностей для игры в шестнадцатеричный ИИ.
• A * pathfinding : я использовал его для симуляции футуристической сети на основе капсул, похожей на капсулу, как дополнение к алгоритму Дейкстры.

Вы можете настроить оба алгоритма в соответствии со своими потребностями.

Надеюсь быть полезным!