Эффективные алгоритмы планирования транспортировки продукции : на примере продуктов с особыми условиями перевозки

• Автор: Сластников, Сергей Александрович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 112 с. : ил.

Оглавление
Введение
Глава 1. Анализ современного состояния проблемы разработки автоматизированных систем управления транспортировкой
1.1 Управление транспортировкой как часть логистической системы
1.2 Обзор программных средств для систем планирования в задачах транспортировки
1.3 Постановка задачи развозки нефтепродуктов
1.4 Задача маршрутизации транспорта и ее виды
1.5 Выводы
Глава 2. Анализ методов решения задач маршрутизации транспорта
2.1 Классификация алгоритмов решения
2.2 Математическая постановка ЗМТ
2.2.1 Трехиндексная постановка ЗМТ
2.2.2 Двухиндексная постановка для симметричной ЗМТ
2.2.3 Постановка Фишера-Джекумера
2.2.4 Постановка, основанная на декомпозиции множеств
2.3 Точные методы решения ЗМТ
2.3.1 Метод ветвей и границ
2.3.2 Динамическое программирование
2.3.3 Целочисленное линейное программирование
2.4 Классические эвристические методы
2.4.1 Конструктивные алгоритмы
2.4.2 Двухфазные алгоритмы
2.4.3 Улучшающие алгоритмы
2.5 Метаэвристические алгоритмы
2.5.1 Имитация отжига
2.5.2 Детерминированный отжиг
2.5.3 Генетические алгоритмы
2.5.4 Методы поиска с запретами
2.5.5 Меметические алгоритмы
2.6 Выводы
Глава 3. Построение модифицированного метода муравьиных колоний для
решения ЗМТ
3.1 Общие положения алгоритмов муравьиных колоний
3.2 Классический алгоритм муравьиных колоний для задачи коммивояжера
3.3 Классический алгоритм муравьиных колонии для задачи маршрутизации транспорта с ограничениями грузоподъемности
3.4 Разновидности алгоритма муравьиных колоний
3.4.1 «Элитная» муравьиная система
3.4.2 Максиминная муравьиная система
3.4.3 Ранжированная муравьиная система
3.4.4 Муравьиная система «лучший-худший»
3.5 Анализ применения муравьиных алгоритмов
3.6 Модифицированный алгоритм муравьиных колоний для ЗМТ
3.7 Двухфазный модифицированный алгоритм муравьиных колоний для ЗМТ
3.8 Программная реализация муравьиных алгоритмов для ЗМТ
3.9 Вычислительные эксперименты для ЗМТ
3.9.1 Результаты вычислительных экспериментов
3.9.2 Подбор оптимальных значений параметров алгоритма
3.10 Выводы
Глава 4. Проектирование системы планирования доставки продукции
4.1 Требования к системе
4.2 Проектирование архитектуры системы
4.3 Выбор платформы разработки
4.4 Проектирование интерфейса
Заключение
Список литературы

Введение
Актуальность работы. Планирование доставки продукции является одной из важнейших задач в транспортной логистике. Системы планирования доставки продукции должны облегчать работу диспетчеров, ответственных за маршрутизацию транспортных средств, а именно должны уметь строить эффективные с экономической точки зрения маршруты развозки. Это - известная задача оптимизации поставок продукции, которая всегда привлекала повышенное внимание как среди экономистов и специалистов по логистике, так и среди математиков. Среди экономистов это обусловлено важностью транспортировки товаров и связанных с ней издержек [3]. Для математиков этот интерес вызван ее значительной сложностью. Соответствующие системы планирования доставки обязаны учитывать правила перевозки разных видов продукции, которые существенно различаются.
Данная работа посвящена разработке эффективных алгоритмов планирования транспортировки продукции, которые применимы, в том числе для продукции, обладающей специфическими условиями транспортировки. Под такими специфическими условиями в данной работе подразумевается следующее:
• транспортные средства, осуществляющие перевозку, состоят из одной или нескольких раздельных секций;
• при загрузке каждого транспортного средства разрешено наполнять каждую из секций только полностью, при разгрузке разрешено опустошать каждую секцию целиком.
На практике подобные ограничения встречаются в задачах развозки нефтепродуктов, некоторых видов спиртов (в частности, бутилового спирта) II сжиженных газов и обусловлены соображениями безопасности транспортировки.
Что нужно для построения эффективного планирования транспортировки продукции? В первую очередь, необходимо конструирование эффективных алгоритмов, способных строить маршруты развозки минимальной (или близкой к

- сложность вычисления величин .
Метод генерации столбцов позволяет преодолеть данные недостатки. Его применение как для решения ¥ЯР, так и для УКРТИ/ можно встретить в работах [45, 46, 55, 73, 74]. Идея метода состоит в том, что многократно решается задача меньшей размерности, содержащая только ограниченное подмножество всех возможных переменных (столбцов) X]. Проверка оптимальности предполагает вычисление столбцам с наименьшими затратами:
2,-ЛУ ^тЩа-ЛУ), (2.11)
3 * ]€ Я 7
где У - вектор-столбец коэффициентов ограничений переменной Х1, Я -двоичный вектор, полученный линейной релаксацией редуцированной задачи. Если Хг неотрицательна, то текущее решение является оптимальным и процедура останавливается. Иначе, Х,: включается в базис и задача повторно
оптимизируется. Так как решение должно быть целочисленным, то эта процедура используется в сочетании с методом ветвей и границ. Решение (2.11) получается использованием алгоритма решения задачи нахождения кратчайшего пути с такими же ограничениями как у исходной ЗМТ.
2.4 Классические эвристические методы
2.4.1 Конструктивные алгоритмы
2.4.1.1 Алгоритм Кларка-Райта
Этот классический алгоритм был впервые предложен Кларком и Райтом в 1964 году для решения ЗМТ с нефиксированным количеством транспортных средств [42]. Основная идея алгоритма основана на процессе объединения нескольких маршрутов в один до тех пор, пока это уменьшает суммарную стоимость объезда. Алгоритм предполагает построение начального решения, при котором каждый клиент посещается отдельно, т.е. создается п маршрутов