Преобразования графов и комбинаторных сочетаний на основе видоизменения формул Виета и алгоритмов сортировки с минимизацией временной сложности в приложении к дискретной оптимизации тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Назарьянц, Елена Геворговна

• Назарьянц, Елена Геворговна
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Назарьянц, Елена Геворговна

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ПРЕОБРАЗОВАНИЕ МАТРИЧНОЙ ФОРМЫ ГРАФА МЕТОДА ВЕТВЕЙ И ГРАНИЦ НА ОСНОВЕ СОРТИРОВКИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

1.1. Постановка вопроса и описание подхода к решению

1.2. Применение устойчивой адресной сортировки для выполнения метода ветвей и границ

1.3. Идентификация экстремумов на основе сортировки для минимизации

временной сложности метода ветвей и границ

1.3.1. Случай возврата к оборванным ветвям

1.4. Численное моделирование алгоритма решения задачи коммивояжера

методом ветвей и границ

1.4.1. Анализ результатов численного эксперимента

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

1.6. Выводы

ГЛАВА 2. ДЕТЕРМИНИРОВАННЫЕ АЛГОРИТМЫ ОДНОМЕРНОЙ УПАКОВКИ НА ОСНОВЕ ВИДОИЗМЕНЕНИЯ ФОРМУЛ ВИЕТА С ПРИМЕНЕНИЕМ СОРТИРОВКИ

2.1. Введение и формальная постановка задачи

2.2. Алгоритм выборки всех возможных сочетаний слагаемых для решения задачи о рюкзаке

2.3. Алгоритм последовательного решения задачи о рюкзаке на основе видоизменения формул Виета

2.4. Временная сложность последовательного алгоритма решения задачи о рюкзаке

2.5. Пример реализации последовательного детерминированного алгоритма

2.6. Решение задачи примера 2.1 методом ветвей и границ и анализ полученных решений

2.7. Параллельные алгоритмы решения задачи о рюкзаке и оценки временной сложности

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

2.9. Выводы

ГЛАВА 3. ДЕТЕРМИНИРОВАННЫЕ АЛГОРИТМЫ ДВУМЕРНОЙ УПАКОВКИ С ПРИМЕНЕНИЕМ СОРТИРОВКИ И ВИДОИЗМЕНЕНИЯ ФОРМУЛ ВИЕТА

3.1. Обзор методов двумерной упаковки и постановка вопроса

3.2. Детеминированные алгоритмы решения задачи двумерной упаковки с минимизацией временной сложности

3.2.1. Применение модификации формул Виета для параллельной генерации сочетаний прямоугольников

3.2.2. Предварительное описание основного алгоритма параллельной упаковки

3.2.3. Детализированное описание основного алгоритма параллельной упаковки

3.3. Разновидности детерминированных алгоритмов параллельной упаковки

и оценки их временной сложности

3.3.1. «Оптимизация» по окаймлению упаковки элементов каждого сохраненного сочетания

3.4. Примеры реализации алгоритма двумерной упаковки с вариантами упаковки сочетания

3.5. Сравнение оценок временной сложности вариантов предложенного параллельного алгоритма с известными

3.6. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

Введение диссертации (часть автореферата) на тему «Преобразования графов и комбинаторных сочетаний на основе видоизменения формул Виета и алгоритмов сортировки с минимизацией временной сложности в приложении к дискретной оптимизации»

ВВЕДЕНИЕ

Актуальность проблемы. Рассматриваемые в работе задачи относятся к задачам комбинаторной оптимизации. В науке и на практике часто встречаются задачи, решая которые приходится составлять различные комбинации, подчиненные тем или другим условиям, из заданных объектов и подсчитывать число комбинаций. Такие задачи получили название комбинаторных задач. Комбинаторные оптимизационные задачи относятся к разделу теории графов и ее приложений. В общем случае оптимизационные задачи делят на два класса: задачи непрерывной (гладкой) и задачи дискретной оптимизации [15]. Первый класс - это задачи с гладкими дифференцируемыми функциями (в некоторых случаях с рядом особенностей), определенные на множестве вещественных или комплексных значений аргументов (как правило, бесконечном или несчетном). Такие задачи возникают в различных разделах научных исследований физики, астрономии, теоретической механики, экономики и др. Второй класс - это задачи, у которых функции берутся от какого-либо дискретного аргумента или дискретной структуры (например, счетного множества, графа). Второй класс задач получил широкую известность в связи с развитием дискретной прикладной математики и ее составляющих (математическое программирование, теория игр, теория графов). В основополагающих работах Лейбница (G. Leibniz), Эйлера (L. Euler) и других известных ученых зародилось новое направление, именуемое комбинаторикой. В рамках комбинаторики изучаются дискретные задачи с дискретными объектами, у которых свои свойства и отношения (между объектами). Задачи комбинаторики возникают в криптографии, в информатике, технике, экономике, и во многих других областях. Часто задачи комбинаторной оптимизации NP-трудны, например, задачи упаковки (одномерной и

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

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

Задача коммивояжера, является одним из вариантов транспортной задачи и имеет следующую классическую постановку. Коммивояжер должен выйти из первого города, посетить по одному разу в неизвестном порядке города 2, 3, 4,..., n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? (1934г., [43]). В 1959 году G. B. Dantzig и J. H. Ramser представили математическую модель для транспортной задачи (TS или Vehicle Routing Problem - VRP) [121]. Первые эвристические методы появились в 1964 году у G. Clark и J. V. Wright [117]. В статье J. K. Lenstra и A. H. G. Rinnooy Kan (1981 г.) [163] была доказана

№-полнота данной задачи. В дальнейшем транспортная задача все более модифицировалась, что привело к появлению большого количества вариантов постановок. В работе R. Ъ. Farahani, S. Rezapor и другие [131] представлена классификация вариантов этой задачи:

Транспортная задача с учетом грузоподъемности (Capacitated VPR)

Двумерное размещение объектов (2L-CVPR)

Трехмерное размещение объектов (3L-CVPR)

Транспортная задача

-Г-

Транспортная задача с учетом грузоподъемно сти и

расстояния (Distance-Constrained and Capacitated VRP)

Транспортная Транспортн Транспортн

задача с ая задача с ая задача с

временными возратами забором и

окнами (VPR (VPR доставкой

withTime With (VPR

Windows) Backhauls) Packupand

delivery)

1. Транспортная задача с учетом грузоподъемности (The Capacitated VRP-CVRP). Рассматривается только грузоподъемность транспортного средства. В рамках данной задачи выделяется несколько типов подзадач. В частности, если кроме грузоподъемности рассматривается размещение предметов внутри транспортного средства, выделяется двумерное размещение объектов (2L-CVRP) и трехмерное (3L-CVRP).

2. Транспортная задача с учетом не только грузоподъемности, но и расстояния (Distance-Constrained and Capacitated VRP). Симметричная модель данной задачи была предложена G. Laporte, Y. Nobert, M. Desrochers в [161]. В задаче существует несколько ограничений: ограничение на грузоподъемность (вместимость) транспортного средства и ограничение на максимальный путь (расстояние, которое может пройти транспортное средство).

3. Транспортная задача с временными окнами (VRP with Time Windows). Модель данной задачи представлена в работе P. Toth, D. Vigo

[209]. Вводится ограничение по времени. Такое ограничение предполагает прием товара в определенные временные интервалы на усмотрение заказчика (временные окна), а также учитывается время на обслуживание (загрузку и разгрузку) прибывшего транспортного средства.

4. Транспортная задача с возвратами (VRP with Back hauls). В задаче вводится условие (ограничение) на обратный путь транспортного средства, при этом нужно собрать использованные тары (емкости). Модель задачи представлена в работе P. Toth, D. Vigo (1999) [208], но для случая, когда все грузы доставлены и сбор тары возможен на обратном пути.

5. Транспортная задача с забором и доставкой (VRP with Pickup and Delivery). Для данной задачи представлена целочисленная модель линейного программирования в работе A. Hoff, I. Gribkovskai и др. [150], а также частично целочисленная модель линейного программирования.

Методы решения транспортной задачи

Рассмотрим следующую классификацию методов решения транспортной задачи [33]

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

1. Точные методы

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

1.1. Комбинаторная оптимизация построена на идее перебора всех допустимых решений. Один из самых известных комбинаторных методов-метод ветвей и границ (Branch and bound). Метод был предложен A. H. Land и A. G. Doig [159] в 1960 году для решения задачи целочисленного программирования. Суть алгоритма состоит в поиске минимума функции f (x) с использованием двух операций: нахождение границ и ветвления. Ветвление разбивает все множество допустимых решений (значений переменной ( x) ) на подмножества, далее процедура применяется рекурсивно к каждому подмножеству. При этом множество подмножеств образует дерево ветвей и границ (дерево поиска), узлами которого являются отдельные подмножества. Процедура нахождения границ сводится к вычислению верхней и нижней границы на подмножестве. Далее происходит исключение подмножеств, на которых нижняя граница больше верхней на любом из других подмножеств. Метод ветвей и границ применялся для решения различных вариантов транспортной задачи. В работе D. Litlla метод ветвей и границ применяется для решения задачи коммивояжера [43]. В работе G. Laporte, H. Mercure, Y. Nobert [160] приводится решение ассиметричной задачи CVRP, а в работе J. Desrosiers, F. Soumis, and M. Desrochers [122] метод ветвей и границ используется в сочетании с методом генерации столбцов (Column Generation Method). В работе H. Hernandez-Pérez, J.-J. Salazar-Gonzalez [148] рассматривается более сложная вариация транспортной задачи VRP with Pickup and Deliver, решаемая данным методом. Существуют другие варианты алгоритмов комбинаторной оптимизации в рамках метода ветвей и границ, например: Branch-and-Cut в работах M.M. Dessouky, Q. Lu и другие [123] и S. Ropke и J.-F. Cordeau [192]; Branch-and-Cut-and-Price в публикациях S. Ropke, J.F. Cordeau и другие [193],

R. Baldacci, E. Bartolini и другие [101]; Branch-and-Price в работе Peetersa M., Degraeveb Z. [186].

1.2. Метод отсечения. Суть этого метода состоит в сужении области допустимых решений задачи с ослабленными ограничениями, например, в случае рассмотрения задачи целочисленного программирования - без учета условия целочисленности. Если полученное решение целочисленное, то задача решена, иначе к ограничениям задачи добавляется новое ограничение, построенное по определенным правилам, и задача решается заново с учетом нового ограничения. И так до тех пор, пока не получим целочисленное решение.

Одним из известных методов отсечения является метод Гомори (Cutting-plane method). Метод известен с 1950-х годов, Р. Гомори применял его для решения задач целочисленного и частично целочисленного линейного программирования. Метод используются для решения большого числа вариантов постановки транспортной задачи: классической транспортной задачи (VRP) и ассиметричной задачи коммивояжера с учетом временных окон (time-window-constrained Asymmetric Travelling Salesman Problems - ATSPs) [176]. В [204] рассматриваемый метод применяется для командно-ориентированной транспортной задачи с учетом временных окон и ограничений вместимости с подбором и доставкой (The Team Orienteering Problem with Pickups, Deliveries, Time Windows and Capacity Constraints). В [28] отсечение используется для сетевого планирования в условиях нечетких ограниченных ресурсов. Представленные точные методы показывают хорошие результаты, если размерности задач небольшие, в противном случае поиск нахождения решения затягивается (на задачах большой размерности почти невозможно найти точное решение за полиномиальное время), поэтому для решения практических задач часто прибегают ко второй группе методов - к эвристическим.

2. Эвристические методы

2.1. Метаэвристические алгоритмы. Впервые термин метаэвристика встречается в [141], включает в себя слияние двух греческих слов («мета» + «эвристика»). «Мета» означает «за его пределами, в верхнем уровне». «Эвристика» происходит от глагола «heuriskein». Метаэвристики - один из популярных и мощных классов оптимизационных методов, которые дают возможность нахождения решений для множества задач из различных приложений. Основное преимущество метаэвристик - возможность решения трудноразрешимых задач оптимизации без знания пространства поиска. Иными словами, метаэвристики - это алгоритмы нахождения оптимальных (близко к оптимальному решению) решений с помощью прямого случайного поиска. Поиск осуществляется до тех пор, пока не будет выполнено некое условие или выполнено заданное число итераций. Поначалу, как правило, для решения сложных задач комбинаторной оптимизации разрабатывались специализированные эвристики. В [143] Фредом Гловером были описаны метаэвристические схемы решений задач комбинаторной оптимизации, иначе метаэвристики. Метаэвристики объединяют основные эвристические методы, направленные на эффективное изучение пространства поиска в рамках алгоритмических схем более высокого уровня. Такой подход уменьшает время работы алгоритма, так как не требуется разрабатывать специальных эвристик с самого начала, а лишь адаптировать метаэвристические схемы решения задач комбинаторной оптимизации.

Отметим основные свойства метаэвристических методов [92]:

• метаэвристики - это стратегии, которые управляют процессом поиска;

• целью метаэвристики является нахождение оптимального решения с использованием пространства поиска;

• метаэвристические алгоритмы являются, вообще говоря, не детерминированными и не проблемно-ориентированными;

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

• метаэвристики допускают абстрактное описание.

Примеры метаэвристичеких алгоритмов: направленный локальный поиск (Guided Local Search, GLS) [211]; поиск с чередующейся окрестностью (variable neighborhoods search VNS) [180, 184]; генетический алгоритм (Genetic Algorithms, GA) [18, 22]; алгоритм оптимизации муравьиной колонии (Ant Colony Optimization, ACO) [126]; имитация отжига (Simulated Annealing, SA) [156]; поиск с запретами (Tabu Search , TS) [142], жадный рандомизированный адаптивный поиск (GRASP) [1ЗЗ, 191], эволюционные стратегии [1, 96] и другие. В 1997г. F.Glover в [142] предложил к использованию поиск с запретами (Tabu Search, TS), по сути это алгоритм управляемого локального поиска со списком запретов, которые нужны для уменьшения количества перебираемых решений. Вводится окрестность, иначе совокупность соседних (близких) решений, между которыми осуществляется переход. Подход успешно применяется для различных модификаций транспортной задачи. Приведем несколько примеров использования метоэвристик в решении различных модификаций транспортных задач. В [185] для решения транспортной задачи с учетом грузоподъемности (CVRP) I. Osman предложена метастратегия, основанная на использовании сочетания двух известных методов: метода имитации отжига и поиска с запретами. В [138] представлен метод TABUROUTE, в котором результатом удаления вершины из одного пути и добавления в новый путь «соседние» решения являются недопустимыми, промежуточные решения - допускаются. В 1996 году Cesar Rego в [114] рассматривает транспортную задачу с учетом грузоподъемности транспортного средства, решение которой основывается на параллельном поиске с запретами с использованием генерации составных шагов, концепция которой лежит в основе цепного процесса выброса (ejectioncha in process). В 2005 году в

работе Herman Sontron, Pietervander Horn и другие [198] для решения задачи с временными окнами (VRPTW) использован двухуровневый алгоритм. Идея состоит в том, что нижний уровень предназначен для генерации маршрутов и использует поиск с запретами, а на втором уровне (верхнем) - используется итерационный локальный поиск (Iterated Local Search). Для этой же задачи (VRPTW) в [181] предлагается для поиска с запретами новая окрестность. Подробный обзор различных вариаций метода поиска с запретами применительно к решению задачи VRPTW был представлен Olli Bräysy, Michel Gendreau [111]. Таким образом, метаэвристические методы, дают оптимальные или близкие к глобально оптимальным решения комбинаторно-оптимизационных задач на большом пространстве, используя небольшое количество ресурсов.

2.2. Генетические алгоритмы - это поисковые алгоритмы, основанные на механизмах селекции и генетики [19]. Генетические алгоритмы (Genetic algorithm, GA) хорошо зарекомендовали себя при решении комбинаторно-оптимизационных задач, в частности в решении транспортной задачи. Такие алгоритмы решают оптимизационные задачи с помощью определенных процедур. Все используемые процедуры можно отметить и в живой природе: отбор, мутации, наследование, кроссинговер (скрещивание). Основным отличием генетического алгоритма от эволюционных алгоритмов является использование рекомбинации решений (процедура кроссинговера). Многими авторами определены основные генетические структуры и процедуры. На данный момент алгоритмы различаются способом кодирования и простейшими структурами. Идея эволюционной симуляции появляется в работе Nils Barricelli, 1954 г. [103]. Сравнение алгоритмов произвел W. Nurfahizul и др. применительно к задачи VRP with backhouls [183]. В [100] Baker, M. A. Ayechew для решения задачи CVRPM генетический алгоритм используется в сочетании с методами поиска ближайшего соседа (Neighbourhood Search Methods). В [40] используются генетические

алгоритмы в комбинаторно-логических задачах искусственного интеллекта. Подробное описание генетического алгоритма можно найти в [19, 38].

2.3. Имитация отжига (Simulated Annealing, SA). Алгоритм имитации отжига моделирует физический процесс отжига металлов и стекла - процесс медленного охлаждения твердого тела, предварительно нагретого до высокой температуры. Ключевую роль в этом процессе играют отдельные частицы тела, которые осуществляют переход в жидкое состояние. В дальнейшем запускается процесс медленного охлаждения температуры тела, до момента образования кристаллической структуры при некоторой заданной температуре. Этот метод использует упорядоченный случайный поиск. В методе процесс остывания вещества и образования кристаллической решетки с минимальной энергией сопоставляется набору состояний вещества. На каждом шаге такого алгоритма происходит переход из текущего состояния в одно из соседних. Переход возможен тогда, когда разность целевой функции нового решения и целевой функции текущего решения не превышает заданного порога. При этом текущее решение заменяется на полученное новое решение. Если разность целевых функций превышает заданный порог, то выбирается другое соседнее решение и к нему применяются все те же операции. При понижении температуры наблюдается падение среднего значения целевой функции за счет того, что разброс уменьшается. Застой процесса появляется при низкой температуре, так как все реже возможно перейти в соседнее решение, что приводит к остановке алгоритма в одном из локальных оптимумов.

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

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

Метод имитации отжига относится к классу пороговых алгоритмов локального поиска [33]. Описание данного метода для решения различных вариантов транспортной задачи представлено в работе H. Kokubugata и H. Kawashima [154]. В 2007 году R. Bai, E. K. Burke и другие предложили адаптивную эвристическую селекцию для алгоритма имитации отжига при решении различных вариантов транспортной задачи [97]. Метод широко используется для решения различных оптимизационных задач.

2.4. Алгоритмы муравьиной колонии (Ant Colony Algorithm). Особую популярность данные алгоритмы получили в решении транспортной задачи в виду того, что разные варианты транспортной задачи имеет много схожего с задачей, которую приходится решать муравьям при поиске пути к пище. Суть этого метода перенята из природы. При поиске пищи муравьи двигаются в случайных направлениях, прокладывая путь, оставляя за собой особый фермент. Этот фермент со временем испаряется, поэтому, чем короче путь к пище, тем больше фермента на этом пути (на длительном пути фермент успевает испариться). Фермент привлекает других муравьев, и они также начнут исследовать это направление, при этом используя уже проложенный путь к пище. Отметим одно из достоинств - алгоритм не зацикливается в локальном оптимуме, так как испарение фермента позволяет выбрать кратчайший путь.

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

Впервые алгоритм применяется для решения задачи поиска рационального пути в графе, в докторской работе Marco Dorigo в 1991 году [126]. Описание применения алгоритма муравьиной колонии для решения задачи VRP представлено в [105] John E. Bella, Patrick R. Mc Mullen (2004 год). В 2007 году Paola Pellegrini, Daniela Favaretto и другие представили работу, где для решения транспортной задачи в постановке VRPTW предложили два варианта алгоритма муравьиной колонии, в решении используется сочетание этих двух алгоритмов, такое сочетание именуется Multiple Ant Colony Optimization [187]. В [108] Yu Bin, Yang Zhong-Zhena и другие (2009 год) предложили улучшенный алгоритм муравьиной колонии (Improved Ant Colony Optimization). В улучшенном алгоритме используется оператор мутации и новой функция феромона (ant-weight strategy).

2.5. Эволюционные стратегии (EA). Эволюционные стратегии относятся к классу эволюционных вычислений, как и генетические алгоритмы. Как и алгоритмы муравьиной колонии, эволюционные стратегии заимствованы из живой природы. Свое начало эти алгоритмы берут в работах Ingo Rechenberg [190] и Schwefel Hans-Paul [147]. Используется простая процедура селекции (селекция с усечением), а оператор создания потомков, как правило, только мутация. В алгоритме участвуют два объекта: родитель и потомок (иногда эту модель называют бинарной [1]). Исторически первое применение эволюционных стратегий выполнено при решении задачи проектирования колена трубопровода с оптимизацией формы сопла двигателя по критерию минимизации сопротивления. В работе [210] была рассмотрена задача доставки досок древесностружечных плит (ДСП), которая является частным случаем задачи 3L-CVRP и сводилась к транспортной задаче и одномерной упаковке (в своей работе авторы именуют задачу, как Multi-Pile Vehicle Routing Problem (MP-VRP)). Решение осуществлялось двумя методами: алгоритмом муравьиной колонии (Savings based Ant Colony Optimization) и алгоритмом поиск с запретами (Tabu

Search). В [138] для решения задачи 2L-CVRP предложили метод, основанный на поиске с запретами и усеченном алгоритме ветвей и границ (нижних границах). В [215] авторы представили управляемый поиск с запретами.

Параллельные алгоритмы решения задачи коммивояжера. В [87] предложен параллельный алгоритм решения задачи коммивояжера, основанный на применении рекуррентной сети Вана с использованием принципа WTA (winner takes all). В работе приводится вычислительный эксперимент, согласно которому скорость решения задачи уменьшается, но по точности предложенный алгоритм уступает методу Литлла. В [84] приводится распараллеливание метода ветвей и границ на базе библиотеки BNB-Solver. BNB-Solver является модульной объектно-ориентированной библиотекой, реализованной на языке C++. Библиотека BNB-Solver позволяет разрабатывать последовательные и параллельные приложения, основанные на методе ветвей и границ. Библиотека была использована при создании программ, предназначенных для решения задач о ранце с одним и несколькими ограничениями и задачи коммивояжера [57]. В работе [84] представлены результаты эксперимента, в которых отражается зависимость количества вводимых данных и времени (ускорения). При этом размерность задачи от 21 до 40, так как не хватает ресурсов для хранения матриц расстояний для каждого ветвления в случае больше 40 вершин. Приводятся графики, отображающие зависимость времени решения задачи от близости начального рекорда к решению. Работа алгоритма рассматривается на параллельной вычислительной системе с 1, 2, 4, 6, 8, 10 и 12 процессорами. Из результатов эксперимента очевидно, что при увеличении числа процессоров требуется более близкий к решению начальный рекорд, для того чтобы был выигрыш во времени. Это происходит из-за того, что процессоры не обмениваются рекордами, а обновляют рекорды лишь при получении очередного набора вершин для ветвления [84]. В [25] решение задачи

коммивояжера осуществляется на многопроцессорных системах с общей и распределенной памятью. Идея состоит в обработке после ветвления отдельно каждого множества. Для параллельной реализации алгоритма применяется библиотека BNB-Solver. Экспериментально сравнивается работа алгоритма, реализованного на многопроцессорной системе с распределенной памятью и общей памятью. Многопроцессорные системы с распределенной памятью показали лучшее ускорение в сравнении с многопроцессорными системами с общей памятью. Такой результат связан с плохой синхронизацией потоков при использовании общих ресурсов. В [39] представлен параллельный генетический алгоритм. В [5] реализовано распараллеливание обхода дерева поиска для решения задачи о рюкзаке на кластерной системе. Обход дерева может быть организован по нескольким ветвям одновременно и взаимно независимо, что позволяет использовать параллельные вычисления. Алгоритм реализован на основе MPI (системе кластерного типа) из 18 узлов. Результаты эксперимента в работе не представлены. В выводах работы утверждается, что алгоритм является универсальным, в сравнении с последовательными алгоритмами при увеличении числа процессоров ускорение возрастает (в некоторых случаях в 20 раз). А эффективность алгоритма зависит от нескольких факторов, связанных с количеством рассматриваемых подмножеств и числа ветвей, исходящих из корня. Отмечается, что при организации такого взаимодействия между процессами возникают проблемы, снижающие эффективность параллельного алгоритма, такие как: определение процесса, задача которого будет разбиваться на подзадачи; организация протокола связи с выбранным процессом; синхронизация работы всех процессов для избегания возникновения состояния дедлока. В [5, 25, 84] оценки временной сложности алгоритмов не представлены.

В [31] предложен фронтальный параллельный метод ветвей и границ (МВГ). Идея параллельного алгоритма состоит в том, что каждый процессор

решает свою ветвь, потом сравниваются полученные решения, и выбирается лучший вариант. Представлена нижняя оценка алгоритма р > 2л/£Т2 - 3, где р - параллельная сложность фронтального алгоритма, £ - количество

вершин в дереве ветвления. Доказано, что получаемая в результате параллельная сложность по порядку роста при стремлении размерности задачи к бесконечности совпадает с полученной нижней оценкой [31].

Список литературы диссертационного исследования кандидат наук Назарьянц, Елена Геворговна, 2018 год

СПИСОК ЛИТЕРАТУРЫ

1. Аверченков В.И., Казаков П.В. Эволюционное моделирование и его применение. Монография. - Москва: Флинта. - 2011. - 200 с.

2. Аккуратов Г.В., Березнев В.А., Брежнева O.A. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности. Межвузовский научный сборник. Уфа: УАИ.- 1990.- С. 145 - 154.

3. Бабаев Ф.В. Оптимальный раскрой материалов с помощью ЭВМ. -М.: Машиностроение. - 1982. - 168 с.

4. Бабаев Ф.В. Оптимизация раскроя материалов: Обзор. - М.: НИИМАШ. - 1978. - 72 с.

5. Беляев В.А., Тимошевская Н.Е. Распараллеливание обхода дерева поиска для решения задачи о рюкзаке на кластерной системе // Высокопроизводительные параллельные вычисления на кластерных системах: Материалы Междунар. науч.-практич. сем. / Под ред. проф. Р.Г. Стронгина. Н. Новгород: Изд-во Нижегор. ун-та. - 2002. - С. 16 - 20.

6. Вайнштейн А.Д. Задачи об упаковке прямоугольников в полосу (обзор) // Управляемые системы.- 1984. - Вып. 25. - C. 17 - 37.

7. Валеева А.Ф. Конструктивные методы для решения задач ортогональной упаковки и раскроя // Диссертация на соискание ученой степени доктора технических наук. Уфимский Государственный Авиационный Университет УФА. - 2006. - 265 с.

8. Валеева А.Ф. Метод динамического перебора для решения задач упаковки. // Материалы конференции «Ресурсосберегающие технологии и математическое обеспечение оптимизационных задач в системах автоматизированного проектирования» (ОПТИМ-2001). - 2001. - C. 29 - 32.

9. Валеева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки // Информационные технологии. - 2005. - № 10. - С. 36 - 43.

10. Валеева А.Ф., Сиразетдинова Т.Ю. Применение метаэвристики "иммитация отжига" для задачи гильотинного прямоугольного раскроя // Междунар. Уфимск. зимн. шк.- конф. по математике и физике для студенов, аспирантов и молодых ученых. - Уфа.- 2005. - С. 99.

11. Валеева А.Ф., Тоцков И.Е. Решение задачи трехмерной упаковки // Труды международной конференции «Комплексный анализ, дифференциальные уравнения, численные методы и приложения». Применение численных методов. Геометрические задачи. - Уфа: ИМВЦ УНЦ РАН - 1996. - С. 30 - 36.

12. Валеев С.С., Валеева А.Ф. Метод динамического перебора и применение нейросетей для задачи рационального использования ресурса // Международное научное издание «Проблемы принятия решений в условиях неопределенности». - 1997. - С. 188 - 198.

13. Валиахметова Ю.И. Гиперэвристические алгоритмы в задачах прямоугольного раскроя // Вестник НГУ: Информационные технологии. 2013. - №11 (2). - С. 36 - 43.

14. Ванидовский В.А., Лебедев О.Б. Двумерная упаковка в полуограниченную полосу на основе моделирования адаптивного поведения муравьиной колонии // Известия южного федерального университета. технические науки. - 2014. - № 7 (156) - С. 34 - 42.

15. Ватутин Э.И., Титов В.С., Емельянов С.Г. Основы дискретной комбинаторной оптимизации. - М.: АРГАМАК-МЕДИА - 2016. -270 с.

16. Вирт Н. Алгоритмы и структуры данных. - М.: Мир- 1989. - 360 с.

17. Гаврилкевич М.В., Солодовников В.И. Эффективные алгоритмы решения задач линейной алгебры над полем из двух элементов // Обозрение прикладной и промышленной математики. - 1995. -№ 2 (3). - С. 399 - 439.

18. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: Учебное пособие. - М: Физматлит. - 2006. - 320 с.

19. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы - учебное пособие. - Ростов-на-Дону: РостИздат. - 2004. - 400 с.

20. Гэри М., Джонсон Д. Вычислительные машины и трудноразрешаемые задачи - М.: Мир. - 1982. - 416 с.

21. Додонова М.М. Изучение различных постановок задачи о рюкзаке и методов их решения // Молодежь и наука: сборник материалов Х Юбилейной Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых с международным участием, посвященной 80 - летию образования Красноярского края [Электронный ресурс]. - Красноярск: Сибирский федеральный университет. - 2014. - Режим доступа: http://conf.sfu-kras.ru/sites/mn2014/directions.html, свободный.

22. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. - М: Физматлит. - 2003. - 432 с.

23. Ерзин А.И. Введение в исследование операций учебное пособие -Новосибирск, Новосибирский государственный университет. - 2006. - 100 с.

24. Жук С.Н. Приближенные алгоритмы упаковки прямоугольников в несколько полос // Дискрет. матем. - 2006. - 18 (1). - C. 91 - 105.

25. Игнатьев А.Л. , Посыпкин М.А., Сигал И.Х. Решение задачи коммивояжера на многопроцессорных системах с общей и распределенной памятью // Труды ИСА РАН.- 2009. - № 46. - С. 111 - 118.

26. Картак В.М., Рипатти А.В. Параллельный подход к решению задачи одномерной продолженной упаковки (1cbpp) с использованием технологии CUDA // Вестник Башкирского университета. - 2013. - № 18 (1). - С. 11 - 14.

27. Кацев С.В. Об одном классе дискретных минимаксных задач // Кибернетика. - 1979. - № 5. - C. 139 - 141.

28. Князева М.В. Сетевое планирование в условиях нечетких ограниченных ресурсов // Диссертация на соискание ученой степени кандидата технических наук. - Таганрог. -2011. - 189 с.

29. Колпаков Р.М, Посыпкин М.А. Асимптотическая оценка сложности метода ветвей и границ с ветвлением по дробной переменной для задачи о ранце", Дискретн. анализ и исслед. опер. - 2008.- №15 (1) - С. 58 - 81.

30. Колпаков Р.М., Посыпкин М.А. Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце // Дискретная математика. - 2010. - № 22 (1). - С. 58 - 73.

31. Колпаков Р.М., Посыпкин М.А., Сигал И.Х. О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ // Автоматика и телемеханика. - 2010. - № 10. - С. 156 - 166.

32. Корчевская О.В. Информационные модели и методы решения задач ортогонального раскроя-упаковки на основе конструктивных и нейросетевых подходов // Диссертация на соискание ученой степени кандидата технических наук. Красноярск, Сибирский государственный технологический университет. - 2009.- 147 с.

33. Кощеев И.С. Оптимизация доставки груза потребителям с учетом его размещения внутри транспортных средств на основе эвристических методов // Диссертация на соискание ученой степени кандидата технических наук. - Уфа. - 2015. - 135 с.

34. Кузнецова О.А. Двумерная упаковка на основе генетического поиска // Известия южного федерального университета. технические науки.-2006. -№ 63 (8). -С. 71 - 76.

35. Кузюрин Н.Н. Онлайновые алгоритмы упаковки прямоугольников в полосы//Российская конференция. Дискретная оптимизация и исследование операций. Владивосток. - 2007. - С. 57 - 60.

36. Курейчик В.В., Заруба Д.В., Запорожец Д.Ю. Иерархический подход при размещении компонентов СБИС // Известия ЮФУ. Технические науки. - 2014. - № 7(156). - С. 75 - 83.

37. Курейчик В.М. Алгоритмы одномерной упаковки элементов // Известия Южного федерального университета. Технические науки. - 2013. -№ 7 (144). -С. 8 - 11

38. Курейчик В.М. Генетические алгоритмы и их применение. -Таганрог. Издательство ТРТУ-издание второе, доп. - 2002. - 242 с.

39. Курейчик В.М. Параллельный генетический алгоритм. Модели и проблемы построения / В.М. Курейчик, Д.С. Кныш // Интегрированные модели и мягкие вычисления в искуственном интеллекте: сб. науч. тр. V Междунар. науч. - практич. конф., Москва :Физматлит. - 2009. - С. 41 - 51.

40. Курейчик В.М., Курейчик В.В. Генетические алгоритмы в комбинаторно-логических задачах искусственного интеллекта // Известия ТРТУ. Технические науки. - 1999. - С. 126 - 128.

41. Курейчик В.М., Потарусов Р.В. Проблема одномерной упаковки элементов // Известия Южного федерального университета. Технические науки. - 2006. - № 63 (8). - С. 88 - 93.

42. Лебедев О.Б., Зорин В.Ю. Упаковка на основе метода муравьиной колонии // Известия ЮФУ. Технические науки. Тематический выпуск. - 2010 - 113 (12). - С. 25 - 29.

43. Литтл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. - 1965. - № 1(1). - С. 94 - 107.

44. Марков В.Н., Руденко Е.А. Критерии эффективности методов решения задачи раскроя - упаковки плоских материалов // Научные труды КубГТУ. - 2014. - №6 - С. 316 - 322.

45. Мудров В.И. Задача о коммивояжере. - М.: «Знание» -1969. - 62 с.

46. Мухачева А.С., Чиглинцев А.В., Смагин М.А., Мухачева Э.А. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения // Приложение к журналу Информационные технологии. Машиностроение. -Москва. - 2001. - № 10. - 24 с.

47. Мухачева А.С., Ширгазин Р.Р. Задачи упаковки прямоугольников: рандомизированная эвристика на базе двойственной схемы локального поиска оптимума // Информационные технологии. М.: Машиностроение. -2003. - №5. - C. 18 - 23.

48. Мухачева А.С., Ширгазин Р.Р., Смагин М.А., Куреленков С.Х. Методы локального поиска оптимума прямоугольной упаковки с использованием двойственной схемы // Информационные технологии. М.: Машиностроение. - 2002. - №10. - C. 26 - 31.

49. Мухачева Э.А. Рациональный раскрой промышленных материалов. Примение в АСУ. - М.: Машиностроение. - 1984. - 176 с.

50. Мухачева Э.А., Мухачева А.С. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автомат. И телемех. - 2004. - №2 - С. 101 - 112.

51. Мухачева Э.А., Мухачева А.С., Чиглинцев А.В. Генетический алгоритм блочной структуры в задачах двумерной упаковки // Информационные технологии. Машиностроение. - Москва. - 1999. - № 11 -С. 13 - 18.

52. Мухачева Э.А., Хасанова Э.И. Гильотинное размещение контейнеров в полосе: комбинирование эвристических технологий // Новые технологии. Информационные технологии. - 2009. - № 11. - С. 8 - 14.

53. Мухлаева И.В. Решение задачи одномерной упаковки с помощью параллельного генетического алгоритма / И.В. Мухлаева // Перспективные информационные технологии и интеллектуальные системы.- 2000. - № 1. -С. 77 - 84.

54. Овезгельдыев А.О., Морозов А.В. Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута // Кибернетика и системный анализ. - 2013. - №5. - С. 112 - 124.

55. Окулов С.М., Пестов А.А., Пестов О.А. Информатика в задачах. -Киров: Изд-во ВГПУ. - 1998. - 343 с.

56. Петренко С.В. Оптимизация размещения двумерных геометрических объектов на анизотропном материале с использованием методов математического программирования // Диссертация на соискание ученой степени доктора технических наук. - Уфа. Уфимский государственный авиационный технический университет. - 2005. - 115 с.

57. Посыпкин М.А. Архитектура и программная организация библиотеки для решения задач оптимизации методом ветвей и границ на многопроцессорных вычислительных комплексах // Труды ИСА РАН.- 2006. - № 25. - С. 18 - 25.

58. Посыпкин М.А., Сигал И.Х. Верхняя оценка для ускорения в одной параллельной реализации метода ветвей и границ решения задач дискретной оптимизации/ Труды третьей международной конференции «параллельные вычисления и задачи управления» РАСО'2006. - Москва. - 2006. - С.897 -908.

59. Посыпкин М.А, Сигал И.Х. Применение параллельных эвристических алгоритмов для ускорения параллельного метода ветвей и границ // Журнал вычислительной математики и математической физики. -2007. - № 47 (9). - С. 1524 - 1537.

60. Потарусов Р.В. Гибридный параллельный группирующий генетический алгоритм для решения задачи упаковки блоков // Известия ЮФУ Технические науки Тематический выпуск: ИНТЕЛЛЕКТУАЛЬНЫЕ САПР. - 2008. - № 4 (81) - С.42 - 45.

61. Рихтер М.Р. Алгоритм трассировки при проектировании СБИС // Научно-технические ведомости СПбГПУ. - 2011. - № 5(133). - С. 111 - 118.

62. Романовский И.В. Алгоритмы решения экстремальных задач. - М.: Наука. - 1977. - 170 с.

63. Романовский И.В., Христова Н.П. Решение дискретных минимаксных задач методом дихотомии // ЖВМ и МФ. - 1973. - №13(5). - С. 1200 - 1209.

64. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки // Диссертация на соискание ученой степени доктора техн. наук. - Таганрог. ТРТУ. - 1999. - 546 с.

65. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. I// Кибернетика и системный анализ. - 2007. - № 1. -С. 165 - 183.

66. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. II // Кибернетика и системный анализ. -2007. - № 2. - С. 161 - 174.

67. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ. - 1994. - № 5. - С. 3 - 23.

68. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. - 1995. - № 4. - С. 13 - 37.

69. Ромм Я.Е., Заика И.В. Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида // Кибернетика и системный анализ. - 2011. - № 2. -С. 165 - 180.

70. Ромм Я.Е., Назарьянц Е.Г. Детерминированный параллельный алгоритм решения задачи об одномерном булевом рюкзаке на основе сортировки и видоизменения формул Виета / ТИ имени А.П. Чехова (филиал) ФГБОУ ВПО "РГЭУ (РИНХ)". - Таганрог, 2015. - 45 с. Деп. в ВИНИТИ 18.02.2015, № 32 - В2015.

71. Ромм Я.Е., Назарьянц Е.Г. Одномерная и двумерная параллельная упаковка // XXVII Международная конференция: «Актуальные проблемы в

современной науке и пути их решения» (Россия, г. Москва, 23 июня 2016 г.) // Евразийский Союз Ученых (ЕСУ) - № 6 (27) Часть 2. - г. Москва, 2016. -С. 50-52.

72. Ромм Я.Е., Назарьянц Е.Г. Параллельная двумерная упаковка // XVII всероссийский симпозиум по прикладной и промышленной математике (осенняя открытая сессия) - 1-8 октября, №4, том 23, 2016 г., г. Сочи-Дагомыс. - С. 383-384.

73. Ромм Я.Е., Назарьянц Е.Г. Параллельная двумерная упаковка на основе видоизменения формул Виета и сортировки // Современные наукоемкие технологии. - 2016. - № 6 (часть 2) - С. 280-287.

74 . Ромм Я.Е., Назарьянц Е.Г. Параллельное решение задачи коммивояжера методом ветвей и границ с применением сортировки // Международная научно-практическая конференция «Информационные технологии: актуальные вопросы, перспективы и инновации», секция -технические науки - 15 августа 2016 г., г. Пенза, издательство «Наука и Просвящение, г. Пенза, 2016. - С. 20 - 28.

75. Ромм Я.Е., Назарьянц ёЕ.Г. Параллельные алгоритмы решения булевой задачи о рюкзаке на основе сортировки и видоизменения формул Виета. // Фундаментальные исследования. - 2015. - № 2. (часть 12). - С. 2575-2580.

76. Ромм Я.Е., Назарьянц Е.Г. Параллельные алгоритмы решения некоторых задач комбинаторной оптимизации // материалы Всероссийской начно-практической конференции с международным участим. Технические науки. «Аспекты развития науки, образования и модернизации промышленности» - 20-21 апреля, 2017г., г. Таганрог - издательство Донской гос. тех. ун-т. - Ростов-на-Дону, ДГТУ, 2017. - С. 35 - 41.

77. Ромм Я.Е., Назарьянц Е.Г. Параллельные детерминированные алгоритмы одномерной упаковки с линейной и логарифмической временной сложностью // XIII Международная научно-техническая конференция

«Новые информационные технологии и системы» - 23-25 ноября, 2016 г., НИТиС-2016, г.Пенза, С. 272 - 276.

78. Ромм Я.Е., Назарьянц Е.Г. Параллельный детерминированный алгоритм двумерной упаковки на основе сортировки и видоизменения формул Виета / ТИ имени А.П. Чехова (филиал) ФГБОУ ВО "РГЭУ (РИНХ)". Таганрог. - 2016. - 39 с. Деп. в ВИНИТИ 14.04.2016, № 61-В2016.

79. Ромм Я.Е., Назарьянц Е.Г. Полиномиальная сложность параллельной формы метода ветвей и границ решения задачи коммивояжера // Известия ЮФУ. Технические науки. - 2015. - № 4 (165). - С. 44-55.

80. Ромм Я.Е., Назарьянц Е.Г. Преобразование метода ветвей и границ для решения задачи коммивояжера на основе максимально параллельной сортировки / ТГПИ. - Таганрог - 2013. - 25 с. Деп. в ВИНИТИ 30.09.2013, № 279-В2013.

81. Ромм Я.Е., Назарьянц Е.Г, Дзюба А.С. Преобразование и численное моделирование метода ветвей и границ для решения задачи коммивояжера на основе максимально параллельной сортировки / ТГПИ. - Таганрог, 2014. - 49 с. Деп. в ВИНИТИ 30.09.2014, № 279-В2013.

82. Руднев А.С. Алгоритмы локального поиска для задач двумерной упаковки // Диссертация на соискание ученой степени кандидата технических наук, Новосибирский государственный университет, Новосибирск. - 2010. - 104 с.

83. Сергиенко И.В., Емец О.А., Емец А.О. Задачи оптимизации с интервальной неопределенностью: метод ветвей и границ // Кибернетика и системный анализ. - 2013. - №5. - С. 38 - 51.

84. Сигал И.Х., Бабинская Я.Л., Посыпкин М.А. Параллельная реализация метода ветвей и границ в задаче коммивояжера на базе библиотеки BNB - Solver / Труды ИСА РАН - 2006. - № 25 - С. 26 - 36.

85. Сигал И.Х, Иванова А.П.. Введение в прикладное дискретное программирование. - М.: ФИЗМАТЛИТ. - 2004. - 240 с.

86. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений // В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. - Л. - 1982. - № 118. - С. 159 - 187.

87. Тарков М.С., Дугаров Г.А. Параллельный алгоритм решения задачи коммивояжера c использованием рекуррентной нейронной сети // Институт физики полупроводников СО РАН им. А.В. Ржанова, г. Новосибирск. - 2010.

- № 2. - С. 4 - 9.

88. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. II // Кибернетика. - 1982. - № 3. - С. 18 - 31.

89. Файзрахманов Р.И. Конструктивный вероятностный алгоритмдля задачи размещения кругов и прямоугольников // Вестник УГАТУ, управление, вычислительная техника и информатика. Уфа.- 2010. - №. 14 (4 (39)). - С. 132 - 138.

90. Филиппова А.С. Методы решения задач ортогональной упаковки на базе технологии блочных структур // Автореферат диссертации на соискание ученой степени доктора технических наук. - Уфа: Изд-во Уфимского Государственного авиационного технического университета. - 2006. - 30 с.

91. Хамидуллин Р.Р., Бригаднов И.А., Морозов А.В. Методы и средства защиты компьютерной информации: Учебное пособие. - СПб.: СЗТУ. - 2005.

- 178 с.

92. Щербина О.А. Метаэвристические алгоритмы для задач комбинаторной оптимизации (обзор) // Таврический вестник информатики и математики. - 2014.- №1 (24). - С. 56 - 72.

93. Adamowicz M., Albano A. Nesting two - dimensional shapes in rectangular modules // Computer-Aided Design. - 1976 - № 8 (1) -P. 27 - 33.

94. Anderson R.J., Mayr E.W., Warmuth M.K. Parallel approximation algorithms for bin packing // Information and Computation. - 1989. - № 82 (3). -pp. 262 - 277.

95. Armas J., Miranda G., León C. Parallelisation of the two-dimensional guillotine strip packing / cutting problem [HHTepHeTpecypc http: //www2 .epcc.ed.ac.uk/~europa/HPCE2/Reports/0645_deArmas .pdf]

96. Back T., Fogel D.B., Michalewicz Z., eds. Handbook of Evolutionary Computation. - Oxford University Press. - 1997. - 940 p.

97. Bai R; Burke E.K; Gendreau M., Kendall G. A Simulated Annealing Hyper-heuristic: Adaptive Heuristic Selection for Different Vehicle Routing Problems. // In proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2007). - Paris, France. - 2007. -pp. 67 - 70.

98. Bak S., Blazewicz J., Pawlak G., Plaza M. A parallel branch-and-bound approach to the rectangular guillotine strip cutting problem // INFORMS Journal on Computing. - 2011. - 23 (1). - pp. 15 - 25.

99. Baker B.S., Coffman E.G.Jr., Rivest R.L. Orthogonal packings in two dimensions // SIAM Journal on Computing - 1980. - № 9 (4). - pp. 846 - 855.

100. Baker M., Ayechew M.A. A genetic algorithm for the vehicle routing problem // Computers & Operations Research. - 2003. -№ 30(5).-pp. 787-800.

101. Baldacci R., Bartolini E., Mingozzi A. An Exact Algorithm for the Pickup and Delivery Problem with Time Windows // Operations Research. - 2010.

- № 59 (2). - pp. 414 - 426.

102. Bansal L., Correre J.R., Kenyon C., Sviridenko M. Bin packing in multiple dimensions: inapproximability results and approximation schemes // Mathematics of Operations Research. - 2006. - № 31. - pp. 31 - 49.

103. Barricelli N. Esempi numerici di processi di evoluzione // Methodos. -1954. - pp. 45 - 68.

104. Baz D.E., Hifi M., Saadi T. Peer-to-peer solution of 2D cutting stocks problems. // Andreas Brieden et al. 11th Cologne - Twente International Workshop on Graphs and Combinatorial Optimization, Munich, Germany. - 2012. - pp. 116

- 120.

105. Bella J.E., McMullen P.R. Ant colony optimization techniques for the vehicle routing problem // Advanced Engineering Informatics. - 2004. - № 18. -pp. 41 - 48.

106. Bhardwaj G., Pandey M. Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU // International Journal of Computer Applications. - 2014. - № 99 (16). - pp. 9 - 13.

107. Bhardwaj G., Pandey M. Parallel implementation of travelling salesman problem using ant colony optimization // International Journal of Computer Applications Technology and Research - 2014. - № 3 (6). - pp. 385 - 389.

108. Bin Y., Zhong-Zhena Y., Baozhen Y. An improved ant colony optimization for vehicle routing problem // European Journal of Operational Research. - 2009. - pp. 171 - 176.

109. Bortfeldt A., Gehring H. Two metaheuristics for strip packing problems // Proceedings of the 5th International Conference of the Decision Sciences Institute, Athen. - 1999. - №2. - pp. 1153 - 1156.

110. Bozejko W., Kacprzak L., Wodeck M., Scherer R., Tadeusiewicz R., Zadeh L., Zurada J. (eds). Parallel coevolutionary algorithm for three -dimensional bin packing problem // Springer International Publishing Switzerland.

- 2015. - № 1 (9119). - pp. 319 - 328.

111. Braysy O., Gendreau M. Tabusearch heuristics for the vehicle routing problem with time windows. // Sociedad de Estadistica e Investigaci6n Operativa.

- 2002. - №10 (2). - pp. 211-237.

112. Brusco M.J, Thompson G.M, Jacobs L.W. A morph-based simulated annealing heuristic for a modified bin-packing problem // Journal of the Operational Research Society. - 1997. - № 48 (4). - pp. 433 - 439.

113. Burke E.K., Guo Q., Kendall G.A Hyper-Heuristic Approach to Strip Packing Problems // Parallel problem solving from nature, PPSN XI. Krakow. -2010. - № 2 - pp. 465 - 474.

114. Cesar R. A parallel tabu search algorithm using ejection chains for the vehicle routing problem // Meta-Heuristics. - 1996. - pp. 661 - 675.

115. Chazelle B. The bottom-left bin packing heuristic: An efficient implementation // IEEE Trans. Compututing. - 1983. - № 32. - pp. 697 - 707.

116. Chen D.Z., Huy X., Huang Y., Li Y., Xuz J. Algorithms for congruent sphere packing and applications // Symposium on Computational Geometry. -2001. - pp. 212 - 221.

117. Clark G., Wright J.V. Scheduling of vehicles from a central depot to a number of delivery points // Operations Research. - 1964. - № 12.- pp. 568 - 581.

118. Cook S.A. The complexity of theorem - priving procedures // Proc. 3rd Annual ACM Symp. On the Theory of Computing. - 1971. - pp. 151 - 158.

119. Crainic T.G., Perboli G., Tadei R. TS2Pack: A two-level tabu search for the three-dimensional bin packing problem // European Journal of Operational Research. - 2009. - pp. 744 - 760.

120. Dagli C.H., Hajakbari A. Simulated annealing approach for solving stock cutting problem Systems // Man and Cybernetics. Conference Proceedings., IEEE International Conference. - 1990. - pp. 221 - 223.

121. Dantzig G.B., Ramser J.H. The truck dispatching problem // Management Science. - 1959. - № 6. - pp. 80 - 91.

122. Desrosiers J., Soumis F., Desrochers M. Routing with time windows by column generation // Networks. - 1984. - № 14. - pp. 545 - 565.

123. Dessouky M., Lu Q., Zhao J., Leachman R. An exact solution procedure for determining the optimal dispatching times for complex rail networks // IIE Transactions. - 2006. - № 38. - pp. 141 - 152.

124. Dimitrijevic V., Milosavljevic M., Markovic M. Branch and bound algorithm for solving a generalized traveling salesman problem // Univ. Beograd. Publ. Elektrotehn. Fak.Ser. - 1996. - № 7. - pp. 31 - 35.

125. Dong S., Hong X., Wu Y., Xiu Z., Gu J. VLSI placement with pre-placed modules based on less flexibility first principles // Proc. ASIC, 2001. -Beijing: IEEEPress. - 2001. - pp. 106 - 109.

126. Dorigo M. Optimization, learning, and natural algorithms // Dissertation for the degree of Doctor PhD Thesis, Politecnico di Milano. Italy. -1991.

127. Dowsland K.A., Dowsland W.B. Packing problems // European Journal of Operational Research. - 1992. - № 56. - pp. 2 - 14.

128. Dyckhoff H. A typology of cutting and packing problems // European Journal of Operational research. - 1990. - № 44. - pp. 145 - 159.

129. Dyckhoff H., Finke U. Cutting and packing in production and distribution.- Heidelberg: PhysicaVerlag, 1992. - 258 p.

130. Dyckhoff H., Scheithauer G., Terno J. Cutting and packing (C&P), in: M. Dell'Amico, F. Maffioli, S. Martello, (eds.). Annotated bibliographies in combinatorial optimization, Wiley, Chichester. - 1997. - pp. 393 - 413.

131. Farahani R.Z., Rezapour S., Kardar L. Logistics Operations and Management: Concepts and Models. Waltham: Elsevier, 2011. - 486 p.

132. Fernández A., Gil C., Baños R., Montoya M.G. A parallel multi-objective algorithm for two-dimensional bin packing with rotations and load balancing // Expert systems with applications. - 2013. - №. 40 (13 (1)). - pp. 5169 - 5180.

133. Festa P., Resende M.G.C. GRASP: An annotated bibliography // Essays and Surveys on Metaheuristics / C.C. Ribeiro and P. Hansen, eds. - Kluwer Academic Publishers - 2002. - pp. 325 - 367.

134. Festa P., Resende M.G.C. GRASP: basic components and enhancements // Telecommunication Systems. - 2011. - № 46 (3) - pp. 253 - 271.

135. García L., Coromoto L., Miranda G., Rodriguez C. A parallel algorithm for the two-dimensional cutting stock problem //SPRING Euro - Par, Parallel processing. - 2006. - № 4128. - pp. 821 - 830.

136. Gehring H., Bortfeld A. A genetic algorithm for solving the container loading problem. // International transactions in operational research. - 1997. - № 4 (5/6). - pp. 401 - 418.

137. Gehring H., Bortfeldt A. A parallel genetic algorithm for solving the container loading problem // International Transactions in Operational Research. -2002. - № 9. - pp. 497 - 511.

138. Gendreau M., Hertz A., Laporte G. A tabu search heuristic for the vehicle routing problem // Management science. - 1994. - № 40 (10). - pp. 1276 -1290.

139. Gilmore P., Gomory R. A Linear Approach to the cutting-stock problem // Operations research. - 1961. - №. 9. - pp. 849 - 859.

140. Gilmore P., Gomory R. The theory and computation of knapsack functions // Operations Research. - 1966. - № 14. - pp. 1045 - 1075.

141. Glover F. Future paths for integer programming and links to artificial intelligence // Computers & Operations Research. - 1986. - № 131. - pp. 533 -549.

142. Glover F. Tabu Search, part I // ORSA, Journal of Computing. - 1989. - № 1. - pp. 190 - 206.

143. Glover F., Kochenberger G., eds. Handbook of metaheuristics. -Norwell: Kluwer Academic Publishers, 2002. - 556 p.

144. Goldberg M. The packing of equal circles in a square // Math. Magazine. -1970. - № 43. - pp. 24 - 30.

145. Goodman E.D., Tetelbaum A.Y., Kureichik V.M. A genetic algorithm approach to compaction, bin packing and nesting problems. - Michigan State University: Technical Report 940702, Case Center for Computer - Aided Engineering and Manufacturing, 1994 - 71 p.

146. Han X, Ye D., Zhou Y. Improved online hypercube packing. // Central European Journal of Operations Research. - 2010. - № 18 (2). - pp. 221 - 239.

147. Hans-Paul S. Cybernetic evolution as strategy for experimental research in fluid mechanics (in german). Diploma Thesis. Hermann Fottinger -Institute for Fluid Mechanics, Technical University of Berlin. - 1965.

148. Hernández-Pérez H., Salazar-González J.-J. The one - commodity pickup-and-delivery travelling salesman problem // Lecture Notes in Computer Science. - 2003. - № 2570. - pp. 89 - 104.

149. Hifi M., M'Hallah R. Approximate algorithms for constrained circular cutting problems computers & operations research. - 2004. - № 31 (5). - pp. 675 -694.

150. Hoff A., Gribkovskaia I., Laporte G., Lokketangen A. Lasso solution strategies for the vehicle routing problem with pickups and deliveries // European journal of operational research. - 2007. - № 192 (3). - pp. 755-766.

151. Huang W. Chen D. An efficient quasi-human heuristic algorithm for solving the rectangle-packing problem // Informs Journal on Computing: - 2011. -№ 23 (1). - pp. 15-25.

152. Jiang H., Zhang S., Xuan J., Wu Y. Frequency distribution based hyper-heuristic for the bin-packing problem // European conference on evolutionary computation in combinatorial optimization, Torino. - 2011. - № 6622. - pp. 118 - 129.

153. Kallrath. J. Cutting circles and polygons from area-minimizing rectangles. // Journal of global optimization. - 2009. - № 43. - C. 299 - 328.

154. Kawashima H., Kokubugata H. Application of simulated annealing to routing problems in city logistics // Simulated annealing / Tan Cher Ming. -Vienna: I-Tech education and publishing. - 2008. - 154 p.

155. Kellerer H., Pferschy U., Pisinger D. Knapsack problems. - Berlin: Springer, 2004. - 546 p.

156. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing // Science. - 1983. - № 220 (4598). - pp. 671 - 680.

157. Kravitz S. Packing cylinders into cylindrical containers // Mathematics Magazine. - № 40. - 1967. - pp. 65 - 71.

158. Kubach T., Bortfeldt A., Tilli T.,Gehring H. Parallel greedy algorithms for packing unequal spheresinto a cuboidal strip or a cuboid. // Fernuniv., Fak. Für Wirtschaftswiss. - 2009. - 20 p.

159. Land A.H., Doig A.G. An automatic method of solving discrete programming problems. - Econometrica. - 1960. - № 28 (3). - pp. 497 - 520.

160. Laporte G., Mercure H., Nobert Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem // Networks. - 1986. - № 16. -pp. 33 - 46.

161. Laporte G., Nobert Y., Desrochers M. Optimal routing under capacity and distance restrictions // Operation Research. - 1985. - № 33. - pp. 1050 - 1073.

162. Leinberger W., Karypis G., Kumar V. Multi-Capacity bin packing algorithms with applications to job scheduling under multiple constraints // Parallel processing, international conference. - 1999. - pp. 404 - 412.

163. Lenstra J.K., Rinnooy Kan A.H.G. Complexity of vehicle and scheduling problems // Networks. - 1981. -№. 11 (2). - pp. 221 - 227.

164. Leon C., Miranda G., Rodriguez C., Segura C. 2D Cutting Stock Problem: a New Parallel Algorithm and Bounds // European conference on parallel processing, Euro-Par. - 2007. - pp. 795 - 804.

165. Levine J., Ducatelle F. Ant colony optimization and local search for bin packing and cutting stock problems // Journal of the operational research society. -2004. - № 55. - pp. 705 - 716.

166. Li Y., Tao Y., Wang F.A compromised large-scale neighborhood search heuristic // European Journal of Operational Research. - 2009. - № 199 (2). - pp. 553 - 560.

167. Liberti L. Branch-and-Bound for the Travelling Salesman Problem // LIX, Ecole Polytechnique, F - 91128 Palaiseau. - 2011. - pp.1 - 8.

168. Lin T.D., Hsu C.C., Hsu L.F. Optimization by ant colony hybrid local search for online class constrained bin packing problem // Applied Mechanics and Materials. - 2013. - № 311. - pp. 123 - 128.

169. Liu D., Teng H. An improved BL - algorithm for genetic algorithm of the orthogonal packing of rectangles. // European Journal of Operation Research. -1999. - №112 (2). - pp. 413 - 420.

170. Lodi A., Martello S., Monaci M. Two-dimensional packing problems: a survey // European Journal of Operational Research. - 2002. - 141 (2). - pp. 241 - 252.

171. Lodi A., Martello S., Vigo D. Heuristic algorithms for the three-dimensional bin packing problem // European Journal of Operational Research. 2002. - № 141. - pp. 410 - 420.

172. Lodi A. Martello S., Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems // INFORMS J. Comput. -1999. - № 11 - pp. 345 - 357.

173. Lodi A., Martello S., Vigo D. Recent advances on two-dimensional bin packing problems. // Discrete Applied Mathematics. - 2002. - 123. - pp. 379 -396.

174. Lodi A., Martello S., Vigo D. TSpack: A unified tabu search code for multi-dimenstional bin packing problem // Annals of Operations Research. -Kluwer Academic Pulishers. - 2004. - № 131. - pp. 203 - 213

175. Lopez-Camachoa E.,Terashima-Marin H., Ross P., Ochoa G. A unified hyper-heuristic framework for solving bin packing problems // Expert Systems with Applications. - 2014. - № 41 (15). - pp. 6876 - 6889.

176. Mak V., Ernst A.T. New cutting-planes for the time and/or precedence-constrained ATSP and directed VRP // Mathematical Methods of Operations Research. - 2007. - № 66. - pp. 69-98.

177. Martello S., Toth P. Knapsacks problems: algorithms and computer implementations.//John Wiley and sons Ltd, 1990. - 296 p.

178. Martello S., Vigo D. Exact solution of two-dimensional finite bin packing problem // Management Science. - 1998. - № 44 (3). - pp. 388 - 399.

179. Martins G.H.A., Dell R.F. The minimum size instance of a Pallet Loading. Problem equivalence class // European Journal of Operational Research. - 2007. - № 179. - pp. 17 - 26.

180. Mladenovic N., Hansen P. Variable neighborhood search // Comput. Oper.Res. - 1997. - № 24. - pp. 1097 - 1100.

181. Moccia L., Cordeau J.-F., Laporte G. An Incremental Tabu Search Heuristic for the Generalized Vehicle Routing Problem with Time Windows // Journal of the Operational Research Society. - 2012. - № 63. - pp. 232 - 244.

182. Mukhacheva E.A., Belov G.N., Kartak V.M., Mukhacheva A.S. Linear one-dimensional cutting-packing problems: numerical experiments with sequential value correction method (SVC) and a modified branch-and-bound method (MBB) // PesquisaOperacional. - 2000. - № 20 (2). - pp. 153 - 168.

183. Nurfahizullfwah W., Shaiful M., Shamsunarnie M.Z., Zainuddin Z.M., Fuad M. Genetic algorithm for vehicle routing problem with backhauls // Journal of Science and Technology. - 2012. -№ 4(1). - pp. 9-16.

184. Ochi L.S., Silva M.B., Drummond L. Metaheuristics based GRASP and VNS for solvimg the traveling purchaser problem // MIC'2001 - 4thMetaheuristics Intern, conf. Porto - 2001. - pp. 489 - 494.

185. Osman I. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem // Annals of Operations Research. - 1993. - № 41 (4). - pp. 421 - 451.

186. Peetersa M., Degraeveb Z. Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem // European Journal of Operational Research. - 2006. - № 170 (2). - pp. 416 - 439.

187. Pellegrini P., Favaretto D., Moretti E. Multiple ant colony optimization for a rich vehicle routing problem: a case study// Knowledge-Based Intelligent

Information and Engineering Systems. - Vietrisul Mare. - 2007. - № 2. - pp. 627

- 634.

188. Poshyanonda P., Bahrami A., Dagli C.H. Two dimensional nesting problem: artificial neural network and optimization approach Neural Networks // 1992. IJCNN., International Joint Conference. - 1992. - № 4. - pp. 572 - 577.

189. Rao R.L., Iyengar S.S. Bin - Packing by Simulated Annealing // Computers Math. Applic. - 1994. - № 27(5).- pp. 71 - 82.

190. Rechenberg I. Evolutionsstrategie - Optimierung technischer Systemenach Prinzipien der biologischen Evolution (PhD thesis). - 1971.

191. Resende M., Ribeiro C.C. Greedy randomized adaptive search procedures // Chapter 8 in Handbook of Metaheuristics, F. Glover and G.A. Kochenberger, eds., Kluwer - 2003. - pp. 219 - 249.

192. Ropke S., Cordeau J.F. Models and Branch-and-Cut Algorithms for Pickup and Delivery Problems with Time Windows // Journal Networks. - 2007. -№. 49 (4). - pp. 258-272.

193. Ropke S., Cordeau J.F., Laporte G. Branch-and-Cut-and-Price for the Pickup and Delivery Problem with Time Windows // Operations Research. - 2008.

- № 43 (3). - pp. 267 - 286.

194. Ross P. Hyper-heuristics. In Burke, E. & Kendall, G. (Eds.). Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Springer-Verlag, 2004. - pp. 529-556.

195. Shor P.W. How to pack better than Best Fit: Tight bounds for average-case on-line bin packing // Proc. 32nd Annual Symposium on Foundations of Computer Science. - 1991. - pp. 752 - 759.

196. Singh N.K., Baidya S. A novel work for bin packing problem by ant colony optimization // International Journal of Research in Engineering and Technology. - 2013. - pp. 71 - 73.

197. Skorin-Kapov N. Routing and wavelength assignment in optical networks // European Journal of Operational Research. - 2007. - № 177. - pp. 1167 - 1179.

198. Sontrop H., Horn P., Uetz M. Fast ejection chain algorithms for vehicle rounting with time windows // Hybrid methaheuristics / авт. книги M.J. Blesa C. Blum, A. Roli, M. Sampels. - Berlin: Springer-Verlag Berlin Heidelberg, 2005. - pp. 78 - 89.

199. Stawowy A. Evolutionary based heuristic for bin packing problem // Computers and Industrial Engineering. - 2008. - № 55 (2). - pp. 465 - 474.

200. Stoyan Yu., Chugay A. Packing cylinders and rectangular parallelepipeds with distances between them into a given region // Europ. J. of Operat. Research. - 2009. - № 197. - pp. 446 - 455.

201. Tang X., Tian R., Wong D.F. Fast evaluation of sequence pair in block placement by longest common subsequence computation // IEEE Trans. Computer Aided Design of Integrated Circuits and Systems. - 2001. - № 20. - pp. 1406 -1413.

202. Tang X., Tian R., Wong D.F. Fast-SP: A fast algorithm for block placement based on sequence-pair // Proc. ASP-DAC, 2001. - New York: ACM. 2001. - pp. 521 - 526.

203. Tarnowski T., Terno J., Scheithauer G. A polynomial time algorithm for the guillotine pallet loading problem // INFOR. - 1994. - № 32. - pp. 275 -287.

204. Tavlaridis-Gyparakis K. A cutting plane Method for the team orienteering Problem with Pickups, deliveries, time windows and capacity constraints // Chios: University of the Aegean School of Business Department of Financial & Management Engineering. - 2012. - pp. 1 - 49.

205. Terashima-Marín H., Ross P., Farías-Zárate C.J., López - Camacho E., Valenzuela - Rendón M. Generalized hyper-heuristics for solving 2D Regular and

Irregular Packing Problems // Annals of Operations Research. - 2010. - № 179 (1). - pp. 369 - 392.

206. Terno J., Lindemann R., Scheithauer G. Zuschnittprobleme und ihre praktische Lösung. - Leipzig: Verlag Harry Deutsch, Thun und Frankfurt / Main, und Fachbuchverlag, 1987. - 207 p.

207. Thiebaut D. 2D - packing images on a large scale // INFOCOMP 2013: The Third International Conference on Advanced Communications and Computation. - 2013. - pp. 19 - 26.

208. Toth P., Vigo D. A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls // European Journal of Operational Research. - 1999. - № 113. - pp. 528 - 543.

209. Toth P., Vigo D. The vehicle routing problem. - Philadelphia: SIAM Monographs on Discrete Mathematics and Applications, 2002. - 363 p.

210. Tricoire F, Doerner K.F., Hartl R.F., Iori M. Heuristic and exact algorithms for the multi-pile vehicle routing problem // OR Spectrum. - 2011. -№ 33 (4). - pp 931 - 959.

211. Voudouris C., Tsang E.P.K. Guided local search joins the elite in discreteoptimization // Proceedings of DIMACS Workshop on ConstraintProgramming and Large Scale Discrete Optimization. - New Jersey :Rutgers. - 1998. - pp. 29 - 40.

212. Wiener R. Branch and Bound Implementations for the Traveling Salesperson Problem // Journal of Object Technology. -2003. - №1 (2). - pp. 65 -86.

213. Wu Y.L., Huang W., Lau S., Wong C.K., Young G.H. An effective quasi-human based heuristic for solving the rectangle packing problem // Europ. J. Oper. Res. - 2002. - № 141. - pp. 341 - 358.

214. Young N.E. Sequential and parallel algorithms for mixed packing and covering // Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. - 2001. - pp. 538 - 546.

215. Zachariadis E.E., Tarantilis C.D., Kiranoudis C.T. A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. // European Journal of Operational Research. - 2009. - № 195. - pp. 729 - 743.

216. Zhao X., Shen H. A parallel algorithm for 2D square packing. // Proceedings of the 14th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT'13. - 2013. - pp. 1 - 5.