Несколько TSP с завихрением

Question

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

Есть несколько соленников. Список городов динамически увеличивается (как, в реальном времени) Каждый город только полностью выгоден в течение ограниченного промежутка времени, так как через некоторое время город вернет меньше вознаграждения И есть общее время предел

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

Answer 1

Возможно, вы сможете использовать программное обеспечение для исследования некоторых операций, чтобы решить вашу проблему, например. Coin-OR, причина в том, что обычно проще добавлять новые ограничения/цели в решатель OR/linear/integer/etc для программирования, чем, например. специализированный TSP-решатель, написанный на C или Fortran или что-то в этом роде (и вряд ли вы найдете код C/Fortran для решения вашей точной проблемы). Here is a tutorial on how to code a Tabu search to solve the basic TSP using Coin-OR. Кроме того, here is an article on modeling the time-dependent TSP (в статье используется ветка и граница для решения проблемы, которая, вероятно, не подходит для вашей проблемы, поскольку она не масштабируется за сотню городов или около того, но модель должна переноситься на приблизительный решатель, такой как Монета-ИЛИ).

Чтобы учесть наличие нескольких продавцов, вы можете захотеть просмотреть разбиение графов, чтобы разделить города среди разных продавцов, например here is a fast online graph partitioning algorithm. Преимущество состоит в том, что после разделения графов вы можете уменьшить или даже устранить синхронизацию между разными продавцами.