Алгоритм оптимизации графика

Question

У меня есть график, и мне нужно посетить каждый узел ni в графе, начиная с выбранного узла. Существует стоимость не посещать узел, который отличается для разных узлов, ci и существует градиент времени к стоимости ci. Другими словами, затраты на не посещение ci являются функцией времени. Существует стоимость транспортировки, линейная на расстоянии между двумя узлами dij для двух соседних узлов i и j.

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

Единственная идея, которую я имею, это переборщить ее и выбрать все возможные маршруты и вычислить стоимость. Мне было интересно, может ли кто-нибудь дать общее представление о решении проблемы. Я не ищу код/​​целое решение только некоторые указатели или некоторые документы, которые указывают на эту проблему. Обратите внимание, что это отличается от проблемы продавцов.

Answer 1

Как вы отвечаете на Draco18s выше, это вариант «классического TSP».

Обозначает классическую версию как cTSP; описывая проблему посещения всех узлов в графике (а также, наконец, возврат к исходному узлу), где функция стоимости содержит только сумму транспортных расходов - линейную на расстоянии --- для перемещения между различными узлами.

Обозначает ваш вариант cTSP как vTSP. Прежде чем решать проблему, мы должны определить некоторые важные различия между cTSP и vTSP. Для экземпляра cTSP из n узлов существует (n-1)!/2 различных путей; для любого определенного пути ни направление, ни начальный узел не будут влиять на стоимость пути. Для экземпляра vTSP проблема сложнее, так как выбор начального узла, а также направления пути повлияет на стоимость пути из-за зависящих от времени затрат на отсутствие (пока) посещающих узлов. Я предполагаю отсюда, что «время, проведенное с начала путешествия», определяется как некоторая связь с «расстоянием, пройденным с начала путешествия», в частности, постоянной скоростью движения. Кроме того, я предполагаю, что эти зависящие от времени функции стоимости монотонно возрастают.

Я не встречал этот конкретный вариант в литературе, поэтому я не могу дать вам никаких указателей в этом направлении. По сравнению с грубой силой (которая для vTSP должна стать довольно трудноразрешимой с увеличением размера проблемы), я бы предложил, однако, приблизиться к проблеме, используя оптимизацию колонии муравьев (ACO). Отказавшись от оптимальности, вы могли бы по крайней мере сравнить его результаты с методом грубой силы за некоторое время на время работы алгоритма. С ACO, чтобы убедиться, что уровни феромонов остаются количественной мерой для хороших путей даже в более сложном vTSP, проблема, вероятно, должна быть разделена на n подзадач, каждая из которых имеет фиксированный начальный город. Первоначально пусть эти подзадачи являются независимыми, возможно, в более позднем периоде, изучая возможность их взаимодействия.

Для каждой подзадачи просто примените (стандартное) ACO, что довольно просто, см., Например,

Уровни феромонов разных краев будут, как и ACO, примененные к cTSP, - все еще просто отражают, если это край, «популярный» среди муравьев. Поскольку исходный узел фиксирован и по мере того, как время относительно пройденного расстояния, муравьи должны способствовать раннему посещению узлов, которые более наказывают до позднего прибытия. Из глаз муравьев дополнительный тип ограничения в vTSP w.r.t. cTSP просто приведет к другому забиванию благоприятных краев (само по себе своего рода грубая сила ...).

В любом случае, возможно, не ответ, который вы искали (если предпочитаете классические методы оптимизации?), Но удачи!