Кратчайший пешеходный тур по пабам Великобритании

Кратчайший пешеходный тур по пабам Великобритании

Маршрут имеет длину 45 495 км, это больше окружности Земли

Уильям Кук

Как последовательно, от одного к другому, кратчайшем путем, посетить все пабы и вернуться домой? Команда математиков решила эту задачу за два года. Используя географические координаты 24 727 пабов, предоставленных сайтом Pubs Galore (Изобилие пабов), и измеряя расстояние между любыми двумя пабами как длину маршрута, созданного Google Maps, авторы проложили самый короткий путь между всеми пабами Великобритании. Точнее не пабами, а остановками рядом с пабами.

Всего существует 305 699 901 пар пабов. Список из 24 727 пабов, расположенных один за другим в правильном порядке, напоминает телефонную книгу большого размера. Построение пути - это решение проблемы коммивояжера (TSP), одна из самых известных задач комбинаторной оптимизации. Инструмент, называемый линейным программированием, позволяет решать подобные задачи. В расчетах использовалась улучшенная версия реализации Concorde метода TSP.

Запущен метод плоскости резки в тандеме с вариантом кода Келда Хельсгауна LKH. Использована процедура поиска ветвей и границ. В этом процессе набор маршрутов неоднократно подразделяется и метод результирующей плоскости применяется к результирующим подзадачам TSP. Общее количество компьютерного времени составило 305,2 дня на одном процессорном ядре сервера Linux. На самом деле, результата не пришлось ждать целых 10 месяцев, так как поиск выполняли параллельно на 48 ядрах. Используя различные настройки для проверки правил выбора, запустили фазу ветвления и привязки второй раз. Этот второй прогон занял в общей сложности 1381,1 дня.

Оптимальный маршрут имеет длину 45 495 239 метров, это больше, чем окружность Земли. Мы не ставили перед собой задачу увеличить число поклонников блуждания по пабам, чтобы пропустить пинту-другую,- сообщил руководитель проекта, профессор Уильям Кук. Проблема британского паба использовалась как средство для разработки и тестирования методов оптимизации общего назначения, которые широко применяются в науке, промышленности и торговле.

Уильям Кук (William Cook), Университет Ватерлоо (University of Waterloo), Канада, Даниэль Эспиноза (Daniel Espinoza), Gurobi Optimization, США, Маркос Гойкулея (Marcos Goycoolea), Университет Адольфо Ибанеса (Universidad Adolfo Ibanez), Чили, Келд Хельсгаун (Keld Helsgaun), Университет Роскилле (Roskilde University), Дания, публикуют результаты грандиозного труда "Кратчайший пешеходный тур по пабам Великобритании", University of Waterloo, Март 2018.