Модификация муравьиного алгоритма для динамической задачи коммивояжёра

Корнилов Вадим Юрьевич

Модификация муравьиного алгоритма для динамической задачи коммивояжёра

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

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36645f1be77c40d58e58

UUID: 1aabf113-3fc7-4fe4-8ba6-f8b6ea67f024

Язык: Русский

Опубликовано: почти 8 лет назад

Просмотры: 61

Корнилов Вадим Юрьевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 570749 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ – ПРОЦЕССОВ УПРАВЛЕНИЯ КАФЕДРА МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ЭКОНОМИЧЕСКИХ СИСТЕМ Корнилов Вадим Юрьевич Выпускная квалификационная работа бакалавра Модификация муравьиного алгоритма для динамической задачи коммивояжёра Направление 010400 Прикладная математика и информатика Заведующий кафедрой, доктор физ.-мат. наук, профессор Захаров В.В. Заведующий кафедрой, доктор физ.-мат. наук, профессор Захаров В.В. Рецензент, ведущий инженерпрограммист ООО "Интермедиа" Щегряев А. Н. Санкт-Петербург 2016

Оглавление 1. ВВЕДЕНИЕ...............................................................................................3 1.1. ИСТОРИЯ ЗАДАЧИ TSP......................................................................... 4 1.2. ПОСТАНОВКА ЗАДАЧИ TSP.................................................................. 5 Математическая модель задачи TSP.................................................6 1.3. ПОСТАНОВКА ЗАДАЧИ TDTSP.............................................................7 Математическая модель задачи TDTSP............................................7 2. ОБЗОР АЛГОРИТМОВ......................................................................... 9 2.1. BIOLOGY-INSPIRED ALGORITHMS......................................................... 9 2.2. ANT COLONY OPTIMIZATION (ACO).................................................. 11 2.3. PARTICLE SWARM OPTIMIZATION (PSO)............................................ 13 2.4. ARTIFICIAL BEE COLONY...................................................................14 2.5. ВЫВОДЫ............................................................................................. 15 3. МУРАВЬИНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ TDTSP....................17 3.1. ПАРАМЕТРЫ ЗАДАЧИ TDTSP............................................................. 17 3.2. ВРЕМЯ ПУТИ МАРШРУТА................................................................... 17 3.3. ЖАДНЫЙ АЛГОРИТМ.......................................................................... 18 3.4. АЛГОРИТМ ЛОКАЛЬНОГО ПОИСКА.....................................................19 3.5. ИНИЦИАЛИЗАЦИЯ ФЕРОМОНОВ.........................................................19 3.6. ОСНОВНАЯ ПРОЦЕДУРА.....................................................................20 4. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ...........................................22 4.1. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ ДЛЯ ЭВРИСТИЧЕСКОГО АЛГОРИТМА......................................................................................................... 23 4.2. ПРОВЕРКА УРОВНЯ ДИНАМИЧЕСКОЙ УСТОЙЧИВОСТИ.....................24 4.3. РЕЗУЛЬТАТЫ ПРОВЕРКИ НА ДИНАМИЧЕСКУЮ УСТОЙЧИВОСТЬ..................25 5. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ.................................................... 27 5.1. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ ДЛЯ ACO...........................................27 2

5.2. РЕЗУЛЬТАТЫ ПРИМЕНЕНИЯ ДИНАМИЧЕСКОЙ АДАПТАЦИИ...............28 5.3. АНАЛИЗ РЕЗУЛЬТАТОВ........................................................................ 29 6. ЗАКЛЮЧЕНИЕ..................................................................................... 30 7. СПИСОК ЛИТЕРАТУРЫ.................................................................... 31 3

1. Введение Объем рынка транспортно-логистических услуг растет во всем мире, и в связи с этим решение различных задач маршрутизации становится все более актуальной проблемой. Основной целью в данных задачах является построение маршрутов для транспортных средств, обслуживающих определенное множество клиентов. При этом выбор неудачного маршрута влечёт за собой дополнительные издержки по транспортировке товара. Класс задач маршрутизации в настоящее время является очень широким. Распространённым и самым ранним примером является задача коммивояжера или задача TSP (Travelling Salesman Problem). Для исследования была выбрана задача коммивояжера, зависящая от времени или задача TDTSP (Times Dependent Travelling Salesman Problem). Алгоритмы, решающие данную задачу, разделяют на точные и эвристические. Так как задача коммивояжера принадлежит классу NPтрудных задач, очевидно, что точные алгоритмы применимы только для малоразмерных задач и не подходят для решения реальных задач. Поэтому, как правило, используют эвристические алгоритмы. Они генерируют решения, приближенные к оптимальному, но за меньшее по сравнению с точными методами время. Особенностью многих эвристиче ских алгоритмов является разнообразие решений, получаемых при применении алгоритма к одному и тому же примеру. Это обусловлено тем, что при построении маршрута различным вариантам продолжения маршрута соответствует вероятность их выбора, так как постоянный выбор наилучшего продолжения на каком-либо шаге алгоритма в итоге не всегда дает оптимальное решение. Ввиду больших расстояний, в рассматриваемых на практике задачах любое улучшение алгоритма позволит существенно уменьшить расхождение полученных решений с оптимальным. В первой главе рассмотрены задачи TSP и TDTSP, представлены их математические модели. Во второй главе приведен обзор литературы по 4

природным алгоритмам и их сравнение. В третьей главе подробно рассмотрено применение муравьиного алгоритма (ACO) для построения решения задачи TDTSP. В четвертой дается определение динамической адаптации как критерия оценки алгоритмов и проведена оценка ACO. В пятой главе предложен метод динамической адаптации алгоритма, а так же его сравнение с ACO. В шестой главе описана проделанная работа и полученные результаты. 1.1. История задачи TSP Откуда пошли истоки задачи коммивояжера, остаётся неясным. саму проблему и рекомендации, основанные на опыте для её решения, начинают упоминать в руководстве для коммивояжеров от 1832г. Также в нем рассматривают некоторые примеры маршрутов по Германии и Швейцарии, но там не содержится математической постановки задачи. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру, который сформулировал её на математическом коллоквиуме в 1930 году так: «Мы называем проблемой посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, её решают многие путешественники) задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известны» [1]. Современное название «Задача странствующего торговца» (Traveling Salesman Problem) , п р е д л о ж и л Хасслер Уитни и з Принстонского университета. В1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и применили для её решения метод отсечений. Используя этот метод [2], они построили путь коммивояжера для одной частной постановки задачи с 49 городами и обосновали его оптимальность. 5

В 1972 году Ричард Карп д о к а з а л NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, доказывалась NP-трудность задачи коммивояжера. В марте 2005 года задача с 33 810 узлами была решена: был вычислен путь длиной в 66 048 945 и доказано отсутствие более коротких путей. В апреле 2006 было найдено решение для экземпляра с 85 900 узлами. 1.2. Постановка задачи TSP Задача коммивояжёра может быть представлена в виде математической модели — графа G=(V , A) [3]. Множество вершин V ={v0 , v 1 ,… , vn−1 } в графе соответствуют городам в задаче коммивояжёра, множество рёбер A={ ( v i , v j )|vi , v j ∈ V , i≠ j } – обозначают дороги, соединяющие пары городов. Каждое ребро из множества A имеет вес – d ij . В зависимости от формулировки задачи, вес ребра ( v i , v j ) из графа G может означать время перехода, стоимость поездки или расстояние между соответствующими вершинами vi и v j . Контур, включающий каждую вершину графа G хотя бы один раз, называется маршрутом коммивояжера. Так же контур, включающий каждую вершину графа G ровно один раз, называется гамильтоновым контуром. Тогда задачей коммивояжера называется задача поиска гамильтонова контура наименьшей общей длины. 6

Математическая модель задачи TSP Пусть I ={0 ,… ,n−1} — множество индексов вершин из тестовой задачи. Определим целевую функцию f как суммарное расстояние маршрута, покрывающего все вершины из рассматриваемой задачи. Параметрами задачи являются элементы матрицы веса D={ d ij∨i , j ∈ I } . В случае асимметричной матрицы D задача коммивояжера моделируется ориентированным графом. То есть следует также учитывать, в каком направлении находятся ребра. В симметричном случае количество возможных маршрутов вдвое меньше асимметричного случая и выполняется равен ство d ij =d ji . Дальше будем рассматривать задачи только с симметричной матрицей расстояний Переменными задачи являются элементы бинарной матрицы переходов между вершинами X ={xij ∨i , j ∈ I } , которые равны 1, если в построенном маршруте для тестовой задачи присутствует ребро (vi , v j ) , 0 - иначе. Тогда задача коммивояжёра может быть сформулирована и решена в рамках линейного целочисленного программирования. [4] [5] [6]. Требуется найти [7]. f =∑ ∑ i ∈ I j ≠i , j ∈ I c ij x ij → min С учетом условий ∑ j≠ i, j∈ I x ij =1 ,∀ i ∈ I (1) ∑ j ≠ i ,i ∈ I x ij =1 ,∀ j ∈ I (2) v i−v j +n x ij ≤ n−1,1 ≤ i≠ j ≤ n (3) Ограничения (1) и (2) обеспечивают посещение города только один раз. Неравенства (3) обеспечивают связность маршрута обхода городов, т.е. он не может состоять из двух и более не связных частей 7

1.3. Постановка задачи TDTSP Задача TDTSP расширяет оригинальную задачу TSP, добавляя в неё параметр времени t , с изменением которого изменяются значения бинарной матрицы веса D ( t )= {d ij ( t )|i , j ∈ I } . Как и TSP, TDTSP о п р е д е л е н а н а г р а ф е G=(V , A ) , гд е V = { v 0 , v 1 ,… , vn−1 }−¿ множество вершин и ребер. Вершина v0 A={ ( v i , v j )|vi , v j ∈ N ,i≠ j } множество - депо. Для каждого ребра ( v i , v j ) известно время d ij (t) , затрачиваемое на его прохождение. Таким образом, задача TDTSP сводится к нахождению кратчайшего маршрута, начинающегося в вершине v0 и заканчивающегося там же, в котором коммивояжер проходит через каждую вершину один раз, и очередность прохождения влияет на остальное время пути. Математическая модель задачи TDTSP П а р а м е т р а м и з а д ач и : п а р а м е т р в р е м е н и t ∈ I , элем енты симметричной матрицы веса D ( t )= {d ij ( t )|i, j ∈ I } . Переменные модели: x tij - принимает 1, если ребро ( v i , v j ) входит в маршрут, 0 - в обратном случае; t обозначает очередность прохождения рёбер. Необходимо минимизировать целевую функцию [8] f =∑ t d ij ( t ) x ij →min ∑ i ∈ I j ≠i , j ∈ I С учетом условий ∑ j≠ i, j∈ I x ij =1 ,∀ i ∈ I (4) ∑ j ≠ i ,i ∈ I x ij =1 ,∀ j ∈ I (5) v i−v j +n x ij ≤ n−1,1 ≤ i≠ j ≤ n (6) 8

t x ij =1,∀ t ∈ I ∑ i, j∈I (7) Ограничения (4) и (5) обеспечивают посещение города только один раз. Ограничение (6) обеспечивают связность маршрута обхода городов, т.е. он не может состоять из двух и более не связных частей. Ограничение (7) отвечает за то, что в любой момент времени t коммивояжёр движется только по одному ребру, что обеспечивает выполнения условия строго последовательного прохождения маршрута. 9

2. Обзор алгоритмов Природно-естественные алгоритмы (Nature-inspired algorithms, NAs), черпают вдохновение из сложных, но хорошо организованных атрибутов природы. Природно-естественные алгоритмы стали очагом исследования изза неэффективности точных алгоритмов (проблема увеличения размера задачи), таких как: линейное программирование [9], динамическое программирование [10], конечных элементов [11]. В общем NAs моделируют взаимодействие и иногда взаимозависимость природных элементов: растений, животных и рек. Самым популярным классом алгоритмов среди NAs является класс биологических алгоритмов. Однако некоторые NAs появились благодаря химии или физике. Они включают в себя Harmony Search (HS) алгоритмы, Intelligent Water Drop (IWD), имитации отжига (SA) и Black Hole (BH) [12]. В данном исследовании нас интересуют биологические алгоритмы. 2.1. Biology-inspired algorithms Биологические алгоритмы (Biology-inspired algorithms,BAs) можно разделить на три больших класса, а именно: эволюционные алгоритмы (EvolutionaryAlgorithms, EAs) , которые основаны на принципах эволюций; алгоритмы роевого интелекта (Swarm Intelligence, SI), которые моделируют коллективное поведение у растений и животных; экологические алгоритмы, которые связаны с внешне- или внутривидовыми конкурентными процессами или кооперативным взаимодействием в пределах природных экосистем[13]. Эволюционные алгоритмы, как правило, моделируют итеративный прогресс, включающий в себя: рост, развитие, размножение, отбор и выживание, – как это наблюдается в популяциях животных. EAs создает допустимые решения, которые оптимизируются, переходя из поколения в поколение. К этой категории относятся: генетическое программирование (Genetic Programming, GP), алгоритм рисового поля (Paddy Field Algorithm, 10

PFA), эволюционная стратегия (Evolutionary Strategies, ES), генетический алгоритм (Genetic Algorithm, GA) и алгоритм Differential Evolution, (DE) [12]. Можно обратить внимание, что эксперты имеют различные мнения относительно классификации DE как эволюционного алгоритма. Причастие DE к эволюционным алгоритмам вытекает из использования им "Эволюции" в качестве одного из основного параметров (так же как и другими EAs). В текущее время весомые доводы не могут характеризовать класс DE как биологический алгоритм [14]. Вторая категория BAs – это алгоритмы роевого интеллекта (SI), которые касаются коллективно–социального поведения организмов. Основой для SI является коллективный интеллект групп простых агентов: насекомых, рыб, птиц, бактерий, червей и других животных, - воссозданный по анализу их поведения в реальной жизни. К примеру, у этих животных появляются исключительные навыки в разведке, когда они работают вместе как группа. Эти алгоритмы отслеживают коллективное поведение животных, которые проявляют децентрализованное поведение, самостоятельно организованные структуры при выполнении поиска пищи. Примерами таких алгоритмов являются: пчелиные колонии (the Bee Colony Optimization, ВСО), алгоритм светлячка (Firefly Algorithm, FFA), метод роя частиц (Particle Swarm Optimization, PSO), муравьиный алгоритм (Ant Colony Optimization, ACO), алгоритм искусственных колоний пчел (Artificial Bee Colony, ABC), Bacteria Foraging Algorithm (BFA), и так далее [15]. Третья категория BAs – экологические алгоритмы, которые связаны с внешне- или внутривидовыми конкурентными проце ссами или кооперативным взаимодействием в пределах природных экосистем. Экосистема состоит из живых организмов вместе с их абиотической средой, с которой организмы взаимодействуют, такие как: вода, воздух и почва. Сотрудничество между организмами включает в себя разделение труда и представляет собой суть их социальности. Некоторые из взаимодействий являются кооперативными, другие конкурентоспособными. Они приводят к 11

сложной и гармоничной сбалансированности в экосистеме. Алгоритмы в этой категории являются PS2O, о снованные на методах сорняка и биогеографической оптимизации [16]. Рассмотрим несколько алгоритмов из класса SI более подробно. 2.2. Ant Colony Optimization (ACO) Алгоритм ACO - это способ оптимизации на основе популяции, который был разработан Марко Дориго и успешно применяется для решения несколько NP-трудных задач комбинаторной оптимизации. Этот алгоритм был вдохновлен поведением колоний муравьев, особенно их поведением в процессе поиска пищи в реальной жизни. Обычно муравьи, когда покидают свои гнезда, начинают беспорядочно перемещаться вокруг районов, окружающих их гнезда в поисках пищи. Если какому-либо из муравьев попадается пища, он сначала собирает некоторые кусочки пищи и на своем пути обратно в гнездо распыляет химическое вещество под названием феромон как способ общения с его коллегами, что он нашел источник пищи. Другие близлежащие муравьи воспринимают аромат феромона и начинают двигаться в направлении феромонова следа. После того, как они обнаруживают источник пищи, они обновляют феромоный след для предупреждения других муравьев, возвращаясь, В течение времени несколько муравьев получают эту информацию и следуют по образовавшемуся пути Еще одна интересная часть поведения муравьев заключается в том, что как только они возвращаются в гнездо, они оптимизируют свой маршрут. За короткое время муравьи создают более короткий маршрут к источнику пищи, чем предыдущие маршруты. Кроме того, если на более короткий маршрут поместить препятствие, делая движения невозможным, муравьи способны найти еще один короткий маршрут из доступных вариантов обходов препятствия. 12

Были различные модификации муравьиных алгоритмов, начиная с исходной Ant System (AS), переходя к Ant Colony System (ACS), затем MinMax System Ant (ММАС), а затем Ant Colony Optimization (ACO) алгоритмам, и так далее [17]. В ACO колония муравьев на каждой итерации высчитывает вероятность, на основе которой муравей в узле i выбирает следующий узел j , к которому будет двигаться дальше. Выбор узла зависит от значения следа феромона τ ij (t) и доступный эвристичестик ηij . В TSP ηij =1/ d ij . Так что муравей перемещается от места P tij= { α [ τ ij ( t ) ] [ ηij ] , if j ∈ N i α ∑ [ τ ij ( t ) ] [ ηij ] β l ∈ Ni с вероятностью k k 0 , иначе представляет собой след феромона, ηij локальную эвристическую информацию, t k j β Здесь τ ij (t) Ni i к представляет представляет собой итерацию, представляет собой множество узлов, в которые муравей может пойти, а α и β являются параметрами, которые управляют изменением следа феромона. К концу итерации след феромона на каждом ребре i j будет модернизирована с помощью следующего уравнения: best τ ij ( t+1 )=( 1− p )∗τ ij ( t ) +∆ τ ij (t) (8) В формуле (8), τ ij ( t +1 ) представляет собой след феромона в итерации t +1 , п а р а м е т р ρ ∈[0.1,0.9] от в еч а е т з а с ко р о с т ь и с п а р е н и я феромона. Количество феромона, оставленным лучшим муравьём, представлен в виде: ∆τ best ij { (t )= f ( s 1 best если лучший муравей прошел в итераци t по дуге ij (t )) 0 , иначе , (9) В (9), s best f ( s best ( t ) ) представляет собой стоимость лучшего решения (t ) . 13

2.3. Particle Swarm Optimization (PSO) Метод роя частиц базируется на социальном поведение стаи птиц или ко с я к е р ы б , я в л я е т с я о д н и м и з б и о л о г и ч е с к и-вдохновленных вычислительных методов, разработанным Эберхартом и Кеннеди [18]. Этот алгоритм получает решения, используя рой частиц, где каждая частица представляет собой вариант решения. По сравнению с эволюционно вычисляемой парадигмой, рой похож на население, и частица представляет собой индивидуума. В поисках решения частицы перелетают через многомерное пространство, где положение каждой частицы регулируется в соответствии с собственным опытом и информацией от соседей. Вектор скорости управляет процессом оптимизации, а также обрабатывает опыт каждой частицы и учитывает информацию в рамках ее окрестности. PSO имеет два управляющих уравнений для поиска решения - (10) и (11). Рассмотрим v tij+1 = x ( vtij +θ1 U 1 ( btij −x tij ) +θ2 U 2 ( bt( n ) ij −x tij ) ) +∆ τ best ij ( t ) (10) Гд е vtij+1 представляет собой текущую скорость, vtij - предыдущая скорость, х -фактор сужения, θ1 и θ2 коэффициенты ускорения, U 1 и U2 - случайные числа, btij - наилучшее положение отдельных частиц, x tij - текущее положение, и bt( n ) ij лучше положение роя. Следующее уравнение в PSO отвечает за положение роя t +1 t t +1 x ij = x ij +x ij (11) В алгоритме PSO частицы движутся в области целевой функции f :Θ ∈ R n , где n представляет переменные, которые будут оптимизированы. Каждая частица на определенной итерации связана с тремя векторами: (a) Текущая позиция, обозначается через х : Этот вектор записывает текущую позицию конкретной частицы. 14

(b) Текущая скорость, обозначается через v : Этот вектор сохраняет направление частицы поиска. (c) Индивидуальное личное положение, обозначается через b : Этот вектор содержит наилучшее решение конкретной частицы до текущего времени, с того момента как начался поиск (момента начала выполнения алгоритма). В дополнение к этому, отдельные частицы связаны с лучшей частицей в рое, которую алгоритм PSO отслеживает на каждой итерации, чтобы помочь направить в область поиска перспективных решений [19]. 2.4. Artificial Bee Colony Этот алгоритм, который был вдохновлен поведением пчелиного роя при сборе меда, был предложен Karaboga и Akay в 2009 году [20]. Он ищет решения за счет использования трех классов пчел: разведчики, пчелы наблюдателей и рабочие пчелы. Разведчиками являются те, которые летают над пространством поиска в поиске решений (источник питания). Пчелы наблюдатели – это те, которые остаются в гнезде в ожидании доклада разведчиков, в то время как рабочие пчелы после просмотра танца пчел разведчиков присоединяются к уборке источника питания (эксплуатации). Особенность этого алгоритма заключается в его возможностях – трансформации пчел. Например, разведчик может преобразовать в рабочую пчелу, когда он (разведчик) участвует в уборке источника пищи, и наоборот. Так правило, пчелы могут изменять свои статусы в зависимости от потребностей алгоритма в определенный момент времени. В этом алгоритме источником питания представляет собой решение задачи оптимизации. Объем нектара в качестве источника питания представляет собой качество (пригодность) решения. Кроме того, предполагает, что каждая из рабочих пчел использует только один источник пищи, а это означает, что число рабочих пчел также соответствует количеству источников пищи. Пчелы v m с более высоким разведчики всегда ищут новые источники пищи ⃗ 15

xm количеством нектара и/или качество ⃗ в близлежащем районе. Пчелы оценивают пригодность нектара, используя v mi =x mi +θmi ( xmi −x ki ) , (12) гд е i это случайно выбранный индекс; θmi представляет собой случайное число в заданном диапазоне; x ki - источником пищи. Качество x m ) рассчитывается по следующей формуле: решения fit m ( ⃗ { 1 x ,if f m ( ⃗ xm ) >0 fit m ( ⃗ x m ) = 1+ f m ( ⃗ x m) 1+ fit m ( ⃗ xm ) ,if f m ( ⃗ x m ) <0 (13) Из вышеизложенного ясно, что есть небольшое сходство (10) в PSO и (12) в ABС, так как каждый алгоритм вычитает переменные из лучших личных и индивидуальных частиц/пчел. Для PSO, вычитаемая переменная представляет нынешнее положение, а для АВC - это разведанное местоположение. Тем не менее, эти два уравнения отличаются в нескольких отношениях: в то время как PSO использует x (будучи фактором сужения) или ω (как фактор инерции, в некоторых версиях PSO), нет таких эквивалентов в АВC. К тому же, в то время как PSO использует случайные числа ( U 1 и U 2 ), в АВC их не содержит, только обучаемые параметры. Так же, PSO использует коэффициенты ускорения ( θ1 и θ2 ); в ABС их нет. Даже если ABC использует ту же методику поиска нахождений решений, алгоритмы совершенно различны. 2.5. Выводы Для оптимизации поиска решений ACO использует технику строительства путей, в то время как PSO и ABC используют технику улучшения пути. PSO использует фон Неймана в качестве лучшей техники для распространения информации [21], а ACO получает хорошие результаты, 16

используя топологию кольца [22]. Топология фон Неймана позволяет частицам соединяться с соседними частицами на востоке, западе, севере и юге. Эффективность состоит в том, что конкретная частица взаимосвязана с четырьмя другими частицами, окружающими её. АСО использует топологию кольца. Конкретный муравей, распыляя феромон, изменяет текущее его количество на пути, по которому он идет, что в целом для системы обеспечивает быстрый и легкий поиск новых маршрутов. 17

3. Муравьиный алгоритм для задачи TDTSP Выше был рассмотрен ACO для простой задачи коммивояжера. Хотя задача TDTSP является усложненным вариантом задачи коммивояжера, но алгоритм муравьиной оптимизации при применении к TDTSP изменений в структуре не произвел. Изменились только тип и представление начальных данных. Ниже представлено описание параметров для задачи TDTSP и основные функции модифицированного муравьиного алгоритма, который был предложен для решения задачи TDTSP в [23]. Значения параметров для алгоритма взяты из этой же статьи. 3.1. Параметры задачи TDTSP Весовая матрица для задачи TDTSP обозначает время, которое требуется затратить, чтобы добраться от одного узла к другому. Изменение матрицы веса D (t ) узла в j задается формулой, гд е d i , j (nup ) для момента nup , целую часть, Δt означает оригинальные значения, di, j (0) которые даются для задачи TSP, t время пути из i - текущее время, скобки [] обозначают обновляемый интервал времени, С f коэффициент изменения дорожной ситуации (0 ≤ C f <1) , и rand ∈[−1,1] - рандомный параметр. d i , j ( nup ( t ) )=d i , j ( nup ( t )−1)∗(1+С f ∗rand) nup ( t )=[ t ] ∆t В работе значения d i , j ( nup ( t ) ) рассчитываются заранее для всех nup ( t ) , что ускоряет работу алгоритма. Когда коммивояжер покидает депо, параметр t =0 и он обязательно должен вернуться в него. 3.2. Время пути маршрута Время, необходимое для путешествия вокруг всего маршрута S, будет называться временем маршрута T (S). Время путешествия между городами 18

рассчитывается с использованием времени t i , когда коммерсант достигает одного из концов дуги. Время маршрута для решения S можно рассчитать по следующим формулам: n−1 T ( S )=∑ d i ,i +1 ( nup ( t i ) ) i=0 t i= { 0,∧i=0 t i−1 +d i−1, i (nup ( t i−1 ) ),∧иначе 3.3. Жадный алгоритм Жадный алгоритм [24] широко используется в генерации начальных решений с нуля путем итеративного добавления компонентов решения в первоначально пустое решение до тех пор, пока решение не будет завершено. В TSP решение (тур) построен путем добавления города с самым маленьким значением времени пути. Алгоритмический план приведен ниже, где i , j и k являются номерами городов, S p представляет собой частичное решение (то есть, список посещаемых городов), и N ' представляет собой набор городов, который еще не посетили. Алгоритм 1: Жадный алгоритм (next) 1: На входе получаем индекс следующего города 2: i=next; 3: S p= ( 0 i ) ; //первый город всегда депо 4 : N ' =N − { 0 } ; 5: Пока ( N ' не пустое){ 6: ' ' N = N −{i} ; 7: k =arg min d i ,i +1 ( nup ( t ) ) ; j ∈N ' 8: S p =S p +k ; 9: i=k ; 10: } 11: Возвращаем полученный маршрут S p . 19

3.4. Алгоритм локального поиска Для улучшения уже построенного маршрута воспользуемся алгоритмом из класса итерационных эвристик. Он обрабатывает готовый маршрут, построенным один из конструктивных методов, в нашем случае муравьиным алгоритмом и жадным алгоритмом, последовательно улучшая его на каждой итерации. Один из самых популярных - 2-окружение (англ.: 2-opt[24]), который используется в основном алгоритме. Алгоритм 2-opt. удаляет два случайных несмежных ребра из маршрута и соединяет две получившиеся части маршрута другим способом. Существует единственный вариант для вставки двух новых рёбер, дабы полученное после произведенной операции решение было допустимым, т.е. являлось бы гамильтоновым циклом. Данные операции производятся при условии, что новый маршрут короче (быстрее) предыдущего. Пример операции 2-opt. продемонстрирован на Error: Reference source not foundError: Reference source not found. Рис 1. Пример операции 2-окружение Алгоритм завершает свою работу, если не существует возможности улучшить готовый маршрут с помощью описанных операций. 3.5. Инициализация феромонов Инициализирование уровня феромона происходит по следующей ´ процедуре, где S0 k , k=1 , n−1 является решением, улучшенным за счет локального поиска (2-OPT) после того, как было построено с помощью жадного алгоритма, r (0 ≤ r ≤ 1) параметр. Алгоритм 2: Инициализация феромонов 1: От i=1 до i=n−1 с шагом 1 запускаем Жад.алг.( i ); 20

2: Улучшаем все полученные решения с помощью локальной оптимизации; 3 : τ i , j =τ 0 , для ∀(i, j)∈ A ; //берется из формулы (14) 4: Обновляется τ i , j по формуле (15); τ i , j =τ 0= n−1 n−1 r ∑ T ( S0k ) k =1 (14) n−1 1 k τ i , j =( 1−r ) τ i , j +r δ τi, j ∑ n−1 k=1 (15) { 1 ,(i , j)∈ S0 k δ τ = T ( S0 k ) 0 , иначе k i, j Здесь первое слагаемое в правой части (15) означает равномерное испарение феромона, а второй член означает централизацию феромонов вокруг локальных оптимальных решений. Параметр r показывает отношение децентрализации инициализируемого феромонного уровня и централизации его. При г=0 предлагаемый способ похож на работу MMAS [25]. В противоположность этому, когда г=1 , инициализируемый феромон распространяется только на дугах, содержащихся в локальных оптимальных решениях. Если локальный поиск не используется, предложенный метод со значением r=0 эквивалентен MMAS. 3.6. Основная процедура Общая процедура модифицированного муравьиного алгоритма приведена ниже, где маршрут Sib является лучшим решением в текущей итерации и маршрут S gb является лучшим решением, найденным с начала алгоритма. Вероятность выбора следующего узла можно рассчитать по формуле (16). 21

t i,j p ( t )= { α β [ τ i , j ( t ) ] [ ηi , j ( t ) ] ,if α β ( ) ( ) τ t η t ∑ [ i,j ] [ i,j ] l ∈ Ni j∈N k k 0 ,иначе (16) ηij ( t )= 1 di , j ( nup ( t ) ) Алгоритм 3: Основная процедура 1: Считываем данные задачи TDTSP; 2: Задаем паратры для алгоритма; 3: Инициализируем феромон; ( 4: Запускаем цикл, который повториться q раз q<1+ 5: От k =1 до k=n−1 с шагом 1{ 6: 7: 8: 9: ) n { 100 Строим решение Sk используя (16); } Sib =arg min T ( Sk ) ; ´ k= 1, n−1 S Если ( T (¿¿ ib)<T (S gb ) то S gb=Sib ; ¿ 10: Обновляем фером исбользуя только глобальное решение; 11:} 12: Выдаем финально решение S gb ; 22

4. Динамическая устойчивость В настоящее время существуют различные критерии оценок эффективности эвристических алгоритмов. Один из них - это точность алгоритма. Для её определения алгоритм для каждого класса задач тестируется на тестовых примерах из открытых библиотек. Для задач с большой размерностью, в основном оптимальные решения не известны, это связано со сложностью расчетов точными алгоритмами. Поэтому для этих задач сохраняются лучшие решения (англ. Best known solution), полученные другими алгоритмами. Раздел с BKS постоянно обновляется. Также важным критерием оценки алгоритма является скорость алгоритма. Методы теории сложности для оценки времени работы эвристических алгоритмов плохо применимы, причина тому их сложная структура. Поэтому под критерием сложности эвристических алгоритмов принимают непосредственное время работа алгоритма. Время работы алгоритма очень сильно зависит от характеристик оборудования, на котором запускают алгоритм и само качество реализации кода алгоритма. Поэтому данный критерий почти не рассматривается при оценке эвристических алгоритмов. Также известны такие критерии, как гибкость и простота [26]. Под гибкостью понимается способность алгоритма учитывать дополнительные ограничения и условия, которые принимаются к задаче. Пример гибкости очень хорошо наблюдается в ACO, когда реализация алгоритма для задачи TSP была перенесена на задачу TDTSP. Простота заключается в лёгкости программной реализации алгоритма. В работе [27] предложен алгоритм для нахождения решения транспортной задачи (Vehicle Routing Problem), который сам изменяет значения своих параметров в ходе поиска решения. 23

4.1. Динамическая устойчивость для эвристического алгоритма В многошаговых динамических многоагентных играх есть свойство сохранение оптимальности решения в каждой подзадаче с начальными условиями на оптимальной траектории, которая построена в начальный момент [28]. То есть у участников кооперации нет никакой объективной мотивации, следуя по выбранной траектории, чтобы отклоняться от неё в любой момент времени. В отношении эвристических алгоритмов для задач TSP этот критерий именуется как динамическая устойчивость. Данное свойство для транспортной задачи означает, что данное решение сохраняет свойство оптимальности в каждой подзадаче при реализации начального маршрута. Это возможно только для оптимального решения, т.е. полученного точными методами. Эвристические алгоритмы, как правило, генерируют динамически неустойчивые решения. Пусть S – произвольное решение задачи TDTSP. Разобьем его на две +¿ ¿ −¿ ∪ S . Функция T (S ' ) части: ¿ S=S принимает значения времени, затраченного на прохождение части S' , входящую в маршрут S . Обозначим ~ V множество вершин маршрута +¿ ¿ S v 0 —начальная вершина и пусть ~ +¿ ~ ~ v0 , ¿ S . Применим алгоритм для вершин из множества V , где д е п о . П у с т ь ~S – полученный маршрут. Теперь можно маршрута v n−1 – сформулировать определение динамической устойчивости решения. 24

Определение 1. Решение S , для которого выполняется +¿ , любом разбиении на −¿ и S ¿ S ¿ +¿ ¿ S ¿ T¿ при называется динамически устойчивым или состоятельным во времени. 4.2. Проверка уровня динамической устойчивости Для описания определения экспериментального уровня динамической устойчивости алгоритма введем следующие обозначения: P={ p1 , p2 , … , pl } – множество тестовых примеров; R ( pi )= { r 1 ( pi ) , r 2 ( pi ) , … , r m ( pi ) } – множество сгенерированных решений для тестового примера p1 ; K – кол-во частей разбиения полученных решений; Q—количество запусков алгоритма проверки на динамическую устойчивость для одного тестового примера; b (r j ( pi ) ) — количество раз, когда решение ri тестового примера pi потеряло устойчивость при общем количестве запусков проверок Q. Определение 2. Экспериментальным уровнем динамической устойчивости алгоритма будем называть величину, задаваемую формулой ¿ R ( p i )∨¿ b(r j ( p i )) ¿ R ( pi )∨¿ ∑ ¿ j =1 1 ¿ ¿ M ∨¿ ¿ 1 ¿ con=1− ∑¿ Q|M| i=1 Проверка решения на динамическую устойчивость происходит по следующему алгоритму: Шаг1. i=1, j=1 , q=1. Шаг2. k =1 . Шаг3. t= T ( r j ( pi ) ) K , Множество ~ – множество, состоящее из всех V вершин маршрута r j ( pi ) , которые были пройдены после времени t∗k , 25

соответственно +¿ ( pi ) r j¿ – часть маршрута r j ( pi ) , которая была пройдена r j ( pi ) коммивояжером после времени t∗k , Генерируем решение ~ для множества вершин ~ V . Шаг4. Если +¿ ( pi ) r j¿ ¿ +¿ ( pi ) ¿ rj T¿ не верно то решение неустойчиво, q=q+1 , идем на Шаг2. иначе k =k +1 , и проверяем Если k ≠ K то идем на Шаг3; иначе решение устойчиво, идем на Шаг5. Шаг5. q=q+1 j= j+1, q=1 и если q <Q , переходим на Шаг2. Если q=Q , то и е сли j <n , то переходим на Шаг2. Е с л и j=n , то i=i+1, j=1, q=1 и если i<¿ P∨¿ , то переходим на Шаг2, иначе СТОП. Не трудно заметить, что кол-во динамически неустойчивых решений будет меньше, чем общее кол-во запусков алгоритма. Из этого следует, что оценка con ≤ 1 , и чем выше её значение, тем выше уровень динамической устойчивости и лучше работает исследуемый алгоритм. 4.3. Результаты проверки на динамическую устойчивость Для проверки уровня динамической устойчивости муравьиного алгоритма для задачи TDTSP были взяты 5 тестовых задач из стандартной библиотеки Travelling Salesman Problem Library [29]. Значение параметров для: |P|=5, M=10, K=5, R=25. Результаты приведены в таблице1. Для каждой из задач было сгенерировано по 25 различных решений. Для каждого решения проводилось 10 тестов. Исходный маршрут разбивался на 5 периодов. Если решение становилось в ходе проверки динамически неустойчивым, то текущий тест прекращался, а результат фиксировался. После завершения пятого периода проводить эксперименты не имеет смысла, т.к. маршрут обхода городов будет закончен. задача Кол-во дин. неус. решений 26

Eil51 Eil76 Eil101 KroA200 Lin318 Сумма Количество экспериментов 1 период 2 период 3 период 4 период 250 250 250 250 250 1250 120 147 110 90 78 545 70 43 58 32 28 231 20 21 24 11 8 84 3 2 5 3 1 14 Кол-во дин. уст. решений 37 37 53 114 135 376 Таблица 1 Оценка динамической устойчивости ACO для TDTSP Количество экспериментов, в которых начальное решение является динамически устойчивым после всех периодов, отличается для каждой тестовой задачи. Это обусловлено уникальной топологией исходных данных в задачах. Стоит заметить, что с увеличением размерности задачи коэффициент динамической устойчивости также увеличивается. Среднее значение экспериментального уровня динамической устойчивости муравьиного алгоритма для решения задачи Time-Depend Travelling Salesman Problem равно 0,6504 con ACO=0,6504 Данное значение является довольно низким: только четверть сгенерированных на начальном этапе решений сохраняют свойство оптимальности в процессе своей реализации. Это означает, что существуют другие маршруты, которые можно получить динамически с помощью того же эвристического алгоритма, значения целевой функции которых будет меньше по сравнению с начальным решением. Алгоритм динамического улучшения эвристических алгоритмов будет подробнее рассмотрен в следующей главе. 27

5. Динамическая адаптация Используя определения динамической устойчивости и проанализировав полученные данные в предыдущей главе, замечаем, что если после периода k начальное решение не соответствует критерию динамической устойчивости, т.е. для оставшейся части узлов было найдено решение лучше, то коммивояжеру нужно продолжить движение по нему. Таким образом, данные действия обеспечат то, что суммарная стоимость итогового маршрута будет меньше изначального. Сама идея постоптимизации была рассмотрена в статье [30], в ней рассматривалась идея сохранения оптимальности решения, когда после получения начального оптимального решения в задачу случайным образом добавлялся или убирался узел. Сама область, на которой базируется данная адаптация эвристического алгоритма, широко исследуется в области теории игр [28][31][32]. 5.1. Динамическая адаптация для ACO Динамическая адаптация(DA) эвристического алгоритма заключается в следующем: Генерируем N решений с помощью алгоритма ACO для всех узлов, из них выбираем лучшее. Это и будет начальным решением. Маршрут разбивается на K частей. После прохождения каждой части, для оставшихся узлов генерируем N решений с помощью той же эвристики. Если среди них есть решение лучше, чем текущее, то заменяем оставшийся маршрут на него, иначе следуем текущему маршруту. Данный алгоритм в основном будет генерировать решения лучше, чем простой муравьиный алгоритм. Это связано с тем, что: 1) каждый раз уменьшая размерность задач, увеличивается точность алгоритма; 2) каждая новая подзадача отличается от предыдущей своим суммарным 28

расположением узлов, что может поспособствует к нахождение локальных или глобальных оптимумов. 5.2. Результаты применения динамической адаптации Чтобы показать качество работы динамической адаптации муравьиного алгоритма, проведем сравнение его решений с решением простого муравьиного алгоритма. Для этого запустили оба алгоритма для тестовых задач по 20 раз, каждый запуск выдавал 50 решений. Параметры для запуска DAACO: K=5, R=50. В Таблица 2. приведены средние значения полученных решений, а также показаны лучшее решений для тестовых задач. Среднее значение задача Лучшее значение ACO DAACO ACO DAACO Eil51 461,26 435,04 426 395 Eil76 576,21 551,43 538 514 Eil101 673,64 634,73 629 612 KroA200 31379,05 30340,80 29368 29002 Lin318 45315,16 44948,71 42029 Таблица 2.Сравнение ACO и DAACO 41950 Так как алгоритм динамической адаптации почти на каждом шаге изменял изначальный маршрут, то это порождает вопрос, насколько динамически устойчивыми являются решения, полученные алгоритмом DAACO. Эксперименты проведем при тех же условиях, как и для алгоритма ACO. Значения параметров: |P|=5, M=10, K=5, R=25. Результаты отображены в Таблица 3. Количество экспериментов 1 2 3 4 Lin318 250 250 250 250 250 16 13 20 8 12 5 6 9 2 4 1 0 2 0 0 0 0 0 0 0 Кол-во дин. уст. решений 228 231 219 240 234 Сумма 1250 69 26 3 0 1152 задача Eil51 Eil76 Eil101 KroA200 Кол-во дин. неус. решений Таблица 3. Проверка на дин. уст. DAACO 29

Таким образом, экспериментальный уровень динамической устойчивости алгоритма DAACO для задачи TDTSP равен 0,9608 conDAGA=0,9608 5.3. Анализ результатов Из данных в Таблица 2 видно, что среднее значение генерируемых решений алгоритмом DAACO меньше, чем алгоритмом ACO. Вычислим процент улучшения по формуле k= T ACO ( pi ) −T DAACO ( pi ) T ACO ( pi ) 100 Г д е T ACO ( pi ) — время маршрута, полученного муравьиным алгоритмом для задачи pi , T DAACO ( pi ) – время маршрута полученного динамически адаптированным муравьиным алгоритмом. Результаты видны в Таблица 4. коэффициент улучшения задача Среднее значение Максимальное значение Eil51 5,68 7,28 Eil76 4,30 4,46 Eil101 5,78 2,70 KroA200 3,31 1,25 Lin318 0,81 0,19 Таблица 4. Коэффициент улучшения Средний процент улучшения решений равен 4%. Из анализа всех данных следует, что динамическая адаптация муравьиного алгоритма позволяет получать лучшие решения относительно критерия динамической устойчивости и точности, чем простой муравьиный алгоритм. 30

6. Заключение В работе была исследована одна из задач маршрутизации транспорта – динамическая задача коммивояжера. Были рассмотрены различные эвристические алгоритмы природного класса. Подробно изучен, описан и реализован на языке программирования Java муравьиный алгоритм (ACO) для решения задачи TDTSP. Произведена оценка уровня динамической устойчивости решений, генерируемых данной эвристикой. Из-за того, что эвристики не обеспечивают получение оптимальных решений, но близких к ним, среднее значение этой величины для рассмотренных задач получилось равным 0,6504. Принцип динамической адаптации показал, что любой алгоритм, который генерирует различные решения для одной и той же задачи, можно улучшить с помощью алгоритма динамической адаптации. Динамическая адаптация муравьиного алгоритма (DAACO) повысила уровень динамической устойчивости решений до 0,9608. Также среднее значение длины решений, сгенерированных алгоритмом DAACO, получилось меньше, чем классическим муравьиным алгоритмом. Средний процент улучшения решений равен 4%. Результаты экспериментов показали, что использование динамической адаптации муравьиного алгоритма будет эффективней, чем простого муравьиного алгоритма, за счет генерируемых маршрутов меньшей длины. 31

7. Список литературы 1. Schrijver A. On the history of combinatorial optimization (till 1960) // Handbook of Discrete Optimization. 2005. P. 1–63 2. Vasek Chvatal, William J. Cook, George B. Dantzig, Delbert Ray Fulkerson,and Selmer M. Johnson. Solution of a large-scale traveling-salesman problem. In 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pages 7–28. 2010. 3. Майника Э. Алгоритмы оптимизации на сетях и графах. М: Мир, 1981. 323 с. 4. Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1982. 5. George B. Dantzig. Linear programming and extensions. Rand Corporation Research Study. Princeton Univ. Press, Princeton, NJ, 1963. 6. Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. 2003, Vol. 35, No 3. P.268–308. 7. Miller C. E., Tucker A. W., Zemlin R. A. Integer programming formulation of traveling salesman problems // J. ACM. 1960. Vol. 7, No 4. P. 326–329. 8. H. Abeledo, R. Fukasawa, A. Pessoa, and E. Uchoa, The Time Dependent Traveling Salesman Problem: Polyhedra and Algorithm, Mathematical Programming Computation 5 (2013), 27-55. 9. Ben-Israel, “A Newton-Raphson method for the solution of systems of equations,” Journal of Mathematical Analysis and Applications, vol. 15, pp. 243–252, 1966. 10. D. P. Bertsekas, Dynamic Programming and Optimal Control,vol. 1, Athena Scientific, Belmont, Mass, USA, 1995. 11. R. G. Ghanem and P. D. Spanos, Stochastic Finite Elements: A Spectral Approach, Courier Corporation, 2003. 12. S. Binitha and S.S. Sathya, “A survey of bio inspired optimization algorithms,”

International Journal of Soft Computing and Engineering, vol. 2, pp. 137–151, 2012. 13. F. Dressler and O. B. Akan, “A survey on bio-inspired networking, ”Computer Networks, vol. 54, no. 6, pp. 881–900, 2010. 14. X.-S. Yang and S. Deb, “Two-stage eagle strategy with differential evolution,” International Journal of Bio-Inspired Computation, vol. 4, no. 1, pp. 1–5, 2012. 15. S. K. Dhurandher, S. Misra, P. Pruthi, S. Singhal, S. Aggarwal, I. Woungang, “Using bee algorithm for peer-to-peer filesearching in mobile ad hoc networks,” Journal of Network and Computer Applications, vol. 34, no. 5, pp. 1498–1508, 2011. 16. A.R. Mehrabian and C. Lucas, “A novel numerical optimization algorithm inspired from weed colonization,” Ecological Informatics, vol. 1, no. 4, pp. 355–366, 2006. 17. M.Dorigo, G. Di Caro, and L.M. Gambardella, “Ant algorithms for discrete optimization,” Artificial Life, vol. 5, no. 2, pp. 137–172, 1999. 18. M. Clerc, Particle Swarm Optimization, vol. 93, John Wiley & Sons, 2010. 19. Z. Yuan, M. A.M. deOca, M. Birattari, T. Stutzle, “Continuous optimization algorithms for tuning real and integer parameters of swarm intelligence algorithms,” Swarm Intelligence, vol.6, no. 1, pp. 49–75, 2012. 20. D. Karaboga, B. Akay, “A survey: algorithms simulating bee swarm intelligence,” Artificial Intelligence Review, vol. 31, no. 1–4, pp. 61–85, 2009. 21. J. Kennedy and R. Mendes, “Population structure and particle swarm performance,” in Proceedings of the Congress on Evolutionary Computation (CEC ’02), vol. 2, pp. 1671–1676, IEEE, Honolulu, Hawaii, USA, May 2002. 22. A.M. Mora, P. Garcıa-Sanchez, J.J. Merelo, and P. A. Castillo, “Migration study on a pareto-based island model for MOACOs,” in Proceedings of the 15th Genetic and Evolutionary Computation Conference (GECCO ’13), pp. 57–64, July 2013. 23. Hitoshi K., Junichi O. Solving Time-Dependent Traveling Salesman Problems Using Ant Colony Optimization Based on Predicted Traffic // Advances in 33

Intelligent and Soft Computing. 2012. 151. 24. Dorigo, M., Stutzle, T. Ant colony optimization. The MIT press, 2004. 25. Stutzle, T., Hoos, H. H. MAN-MIN ant system. Future Generation Computer System, Vol. 16, No. 8, 2000, 889–914. 26. J.F. Cordeau, M. Gendreau, G. Laporte, J.Y. Potvin, and F.Semet. A guide to vehicle routing heuristics. Journal of the Operational Research Society, pages 512–522, May 2002. 27. .Jean-Francois Cordeau, Michel Gendreau, and Gilbert Laporte. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30(2):105–119, 1997. 28. Петросян Леон Аганесович и Зенкевич Николай Анатольевич. Принципы устойчивой кооперации. Управление большими системами: сборник трудов, (3):100–120, 2009. 29. G. Reinelt. Travelling Salesman Problem Library, 2008. http://comopt.ifi.uniheidelberg.de/software/TSPLIB95/. 30. Giorgio Ausiello, Bruno Escoffier, JeRoMe Monnot, and Vangelis Paschos. Reoptimization of minimum and maximum traveling salesman’s tours. J. of Discrete Algorithms, 7(4):453–463, December 2009. 31. .V. Zakharov and M. Dementieva. Multistage cooperative games and problem of time consistency. International Game Theory Review, 6:157–170, 2004. 32. .V.V. Zakharov and A.N. Shchegryaev. Multi-period cooperative vehicle routing games. Contributions to Game Theory and Management, 7(2):349– 359, April 2014. 34

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв