Оптимизация маршрута доставки однородного груза от множества производителей множеству потребителей

• Автор: Гиндуллин, Рамиз Вилевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Уфа
• Количество страниц: 147 с. : ил.

ОГЛАВЛЕНИЕ

Введение

1 ОБЗОР ЗАДАЧ ТРАНСПОРТНОЙ МАРШРУТИЗАЦИИ

1.1 Задачи транспортной маршрутизации

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

1.3 Задача коммивояжера (TSP, Traveling salesman problem)

1.4 Выводы
2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ МОНОНОМЕНКЛАТУРНОЙ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ МАРШРУ ТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ
2.1 Задача
2.2 Задача
2.3 Задача
2.4 Задача
3 ПОСТАНОВКА ЧИСЛЕННЫХ ЭКСПЕРИМЕНТОВ, ИССЛЕДОВАНИЕ РЕЗУЛЬТАТОВ
3.1 Точные решения задачи
3.2 Зависимость длины оптимального маршрута от вместимости
транспортного средства
3.3 Сравнение эффективности эвристик для решения задачи 2
3.4 Сравнение эффективности эвристик для решения задачи 3
3.5 Сравнение эффективности жадных алгоритмов для решения
задачи
ЗАКЛЮЧЕНР1Е
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А

ВВЕДЕНИЕ
Актуальность темы работы. Транспортная промышленность необходима для обеспечения производства сырьем и доставки готового товара потребителям. Особое внимание уделяется задачам, связанным с планированием маршрутов. По разным оценкам от 30% до 50 % всех затрат на логистику связано с транспортными издержками.
Формирование рациональных маршрутов при строгом соблюдении сроков поставок помогает добиться не только минимизации затрат на эксплуатацию, на перевозку людей, но и сократить товарнопроизводственные запасы на складах.
Задачам в области формирования оптимальных транспортных маршрутов посвящены многочисленные исследования в разных странах мира. Особую актуальность приобретают работы, позволяющие точно вычислять объемы грузоперевозок, рассчитывать количество единиц транспорта, необходимых для обеспечения грузопотоков, определять рациональные маршруты движения, а также сократить суммарные затраты на транспортировку. Эти обстоятельства подтверждают актуальность темы диссертации.
Степень разработанности темы исследования. В работе
рассматривается разновидность задачи маршрутизации транспортных
средств при перевозке грузов - VRP (Vehicle Routing Problem) - SVRPPD -
задача транспортной маршрутизации с вывозом и доставкой одним
транспортным средством. Первая задача транспортной маршрутизации была
сформулирована Г. Данцигом и Дж. Рамсером в 1959 году, ее постановка
инициировала важный класс задач оптимизации. Наиболее часто
встречающиеся постановки задач данного класса предполагают доставку
однородных грузов из пункта производства или склада потребителям.
Предполагается, что целью является минимизация стоимости
транспортировки. Встречаются задачи и с другой целевой функцией

(например, временем доставки грузов), но их, как правило, можно переформулировать таким образом, что целевая функция будет носить экономический смысл Как правило, задачи данного класса относятся к NP-трудным, точное решение которых при сколько-нибудь значительной размерности требует огромного количества времени. На сегодняшний день сформулировано множество вариантов данной задачи, в которых учитываются различные реальные ограничения, разработан ряд алгоритмов приближенного поиска оптимальных решений. Это связано с тем, что развитие логистических процессов и потребность в учете новых факторов ведут к постановке новых задач, требующих, в свою очередь, применения новых методов решения. Создана европейская рабочая группа VeRoLog (Vehicle Routing and Logistics), которая активно занимается задачами транспортной маршрутизации.
Необходимо указать на отличие задачи в рассматриваемой постановке от классической задачи маршрутизации транспортных средств. Особенностями рассматриваемой задачи являются наличие множественных пунктов-производителей, из которых производится вывоз груза. Поставленная задача может быть сформулирована, как целочисленная линейная оптимизационная задача, и является обобщением двух известных задач: задачи коммивояжера и задачи о загрузке рюкзака. Менее 10% работ, посвященных задачам транспортной маршрутизации, рассматривают данный вариант задачи. Результаты по близким задачам получены Cordeau J.-F. [51], Laporte G. [61, 173], Renaud J. [173], Desrosiers J. [67], Mingozzi A. [41], Pankratz G. [163], Ченцовым А.Г. [16], Гимади Э.Х. [11] и другими учёными. Также, создана европейская рабочая группа VeRoLog (Vehicle Routing and Logistics), которая активно занимается задачами транспортной маршрутизации.
Область исследования. Задачи организации транспортировки грузов.

Поставленную задачу можно свести к булевой задаче линейного программирования. Для этого введем матрицу перестановки X: Ху= (/,7=0,1,...,«), если число у расположено на г-ом месте перестановки и 0 в противном случае. Тем самым Х0о=1.
Должны выполняться следующие условия.
(1)-(5) это задача линейного целочисленного программирования. Для таких задач, которые относятся к классу АР-трудных, разработан целый ряд точных (ветвей и границ, отсечений), а также эвристических и метаэвристических алгоритмов.
Приведем оценки величины Дпш.
Алгоритм 1. Пусть р(Х),...,р{к) - положительные члены
последовательности («(/)) , т.е. объемы грузов в пунктах производства, - отрицательные члены последовательности (а(/)), т.е. потребности груза в пунктах потребления. Определим индуктивно следующие величины. к - максимальное натуральное число, для которого
2д(0 — 1 - максимальное натуральное число, для которого
£/>(/)+ ]Гд(У)> 0, кг — максимальное натуральное число, для которого
адо,і},

0<ЦХуа(У)<Д(£ = 1,...,«),
1=0 7=

5 -МПІП.