автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Комплекс программ для исследования методов решения задачи о коммивояжере

На правах рукописи

003 166334

Ляликов Вадим. Николаевич

КОМПЛЕКС ПРОГРАММ ДЛЯ ИССЛЕДОВАНИЯ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ О КОММИВОЯЖЕРЕ

05 13 18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Ульяновск - 2008

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

Научный руководитель

кандидат физико-математических наук, доцент Воденин Дмитрий Ростиславович

Официальные оппоненты

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

Мельников Борис Феликсович доктор технических наук, профессор Смагин Алексей Аркадьевич

Ведущая организация

ГОУ ВПО Ульяновский государственный технический университет

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

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

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

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

Ученый секретарь диссертационного сове i а

Волков М А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность исследования. Задача о коммивояжере - traveling salesman problem (TSF, 3KB) - является NP-сложной задачей дискретной оптимизации Для нее не найдено, и возможно, не существует быстрых, полиномиальных алгоритмов На графах она формулируется следующим образом требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе Т е выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути

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

• релаксации линейного программирования, релаксация Лагранжа, метод ветвей и отсечений, меюд ветвей и 1раниц (МВГ)

• распределенный метод ветвей и границ, решатели ЛП (задачи линейного программирования)

• эвристические симулированный отжиг, генетические алгоритмы, цепная локальная оптимизация, поиск с запретами

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

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

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

• Оптимизацию в сетях

• Оптимизацию маршрутов

• Приложения в кристаллографии

• Управление роботами

• Обработку печатных плат

• Исследование ДНК

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

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

• Быстрое точное решение асимметричных и симметричных ЗКВ больших размерностей

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

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

2 A Lodi А Р Punnen ' TSP software" "The traveling salesman problem and its variations" edited by G Gutm A Punnen - Dordrecht Kluwer Academic Publishers, 2002, pp 737-749

3 Helsgaun К An Lffective implementation ol the L'n-Kermghan Traveling Salesman Heuristic ', DATAI OGISKE SKRIFTFR (Writings on Computer Science), N'o 81, Roskilde University, 1998

3

• Разработка быстрых схем аппроксимации ЗКВ высокой точности Диссертация посвящена новым подходам к решению этих задач

разработке новых алгоритмов и оптимизации существующих решений Цель работы. Целью настоящей работы является

• создание новых алгоритмов и программ для точного и приближенного решения асимметричной и симметричной задачи о коммивояжере

• реализация и получение экспериментальных оценок эффективности схем аппроксимации ЗКВ

• улучшение качества тура и ускорение существующих программ решения ЗКВ

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

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

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

1 Разработан алгоритм решения асимметричной задачи о коммивояжере (АЗКВ, ATSP) с помощью неэквивалентного преобразования к симметричной задаче о коммивояжере (СЗКВ, STSP) Выработаны рекомендации по применению

2 Реализованы и исследованы на эффективность алгоритмы распределенного метода ветвей и границ (МВГ) и полиномиальной аппроксимации СЗКВ РМСА4

3 Реализован алгоритм усеченного МВГ ZHANG I3 с задачей о назначениях для АЗКВ Получены оценки времени работы и качества тура Выработаны рекомендации по применению

4 Разработаны схемы экспериментов для исследования эффективности локальных отсечений в методах ветвей и отсечений (МВО, Branch and Cut)6 и эквивалентных преобразований в приближенных k-opt алгоритмах для АЗКВ По результатам выработаны рекомендации по оптимизации времени и качества тура

5 Экспериментально исследована эффективность отсечений ЗКВ для решения задачи маршрутизации (Vehicle Routing Problem - VRP) Подтверждена эффективность подхода

4 Hans-Joachim Bockenhaucr, Juraj Hromkovic, Ralf Klasing, Sebabtian 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

Weixiong 7hang, Truncated Branch-and-Bound A Case Study on the Asymmetric TSP", in P-oc AAA1 1993 Spring Symp A1 and NP-Hard Problems, Stanford, CA 1993, pp 160-166

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

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

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

2 Программная реализация и экспериментальная оценка эффективности схемы полиномиальной аппроксимации симметричной задачи о коммивояжере и распределенного метода ветвей и границ для симметричной задачи о коммивояжере

3 Методика повышения эффективности программ метода ветвей и отсечений, метода ветвей и границ с задачей о назначениях, и локальной оптимизации для асимметричной задачи о коммивояжере

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

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

• VI Международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (г Ульяновск, 2005)

• «XIII Всероссийской школе-коллоквиуме по стохастическим методам и VII Всероссийском симпозиуме по прикладной математике» (г Йошкар-Ола, 2006)

• девятом международном семинаре «Дискретная математика и ее приложения» (г Москва, 2007)

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

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

СОДЕРЖАНИЕ РАБОТЫ Во введении приводится общий обзор диссертационной работы, план следующих глав, связывающие их элементы

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

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

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

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

Основное утверждение, доказанное Громковичем, состоит в том, что для

любого fi е существует аппроксимирующий алгоритм для д^^-TSP,

работающий за время О(и')

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

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

В таблице 1 приведены результаты вычислительных экспериментов В первом столбце указаны имена файлов с тестовыми матрицами Во втором и

третьих столбцах - качес1во полученного с помощью алгоритмов ОтчШМеч и РМСА тура в процентах относительно длины оптимально! о тура

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

Название задачи Chnstofides РМСА

Elk 0-EJLk 3 112% 113%

Mlk 0-Mlk 3 5468% 6952%

Эксперименты с разработанной реализацией РМСА показали, чго

• Качество получаемого тура близко к качеству тура алгоритма Крисюфидеса (менее чем на один процент хуже на евклидовых матрицах размера ] ООО городов из набора DIMACS)

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

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

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

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

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

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

составляла около десятой доли процента и менее, для оного класса - несколько десятых долей а для двух оставшихся - более десяти процентов Причем в первом случае разность с увеличением размера задачи уменьшалась, а в последнем (худшем) наоборот увеличивалась

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

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

Класс Задач Средняя разность ХК-гНАКС1 для задач в 316 городов, % Средняя разность ХК-2НАЫС1 для задач в 1000 городов, % Среднее время г316 ' с Среднее время 'lOOO > с Оценка временной сложности 1п(/1(КЮ 1п(1000/316)

com 10 62 12 34 54 83 3615 85! 3 64 1

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 016 0 04 6 34 372 16 3 54

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

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

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

8

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

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

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

Вход: АЗКВ задача Выход: тур

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

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

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

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

• неэквивалентное преобразование состояло в замене длин пары входящих и исходящих дуг на их среднее арифметическое,

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

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

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

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

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

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

• Использовании нового преобразователя на первом шаге алгоритма

• Использовании нового решателя на втором шаге алгоритма

• Выборе специфичных близких к симметричным асимметричных матриц

Вывод предложенный новый алгоритм решения "близких к симметричным"

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

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

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

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

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

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

Кроме использования разных эквивалентных преобразователей АЗКВ -> СЗКВ, при проведении экспериментов изменялись четыре параметра конфигурации LKH Эти четыре параметра были выделены среди остальных

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

1 MAX_TRIALS максимальное число попыток (trial) при одном запуске

(run) Значение по умолчанию = DIMENSION 2. EXCESS максимальное допустимое для ребра «-значение устанавливается в EXCESS, умноженное на абсолютное значение нижней границы результирующего тура, определяемую с помощью

подъема (ascent) 1-дерева Значение по умолчанию =-—-

v ' ^ : DIMENSION

3 MAX SWAPS. определяет максимальное число обменов (swaps, flips) при поиске улучшения в туре Значение по умолчанию = DIMENSION

4 INITIAL PERIOD = Длительность первого периода при подъеме (ascent)

г, DIMENSION , 1ПАЧ

1-дерева Значение по умолчанию =---(но минимум 100)

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

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

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

• Качество тура в основном лучше у эталонного встроенного 2-nodc преобразователя У З-поёс-без параметров иногда хуже У 3-node-c-параметрами чаще хуже

• Среднее время решения у 2-node обычно больше, чему у 3-node-c-параметрами, у 3-node-6e3-napaMeTpoB время может быть и больше и меньше 2-node

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

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

1 Качество тура на некоторых матрицах и у 3-node-6e3-napaMeTpoe и у 3-node-c-параметрами лучше, чем у встроенного 2-node преобразователя

2 Среднее время работы З-поде-с-параметрами меньше на 20%, чем для 2-node, однако для 3-node-6e3-napaMeTpoe время стабильно больше, чем для 2-node

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

1 LKH обладает большей по сравнению с Branch and Cut кодом (метод ветвей и отсечений) concorde чувствительностью к эквивалентному преобразователю, используемому для преобразования АЗКВ к эквивалентной СЗКВ

2 использование а -меры близости ребер позволяет эффективно использовать 3-nodc преобразователи Список ребер-кандидатов при увеличении размера задачи уменьшается, но при этом качество тура остается приемлемым, и в некоторых случаях даже улучшается, а время работы алгоритма может быть меньше, чем при использовании 2-node преобразователей

3 встроенный 2-nodc преобразователь предпочтителен на матрицах размера 316 В этом сяучае почти всегда находится оптимальное решение при использовании любого преобразователя Но время решения при использовании 3-node преобразователей, на удивление, оказалось часто меньше, чем у встроенною 2-node, однако 3-node иногда давали не оптимальные туры

4 при решении же матриц оазмера 1000, на некоторых классах, например сот, преобразователь 3-nodc, со значениями параметров конфигурационного файла, соответствующих размеру 2-node, выдавал лучшие, чем 2-node, туры и за меньшее время

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

улучшение решения и даже одновременное уменьшение времени работы программы

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

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

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

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

1 вершина для ветвления выбирается первая с наименьшим значением

границы

2 ребро для ветвления выбирается по наименьшему количеству нулей в

строке и столбце вершины

3 минимальный размер матрицы для ветвления - 3

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

Алгоритм PVMSyncSolverClient

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

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

1 Пока очередь вершин МВГ не пуста

2 Проверить сообщения от сервера

3 Если пришла новая верхняя граница - обновить ее

4 Взять вершину с наименьшей границей из очереди вершин МВГ

5 Если ее граница больше наилучшего решения - выйти

6 Если ее размер меньше 3

7 Решить ее на оптимальность

8 Если ее решение лучше текущего лучшего решения

' С Гудман, С XrAûiHHCMi-* «Ввелеч^р в разработку и опалка ai горишов» v 1981

Мир,

9. Запомнить новое лучшее решение

10. Послать его значение и его тур на сервер

11. Иначе

12. Ветвить её на две вершины и добавить их в очередь вершин МВГ

13. Вернуть лучшее решение

Алгоритм РУ!У1£упс8о1\'ег8егуег: Вход: Матрица ЗКВ, число клиентов N Выход: Оптимальный тур

1. Ветвить матрицу до получения N вершин МВГ. Получить оценку длины тура сверху.

2. Запустить N клиентов РУМ8упс8о1уегСПеп1. Каждому раздать свою вершину МВГ и оценку сверху.

3. Пока есть не завершившие работу клиенты

4. Ждать сообщения

5. Если сообщение содержит новое лучшее решение

6. Запомнить новое лучшее решение.

7. Разослать новое лучшее решение всем клиентам

8. Вернуть лучшее решение

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

51тр1е/Р\/М51тр1е/Р\/М8упс решатели, среднее время/число клиентов

1 23456789 10

число клиентов

Рис 1. Среднее время решения в зависимости от числа клиентов (для 8т1р1е8о1уег оно всегда равно 1). Решатели 8штр1е8о1уег (эталон) , РУМ8нт1р!е8о1уег (увеличение времени), РУМ8упс8о^ег (уменьшение времени)

Эксперименты, проведенные с двумя разработанными распределёнными вариантами МВГ в сети из пяти рабочих станций на матрицах размерности до

14

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

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

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

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

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

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

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

затем оптимальное значение параметра применяется для решения целой матрицы, позволяя в итоге уменьшить время решения целой матрицы

Таблица 3. Разность времен -С 0 и -С 16 для матрицы С1к 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

Зй запуск, с 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

Отношение среднего разности к среднему -С 0,1 0,13 -0,16 0,25 0,32 0,41 0,34

Отношение отклонения разности к среднему -С 0,1 0,41 0,11 0,35 0,19 0,18 0,30

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

1 Параметр -С, задающий объемы генерации local cuts (локальных отсечений) конкордом, действительно существенно влияет на время работы В целом значение по умолчанию - 16, как показали эксперименты, является оптимальным для матриц размера 1000 и выше

2 Параметр -s (rand seed) также существенно влияет на время работы (пожалуй, даже еще сильнее, чем -С в некоторых случаях) Это, например, не было учтено в работе Фишетти

3 Параметр -С оказывает схожее влияние, как при решении симметричных матриц, так и асимметричных Особых отличий не обнаружено Пример -таблица 3

4 Влияние параметра -С скорее зависит от размера матрицы, нежели от ее происхождения (асимметричности) Отличия между разными преобразователями АЗКВ -»СЗКВ есть, но в целом результаты похожи Зависимости между влиянием -С на подматрицу и на всю матрицу конкретной задачи не обнаружено

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

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

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

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

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

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

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

последовательностей, используемого внутри VRP Результаты по времени для разных запусков отличались лишь на проценты Однако, чтобы повысить воспроизводимость ре культа 1 ов в конфигурационные файлы VRP был добавлен параметр rand_seed, и все последующие îecm проводились со чначением randseed 1196638233, соответствующим системному времени на момент первого теста

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

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

Таблица 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,49 3,50

P-n4Q-k5 5,54 5,55 3,62 3,57 5,41 5,41 3,5s1

P-n45-k5 ; 23,58 23,14 19,95 1532 2,3,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 j 20,68 20,68 14,09 13,19 20,70 20,71 17,16 12,97

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

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

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

8 R Lougcc-Hurncr The Common Op'iiTf zaiiori INterface for Operations Research Promoting open-source softwaic in the operations rescaich community iBM Journal of Reseaich and Development, volume 47, Number 2003 Mathematical Sciences ai 40

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

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

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

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

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

> Г

Матрица ЗКВ

> г

Матрица ЗКВ

Standalone решатель (РМСА, GOBLIN)

Тур

Библиотека общих классов

- матрицы

- туры

- перестановки

- пути

- узлы дерева В&В

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

внимание уделялось решению асимметричной ЗКВ как менее изученной Были исследованы некоторые новые подходы к использованию зарекомендовавших

19

себя лидеров — concorde и LKH, а также подходы, для которых в литературе не было встречено экспериментальных оценок

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

] Предложен, реализован и экспериментально исследован новый алгоритм решения асимметричной задачи о коммивояжере путем неэквивалентного преобразования к симметричной задаче о коммивояжере

2 Выполнена программная реализация и экспериментальная оценка эффективности схемы полиномиальной аппроксимации симметричной задачи о коммивояжере и распределенного метода ветвей и границ для симметричной задачи о коммивояжере

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

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

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

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

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

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

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

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

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

6 Ляликов В H Распределенный метод ветвей и границ для задачи коммивояжера//Сборник статей II Международной научно-технической

конференции "Аналитические и численные методы моделирования естественнонаучных и социальных проблем", Пенза ПГУ - 2007 -с 165-167

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

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

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

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

Подписано в печать 18 03 08 Формат 60x84/16 Уел печ л 1,0 Тираж 100 экз Заказ Ш ОЦбО

Отпечатано с оригинал-макета в Издательском центре Ульяновского государственного университета 432970, г Ульяновск, ул Л Толстого, 42

Оглавление.

Введение.

Глава 1. Современные методы решения задачи о коммивояжере.

§1.1. Формулировки ЗКВ. I 1 I I ' i ' ' '

§1'.12\| Алгоритмы и методы решения ЗКВ.

§1.3. Средства решения ЗКВ.

§1.4. Замечания о проведении вычислительных экспериментов.

Глава 2. Методы приближенного решения ЗКВ.

§2.1. Стабильная аппроксимация Л-ЗКВ.

2.1.1 Формальное описание алгоритма РМСА.

2.1.2. Экспериментальное исследование алгоритма РМСА.

2.1.3. Результаты вычислительных экспериментов.

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

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

• релаксации линейного программирования, релаксация Лагранжа, метод ветвей и отсечений, метод ветвей и границ

• распределенный метод ветвей и границ, решатели ЛП (задачи линейного программирования)

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

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

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

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

• Оптимизацию в сетях

• Оптимизацию маршрутов

• Приложения в кристаллографии

• Управление роботами

• Обработку печатных плат

• Исследование ДНК

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

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

• Быстрое точное решение асимметричных и. симметричных ЗКВ больших размерностей

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

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

• создание новых алгоритмов и программ для точного и приближенного решения асимметричной и симметричной задачи о коммивояжере

• реализация и получение экспериментальных оценок эффективности схем аппроксимации ЗКВ

• улучшение качества тура и ускорение существующих программ решения ЗКВ

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

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

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

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

1. Разработан алгоритм решения асимметричной задачи о коммивояжере (АЗКВ, ATSP) с помощью неэквивалентного преобразования к симметричной задаче о коммивояжере (СЗКВ, STSP). Выработаны рекомендации по применению.

2. Реализованы и исследованы на эффективность алгоритмы распределенного метода ветвей и границ (МВГ) и полиномиальной аппроксимации СЗКВ РМСА [35].

3. Реализован алгоритм усеченного МВГ ZHANG1 [88] с задачей о назначениях для АЗКВ. Получены оценки времени работы и качества тура. Выработаны рекомендации по применению.

4. Разработаны схемы экспериментов для исследования эффективности локальных отсечений в методах ветвей и отсечений (MB О, Branch and Cut) [54] и эквивалентных преобразований в приближенных k-opt [56] алгоритмах для АЗКВ. По результатам выработаны рекомендации по> оптимизации времени и качества тура.

5. Экспериментально исследована эффективность отсечений ЗКВ для решения задачи, маршрутизации (Vehicle Routing Problem - VRP). Подтверждена эффективность подхода.

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

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

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

2. Программная реализация и экспериментальная оценка эффективности схемы полиномиальной аппроксимации симметричной задачи о коммивояжере и распределенного метода ветвей и границ для симметричной задачи о коммивояжере.

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

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

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

• VI Международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (г. Ульяновск, 2005)

• «XIII Всероссийской школе-коллоквиуме по стохастическим методам и VII Всероссийском симпозиуме по прикладной математике» (г. Йошкар-Ола, 2006)

• девятом международном семинаре «Дискретная математика и ее приложения» (г. Москва, 2007)

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

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

Вывод:

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

§3.4. Комплекс программ Описание программного комплекса

В рамках диссертационной работы разработан комплекс программ. Он реализован в виде набора взаимосвязанных классов на языке С++ (набора классов импорта/экспорта и базовых операций над матрицами, а также решателей - переборного SimpleSolver, распределенного МВГ, неэквивалентного преобразования АЗКВ -> СЗКВ; эвристики Жанга, оболочки конкорда и других), нескольких программ и библиотек сторонних разработчиков. Все использовавшееся программное обеспечение распространялось свободно (по крайней мере, для академического использования) и с открытыми исходными текстами. Последний пункт являлся важным критерием при подборе библиотек и программ, так как позволял вносить лишь необходимые модификации, основываясь на уже разработанном и оттестированном коде, как например, реализация схемы аппроксимации РМСА на основе реализации эвристики Кристофидеса из пакета GOBLIN.

Разработка академического программного обеспечения в рамках парадигмы свободного программного обеспечения (СПО) является современной тенденцией и поддерживается влиятельными учебными заведениями, например, Университетом Беркли, и крупными коммерческими компаниями, такими как IBM. Как отмечается в [67], использование СПО и разработка нового ПО в рамках СПО позволяет уменьшить недостатки присущие стандартной схеме разрабатываемого в рамках научных исследований ПО:

• Результаты невоспроизводимы.

В отличие, например, от детально описываемых физических экспериментов, программы характеризуются не только- сложностью алгоритмов, но и эффективностью реализации. Показателен пример Кармаркара [67].

• Пристрастность сравнений.

Авторам программ приходится сравнивать «мою реализацию вашей идеи» и «мою реализацию моей идеи»

• Модели и реализации теряются

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

• Развитие тормозится

Без обмена идеями и решениями развитие в области идет медленнее.

• «Велосипеды изобретаются заново»

Особенно негативно это сказывается в области разработки ПО: бурное развитие • отрасли может обесценить разработку, затянувшуюся слишком' надолго. Вместо того, чтобы делать лишь необходимые модификации уже имеющихся программ, исследователям приходится » разрабатывать их снова и снова. Это требует навыков и времени.

• Обмен знаниями ограничен

Часто новые теоретические разработки для одного класса задач можно применять и для других классов. Если программные реализации закрыты - перенос невозможен.

• Сотрудничество затруднено недостатком стандартов

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

Несмотря на то, что наиболее известными программами СПО являются низкоуровневые приложения, такие как GNU/Linux (операционная система), apache (веб сервер), bind (сервис доменных имен), Perl (скриптовый язык), что в значительной степени связано с гораздо более широкой целевой аудиторией, в рамках исследовательских работ, находящихся обычно на среднем и высоком уровнях стэка, и разрабатываемых ограниченным сообществом, эта парадигама также оказывается эффективной [67].

В рамках диссертационной работы было проведено исследование СПО средств решения задач ЛП и ЦЛП, являющихся важными элементами реализаций алгоритмов Branch & Cut и Branch & Price. Результаты вычислительных экспериментов показали, насколько затратным по времени и проблематичным по качеству результата является процесс разработки крупных СПО проектов.

Как указано! в обзоре [65], существует множество закрытых и несколько открытых программных продуктов для решения указанных задач.

Целью одного из этапов работы было сравнение возможностей и производительности свободных библиотек целочисленного линейного программирования (ЦЛП). Сравнивались два наиболее крупных пакета с открытой лицензией, способных решать задачи ЦЛП: GLPK (GLKP 4.8) и lpsolve (lpsolve 5.1). Примеры задач ЦЛП для тестирования были выбраны с учетом доступности, что позволяет сравнивать результаты с другими работами. В отчете представлены данные для задач из набора, предложенного профессором Гансом Миттелманом [70] . В [70] не использовалась библиотека lpsolve, но представлены результаты для нескольких закрытых, не рассматривающихся здесь . Тесты проводились на машине: Athlon 2000+, 512 Mb DDR SDRAM (памяти было достаточно для проведения всех тестов), OS GNU/Linux 2.4

Параметры тестовых задач, такие как число строк, столбцов, целых и ненулевых переменных, можно посмотреть в [70].

Затраты времени на решение задач приведены на (рис. 4.1) Стандартный решатель lpsolve не справился с некоторыми задачами и выдавал сообщение об этом по истечении определенного времени. Такие случаи отмечены вертикальными линиями вместо точек.

В заключение можно отметить, что как и указано в [68], используемые в библиотеке вЬРК алгоритмы еще не полностью проработаны и слабо оптимизированы, что проявляется в существенном проигрыше по времени некоторым закрытым аналогам. Также были выявлены проблемы со стабильностью вычислений, особенно у библиотеки 1рБо1уе. Если же рассматривать только открытые реализации, то ОЬРК на данный момент является предпочтительной для использования и доработки. А в целом сравнение ОЬКР и 1рБо1уе показывает, насколько затратным и сложным процессом является разработка современных новых ЛП-решений.

3000 к 2500 s 2000 Q)

1500 а; 1000 Q. ш

500 0

Решение задач ЦЛП. GLPK и lpsolve

- In snlvfí / - 1

GLPK ^ nug08 irp mas284 bienstl dano33 dano34markshare11

Задача,название

Рис 4.1. Время решения задач ЦЛП, с

Некоторые решатели, входящие в комплекс (на (рис. 4.2) они перечислены справа), были реализованы в виде классов Solver - с общим интерфейсом, что позволяло унифицировать импорт/экспорт задач и запуск тестов. Некоторые другие решатели были реализованы как дополнения и модули к сторонним программам, например, как схема РМСА. Однако при необходимости их тоже можно с небольшими по времени затратами привести к формату Solver.

Список основных использовавшихся библиотек и программ (в скобках отмечены основные критерии, по которым программное обеспечение подбиралось):

• С++, stl - язык и библиотеки (удобная реализация стандартных алгоритмов со стандартными типами данных, например, со строками; механизм шаблонов, позволяющий создавать шаблоны алгоритмов и типов данных, например, алгоритмов сортировки и очередей, специфичных для задачи; удобство создания объектно-ориентированной модели приложения и ее реализации; относительная простота интеграции с кодами сторонних разработчиков, которые в основном были реализованы на языках ANSI С и С++)

• PVM — библиотека распределенных вычислений (для распределенных вычисления в гетерогенных сетях) (промышленный стандарт, оттестированный и переносимый)

• libhungarian - библиотека для решения задачи о назначениях (оттестированность, компактность)

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

• concorde - программа решения ЗКВ. Использовалась для решения ЗКВ на оптимальность средствами ветвей и границ (лучший по производительности код В&С оптимизации ЗКВ на 2008 год), и получения нижних оценок ЗКВ - границы Хелда-Карпа.

• LKH - программа приближенного решения ЗКВ (один из лучших по качеству тура и времени работы алгоритмов приближенного решения ЗКВ на 2008)

• Каркас SYMPHONY и приложение VRP из набора программ COIN-OR - средств СПО для создания решателей МВГ, МЕЮ (Branch & Cut), Branch & Price.

Входом каждого решателя является матрица симметричной или асимметричной задачи о коммивояжере в формате TSPLIB [81] или во внутреннем формате. Выходом является значение стоимости найденного тура и опционально сам тур. При необходимости перед передачей матрицы на вход Solver'а она может быть преобразована в эквивалентную или в матрицу специального формата. Например, из асимметричной в симметричную. Соответственно после того, как Solver выдаст решение, оно должно будет пройти соответствующую постобработку. Например, вычитание стоимостей, добавленным к ребрам в 2-node АЗКВ-»СЗКВ преобразователе.

Заключение

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

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

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

На научную новизну претендуют:

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

2. Программная реализация и экспериментальная оценка эффективности схемы полиномиальной аппроксимации симметричной задачи о коммивояжере и распределенного метода ветвей и границ для симметричной задачи о коммивояжере.

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

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

1. уменьшение времени работы (увеличение скорости решения) в случае точных методов

2. уменьшение времени работы и уменьшение длины тура в случае приближенных методов

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

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

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

1. Алгоритмы. Построение и анализ Текст. / Т. Кормен [и др.] ; пер. с англ. И. В. Красикова, Н. А. Ореховой, В. Н. Ромашова. 2-е изд. - М. : Вильяме, 2005. - 1290 с.

2. Ашманов С. А. Линейное программирование Текст. : учеб. пособие для вузов / С. А. Ашманов. М. : Наука, 1981. - 304 с.

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

4. Воеводин В. В. Параллельные вычисления Текст. : учеб. пособ. для студентов вузов, обучающихся по направлению 510200 "Прикладная математика и информатика" / В. В. Воеводин, Вл. В. Воеводин. СПб. : БХВ-Петербург, 2002. - 599 с.

5. Гудман С. Введение в разработку и анализ алгоритмов Текст. / С. Гудман, С. Хидетниеми ; пер. с англ. Ю. Б. Котова [и др.]. М. : Мир, 1981.-366 с.

6. Информационные материалы, посвященные высокопроизводительным и параллельным вычислениям Электронный ресурс. / Всероссийский Информационно-Аналитический Центр по параллельным вычислениям. -Режим доступа: http://parallel.ru/.

7. Кристофидес Н. Теория графов. Алгоритмический подход Текст. / Н. Кристофидес, М. : Мир, 1978. - 429 с.

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

9. Ляликов В. Н. Неравенства задачи о коммивояжере для задачи маршрутизации Текст. / В. Н. Ляликов // Обозрение прикладной и промышленной математики. — 2008. Т. 15, Вып. 1. - С. 154.

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

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

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

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

14. B. Н. Ляликов // Программное и информационное обеспечение поддержки научно-исследовательских работ. — М. : ВНТИЦ, 2007.

15. Схрейвер А. Теория линейного и целочисленного программирования Текст. : в 2-х т. / А. Схрейвер ; пер. с англ. С. А. Тарасова, М. А. Фрумкина, В. И. Шлыка ; под ред. Л. Г. Хачияна. М. : Мир, 199Г.

16. Харари Ф. Теория графов Текст. / Ф. Харари ; пер. с англ. и предисл. В. П. Козырева ; под ред. Г. П. Гаврилова. 3-е изд. — М. : КомКнига, 2006. -300 с.

17. Ху Т. Целочисленное программирование и потоки в сетях Текст. / Т. Ху ; пер. с англ. П. Л. Бузыцкого [и др.] ; под ред. и с предисл. А. А. Фридмана. -М. : Мир, 1974.-519 с.

18. Aardal К. Polyhedral Techniques in Combinatorial Optimization Текст. / К. Aardal, S. van Hoesel // Statistica Neerlandica : orgaan van de Vereniging voor Statistiek. 1996. - № 50. - P. 3-26.

19. Andaljayalakshmi G. A hybrid genetic algorithm a new approach to solve traveling salesman problem Текст. / G. Andaljayalakshmi, S. Sathiamoorthy,

20. R. Rajaram // International Journal of Computational Engineering Science. -2001. Vol. 2, №2.-P. 339-355.

21. Applegate D. "Finding Cuts in the TSP" : a preliminary report Текст. / D. Applegate, R. Bixby // DIMACS Technical Report. 1995. - P. 95-105.

22. Applegate D. TSP cuts outside the template paradigm Электронный,ресурс. /. D. Applegate, R. E. Bixby, V. Chvatal.// Technical report, Computer Sciences, Rutgers University. — Режим доступа : http://www.cs.rutgers.edu/~chvatal/dagstuhl.ps, 2000.

23. Applegate D. Chained Lin-Kernighan for large traveling salesman problems Текст. / D. Applegate, W. Cook, A. Rohe // INFORMS J. Comput. 2003. -Vol. 15.-P. 82-92.

24. Arora S. Polynomial Time Approximation Schemes for Euclidian Traveling Salesman and Other Geometric Problems Текст. / S. Arora // Journal of the ACM. 1998. - Vol.- 45, № 5. - P. 753-782.

25. Balas E. Polyhedral theory for the asymmetric traveling salesman problem Текст. / E. Balas // The traveling salesman problem and its variations / edited by G. Gutin, A. Punnen. Dordrecht: Kluwer Academic Publishers, 2002. - P. 117-168.

26. Balas E. Branch and bound methods Текст. / E. Balas, P. Toth // The Traveling Salesman Problem / edited by E. L. Lawler, J. K. Lenstra. John Wiley & Sons Ltd, 1985. - P. 361-401.

27. Baumann F. ABACUS. A Branch-And-CUt System Электронный ресурс. / F. Baumann. Version 3.0 // User's Guide and Reference Manual. - Режим доступа: http://www.informatik.uni-koeln.de/abacus/, 2007.

28. Bentley J. L. Fast algorithms for geometric traveling salesman problems Текст. / J. L. Bentley // ORSA. Journal on Computing. 1992. - Vol. 4. -P. 387-411.

29. Blasum U. Application of the Branch and Cut Method to the Vehicle Routing Problem Текст. / U. Blasum, W. Hochstattler // Zentrum fiir Angewandte Informatik Koln Technical Report. 2000. - P. 386.

30. Bockenhauer H.-J. Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem Текст. / H.-J. Bockenhauer, J. Hromkovic, R. Klasing // Theoretical Computer Science. -2002. № 285. - P. 3-24.

31. Bockenhauer H.-J. Improved lower bounds on the approximability of the traveling salesman problem Текст. / H.-J. Bockenhauer, S. Seibert // RAIRO Theoretical Informatics and Applications. 2000. - Vol. 34. - P. 213-255.

32. Caprara A. {1, /4}-Chvatal-Gomory Cuts Текст. / A. Caprara, M. Fischetti // Mathematical Programming. Series A and B. 1966. - Vol. 74, № 3. - P. 221<-235.

33. Christine L. Valenzuela Estimating the Held-Karp lower bound for the geometric TSP Текст. / L. Christine Valenzuela, J. Jones. Antonia' // University of Wales. -2001.-12 July.

34. Cirasella J. The asymmetric traveling salesman problem : algorithms, instance generators, and tests, ALENEX 2001 proceedings Текст. / J. Cirasella, D. S. Johnson, L. A. McGeoch // Springer Lecture Notes in Computer Science. P. 32-59.

35. Concorde (a computer code for the symmetric traveling salesman problem (TSP) and some related network optimization problems) webpage Электронный ресурс. Режим доступа : http://www.tsp.gatech.edu/concorde.html.

36. Dahl G. An introduction to convexity, polyhedral theory and combinatorial optimization Текст. / G. Dahl. University of Oslo, 1997.

37. Diestel R. Graph Theory Текст. / R. Diestel. New York : Springer-Verlag, 1997.

38. DIMACS 8th Implementation Challenge Электронный ресурс. Режим доступа: http://www.research.att.com/~dsj/chtsp.

39. Fischetti М. Local branching Текст. / M. Fischetti, A. Lodi // Math. Program. Ser. B. 2003. - Vol. 98. - P. 23-47.

40. Fortini M. LP-based heuristics for the traveling salesman problem Текст. / M. Fortini // Dottorato di Ricerca in Automatica e Ricerca Operativa (MAT/09). -Universita.degli studi di Bologna, 2007.

41. Fredman M. L. Data structures for traveling salesman Текст. / M. L. Fredman, D. S. Johnson, L. A. McGeoch. // Journal of Algorithms. 1995. — Vol. 18. -P. 432-479.

42. Fugenschuh A. Computational Integer Programming and Cutting Planes Текст. / A. Fugenschuh, A. Martin // Handbooks in Operations Research and Management Science, Kluwer. 2005. - P. 69-122.

43. Geist A. PVM : Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing Текст. / A. Geist, A. Beguelin, J. Dongarra. -Cambridge : The MIT Press, 1994.

44. Geist G. A. PVM and MPI: a Comparison of Features / G. A. Geist, J. A. Kohl, P. M. Papadopoulos Текст. // Calculateurs Paralleles. 1996. - Vol. 8(2).-P. 137-150.

45. GOBLIN Graph Library 2.8Ы6 : GOBLIN is a С++ class library focussed on graph optimization and network programming problems. Reference Manual,

46. February 4, 2007 Электронный ресурс. Release 2.8. - Режим доступа : http://www.math.iini-augsburg.de/~fremuth/goblin.html, 2007.

47. Grötschel M. Padberg Polyhedral theory Текст. /М. Grötschel // The Traveling Salesman Problem / edited by E. L. Lawler, J. K. Lenstra. Hoboken : John Wiley & Sons Ltd, 1985. - P. 251-305.

48. Haupt R. L. Practical genetic algorithms Текст. / R. L. Haupt, S. E. Haupt. -Hoboken : John Wiley & Sons, 2004. 253 p.

49. Helsgaun, K. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic Текст. / К. Helsgaun // DATALOGISKE SKRIFTER (Writings on Computer Science). 1998. - № 81.

50. Hromkovic J. Algorithmics for Hard Problems Текст. / J. Hromkovic. 2-nd edition. - Springer, 2003.

51. Johnson D. S. Experimental.analysis of heuristics for the STSP Текст. / D. S. Johnson, L. A. McGeoch // The traveling salesman problem and its variations / edited by G. Gutin, A.'Punnen. Dordrecht : Kluwer Academic Publishers, 2002.-P. 369-443.

52. Junger M. The Design of the Branch-and-Cut System ABACUS Текст. : technical report / M. Junger, S. Thienel ; Institut fur Informatik, Universität zu Köln. Köln, 1997.

53. Kindervater G. A. P. Parallel local search for the time-constrained traveling salesman problem Текст. / G. A. P. Kindervater, J. K. Lenstra, M. W. P. Savelsbergh // European* Journal of Operational Research. Vol. 33 (1988). - P. 65-81.

54. Ladanyi L. Introduction to BCP MCF Example Электронный ресурс. : web document 2006 / L. Ladanyi, F. Margot. - Режим доступа : http://dimacs.rutgers.edu/Workshops/COIN/slides/bcp tutorial.pdf

55. Lecture : The Traveling Saleman Problem Текст. / W. Cook // INFORMS Annual Meeting. Miami. 2001. - November 5.

56. Lecture : TSP Cuts that do not follow the template paradigm, Combinatorial Optimization and Integer Programming Текст. / V. Chvatal. The State of the Art Columbia University. - 2001, November 28.

57. Linear Programming Frequently Asked Questions Электронный ресурс. — Режим доступа : http://www-unix.mcs.anl.gov/otc/Guide/faq/Hnear-programming-faq.html, September 2, 2004

58. Lodi A. TSP software Текст. / A. Lodi, A. P. Punnen // The traveling salesman problem and its variations / edited by G. Gutin, A. Punnen. Dordrecht : Kluwer Academic Publishers, 2002. - P. 737-749.

59. Lougee-Heimer R. The Common Optimization INterface for Operations Research Текст. / R. Lougee-Heimer // IBM Journal of Research and Development. Mathematical Sciences. 2003. - Vol. 47, № 1. - P. 57-66.

60. Makhorin A. GNU Linear Programming Kit Электронный ресурс. / A. Makhorin // Reference Manual, version 4.8. Moscow Aviation Institute 2005. -Режим доступа : http://www. gnu.msn.bv/people/people.html.

61. Mitchell J. E. Branch-and-Cut Algorithms for Combinatorial Optimization Problems Текст. : handbook of Applied Optimization / J. E. Mitchell. -Oxford University Press, 2000.

62. Mittelmann H. Mixed Integer Linear Programming Benchmark (free codes) Электронный ресурс. / H. Mittelmann. Режим доступа : ftp://plato.la.asu.edu/pub/milpf.txt., May 18, 2005.

63. Moore A. W. An introductory tutorial on kd-trees : Текст. extract from A. Moore's PhD Thesis : Efficient Memory-based learning for robot control : technical Report, No. 209 / A. W. Moore ; Computer Laboratory, University of Cambridge, 1991.

64. Padberg M. W. Polyhedral computations Текст. / M. W. Padberg, M. Grotsche7

65. The Traveling Salesman Problem / edited by E. L. Lawler et al.. Hoboken : John Wiley & Sons Ltd, 1985. - P. 307-360.

66. Parberry I. Problems on Algorithms Электронный ресурс. / I. Parberry, W. Gasarch. 2-е edition. — Режим доступа : http://www.eng.unt.edu/ian/books/poa.html, 2002.

67. Punnen A. P. The traveling salesman problem Текст. : applications, formulations and variations / A. P. Punnen // The traveling salesman problem and its variations / edited by G. Gutin, A. Punnen. Dordrecht : Kluwer Academic Publishers, 2002. - P. 1-28.

68. Ralphs Т. K. Parallel Branch and Cut for Capacitated Vehicle Routing Текст. / Т. К. Ralphs // Parallel Computing. 2003. - Vol. 29. - Issue 5. - P. 607 - 629.

69. Ralphs Т. K. SYMPHONY 5.1.4 User's Manual Электронный ресурс. / Т. К. Ralphs. Режим доступа : www.branchandcut.org/SYMPHQNY, 2007.

70. Ralphs Т. К. Capacitated Node Routing Problem Электронный ресурс. / Т. К. Ralphs, J. С. Hartman. Режим доступа : http://coral.ie.lehigh.edu/~ted/files/papers/CNRP.pdf, 2001.

71. Ralphs Т. К. An improved algorithm for solving biobjective integer programs Текст. / Т. К. Ralphs, M. J. Saltzman, M. M. Wiecek // Annals of Operations Research. 2006. - Vol. 147, № 1. - P. 43 - 70.

72. Reinelt G. TSPLIB A Traveling Salesman Problem Library Текст. / G. Reinelt// ORSA J. Comput. - 1991.-№ 3/4.-P. 376-385.

73. Sedgewick R. Algorithms Текст. / R. Sedgewick. Addison-Wesley, 1984. 83.Sleator D.D. Self-adjusting binary search trees [Текст] / D. D. Sleator, R. E. Taijan // J. ACM. - 1985. - № 32. - P. 652-686.

74. Stroustrup В. The С++ Programming Language third ed. Текст. / В. Stroustrup // AT&T Labs Murray Hill. New Jersey, 1997.

75. TSPLIB homepage Электронный ресурс. Режим доступа : http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html

76. Usami Y. Traveling salesman problem and statistical physics Текст. / Y. Usami, M. Kitaoka // International Journal of Modern Physics. Vol. 11, No. 13 (1997).-P. 1519-1544.

77. Zhang W. Depth-First Branch-and-Bound versus Local Search Текст. : a Case Study / W. Zhang // Proc. 17th National Conference on Artificial Intelligence (AAAI-2000). Austin : Texas, 2000. - P. 930-935.

78. Zhang W. Truncated Branch-and-Bound Текст. : a Case Study on the Asymmetric TSP / W. Zhang // Proc. AAAI 1993 Spring Symp. AI and NP-Hard Problems. Stanford : CA, 1993. - P. 160-166.

79. Website for the DIMACS : implementation Challenge on the Traveling Salesman Problem Электронный ресурс. / D. S. Johnson [et al.]. Режим доступа: http://www.research.att.com/~dsi/chtsp/