Комплекс программ для исследования методов решения задачи о коммивояжере 05. 13. 18 математическое моделирование, численные методы и комплексы программ

Работа выполнена на кафедре прикладной математики в Государственном образовательном учреждении высшего профессионального образования Ульяновский государственный университет


Научный руководитель: кандидат физико-математических наук,

доцент Воденин Дмитрий Ростиславович


Официальные оппоненты: доктор физико-математических наук,

профессор

Мельников Борис Феликсович

доктор технических наук, профессор

Смагин Алексей Аркадьевич


Ведущая организация: ГОУ ВПО Ульяновский государственный

технический университет


Защита диссертации состоится « 23 » апреля 2008 года в 10 часов на заседании диссертационного совета Д 212.278.02 при Ульяновском государственном университете по адресу: Набережная р. Свияги, 106, корп. 1, ауд. 703.


С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета, с авторефератом - на сайте вуза lsu.ru


Отзывы по данной работе просим направлять по адресу: 432000, г. Ульяновск, ул. Л.Толстого, д. 42, УлГУ, Управление научных исследований


Автореферат разослан «____» марта 2008 года


Ученый секретарь

диссертационного совета Волков М.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования. Задача о коммивояжёре – traveling salesman problem (TSP, ЗКВ) – является NP-сложной задачей дискретной оптимизации. Для нее не найдено, и возможно, не существует быстрых, полиномиальных алгоритмов. На графах она формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.

Поиск точных и приближённых способов решения задачи о коммивояжёре остается актуальным и с теоретической и с практической точек зрения. Результатом теоретических исследований¹ являются такие методы как:

• релаксации линейного программирования, релаксация Лагранжа, метод ветвей и отсечений, метод ветвей и границ (МВГ)
  
• распределенный метод ветвей и границ, решатели ЛП (задачи линейного программирования)
  
• эвристические: симулированный отжиг, генетические алгоритмы, цепная локальная оптимизация, поиск с запретами.
  

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

Программные коды, предназначенные для решения на оптимальность задачи о коммивояжёре, за последние 30 лет развились от решения задач размерности 100 до 10 000².

Среди приложений ЗКВ, встречающихся в литературе³, можно отметить:

• Оптимизацию в сетях
  
• Оптимизацию маршрутов
  
• Приложения в кристаллографии
  
• Управление роботами
  
• Обработку печатных плат
  
• Исследование ДНК
  

«Городами» в различных задачах могут выступать как физические объекты, так и процессы, и другие сущности.

Основными актуальными вопросами, связанными с решением ЗКВ, являются

• Быстрое точное решение асимметричных и симметричных ЗКВ больших размерностей
  
• Быстрое приближённое решение асимметричных и симметричных ЗКВ больших размерностей
  
• Разработка быстрых схем аппроксимации ЗКВ высокой точности
  

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

Цель работы. Целью настоящей работы является

• создание новых алгоритмов и программ для точного и приближённого решения асимметричной и симметричной задачи о коммивояжёре
  
• реализация и получение экспериментальных оценок эффективности схем аппроксимации ЗКВ
  
• улучшение качества тура и ускорение существующих программ решения ЗКВ
  
• поиск новых способов эффективного использования существующего программного обеспечения (ПО) по решению ЗКВ
  

Методы исследования. В исследовании использовались методы комбинаторного анализа, теории графов, дискретной оптимизации, линейного программирования, технологий распределённых вычислений.

Достоверность результатов обеспечивается строгостью постановок задач и использованием оттестированных компонентов программного обеспечения сторонних исследователей и разработчиков.

Научная новизна

Для достижения поставленных целей решены следующие задачи:

1. Разработан алгоритм решения асимметричной задачи о коммивояжёре (АЗКВ, ATSP) с помощью неэквивалентного преобразования к симметричной задаче о коммивояжёре (СЗКВ, STSP). Выработаны рекомендации по применению.
   
2. Реализованы и исследованы на эффективность алгоритмы распределенного метода ветвей и границ (МВГ) и полиномиальной аппроксимации СЗКВ PMCA⁴.
   
3. Реализован алгоритм усеченного МВГ ZHANG1⁵ с задачей о назначениях для АЗКВ. Получены оценки времени работы и качества тура. Выработаны рекомендации по применению.
   
4. Разработаны схемы экспериментов для исследования эффективности локальных отсечений в методах ветвей и отсечений (МВО, Branch and Cut)⁶ и эквивалентных преобразований в приближённых k-opt алгоритмах для АЗКВ. По результатам выработаны рекомендации по оптимизации времени и качества тура.
   
5. Экспериментально исследована эффективность отсечений ЗКВ для решения задачи маршрутизации (Vehicle Routing Problem – VRP). Подтверждена эффективность подхода.
   

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

Основные положения, выносимые на защиту:

1. Новый алгоритм решения асимметричной задачи о коммивояжёре путем неэквивалентного преобразования к симметричной задаче о коммивояжёре.
   
2. Программная реализация и экспериментальная оценка эффективности схемы полиномиальной аппроксимации симметричной задачи о коммивояжёре и распределенного метода ветвей и границ для симметричной задачи о коммивояжёре.
   
3. Методика повышения эффективности программ метода ветвей и отсечений, метода ветвей и границ с задачей о назначениях, и локальной оптимизации для асимметричной задачи о коммивояжёре.
   

Апробация работы.

Основные научные и практические результаты исследований по теме диссертации докладывались на

• VI Международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (г. Ульяновск, 2005)
  
• «XIII Всероссийской школе-коллоквиуме по стохастическим методам и VII Всероссийском симпозиуме по прикладной математике» (г. Йошкар-Ола, 2006)
  
• девятом международном семинаре «Дискретная математика и ее приложения» (г. Москва, 2007)
  

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

Публикации. По теме диссертации опубликовано 10 работ, в том числе 4 в ведущих рецензируемых журналах, рекомендованных ВАК.

Структура и объем диссертации. Общий объем диссертации 123 страницы. Диссертация состоит из введения, трех глав, заключения, списка используемой литературы из 89 наименований и одного приложения.


СОДЕРЖАНИЕ РАБОТЫ

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

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

В главах 2 и 3 изложен основной материал диссертационной работы. Глава 2 посвящена алгоритмам приближённого решения ЗКВ, а глава 3 – алгоритмам точного решения. Обе главы разбиты на параграфы, в каждом из которых рассматривается один из алгоритмов или аспектов решения ЗКВ. В конце каждого параграфа имеется заключение.

В §2.1 «Стабильная аппроксимация -ЗКВ» реализована одна из схем полиномиальной аппроксимации ЗКВ - PMCA. Новыми являются экспериментальные оценки качества тура, не встречавшиеся авторам в литературе.

Для ЗКВ в общем случае не существует полиномиальной схемы аппроксимации. Они созданы лишь для некоторых частных случаев, например, алгоритм Кристофидеса (Christofides) для симметричной ЗКВ с неравенством треугольника. Одним из возможных развитий подхода является разделение задачи в общей постановке на подклассы, и создание алгоритмов, эффективных, но возможно, не на всех подклассах. Громковичем (Hromkovic) и соавторами был предложен алгоритм стабильной аппроксимации для симметричной ЗКВ.

Основное утверждение, доказанное Громковичем, состоит в том, что для любого существует - аппроксимирующий алгоритм для -TSP, работающий за время

Была введена мера «треугольности» задачи, функция расстояния между задачами и разработан соответствующий алгоритм стабильной аппроксимации на основе алгоритма Кристофидеса. Основное отличие алгоритма PMCA от алгоритма Кристофидеса состоит в дополнительных шагах, позволяющих гарантировать, что при обходе деревьев и циклов суммарно будет сокращено не более четырех подряд идущих ребер. В нескольких опубликованных ими работах доказывается строгая оценка качества получаемого тура относительно введенной меры треугольности и времени работы алгоритма (приведенная в утверждении выше), но не приводится абсолютных оценок качества тура.

Целью данной части диссертационной работы было получение экспериментальных оценок эффективности алгоритма PMCA. Программная реализация алгоритма PMCA была произведена с использованием библиотеки оптимизации на графах и сетях GOBLIN, разработанной в Университете Аугсбурга.

В таблице 1 приведены результаты вычислительных экспериментов. В первом столбце указаны имена файлов с тестовыми матрицами. Во втором и третьих столбцах – качество полученного с помощью алгоритмов Christofides и PMCA тура в процентах относительно длины оптимального тура.


Таблица 1. Длина тура в процентах от оптимальной.

Название задачи	Christofides	PMCA
E1k.0-E1k.3	112%	113%
M1k.0-M1k.3	5468%	6952%

Эксперименты с разработанной реализацией PMCA показали, что

• Качество получаемого тура близко к качеству тура алгоритма Кристофидеса (менее чем на один процент хуже на евклидовых матрицах размера 1000 городов из набора DIMACS)
  
• Соответственно алгоритм представляет в основном теоретический интерес, а для приближённых решений лучше использовать алгоритмы локальной оптимизации
  

В §2.2 «Задача о назначениях для решения ЗКВ» реализован и экспериментально исследован усечённый метод ветвей и границ для асимметричной ЗКВ.

Одной из наиболее удачных для асимметричной ЗКВ релаксаций является задача о назначениях (ЗН), решением которой, в отличие от ЗКВ, может быть не один, а множество непересекающихся туров. В некоторых публикациях высказывалось предположение о зависимости качества ЗН-релаксации от разности границ Хелда-Карпа (ХК, HK) и задачи о назначениях (ЗН) для выбранного класса матриц. Что приводит к тому, что ЗН-релаксация оказывается стабильной, но с разными нижними границами: на некоторых классах дает очень хорошие приближения за малое время, а на некоторых даже с расширением пространства и времени поиска показывает слабые результаты.

Открытых кодов подобных реализаций авторами найдено не было. Целью данной части работы было создать программу, реализующую усечённый МВГ для АЗКВ в варианте, предложенном Жангом, исследовать временные характеристики и качество тура. Для выбора элемента ветвления и узла ветвления использовались правила Карпането-Тота, ветвление проводилось поиском в глубину, в памяти сохранялись вершины от корня до текущей, плюс все потомки ближайшей родительской вершины. Для решения ЗН использовался интерфейс библиотеки libhungarian без дополнительной оптимизации.

В таблице 2 приведены результаты вычислительных экспериментов на асимметричных матрицах классов coin, rtilt, disk, shop, super и amat размерности 316 и 1000 городов.

Эксперименты с использованием алгоритма ZHANG1 для решения задач АЗКВ шести разных классов из тестового набора ATSP Challenge, подтвердило наличие чёткой границы ZHANG1 для некоторых классов (тем больше, чем больше разница ХК-ЗН). Она изменяется с изменением размера задачи, но порядок остаётся постоянным. Так для трёх классов разность ХК-ZHANG1 составляла около десятой доли процента и менее, для оного класса – несколько десятых долей, а для двух оставшихся – более десяти процентов. Причём в первом случае разность с увеличением размера задачи уменьшалась, а в последнем (худшем) наоборот увеличивалась.

Простая оценка временной сложности алгоритма показала, что простой неоптимизированный вариант с использованием внешней библиотеки венгерского алгоритма с решением полной ЗН в каждом узле дерева МВГ получается со сложностью - , которую при использовании описанных в литературе оптимизаций можно снизить до .


Таблица 2. Качество тура и время работы ZHANG1

Класс Задач	Средняя разность ХК-ZHANG1 для задач в 316 городов, %	Средняя разность ХК-ZHANG1 для задач в 1000 городов, %	Среднее время , с	Среднее время , с	Оценка временной сложности
coin	10.62	12.34	54.83	3615.85	3.64
rtilt	10.78	12.81	109.82	8960.02	3.82
disk	0.21	0.03	10.14	364.34	3.11
shop	0.07	0.04	191.17	15642.32	3.82
super	0.24	0.22	26.65	1761.75	3.64
amat	0.16	0.04	6.34	372.16	3.54

В заключение можно сказать, что для классов АЗКВ с малой разницей границ ХК-ЗН релаксация к задаче о назначениях, например, варианты алгоритма Жанга, может быть очень успешной и находить туры высокого качества за время, сравнимое с алгоритмами локальной оптимизации.


В §2.3 «Решение близких к симметричным асимметричных ЗКВ необратимым преобразованием их к симметричным ЗКВ равного размера» разработан новый алгоритм приближённого решения АЗКВ с помощью неэквивалентного преобразования в СЗКВ того же размера.

АЗКВ является менее изученной, чем СЗКВ. Известно, что АЗКВ можно преобразовать к эквивалентной СЗКВ несколькими способами. Чаще всего для этого используют модификации 2-node и 3-node преобразователей, в которых удваивается или соответственно утраивается число вершин задачи, и также возможно, изменяются веса рёбер. Увеличение размеров матрицы априори приводит к увеличению пространства поиска, а значит и времени работы. Было решено попробовать использовать для решения АЗКВ неэквивалентные преобразования, сохраняющие размер матрицы.

Упоминания о псевдометрических, близких к симметричным матрицах, встречаются в литературе, например, в работах Б.Ф. Мельникова. Задачи такого класса могут соответствовать практическим задачам маршрутизации. Однако алгоритмов и экспериментальных оценок неэквивалентных преобразований в литературе не встречалось.

Основным вопросом, исследовавшимся в данной части работы, было качество получаемого тура. Схема предложенного алгоритма такова:


Вход: АЗКВ задача.

Выход: тур

1. Преобразовать АЗКВ в неэквивалентную СЗКВ того же размера

2. Решить полученную СЗКВ

3. Посчитать стоимость полученного тура на АЗКВ матрице.


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

• неэквивалентное преобразование состояло в замене длин пары входящих и исходящих дуг на их среднее арифметическое,
  
• в качестве оптимизационного алгоритма использовался конкорд (concorde) – оптимизационный код, разработанный в Принстонском университете.
  

Алгоритм тестировался на общедоступных и широко известных матрицах из набора DIMACS TSP challenge.

Для оптимального решения получаемой неэквивалентной СЗКВ использовался код concorde, который, как и большинство программ для решения ЗКВ, является Las-Vegas алгоритмом, т.е. при разных запусках всегда выдает оптимальные, но возможно, разные туры. Т.к. в нашем алгоритме стоимость полученного тура рассчитывалась по изначальной матрице АЗКВ, то стоимости этих туров соответственно получались различными. Было проведено по два запуска на задачах разных классов АЗКВ, входивших в общедоступный тестовый набор соревнования по решению ЗКВ – DIMACS.

Размеры исследовавшихся задач – 316 и 1000 городов, определяются тем, что в данной схеме использовался конкорд. В случае использования, например, алгоритма приближённого решения LKH размеры можно увеличить.

Приемлемые по качеству тура результаты были получены для класса задач coin, у которого велика симметричность матрицы. Качество тура и время работы сравнимо с лучшими эвристиками локального поиска – I3opt, IKP (Каннелакис-Пападимитриу) и LK Helsgaun (LKH), уступая двум последним по качеству тура.

Дальнейшие исследования возможны в

• Использовании нового преобразователя на первом шаге алгоритма
  
• Использовании нового решателя на втором шаге алгоритма
  
• Выборе специфичных близких к симметричным асимметричных матриц
  

Вывод: предложенный новый алгоритм решения "близких к симметричным" АЗКВ путем неэквивалентного преобразования в СЗКВ равного размера и последующего решения с помощью эффективных СЗКВ инструментов может сравниться с лучшими из приближённых АЗКВ алгоритмов по времени работы и качеству тура.


В §2.4 «Локальный поиск LKH для асимметричной ЗКВ» исследуются вопросы улучшения алгоритма локального поиска LKH для асимметричных ЗКВ.

Наиболее успешным алгоритмом приближённого решения ЗКВ является алгоритм цепного локального поиска Lin Kernighan, а лучшей его реализацией считается модифицированный вариант - LKH, предложенный Хелсгауном (Helsgaun). Основные его отличия заключаются в подборе используемых в оптимизации рёбер, используя -меру расстояния, подсчитываемую с помощью релаксации на 1-деревьях; и 4-opt, 5-opt шаги локальной оптимизации.

Код Хелсгауна также может решать асимметричные задачи. Для этого используется внутренний 2-node преобразователь с использованием больших отрицательных и положительных констант без модификации весов остальных ребер. В литературе не встречалось обоснования использования именно такого преобразователя, и экспериментов с другими эквивалентными преобразователями, в отличие, например, от обзоров конкорда.

Задачей данной части работы было исследование влияния разных 2-node и 3-node эквивалентных преобразователей АЗКВ в СЗКВ, и внешних параметров кода LKH на время и качество получаемого LKH решения. Новым является использование нескольких различных преобразователей и исследования их влияния на окончательное качество тура и время работы алгоритма. Коды самих преобразователей не сложны, и большая часть из них описана в литературе. Для сбора дополнительных статистических данных код LKH был несколько модифицирован.

Для тестирования использовались 3 разных преобразователя и изменения четырёх параметров конфигурационных файлов LKH, значения по умолчанию которых зависят от размера матрицы. Преобразователи отличались размером результирующей матрицы (2-node преобразователи увеличивали размер вдвое, а 3-node – в три раза), использованием/не использованием ребер отрицательного веса (которые являются неприемлемыми для некоторых алгоритмов и реализаций) и характером преобразования основного множества рёбер (веса либо остаются без изменений, либо увеличиваются на большую положительную константу). Вычислительные эксперименты проводились с матрицами размером в 316 и 1000 городов.

Кроме использования разных эквивалентных преобразователей , при проведении экспериментов изменялись четыре параметра конфигурации LKH. Эти четыре параметра были выделены среди остальных потому, что их значения по умолчанию зависят от размера задачи. Внутренний 2-node преобразователь LKH при подготовке ребер-кандидатов для оптимального тура и прочих операциях учитывает тот факт, что размер задачи удвоен по сравнению с оригинальной асимметричной. Однако при использовании внешних преобразователей LKH нельзя указать размер «оригинальной» асимметричной задачи, поэтому при тестировании внешних 2-node и 3-node преобразователей значения следующих четырёх параметров задавались в конфигурационном файле LKH в явном виде:

1. MAX_TRIALS: максимальное число попыток (trial) при одном запуске (run). Значение по умолчанию = DIMENSION
   
2. EXCESS: максимальное допустимое для ребра -значение устанавливается в EXCESS, умноженное на абсолютное значение нижней границы результирующего тура, определяемую с помощью подъема (ascent) 1-дерева. Значение по умолчанию =
   
3. MAX_SWAPS: определяет максимальное число обменов (swaps, flips) при поиске улучшения в туре. Значение по умолчанию = DIMENSION.
   
4. INITIAL_PERIOD = Длительность первого периода при подъёме (ascent) 1-дерева. Значение по умолчанию = (но минимум 100)
   

Альтернативный 2-node преобразователь, изменяющий веса всех рёбер («ЗКВ и вариации», глава4), который хорошо зарекомендовал себя при решении асимметричных задач на оптимальность с помощью concorde, при использовании с LKH привел к существенному ухудшению качества тура и увеличению времени работы. Это можно объяснить тем, что задача, преобразованная с его помощью, получалась более близкой к метрической, относительная разница между значениями весов рёбер уменьшалась, и как следствие, подбор подходящих для оптимизации ребер затруднялся. Результаты вычислительных экспериментов с этим преобразователем не приводятся в силу низкого получаемого с его помощью качества тура и большого времени работы, т.е. малой практической интересности.

Дальнейшее описание относится к экспериментам со встроенным 2-node преобразователем и 3-node преобразователем из набора DIMACS ATSP Challenge, распространявшегося общедоступно в составе тестового пакета. 3-node преобразователь использовался с двумя наборами указанных выше четырех параметров LKH. В первом наборе (далее он обозначается 3-node-без-параметров) значения параметров в явном виде не задавались, и соответственно, получали значения по умолчанию, соответствующие утроенному размеру задач. Во втором случае (далее он обозначается 3-node-с-параметрами) значения параметров рассчитывались по значению DIMENSION, равному размерности оригинальной асимметричной задачи.

Анализируя экспериментальные данные, полученные для матриц размера 316 можно заметить, что

• Качество тура в основном лучше у эталонного встроенного 2-node преобразователя. У 3-node-без параметров иногда хуже. У 3-node-с-параметрами чаще хуже.
  
• Среднее время решения у 2-node обычно больше, чему у 3-node-с-параметрами, у 3-node-без-параметров время может быть и больше и меньше 2-node.
  
• Средний размер множества ребер-кандидатов больше у 2-node, у 3-node-с-параметрами - меньше, у 3-node-без-параметров ещё меньше. Т.е. при увеличении размера эквивалентной матрицы, использование -меры при построении списка ребер-кандидатов на улучшение тура позволяет сократить область перебора и таким образом ускорить поиск, как если бы матрица была меньшего размера.
  

Результаты экспериментов с матрицами в 1000 городов отличаются от результатов для матриц размера 316:

1. Качество тура на некоторых матрицах и у 3-node-без-параметров и у 3-node-с-параметрами лучше, чем у встроенного 2-node преобразователя
   
2. Среднее время работы 3-node-с-параметрами меньше на 20%, чем для 2-node, однако для 3-node-без-параметров время стабильно больше, чем для 2-node
   

Резюмируя результаты анализа экспериментальных данных, можно сказать, что

1. LKH обладает большей по сравнению с Branch and Cut кодом (метод ветвей и отсечений) concorde чувствительностью к эквивалентному преобразователю, используемому для преобразования АЗКВ к эквивалентной СЗКВ
   
2. использование -меры близости рёбер позволяет эффективно использовать 3-node преобразователи. Список ребер-кандидатов при увеличении размера задачи уменьшается, но при этом качество тура остается приемлемым, и в некоторых случаях даже улучшается, а время работы алгоритма может быть меньше, чем при использовании 2-node преобразователей
   
3. встроенный 2-node преобразователь предпочтителен на матрицах размера 316. В этом случае почти всегда находится оптимальное решение при использовании любого преобразователя. Но время решения при использовании 3-node преобразователей, на удивление, оказалось часто меньше, чем у встроенного 2-node, однако 3-node иногда давали не оптимальные туры.
   
4. при решении же матриц размера 1000, на некоторых классах, например coin, преобразователь 3-node, со значениями параметров конфигурационного файла, соответствующих размеру 2-node, выдавал лучшие, чем 2-node, туры и за меньшее время.
   

Вывод: использование различных типов эквивалентных преобразователей АЗКВ в СЗКВ, в частности 3-node преобразователей, при приближённом решении с помощью ПО LKH, на матрицах большого размера может дать улучшение решения и даже одновременное уменьшение времени работы программы.

В главе 3 исследуются алгоритмы точного решения ЗКВ.

В §3.1 «Распределенный Метод Ветвей и Границ» построена распределенная реализация алгоритма ветвей и границ для СЗКВ. Для решения ЗКВ больших размерностей (на 2008 год это десятки тысяч городов) часто используют параллельные алгоритмы Ветвей и Отсечений (Branch and Cut). Примерами могут служить программы Concorde и SYMPHONY (из проекта COIN-OR). Однако для базовых алгоритмов МВГ, например, описанных в работе Гудмана⁷, оценок эффективности распараллеливания алгоритмов в литературе не встречалось.

Несмотря на то, что с практической точки зрения такой алгоритм, использующий для оценок снизу только несложные эквивалентные преобразования матрицы, может быть не интересен для стандартных классов задач, в частных случаях он может быть применим. Например, как в описываемом в «ЗКВ и вариациях» в десятой главе случае, когда исследователям было необходимо решать большое количество матриц размерности 27, они остановили выбор на специализированном варианте метода ветвей и границ.

При создании параллельной среды использовалась библиотека PVM, клиент-серверная модель crowd computation, и следующие критерии выбора элемента ветвления и матрицы для ветвления:

1. вершина для ветвления выбирается первая с наименьшим значением границы.
   
2. ребро для ветвления выбирается по наименьшему количеству нулей в строке и столбце вершины.
   
3. минимальный размер матрицы для ветвления - 3.
   

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

Алгоритм PVMSyncSolverClient:

Вход: Вершина МВГ и сообщения о новых верхних границах от PVMSyncSolverServer

Выход: Вершина МВГ с лучшим (наименьшим) значением длины тура

1. 
   Пока очередь вершин МВГ не пуста
   
2. Проверить сообщения от сервера
   
3. Если пришла новая верхняя граница – обновить её
   
4. Взять вершину с наименьшей границей из очереди вершин МВГ
   
5. Если её граница больше наилучшего решения – выйти
   
6. Если её размер меньше 3
   
7. Решить её на оптимальность
   
8. Если её решение лучше текущего лучшего решения
   
9. Запомнить новое лучшее решение
   
10. Послать его значение и его тур на сервер
    
11. Иначе
    
12. Ветвить её на две вершины и добавить их в очередь вершин МВГ
    
13. Вернуть лучшее решение
    

Алгоритм PVMSyncSolverServer:

Вход: Матрица ЗКВ, число клиентов N

Выход: Оптимальный тур

1. 
   Ветвить матрицу до получения N вершин МВГ. Получить оценку длины тура сверху.
   
2. Запустить N клиентов PVMSyncSolverClient. Каждому раздать свою вершину МВГ и оценку сверху.
   
3. Пока есть не завершившие работу клиенты
   
4. Ждать сообщения
   
5. Если сообщение содержит новое лучшее решение
   
6. Запомнить новое лучшее решение.
   
7. Разослать новое лучшее решение всем клиентам
   
8. Вернуть лучшее решение
   

На рисунке 1 показаны результаты вычислительных экспериментов с тремя решателями. Эталонный изображен горизонтальной линией.




Рис 1. Среднее время решения в зависимости от числа клиентов (для SimpleSolver оно всегда равно 1). Решатели SimpleSolver (эталон) , PVMSimpleSolver (увеличение времени), PVMSyncSolver (уменьшение времени)


Эксперименты, проведенные с двумя разработанными распределёнными вариантами МВГ в сети из пяти рабочих станций на матрицах размерности до 30, показали, что рассматриваемый вариант МВГ для СЗКВ может быть успешно распараллелен при использовании предложенного алгоритма синхронизации лучшего локального решения. В результате увеличения числа машин с 1 до 5 удалось уменьшить время решения в 3,08 раза, что в 2,36 раза быстрее базового непараллельного решателя. Предложенный подход к получению распределенных вариантов МВГ может быть использован для построения практически применимых вариантов путем учета специфики узких классов ЗКВ (метрических с неравенством треугольника и т.п.), либо разработки схемы распределённого приближённого (в данной работе рассматривались только точные) решения, если целевой алгоритм предназначен для решения широкого класса задач.


В §3.2 «Исследование оптимизации использования локальных отсечений CONCORDE» рассматривается проблема оптимального способа применения локальных отсечений в программе конкорд (concorde) – эффективной реализации метода ветвей и отсечений для ЗКВ.

Наиболее успешным подходом решения ЗКВ на оптимальность (точного решения) на данный момент является использование методов ветвей и отсечений линейного программирования. Лучшим кодом является concorde.

В исследовании решения на оптимальность АЗКВ, приведенном Фишетти и соавторами в главе 4 «ЗКВ и вариации», указывается, что один из внешних параметров конкорда – максимальный размер множества вершин для локальных отсечений, существенным образом влияет на время решения АЗКВ и, возможно, позволяет учитывать специфичную для асимметричных ЗКВ структуру матрицы.

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

Задачей данной части работы было исследование влияния размера матрицы, структуры матрицы («асимметричности») и внешних параметров конкорда, задающих режим работы локальных отсечений, на время решения.

Новой в данной части работы является разработанная схема экспериментов. Для их проведения были разработаны вспомогательные программы – конвертирования матриц в разные форматы, конвертирования асимметричных матриц в эквивалентные симметричные матрицы.

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


Таблица 3. Разность времен –C 0 и –C 16 для матрицы C1k.0 (в секундах)

Rand seed (2-ой столбец) / Размер подматрицы (1-ая строка)		500	600	700	800	900	1000 (полный размер)
1й запуск, с	1189364467	7,85	-5,46	1,55	1,29	38	72,1
2й запуск, с	1189367225	0,62	0,62	6,53	5,05	31,41	-11,84
3й запуск, с	1189367879	-2,49	-6,46	16,88	10,75	12,78	26,21
4й запуск, с	1189410979	0,43	-8,47	8,77	4,79	20,21	78,59
5й запуск, с	1189416458	-0,15	-4,09	-4,73	7,36	44,83	39,14
Среднее разности, с		1,25	-4,77	5,80	5,85	29,45	40,84
Отношение среднего разности к среднему -C 0, 1		0,13	-0,16	0,25	0,32	0,41	0,34
Отношение отклонения разности к среднему -C 0, 1		0,41	0,11	0,35	0,19	0,18	0,30

Эксперименты с асимметричными и симметричными матрицами, с тремя различными видами эквивалентных преобразований АЗКВ в СЗКВ и различными значениями параметров, задающих режим работы конкорда с локальными отсечениями, показали, что

1. Параметр –C, задающий объемы генерации local cuts (локальных отсечений) конкордом, действительно существенно влияет на время работы. В целом значение по умолчанию - 16, как показали эксперименты, является оптимальным для матриц размера 1000 и выше.
   
2. Параметр –s (rand seed) также существенно влияет на время работы (пожалуй, даже еще сильнее, чем –C в некоторых случаях). Это, например, не было учтено в работе Фишетти.
   
3. Параметр –C оказывает схожее влияние, как при решении симметричных матриц, так и асимметричных. Особых отличий не обнаружено. Пример - таблица 3.
   
4. Влияние параметра –C скорее зависит от размера матрицы, нежели от ее происхождения (асимметричности). Отличия между разными преобразователями АЗКВСЗКВ есть, но в целом результаты похожи. Зависимости между влиянием –C на подматрицу и на всю матрицу конкретной задачи не обнаружено.
   

В §3.3 «ЗКВ как модель задачи дискретной оптимизации на примере задачи о маршрутизации (VRP)» исследуется вопрос применения программных кодов ЗКВ для решения других задач дискретной оптимизации.

Как отмечалось во введении (аннотации), методы решения ЗКВ могут быть использованы для решения других задач дискретной оптимизации. Т.е. ЗКВ часто можно рассматривать как общую модель задач дискретной оптимизации. В рамках диссертационной работы был исследован вопрос использования программного кода генерации отсечений ЗКВ из программы конкорд, для решения VRP – задачи маршрутизации. Она отличается от ЗКВ наличием не одного, а многих транспортных средств ограниченной вместимости, доставляющих в каждый город фиксированное количество товара. С полиэдральной точки зрения политоп VRP содержится в политопе ЗКВ, но с практической стороны эффективность может зависеть от многих факторов, например, стартовое решение может изначально находиться в ЗКВ политопе.

Практическое исследование трёх типов ЗКВ отсечений: subtour (подтур), comb (гребень), blossom (цвет) из библиотеки конкорда в приложении VRP, входящем в комплекс SYMPHONY составило данную часть экспериментальной работы. Одной из наиболее трудоёмких частей работы был выбор приложения. Рассматривалось несколько фреймворков, реализующих методы ветвей и границ: ABACUS, SYMPHONY, concorde. У каждого из них есть свои плюсы и минусы. Выбор был сделан в пользу SYMPHONY – в рамках этого проекта под началом COIN-OR (проекта по созданию открытого программного обеспечения для исследования операций) сторонними авторами уже было создано два приложения, использующих код конкорда – CNRP (для задачи Capacitated Node Routing Problem) и VRP (Vehicle Routing Problem). Для проведения экспериментов был выбран решатель VRP, потому что для CNRP нет общепринятых схем тестирования и наборов задач. Соответственно труднее оценивать результаты и эффективность тех или иных подходов.

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

Эксперименты на матрицах из набора VRPLIB показали, что одновременное использование трёх типов отсечений конкорда позволяет получить сокращение времени решения более чем на десять процентов на приблизительно десяти процентах матриц. При этом число отсечений в пулах оказывается меньшим, чем без использования ЗКВ отсечений.

Далее на отобранных задачах были проведены дополнительные эксперименты. Как показали результаты вычислений, базовый алгоритм VRP, не использующий ЗКВ отсечения, является весьма стабильным относительно инициализирующего значения генератора псевдослучайных последовательностей, используемого внутри VRP. Результаты по времени для разных запусков отличались лишь на проценты. Однако, чтобы повысить воспроизводимость результатов в конфигурационные файлы VRP был добавлен параметр rand_seed, и все последующие тесты проводились со значением rand_seed 1196638233, соответствующим системному времени на момент первого теста.

Вторая серия экспериментов имела целью исследование всех комбинаций трех ЗКВ отсечений на время решения VRP. Для каждой комбинации ЗКВ отсечений и каждой из отобранных на первом этапе матриц, чтобы учесть вероятностный характер работы concorde, было проведено по три запуска, как и в работе авторов VRP.

Использование разных комбинаций отсечений может привести как к увеличению времени работы, так и к уменьшению, но в большинстве случаев при получении положительных результатов для полного набора отсечений, частичные комбинации также приводят к уменьшению времени работы. Основным фактором, влияющим на стабильность результатов, является архитектура генератора отсечений. В проекте VRP используется concorde, генерирующий отсечения с использованием генератора псевдослучайных последовательностей, т.е. Лас-Вегас алгоритм, результаты работы которого могут значительно изменяться при изменении стартового значения генератора псевдослучайных последовательностей.


Таблица 4. Средние значения времени решения по трем запускам VRP, в секундах (жирным подчеркнутым шрифтом отмечены комбинации, в которых было получено уменьшение времени работы). Столбцы 0-7 соответствуют восьми различным подмножества множества трех отсечений ЗКВ. Столбец 0 – эталонный, без использования отсечений ЗКВ.

Название матрицы	0	1	2	3	4	5	6	7
A-n36-k5	37,45	37,18	23,24	24,28	37,03	37,37	30,62	26,13
B-n38-k6	5,21	4,95	5,73	4,65	4,72	5,33	3,98	3,60
B-n43-k6	54,49	53,86	65,72	54,89	53,59	54,25	61,10	53,07
B-n51-k7	48,51	48,29	41,73	41,61	48,81	48,72	41,17	41,49
P-n40-k5	5,54	5,55	3,62	3,57	5,41	5,41	3,58	3,50
P-n45-k5	23,58	23,14	19,95	15,32	23,78	23,75	17,98	14,62
E-n51-k5	11,00	10,91	8,97	8,79	10,66	10,48	8,88	8,88
hk-n48-k4	20,68	20,68	14,09	13,19	20,70	20,71	17,16	12,97

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


В §3.4 «Комплекс программ» описывается разработанный комплекс программ.

Для повышения воспроизводимости результатов, сохранения разработанных кодов и ускорения разработки была выбрана модель open source (открытые исходные тексты), что является тенденцией в задачах исследования операций⁸.

Для хранения исходных текстов был создан репозитарий Subversion. Среди использованных в экспериментах open source проектов можно отметить: concorde, LKH (версия алгоритма LK – Lin Kernighan, разработанная Хелсгауном (Helsgaun)), GOBLIN, Symphony.

Разработанный комплекс программ зарегистрирован в Отраслевом фонде алгоритмов и программ.

На рисунке 2 приведена схема высокого уровня.

Большая часть нового и использованного кода написана на языках ANSI C, C++. Библиотека общих классов включает классы работы с матрицами, турами, перестановками, путями и вершинами метода ветвей и границ. Основная часть новых реализаций алгоритмов решения закодирована в виде решателей – Solver. Solver принимает на вход обработанную при необходимости матрицу ЗКВ и возвращает результирующий тур и/или его стоимость. При необходимости тур после этого может быть специальным образом обработан.

Комплекс включает несколько решателей для проведения вычислительных экспериментов по точному и приближённому решению ЗКВ. Основное




Рис. 2. Комплекс программ


внимание уделялось решению асимметричной ЗКВ как менее изученной. Были исследованы некоторые новые подходы к использованию зарекомендовавших себя лидеров – concorde и LKH, а также подходы, для которых в литературе не было встречено экспериментальных оценок.


ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Предложен, реализован и экспериментально исследован новый алгоритм решения асимметричной задачи о коммивояжёре путем неэквивалентного преобразования к симметричной задаче о коммивояжёре.
   
2. Выполнена программная реализация и экспериментальная оценка эффективности схемы полиномиальной аппроксимации симметричной задачи о коммивояжёре и распределённого метода ветвей и границ для симметричной задачи о коммивояжёре.
   
3. Предложена методика повышения эффективности программ метода ветвей и отсечений, метода ветвей и границ с задачей о назначениях, и локальной оптимизации для асимметричной задачи о коммивояжёре. Реализованы соответствующие алгоритмы
   

Для алгоритмов точного решения уменьшено время работы (увеличена скорость решения). Для алгоритмов приближённого решения уменьшено время работы и улучшена (уменьшена) длина результирующего тура. Для некоторых алгоритмов, в том числе для полиномиальной схемы аппроксимации симметричной задачи о коммивояжёре, впервые получены экспериментальные оценки качества тура и времени работы. Созданный комплекс программ зарегистрирован в Отраслевом фонде алгоритмов и программ.


Публикации в журналах, входящих в список ВАК

1. Ляликов В.Н. Получение решений близких к симметричным ATSP преобразованием к STSP.// Обозрение прикладной и промышленной математики, т. 13, вып. 6. М.: ОПиПМ. – 2006. – с.1094-1095.

2. Воденин Д.Р., Ляликов В.Н. Эвристика Жанга для асимметричной задачи коммивояжера.// Обозрение прикладной и промышленной математики, т. 13, вып. 6. М.: ОПиПМ. – 2006. – с.1062-1063.

3. Ляликов В.Н. Неравенства задачи о коммивояжере для задачи маршрутизации.// Обозрение прикладной и промышленной математики, т. 15, вып. 1. М.: ОПиПМ. – 2008. – с.154.

4. Ляликов В.Н. Оптимизация локального поиска для асимметричной задачи о коммивояжере.// Обозрение прикладной и промышленной математики, т. 15, вып. 1. М.: ОПиПМ. – 2008. – с.154-155.

Публикации в прочих изданиях

5. Воденин Д.Р., Ляликов В.Н. Тестирование свободных пакетов программ решения задачи целочисленного линейного программирования//VI Международная конференция “Математическое моделирование физических, экономических, технических, социальных систем и процессов” Ульяновск: УлГУ – 2005. – с.33-35.

6. Ляликов В.Н. Распределенный метод ветвей и границ для задачи коммивояжера//Сборник статей II Международной научно-технической конференции "Аналитические и численные методы моделирования естественнонаучных и социальных проблем", Пенза: ПГУ - 2007. -с.165-167.

7. Ляликов В.Н. Экспериментальное исследование стабильной аппроксимации симметричной дельта-задачи коммивояжера.//Сборник статей II Международной научно-технической конференции "Аналитические и численные методы моделирования естественнонаучных и социальных проблем", Пенза: ПГУ - 2007. -с.167-168.

8. Ляликов В.Н. Методы линейного программирования для решения асимметричной задачи коммивояжера// Материалы конференции XV Туполевские чтения, том II, Казань: КГТУ – 2007. –с. 87-88.

9. Ляликов В.Н. О локальных отсечениях для задачи о коммивояжере//Материалы конференции «Информационно-математические технологии в экономике, технике и образовании», Екатеринбург: УПИ – 2007. –с. 34-36.

10. Ляликов В.Н. Программный комплекс для проведения вычислительных экспериментов с целью исследования методов решения симметричной и асимметричной задачи коммивояжера.//Москва: ВНТИЦ. Программное и информационное обеспечение поддержки научно-исследовательских работ, 2007. ЕСПД 03524577.02165-01

1 A. P. Punnen “The traveling salesman problem: applications, formulations and variations”, "The traveling salesman problem and its variations" edited by G. Gutin, A. Punnen - Dordrecht: Kluwer Academic Publishers, 2002, pp. 1-28. (сборник далее как «ЗКВ и вариации»).

2 A. Lodi, A. P. Punnen “TSP software”, "The traveling salesman problem and its variations" edited by G. Gutin, A. Punnen - Dordrecht: Kluwer Academic Publishers, 2002, pp. 737-749

3 Helsgaun K., “An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic”, DATALOGISKE SKRIFTER (Writings on Computer Science), No. 81, Roskilde University, 1998.

4 ^ Hans-Joachim Bockenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, and Walter Unger “Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem” Theoretical Computer Science 285, 2002, pp. 3-24

5 ^ Weixiong Zhang, “Truncated Branch-and-Bound: A Case Study on the Asymmetric TSP”, in Proc. AAAI 1993 Spring Symp. AI and NP-Hard Problems, Stanford, CA, 1993, pp. 160-166

6 ^ D. Naddef “Polyhedral theory and branchand-cut algorithms for the symmetric TSP”, "The traveling salesman problem and its variations" edited by G. Gutin, A. Punnen - Dordrecht: Kluwer Academic Publishers, 2002, pp. 29-116.

7 С.Гудман, С. Хидетниеми «Введение в разработку и анализ алгоритмов» М.: Мир, 1981.

8 R. Lougee-Heimer, The Common Optimization INterface for Operations Research: Promoting open-source software in the operations research community, IBM Journal of Research and Development, volume 47, Number 1, 2003, Mathematical Sciences at 40