two opt inversion

Уважаемые коллеги, добрый день Нужен алгоритм для решения TSP - 2-opt

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

Поиск в гугле не дает нормального описания или я не там ищу.

У меня уже есть построенный маршрут по городам. Теперь нужно данный маршрут прогнать 2opt inversion, т.е. оптимизировать уже имеющийся. Написал программу, но она работает не так как нужно, поэтому нужно изучить теорию. На сайте https://tspvis.com/ нашел код (javascript ???) не все понимаю , что делает код , а мне нужна однозначность

const twoOptInversion = async path => {
  path.push(path[0])
  let best = pathCost(path)
  let swapped = true

  while (swapped) {
    swapped = false
    for (let pt1 = 1; pt1 < path.length - 1; pt1++) {
      for (let pt2 = pt1 + 1; pt2 < path.length - 1; pt2++) {
        // section of the path to reverse
        const section = path.slice(pt1, pt2 + 1)

        // reverse section in place
        section.reverse()

        // replace section of path with reversed section in place
        path.splice(pt1, pt2 + 1 - pt1, ...section)

        // calculate new cost
        const newPath = path
        const cost = pathCost(newPath)

        if (cost < best) {
          // found a better path after the swap, keep it
          swapped = true
          best = cost
          self.setBestPath(newPath, best)
        } else {
          // un-reverse the section
          section.reverse()
          path.splice(pt1, pt2 + 1 - pt1, ...section)
        }
      }
    }
  }
}


Задача заключается в поиске оптимального маршрута -классическая задача коммивояжера. Я нашел маршрут с помощью жадного алгоритма, используя в качестве отправной точки перебор всех вершин и выбрав самый лучший путь. А теперь хочу прогнать этот "оптимальный" путь с помощью 2opt алгоритма, но не очень понимаю алгоритм его работы, поэтому и прошу помочь с алгоритмом (такой как на сайте по ссылке). Программа написана на VBA, но работает некорректно. Приложил сам файл. файл эксель с реализацией


Ответы (0 шт):