Фон

Задача коммивояжера (TSP) требует кратчайшего маршрута, который посещает данную коллекцию городов. Для целей этого вопроса города будут точками на плоскости, а расстояния между ними будут обычными евклидовыми расстояниями (с округлением до ближайшего целого числа). Цепь должна быть "круговой", то есть она должна вернуться в стартовый город.

Решатель Concorde TSP может решить экземпляры евклидовой задачи коммивояжера, точно и гораздо быстрее , чем можно было бы ожидать. Например, Concorde смог точно решить экземпляр на 85 900 пунктов , части которого выглядят так:

Однако некоторые экземпляры TSP занимают слишком много времени даже для Concorde. Например, никто не смог решить этот экземпляр на 100 000 пунктов на основе Моны Лизы . (Предлагается приз в размере 1000 долларов, если вы можете его решить!)

Concorde доступен для скачивания в виде исходного кода или исполняемого файла. По умолчанию он использует встроенный решатель линейных программ (LP) QSopt , но он также может использовать лучшие решатели LP, такие как CPLEX.

Соревнование

Какой самый маленький экземпляр TSP, который вы можете сгенерировать, требует Concorde более пяти минут ?

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

счет

Чем меньше очков в инстансе, тем лучше. Связи будут нарушены размером файла экземпляра (см. Ниже).

Стандартизация

Различные компьютеры работают быстрее или медленнее, поэтому мы будем использовать NEOS Server for Concorde в качестве стандарта измерения времени выполнения. Вы можете отправить список точек в следующей простой 2-й форме координат:

#cities
x_0 y_0
x_1 y_1
.
.
.
x_n-1 y_n-1

Настройки, которые должны использоваться в NEOS: «Конкордные данные (файл xy-списка, норма L2)», «Алгоритм: Конкорд (QSopt)» и «Случайное начальное число: исправлено».

базисный

Экземпляр rl1889.tspс 1889 точками из TSPLIB занимает «Общее время выполнения: 871,18 (секунд)», что составляет более пяти минут. Это выглядит так:

88 городов, 341 секунд выполнения на NEOS

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

http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html

88 городских экземпляров из этого семейства принимают Concorde на сервере NEOS более 5 минут. Экземпляр из 178 городов этой семьи требует уже больше одного дня.

77 городов, среднее время пробега по NEOS 7,24 минуты (434,4 секунды)

Я немного опоздал на вечеринку, но я хотел бы добавить экземпляр с 77 узлами, weruSnowflake77.

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

Чтобы построить этот экземпляр, я начал с базового графа (13 x 13 квадратов), а затем систематически вводил новые точки или переводил старые точки, сохраняя корректировки, которые, казалось, делали конкорд в среднем глубже в его ветви перед резкой.

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

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

При 10 пробных запусках на NEOS с использованием фиксированного начального числа и QSopt среднее время выполнения составило 7,24 минуты (434,531 секунды). Минимальное время выполнения составило 5,6 минуты (336,64 секунды). Максимальное время выполнения составило 8,6 минуты (515,80 секунды). Ни одно испытание не было отменено. Полная таблица тестов ниже:

Результаты теста за 10 запусков:

----------------------------------
| Run | Job ID# | Total running  |
|     |         | time (seconds) |
|-----|---------|----------------|
| 1   | 7739963 | 513.44         |
| 2   | 7740009 | 336.64         |
| 3   | 7740023 | 514.25         |
| 4   | 7740029 | 447.97         |
| 5   | 7740038 | 357.10         |
| 6   | 7740072 | 447.47         |
| 7   | 7740073 | 336.19         |
| 8   | 7740075 | 515.80         |
| 9   | 7740088 | 361.26         |
| 10  | 7740091 | 515.19         |
----------------------------------

weruSnowflake77 (xy список, норма L2):

77
-700 -700
700 -700
200 0
0 200
-200 0
0 -200
0 0
-600 600
-500 600
-400 600
-300 600
-200 600
-100 600
0 600
100 600
200 600
300 600
400 600
500 600
600 600
-600 -600
-500 -600
-400 -600
-300 -600
-200 -600
-100 -600
0 -600
100 -600
200 -600
300 -600
400 -600
500 -600
600 -600
600 -500
600 -400
600 -300
600 -200
600 -100
600 0
600 100
600 200
600 300
600 400
600 500
-600 -500
-600 -400
-600 -300
-600 -200
-600 -100
-600 0
-600 100
-600 200
-600 300
-600 400
-600 500
-500 -500
-400 -400
-300 -300
-200 -200
-100 -100
100 100
200 200
300 300
400 400
500 500
100 -100
200 -200
300 -300
400 -400
500 -500
-100 100
-200 200
-300 300
-400 400
-500 500
700 700
-700 700

вместилище

• URL Github: https://github.com/LDubya/weruSnowflake77

Задача установить файлы из репо:

• weruSnowflake77.txt (файл списка xy, норма L2)
• weruSnowflake77.tsp (формат TSPLIB, EUC_2D)

Python 3, 911 городов, 1418 секунд времени выполнения на NEOS

Следующий скрипт Python 3.x генерирует координаты 911 городов. NEOS потребовалось 1418 секунд, чтобы рассчитать кратчайший путь из 47739.

Вот картина самого короткого пути (спасибо А. Рекс):

Код / алгоритм основан на бифуркации Фейгенбаума , которую я использовал для генерации серии значений, которые я использовал в качестве основы для генерации координат городов. Я экспериментировал с параметрами, пока не нашел число городов до 1000, что заняло у NEOS удивительное количество времени (значительно больше требуемых 5 минут).

x = 0.579
coords = []
for _ in range(1301):
    if int(3001*x) not in coords:
        coords.append(int(3001*x))
    x = 3.8*x*(1-x)
coords = list(zip(coords, coords[::-1]))
print(len(coords))
for coord in coords:
    print(f"{coord[0]} {coord[1]}")

PS: у меня есть скрипт, выполняющий поиск меньшего числа городов, который также занимает> 5 минут на NEOS. Я опубликую их в этом ответе, если найду.

PS: Блин! Запуск этого сценария с параметром l 1811 вместо 1301 приводит к 1156 городам с временем работы в NEOS чуть более 4 часов , что намного больше, чем в других случаях с аналогичными параметрами ...