2-опт - 2-opt

2-опт

В оптимизации , 2-неавтоматический простой локальный алгоритм поиска для решения задачи коммивояжера . Алгоритм 2-opt был впервые предложен Крузом в 1958 году, хотя основной ход уже был предложен Фладом. Основная идея заключается в том, чтобы выбрать маршрут, который пересекает сам себя, и изменить его порядок, чтобы он не пересекался. 

 - A   B -             - A - B -
     ×         ==>
 - C   D -             - C - D -

Полный локальный поиск с двумя вариантами будет сравнивать все возможные допустимые комбинации механизма подкачки. Этот метод может быть применен к задаче коммивояжера, а также ко многим связанным с ней задачам. К ним относятся проблема маршрутизации транспортных средств (VRP), а также ограниченная VRP, которые требуют незначительной модификации алгоритма.

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

procedure 2optSwap(route, i, k) {
    1. take route[0] to route[i-1] and add them in order to new_route
    2. take route[i] to route[k] and add them in reverse order to new_route
    3. take route[k+1] to end and add them in order to new_route
    return new_route;
}

Вот пример вышеперечисленного с произвольным вводом:

  • Пример маршрута: A → B → C → D → E → F → G → H → A
  • Пример параметров: i = 4, k = 7 (начальный индекс 1)
  • Пошаговое содержание new_route:
    1. (A → B → C)
    2. А → В → С → (G → F → E → D)
    3. A → B → C → G → F → E → D → (H → A)

Это полный 2-опционный своп, использующий вышеуказанный механизм: 

repeat until no improvement is made {
    best_distance = calculateTotalDistance(existing_route)
    start_again:
    for (i = 0; i <= number of nodes eligible to be swapped - 1; i++) {
        for (k = i + 1; k <= number of nodes eligible to be swapped; k++) {
            new_route = 2optSwap(existing_route, i, k)
            new_distance = calculateTotalDistance(new_route)
            if (new_distance < best_distance) {
                existing_route = new_route
                best_distance = new_distance
                goto start_again
            }
        }
    }
}

Примечание. Если вы начинаете / заканчиваете на определенном узле или депо, вы должны удалить его из поиска как подходящего кандидата для обмена, так как изменение порядка приведет к неверному пути.

Например, с депо в А: 

   A → B → C → D → A

Обмен с использованием узла [0] и узла [2] даст 

   C → B → A → D → A

что не действует (не выезжает из депо А).

Смотрите также

использованная литература

  • Дж. Кроуз (1958). Метод решения задач коммивояжера . Операции Res. 6 (1958), стр., 791-812.
  • ММ НАВОДНЕНИЕ (1956). Задача коммивояжера . Операции Res. 4 (1956), стр. 61-75.

внешние ссылки