Адаптация эвристических алгоритмов маршрутизации на большой сети
|
1. ВВЕДЕНИЕ 3
1.1. ВИДЫ ЗАДАЧИ VRP 4
1.2. ПОСТАНОВКА ЗАДАЧИ СVRP 5
1.3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ CVRP 6
2. МУРАВЬИНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ VRP 9
2.1. МУРАВЬИНАЯ ЭВРИСТИКА 9
2.2. ACO ДЛЯ ЗАДАЧИ CVRP 13
2.3. ИСПОЛЬЗУЕМАЯ РЕАЛИЗАЦИЯ ACO 13
2.4. ОСНОВНАЯ ПРОЦЕДУРА ACO 15
2.5. ВЫБОР ПАРАМЕТРОВ ДЛЯ ACO 15
3. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ 17
3.1. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ ДЛЯ ЭВРИСТИЧЕСКОГО АЛГОРИТМА 18
3.2. ПРОВЕРКА УРОВНЯ ДИНАМИЧЕСКОЙ УСТОЙЧИВОСТИ 19
3.3. РЕЗУЛЬТАТЫ ПРОВЕРКИ НА ДИНАМИЧЕСКУЮ УСТОЙЧИВОСТЬ 20
4. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ 22
4.1. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ ДЛЯ ACO 22
5. ОЦЕНКА ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМА DAACO 24
6. АНАЛИЗ ЭФФЕКТИВНОСТИ DAACO 26
6.1. ОЦЕНКА ДИНАМИЧЕСКОЙ УСТОЙЧИВОСТИ 26
6.2. СРАВНЕНИЕ РЕШЕНИЙ DAACO И ACO 27
6.3. ЭФФЕКТИВНОСТЬ DAACO ЗА ВРЕМЯ РАБОТЫ ACO 28
7. ЗАКЛЮЧЕНИЕ 29
8. СПИСОК ЛИТЕРАТУРЫ 31
ПРИЛОЖЕНИЕ 1 33
ПРИЛОЖЕНИЕ 2 34
ПРИЛОЖЕНИЕ 3 38
ПРИЛОЖЕНИЕ 4 42
ПРИЛОЖЕНИЕ 5 43
1.1. ВИДЫ ЗАДАЧИ VRP 4
1.2. ПОСТАНОВКА ЗАДАЧИ СVRP 5
1.3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ CVRP 6
2. МУРАВЬИНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ VRP 9
2.1. МУРАВЬИНАЯ ЭВРИСТИКА 9
2.2. ACO ДЛЯ ЗАДАЧИ CVRP 13
2.3. ИСПОЛЬЗУЕМАЯ РЕАЛИЗАЦИЯ ACO 13
2.4. ОСНОВНАЯ ПРОЦЕДУРА ACO 15
2.5. ВЫБОР ПАРАМЕТРОВ ДЛЯ ACO 15
3. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ 17
3.1. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ ДЛЯ ЭВРИСТИЧЕСКОГО АЛГОРИТМА 18
3.2. ПРОВЕРКА УРОВНЯ ДИНАМИЧЕСКОЙ УСТОЙЧИВОСТИ 19
3.3. РЕЗУЛЬТАТЫ ПРОВЕРКИ НА ДИНАМИЧЕСКУЮ УСТОЙЧИВОСТЬ 20
4. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ 22
4.1. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ ДЛЯ ACO 22
5. ОЦЕНКА ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМА DAACO 24
6. АНАЛИЗ ЭФФЕКТИВНОСТИ DAACO 26
6.1. ОЦЕНКА ДИНАМИЧЕСКОЙ УСТОЙЧИВОСТИ 26
6.2. СРАВНЕНИЕ РЕШЕНИЙ DAACO И ACO 27
6.3. ЭФФЕКТИВНОСТЬ DAACO ЗА ВРЕМЯ РАБОТЫ ACO 28
7. ЗАКЛЮЧЕНИЕ 29
8. СПИСОК ЛИТЕРАТУРЫ 31
ПРИЛОЖЕНИЕ 1 33
ПРИЛОЖЕНИЕ 2 34
ПРИЛОЖЕНИЕ 3 38
ПРИЛОЖЕНИЕ 4 42
ПРИЛОЖЕНИЕ 5 43
Транспортная логистика занимает важное место на современном рынке, предприятия должны ориентироваться на интересы потребителей, а не на собственные. Для этого они должны сконцентрироваться на максимальном удовлетворении запросов клиентов. Оно выражается в достойном качестве товаров и услуг. Но больше всего влияют на цену товаров логистические издержки. В частности, поставщики поставляют ресурсы производителю, производитель направляет готовый товар посредникам, а те, в свою очередь – конечному покупателю. Любое предприятие заинтересовано в максимально продуманном, быстром и дешевом перемещении продукции.
Есть большое разнообразие математических моделей для описания логистических процессов. Классической задачей является проблема маршрутизации транспортного средства (Vehicle Routing Problems, VRP) – это общее название для целого класса задач, в которых для нескольких разбросанных городов или клиентов должен быть определен набор маршрутов для транспортных средств, расположенных на одном или нескольких складах. Данная модель предложена Данцигом и Рамсером в 1959 году.
VRP относится к классу NP-полных задач, что накладывает ограничение размерности задачи для целесообразной возможности применения точных алгоритмов. Для решения задачи на больших сетях используют алгоритмы, основанные на различных эвристиках и в том числе их комбинации. Но из-за особенности в вычислениях для одной и той же задачи эвристические алгоритмы могут генерировать различные решения, притом в основном лишь приближенные к оптимальному решению. В связи с этим присутствует большая заинтересованность в модификациях эвристических алгоритмов для их улучшения. У каждой реальной задачи имеются свои особенности, для которых нужны оптимизации вычислительных алгоритмов по определенным параметрам. Например, для курьерской службы важно время построения маршрутов, так как заказы могут поступать в реальном времени и есть необходимость в моментальном пересчете маршрута, в то же время для крупных предприятий важно построение маршрутов с низкой стоимостью, на которое они могут отвести определенное время, но гарантировать надежность данных маршрутов.
В первой главе рассмотрены задачи VRP и CVRP, представлена математическая модель задачи CVRP. Во второй главе подробно рассмотрен муравьиный алгоритм (ACO) и способы его применения для задачи CVRP. Проведен эксперимент по определению лучших наборов параметров для алгоритма ACO. В третьей главе дается определение динамической адаптации как критерия оценки алгоритмов и проведена оценка ACO. В четвертой главе предложен метод динамической адаптации алгоритма, приведена блок-схема алгоритма. В пятой главе рассмотрена вычислительная сложность алгоритма ACO и проведено вычисление её вида для алгоритма DAACO. В шестой главе произведен анализ алгоритма DAACO, метод экспериментального сравнения с алгоритмом ACO на ряде тестовых задач с использованием различных критериев. В седьмой главе описана проделанная работа и полученные результаты с выводами.
Есть большое разнообразие математических моделей для описания логистических процессов. Классической задачей является проблема маршрутизации транспортного средства (Vehicle Routing Problems, VRP) – это общее название для целого класса задач, в которых для нескольких разбросанных городов или клиентов должен быть определен набор маршрутов для транспортных средств, расположенных на одном или нескольких складах. Данная модель предложена Данцигом и Рамсером в 1959 году.
VRP относится к классу NP-полных задач, что накладывает ограничение размерности задачи для целесообразной возможности применения точных алгоритмов. Для решения задачи на больших сетях используют алгоритмы, основанные на различных эвристиках и в том числе их комбинации. Но из-за особенности в вычислениях для одной и той же задачи эвристические алгоритмы могут генерировать различные решения, притом в основном лишь приближенные к оптимальному решению. В связи с этим присутствует большая заинтересованность в модификациях эвристических алгоритмов для их улучшения. У каждой реальной задачи имеются свои особенности, для которых нужны оптимизации вычислительных алгоритмов по определенным параметрам. Например, для курьерской службы важно время построения маршрутов, так как заказы могут поступать в реальном времени и есть необходимость в моментальном пересчете маршрута, в то же время для крупных предприятий важно построение маршрутов с низкой стоимостью, на которое они могут отвести определенное время, но гарантировать надежность данных маршрутов.
В первой главе рассмотрены задачи VRP и CVRP, представлена математическая модель задачи CVRP. Во второй главе подробно рассмотрен муравьиный алгоритм (ACO) и способы его применения для задачи CVRP. Проведен эксперимент по определению лучших наборов параметров для алгоритма ACO. В третьей главе дается определение динамической адаптации как критерия оценки алгоритмов и проведена оценка ACO. В четвертой главе предложен метод динамической адаптации алгоритма, приведена блок-схема алгоритма. В пятой главе рассмотрена вычислительная сложность алгоритма ACO и проведено вычисление её вида для алгоритма DAACO. В шестой главе произведен анализ алгоритма DAACO, метод экспериментального сравнения с алгоритмом ACO на ряде тестовых задач с использованием различных критериев. В седьмой главе описана проделанная работа и полученные результаты с выводами.
В работе была исследована одна из задач транспортной маршрутизации – CVRP, а так же один из классических эвристических алгоритмов для её решения – ACO.
Подробно изучен, описан и реализован на языке программирования Java муравьиный алгоритм (ACO) для решения задачи CVRP, приведены полученные экспериментальным путем наборы параметров для запуска муравьиного алгоритма. Произведена его оценка уровня динамической устойчивости решений, генерируемых данной эвристикой. Из-за того, что эвристики не обеспечивают получение оптимальных решений, но генерирует решения близкие к оптимальным, среднее значение этой величины для рассмотренных задач получилось равно 0, из чего делается вывод, что значение итераций для ACO было недостаточно высоким, но и оно не гарантирует отсутствие зацикливания алгоритма на локальном минимуме. Таким образом, использовать чистую эвристику ACO без алгоритмов локального поиска даже при больших значениях итераций и количества муравьиных агентов не целесообразно.
Принцип динамической устойчивости показал, что любой эвристический алгоритм, который генерирует различные решения для одной и той же задачи, можно улучшить с помощью алгоритма динамической адаптации. Динамическая адаптация муравьиного алгоритма (DAACO) повысила уровень динамической устойчивости решений до 0,571. Также значения целевых функций решений, сгенерированных алгоритмом DAACO, и их среднее меньше, чем полученные с помощью классического муравьиным алгоритмом. Средний процент улучшения решений равен 8%. К тому же, динамическая адаптация муравьиного алгоритма показала лучшие результаты на меньших значениях параметров итераций алгоритма, затратив на вычисление меньше времени, чем обычный муравьиный алгоритм.
Результаты экспериментов показали, что использование динамической адаптации муравьиного алгоритма будет эффективней, чем использование простого муравьиного алгоритма, точность вычисления увеличивается, уменьшается разброс получаемых решений, а главное, позволяет уменьшить время вычислений за счет уменьшения значений параметров итераций и численности муравейника, не ухудшив значения генерируемых решений и не используя посторонние способы улучшения.
Подробно изучен, описан и реализован на языке программирования Java муравьиный алгоритм (ACO) для решения задачи CVRP, приведены полученные экспериментальным путем наборы параметров для запуска муравьиного алгоритма. Произведена его оценка уровня динамической устойчивости решений, генерируемых данной эвристикой. Из-за того, что эвристики не обеспечивают получение оптимальных решений, но генерирует решения близкие к оптимальным, среднее значение этой величины для рассмотренных задач получилось равно 0, из чего делается вывод, что значение итераций для ACO было недостаточно высоким, но и оно не гарантирует отсутствие зацикливания алгоритма на локальном минимуме. Таким образом, использовать чистую эвристику ACO без алгоритмов локального поиска даже при больших значениях итераций и количества муравьиных агентов не целесообразно.
Принцип динамической устойчивости показал, что любой эвристический алгоритм, который генерирует различные решения для одной и той же задачи, можно улучшить с помощью алгоритма динамической адаптации. Динамическая адаптация муравьиного алгоритма (DAACO) повысила уровень динамической устойчивости решений до 0,571. Также значения целевых функций решений, сгенерированных алгоритмом DAACO, и их среднее меньше, чем полученные с помощью классического муравьиным алгоритмом. Средний процент улучшения решений равен 8%. К тому же, динамическая адаптация муравьиного алгоритма показала лучшие результаты на меньших значениях параметров итераций алгоритма, затратив на вычисление меньше времени, чем обычный муравьиный алгоритм.
Результаты экспериментов показали, что использование динамической адаптации муравьиного алгоритма будет эффективней, чем использование простого муравьиного алгоритма, точность вычисления увеличивается, уменьшается разброс получаемых решений, а главное, позволяет уменьшить время вычислений за счет уменьшения значений параметров итераций и численности муравейника, не ухудшив значения генерируемых решений и не используя посторонние способы улучшения.
Подобные работы
- Модификация муравьиного алгоритма для динамической задачи коммивояжёра
Бакалаврская работа, математика. Язык работы: Русский. Цена: 3850 р. Год сдачи: 2016 - Модификация муравьиного алгоритма для динамической задачи коммивояжёра
Бакалаврская работа, информатика. Язык работы: Русский. Цена: 4210 р. Год сдачи: 2016 - Динамический эвристический алгоритм для задачи транспортной маршрутизации с использованием кросс-докинга
Дипломные работы, ВКР, информатика. Язык работы: Русский. Цена: 4330 р. Год сдачи: 2016 - Задачи маршрутизации транспорта на сети мегаполиса
Магистерская диссертация, информатика. Язык работы: Русский. Цена: 5610 р. Год сдачи: 2017