📄Работа №75044
Тема: Динамическая адаптация эвристических алгоритмов в задачах маршрутизации транспорта
Тип работы
Дипломные работы, ВКР
Предмет
логистика
Объем:
62 листов
Год:
2018
Просмотров:
354
4770
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
Глава 1. Математические модели маршрутизации 5
1.1. Классическая задача коммивояжёра 5
1.2. Задача маршрутизации транспорта 8
1.3. Задача сбора и доставки 10
1.4. Задача маршрутизации запасов 13
1.5. Актуальные модификации задач маршрутизации 16
Глава 2. Алгоритмы решения задач маршрутизации 20
2.1. Обзор и классификация актуальных алгоритмов 20
2.2. Adaptive Large Neighborhood Search 23
Глава 3. Динамическая адаптация алгоритмов 26
3.1. Введение в динамическую адаптацию 26
3.2. Оценка состоятельности во времени 27
3.3. Динамическая адаптация алгоритмов 28
3.4. Неустойчивая задача. Пример IRP 29
3.5. Устойчивая задача. Пример PDP 32
Глава 4. Кооперативные задачи маршрутизации 35
4.1. Введение 35
4.2. Построение кооперативной модели IRP 36
4.3. Характеристическая функция 39
4.4. Пример построения характеристической функции 40
4.5. Вычислительные эксперименты 43
4.6. Анализ устойчивости экспериментов 49
Заключение 53
Список литературы 54
Приложения
Глава 1. Математические модели маршрутизации 5
1.1. Классическая задача коммивояжёра 5
1.2. Задача маршрутизации транспорта 8
1.3. Задача сбора и доставки 10
1.4. Задача маршрутизации запасов 13
1.5. Актуальные модификации задач маршрутизации 16
Глава 2. Алгоритмы решения задач маршрутизации 20
2.1. Обзор и классификация актуальных алгоритмов 20
2.2. Adaptive Large Neighborhood Search 23
Глава 3. Динамическая адаптация алгоритмов 26
3.1. Введение в динамическую адаптацию 26
3.2. Оценка состоятельности во времени 27
3.3. Динамическая адаптация алгоритмов 28
3.4. Неустойчивая задача. Пример IRP 29
3.5. Устойчивая задача. Пример PDP 32
Глава 4. Кооперативные задачи маршрутизации 35
4.1. Введение 35
4.2. Построение кооперативной модели IRP 36
4.3. Характеристическая функция 39
4.4. Пример построения характеристической функции 40
4.5. Вычислительные эксперименты 43
4.6. Анализ устойчивости экспериментов 49
Заключение 53
Список литературы 54
Приложения
📖 Введение
Данная работа посвящена математическому исследования задач оптимизации вопросов логистики. Под логистикой обычно понимают область деятельности предприятия, связанную с планированием, организацией, управлением и контролем движения материальных и информационных потоков в пространстве и во времени от их первичного источника до конечного потребителя, а также науку, изучающую эти процессы [1].
Одной из основных целей оптимизации логистики является, наравне с максимизацией прибыли, также минимизация расходов, связанных с затратами на логистические операции. Наиболее общими операциями логистики здесь являются планирование закупок, распределения и сбыта, организация складирования и управление запасами, планирование перевозок, планирование производства и управление производственными процессами [1].
Фокусом данной работы являются задачи, связанные с планированием маршрутов, поскольку задачи данного класса не только актуальны в практике, но также и являются математически сложными - они принадлежат классу NP вычислительной сложности задач. Это означает, что доказательство оптимальности решения требует полного перебора решений, и в случае даже простейшей задачи маршрутизации n точек этим числом решений будет n!.
С ростом предприятий и рынков сбыта растёт и размерность задач, которые требуется разрешить. Фактически, это означает, что требования к вычислительным ресурсам для решения этой задачи традиционным точным методом растут более чем полиномиально с ростом размерности задачи, и уже сегодня их зачастую не хватает для нахождения оптимального решения этим способом. Таким образом, на практике становятся всё более популярными приближённые (эвристические) методы, а класс задач маршрутизации становится актуальным для теоретического исследования.
В реальности, к тому же, с построением маршрута связаны и многие другие факторы, из-за которых даже отдельный оптимальный маршрут может дать плохое решение для в целом, поскольку в современной практике реальные задачи обычно содержат различные дополнительные условия, ограничения и возможности. В связи с этим в теоретических исследованиях возникает необходимость рассмотрения более сложных задач. Можно выделить четыре основных класса математических моделей маршрутизации, исследуемых в настоящее время: задача коммивояжёра (travelling salesman problem), задача маршрутизации транспорта (vehicle routing problem), задача маршрутизации и управления запасом (inventory routing problem) и задача сбора и доставки (Pickup and Delivery Problems).
Вкладом данной работы являются разработка и формализация общего вида алгоритма Динамической адаптации эвристических алгоритмов и его апробация на различных классах задач маршрутизации. Дополнительно, в ходе работы предложен, сформулирован и исследован новый класс задач маршрутизации - кооперативные игры маршрутизации, являющийся расширением стандартных задач с добавлением возможности кооперации перевозчиков, что позволяет получать более эффективные решения по сравнению со стандартными случаями. Исследованы проблемы, возникающие при решении таких задач и методы их разрешения.
Данная работа включает следующие части. Во второй части представлен обзор литературы по теме актуальных моделей маршрутизации и представлены математические постановки стандартных задач. В третьей части представлена аналогичная работа по теме алгоритмов нахождения решений задач маршрутизации, а также представлена схема с подробным описанием основного алгоритма, использующегося в данной работе - адаптирующегося алгоритма поиска в большой окрестности (Adaptive Large Neighborhood Search, ALNS). Четвёртая часть содержит описание проделанной работы над концепцией Динамической адаптации: основные идеи, метод применения, общая схема динамически адаптированного алгоритма и полученные результаты при применении к различным задачам. В пятой части предлагается концепция кооперативного расширения стандартных задач маршрутизации, рассматриваются проблемы таких постановок и представляются экспериментальные результаты улучшения качества решений и устойчивости коалиций в такой задаче.
Одной из основных целей оптимизации логистики является, наравне с максимизацией прибыли, также минимизация расходов, связанных с затратами на логистические операции. Наиболее общими операциями логистики здесь являются планирование закупок, распределения и сбыта, организация складирования и управление запасами, планирование перевозок, планирование производства и управление производственными процессами [1].
Фокусом данной работы являются задачи, связанные с планированием маршрутов, поскольку задачи данного класса не только актуальны в практике, но также и являются математически сложными - они принадлежат классу NP вычислительной сложности задач. Это означает, что доказательство оптимальности решения требует полного перебора решений, и в случае даже простейшей задачи маршрутизации n точек этим числом решений будет n!.
С ростом предприятий и рынков сбыта растёт и размерность задач, которые требуется разрешить. Фактически, это означает, что требования к вычислительным ресурсам для решения этой задачи традиционным точным методом растут более чем полиномиально с ростом размерности задачи, и уже сегодня их зачастую не хватает для нахождения оптимального решения этим способом. Таким образом, на практике становятся всё более популярными приближённые (эвристические) методы, а класс задач маршрутизации становится актуальным для теоретического исследования.
В реальности, к тому же, с построением маршрута связаны и многие другие факторы, из-за которых даже отдельный оптимальный маршрут может дать плохое решение для в целом, поскольку в современной практике реальные задачи обычно содержат различные дополнительные условия, ограничения и возможности. В связи с этим в теоретических исследованиях возникает необходимость рассмотрения более сложных задач. Можно выделить четыре основных класса математических моделей маршрутизации, исследуемых в настоящее время: задача коммивояжёра (travelling salesman problem), задача маршрутизации транспорта (vehicle routing problem), задача маршрутизации и управления запасом (inventory routing problem) и задача сбора и доставки (Pickup and Delivery Problems).
Вкладом данной работы являются разработка и формализация общего вида алгоритма Динамической адаптации эвристических алгоритмов и его апробация на различных классах задач маршрутизации. Дополнительно, в ходе работы предложен, сформулирован и исследован новый класс задач маршрутизации - кооперативные игры маршрутизации, являющийся расширением стандартных задач с добавлением возможности кооперации перевозчиков, что позволяет получать более эффективные решения по сравнению со стандартными случаями. Исследованы проблемы, возникающие при решении таких задач и методы их разрешения.
Данная работа включает следующие части. Во второй части представлен обзор литературы по теме актуальных моделей маршрутизации и представлены математические постановки стандартных задач. В третьей части представлена аналогичная работа по теме алгоритмов нахождения решений задач маршрутизации, а также представлена схема с подробным описанием основного алгоритма, использующегося в данной работе - адаптирующегося алгоритма поиска в большой окрестности (Adaptive Large Neighborhood Search, ALNS). Четвёртая часть содержит описание проделанной работы над концепцией Динамической адаптации: основные идеи, метод применения, общая схема динамически адаптированного алгоритма и полученные результаты при применении к различным задачам. В пятой части предлагается концепция кооперативного расширения стандартных задач маршрутизации, рассматриваются проблемы таких постановок и представляются экспериментальные результаты улучшения качества решений и устойчивости коалиций в такой задаче.
✅ Заключение
Таким образом, была проведена работа по обширному исследованию различных математических моделей задач маршрутизации и был проведён сравнительный анализ экспериментальных показателей в разных задачах.
В ходе работы была разработана эффективная реализация на языке C++ современного алгоритма эвристической оптимизации ALNS, и была проведена адаптация этого алгоритма на широкий круг различных задач.
На базе созданной реализации была собрана обширная база экспериментальных данных по нескольким актуальным задачам маршрутизации. Был проведён анализ всех полученных данных, по результатам которого были сделаны выводы:
• об эффективности нового метода Динамической адаптации и актуальности его использования в тех или иных задачах, основываясь на новом методе экспериментальной оценки Состоятельности во времени;
• о существенных перспективах исследования и выгоде практического применения новой модели Кооперативной игры маршрутизации запасов;
• об устойчивости различных подходов к кооперации, основанных на различных методах дележа и различных методах построения характеристической функции игры;
• о важности вычисления характеристической функции по новому методу Прямой индукции коалиций для повышения устойчивости кооперации в задачах маршрутизации.
По результатам проведённой в совокупности научной работы были опубликованы работы «Dynamic adaptive large neighborhood search for inventory routing problem» в журнале Modelling, Computation and Optimization in Information Systems and Management Sciences издательства Springer, «Heuristic evaluation of the characteristic function in the Cooperative Inventory Routing Game» в Journal on Vehicle Routing Algorithms издательства Springer и подготовлена статья «Проблема формирования устойчивых коалиций в кооперативной игре маршрутизации и управления запасами» в журнал Математическая теория игр и её приложения.
В ходе работы была разработана эффективная реализация на языке C++ современного алгоритма эвристической оптимизации ALNS, и была проведена адаптация этого алгоритма на широкий круг различных задач.
На базе созданной реализации была собрана обширная база экспериментальных данных по нескольким актуальным задачам маршрутизации. Был проведён анализ всех полученных данных, по результатам которого были сделаны выводы:
• об эффективности нового метода Динамической адаптации и актуальности его использования в тех или иных задачах, основываясь на новом методе экспериментальной оценки Состоятельности во времени;
• о существенных перспективах исследования и выгоде практического применения новой модели Кооперативной игры маршрутизации запасов;
• об устойчивости различных подходов к кооперации, основанных на различных методах дележа и различных методах построения характеристической функции игры;
• о важности вычисления характеристической функции по новому методу Прямой индукции коалиций для повышения устойчивости кооперации в задачах маршрутизации.
По результатам проведённой в совокупности научной работы были опубликованы работы «Dynamic adaptive large neighborhood search for inventory routing problem» в журнале Modelling, Computation and Optimization in Information Systems and Management Sciences издательства Springer, «Heuristic evaluation of the characteristic function in the Cooperative Inventory Routing Game» в Journal on Vehicle Routing Algorithms издательства Springer и подготовлена статья «Проблема формирования устойчивых коалиций в кооперативной игре маршрутизации и управления запасами» в журнал Математическая теория игр и её приложения.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.