Содержание к диссертации
Введение
ГЛАВА 1 Состояние вопроса и постановка задач исследования 9
1.1 Современное состояние внутригородских перевозок мелких партий грузов 9
1.2 Обзор методов решения задач планирования перевозок мелких партий грузов 22
1.3 Цель и задачи исследования 37
ГЛАВА 2 Теоертические предпосылки планирования перевозок мелких партий грузов 42
2.1 Математическая модель задачи планирования перевозок мелких партий грузов 42
2.2 Алгоритм упорядоченного перебора пунктов транспортной сети 52
2.3 Оптимизация последовательности объезда пунктов 60
2.4 Выводы по 2 главе 65
ГЛАВА 3 Компьютерная программа и методика проведения экспериментаьных исследований 68
3.1 Методика оптимизации развозочных маршрутов 70
3.2 Экспериментальные исследования по проверке эффективности методики оптимизации развозочных маршрутов 79
3.2.1 Цель и задачи экспериментальных исследований 79
3.2.2 Методика проведения эксперимента 80
3.3 Экспериментальные исследования по выявлению влияния факторов на главный критерий оптимизации 88
3.3.1 Цель и задачи экспериментальных исследований 88
3.3.2 Условия внутригородских перевозок мелких партий грузов 89
3.3.3 Методика проведения эксперимента 97
3.4 Выводы по 3 главе 98
ГЛАВА 4 Экспериментальная проверка теоеретических положений и оценка эффективности исследований 100
4.1 Обработка экспериментальных данных по оценке эффективности разработанной методики оптимизации развозочных маршрутов 100
4.1.1 Обработка экспериментальных данных на предприятиях 100
4.1.2 Обработка экспериментальных данных по результатам моделирования 103
4.2 Обработка экспериментальных данных по выявлению влияния факторов на главный критерий оптимизации 115
4.3 Проверка экономической эффективности методики оптимизации развозочных маршрутов 122
4.4 Выводы по 4 главе 130
Заключение 131
- Обзор методов решения задач планирования перевозок мелких партий грузов
- Алгоритм упорядоченного перебора пунктов транспортной сети
- Условия внутригородских перевозок мелких партий грузов
- Обработка экспериментальных данных по выявлению влияния факторов на главный критерий оптимизации
Введение к работе
Актуальность проблемы. Развитие в стране рыночных условий
хозяйствования привело к существенным изменениям в содержании
коммерческой работы предприятий. С момента перехода экономики страны и
региона на рыночные отношения все большее значение стала приобретать
задача интенсификации производства. Повышение производительности
труда за счет внедрения новых технологий и технических средств,
совершенствования организации производства, оптимизации
технологических процессов является основным средством, обеспечивающим решение многообразных экономических и социальных задач, стоящих перед страной. В полной мере это относится и к грузовому автомобильному транспорту, который является одной из важных отраслей экономики страны и региона.
В связи с развитием малого и среднего бизнеса, которое привело к значительному увеличению числа как грузоотправителей, так и грузополучателей, объем перевозок грузов автомобильным транспортом до 2005 года может быть увеличен на 36,5%. В то же время происходит непрерывный процесс изменения и качественных характеристик грузов, в частности, - увеличивается стоимость единицы перевозимого груза.
С точки зрения эффективности, - сокращения складских запасов, ускорения оборачиваемости средств, - более дорогой груз выгоднее перевозить мелкими партиями. Этим обстоятельством, в том числе, объясняется наличие партионных грузов в структуре грузооборота автомобильного транспорта. С другой стороны, считается экономически оправданным, когда только возможно, перевозить груз большими партиями. Это противоречие определяет существование специфической формы организации работы автомобилей — развозочных маршрутов, - планирование которой сопряжено с необходимостью учета большого количества
5 технологических ограничений и обработки исходной информации значительного объема. При этом перевозки мелких партий грузов являются гораздо более дорогостоящими, чем перевозки массовых грузов.
Рыночные отношения, которые в значительной степени формируются в условиях неопределенности и неустойчивости среды, требуют высокоэффективных методов организации перевозок в плане повышения качества обслуживания заказчиков и экономии собственных ресурсов предприятий, что особенно важно при развитии конкуренции на рынке автотранспортных услуг. Это обуславливает необходимость разработки достаточно простых и быстрореализуемых алгоритмов оптимизации перевозок мелких партий грузов. В связи с этим повышение эффективности работы автомобилей на развозочных маршрутах является актуальной научной задачей.
Цель и задачи исследования. Цель диссертационной работы состоит в повышении качества оперативного планирования работы автомобильного транспорта при перевозках мелких партий грузов на основе разработки методики оптимизации развозочных маршрутов.
Достижению поставленной цели способствует решение следующих основных задач, определивших логику и внутреннюю структуру исследования:
анализ методов разработки маршрутов движения автомобилей при перевозках мелких партий грузов;
разработка математической модели и методики оптимизации маршрутов движения автомобилей при перевозке мелких партий грузов;
разработка алгоритма перебора пунктов транспортной сети, позволяющего оценить все возможные варианты маршрутов движения автомобилей;
разработка компьютерной программы для практической реализации предлагаемой методики, позволяющей провести исследования влияния факторов на главный критерий оптимизации -минимальный пробег автомобилей;
проведение экспериментальных исследований с целью оценки эффективности предлагаемой методики;
определение эффекта от использования предлагаемой методики.
Объектом исследования является ряд предприятий производственной
инфраструктуры многообразных организационно-правовых форм, использующих автомобильный транспорт для доставки мелких партий грузов.
Предметом исследования является процесс организации автомобильных перевозок мелких партий грузов.
Научная новизна исследования заключается в следующих положениях:
доказано, что имеющиеся к настоящему времени методы разработки маршрутов движения автомобилей при перевозках мелких партий грузов позволяют получить только один оптимальный маршрут (когда грузоподъемность автомобиля равна или больше суммарного объема перевозок по всем пунктам);
предложен алгоритм перебора пунктов транспортной сети, позволяющий оценить все возможные варианты маршрутов движения при обслуживании всех пунктов завоза - вывоза грузов мелкими партиями;
разработана математическая модель и методика оптимизации маршрутов движения автомобилей при перевозке мелких партий грузов, обеспечивающая получение оптимального результата;
выявлены зависимости влияния факторов (таких как: число маршрутов, грузоподъемность автомобиля, суммарный объем
7
вывоза груза, число пунктов завоза груза, соотношение числа
пунктов завоза груза и числа звеньев транспортной сети) на
снижение общего пробега автомобилей при обслуживании всех
пунктов.
Практическая ценность работы. Разработана эффективная методика
оптимизации развозочных маршрутов, обладающая высоким
быстродействием, экономичностью, оптимальным результатом решения.
Применение такой методики позволит повысить конкурентоспособность
предприятий за счет экономии собственных ресурсов вследствие снижения
общего пробега автомобилей при обслуживании всех пунктов завоза грузов
мелкими партиями, использования рациональных схем перевозок мелких
^ партий грузов.
Результаты выполненного исследования могут быть использованы предприятиями производственной инфраструктуры при доставке продукции от поставщиков до потребителей, в том числе организациями транспортной отрасли. А также в учебном процессе для студентов специальностей 240100.01 «Организация перевозок и управлении на транспорте» и 240400.01 «Организация и безопасность движения», направление подготовки 653400 -Организация перевозок и управление на автомобильном транспорте.
Реализация работы. Основные результаты теоретических и экспериментальных исследований приняты к практическому использованию в МУП «Спецавтохозяйство» г. Иркутска при планировании вывоза твердых бытовых отходов, при проектировании маршрутов доставки продукции с ОАО «Иркутского масложиркомбината» и в учебном процессе на кафедре «Менеджмент на автомобильном транспорте» Иркутского Государственного Технического Университета.
Апробация работы. Основные положения диссертационного исследования были представлены:
на ежегодных научно-технических конференциях ИрГТУ (г.
8 Иркутск, 2000 - 2003 гг.);
на смотре конкурсе НИР, НИРС и НТТМ молодых ученых и специалистов (г. Иркутск, 2001 г.)
на 5-ой межрегиональной научно-практической конференции «Интеллектуальные и материальные ресурсы Сибири» (г. Иркутск, 2002 г.);
на региональной научно-практической конференции «Актуальные проблемы АПК» (г. Иркутск, 2002 г.);
на II международной научно-технической конференции «Современные научно-технические проблемы транспорта России» (г. Ульяновск, 2002 г.);
на региональной научно-практической конференции «Роль предприятий и отраслей транспортной системы в социально-экономическом развитии Прибайкальского региона» (г. Иркутск, 2003 г.);
на X международной научно-практической конференции «Социально-экономические проблемы развития транспортных систем городов и зон их влияния» (г. Екатеринбург, 2004 г.).
Публикации. Основные положения и результаты диссертационной работы изложены в 12 публикациях.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, выводов, списка литературы и двух приложений. Работа изложена на 169 стр. машинописного текста, содержит 31 таблицу и 46 рисунков. Библиография на 10 стр. включает 124 наименования, в том числе 25 на иностранном языке.
Обзор методов решения задач планирования перевозок мелких партий грузов
Задача маршрутизации перевозок мелких партий грузов известна в двух постановках: как «задача коммивояжера» - когда для объезда всех пунктов должен быть построен только один маршрут движения грузового автомобиля или как «задача развозки» - когда строится несколько развозочных маршрутов, замкнутых у единственного отправителя [40]. Вторая постановка задачи - «задача развозки» - имеет большую практическую ценность, поскольку больше соответствует реальным условиям планирования перевозок мелких партий грузов.
Как известно, нахождение оптимальных маршрутов перевозок грузов представляет собой сложную математическую проблему. Эта проблема охватывает два взаимосвязанных вопроса - комплектацию маршрутов (набор пунктов транспортной сети) и определение порядка их объезда. Таким образом, в процессе планирования этих перевозок возникает задача построения маршрутов, при которых не превышалась бы грузоподъемность выделенных автомобилей, а суммарная длина всех маршрутов была бы минимальной.
Согласно [40, 41], для решения задачи маршрутизации перевозок мелких партий грузов разработан набор приемов, которые можно сгруппировать под следующими названиями: динамическое программирование; целочисленное линейное программирование; метод «ветвей и границ»; методы локальной оптимизации; методы случайного поиска; эвристические методы. Применение методов первых трех групп обеспечивает нахождение решения задачи, соответствующего объективному оптимуму целевой функции (обычно это - минимум пробега). Их называют точными методами. Методы последних трех групп дают из всех допустимых решений достаточно хорошие, но не обязательно лучшие решения. Поэтому в совокупности их называют методами получения приближенных решений. Наибольшее распространение, ввиду своей экономичности, получили эвристические методы. Практически все известные пакеты прикладных программ решения задач маршрутизации перевозок мелких партий грузов основаны на эвристических алгоритмах [16]. Примеров применения точных методов для решения практических задач в настоящее время не известно, однако есть примеры разработки эффективных алгоритмов, основанных на их модификации. Первой попыткой получения точного решения «задачи коммивояжера» было использование для этих целей метода динамического программирования [11, 95]. Основная идея этого метода заключается в следующем. Весь процесс вычислений разбивается на т + 1 стадий (т — общее количество пунктов завоза). На каждой к — той стадии рассматривается пункт, номер которого равен номеру стадии. Для каждой дуги, выходящей из этого пункта подсчитывается оценка (функция состояния) .] и из всех оценок выбирается та, которая имеет минимальное значение. Соответствующая выбранной дуге комбинация пунктов проверяется на выполнение условий: в каждый пункт входит только одна дуга; из каждого пункта выходит только одна дуга; в полученном фрагменте маршрута доставки груза нет подциклов (участков, замкнутых на себя). Если на данной стадии все дуги нарушают эти условия, то производится возврат на одну стадию назад и принятая на этой стадии дуга (к - 1)-7 игнорируется и выбирается следующая по оценке f(k-\)-i -f(k-\)-j (і j) дуга. Если условия не нарушены хотя бы для одной дуги, то производится переход на одну стадию вперед. Вычисления заканчиваются, когда достигнута т + 1 стадия. В изложенном виде этот алгоритм позволяет находить оптимальные решения для задач размерностью в 12 - 15 пунктов [40, 44]. В работе [44] предложена модификация этого метода, упрощающая поиск оптимального решения за счет коррекции функций состояния, что позволяет заранее указать варианты, превышающие верхнюю границу, следовательно, неоптимальные и исключать их из рассмотрения. Такая модификация метода позволяет находить оптимальные решения уже для задач размерностью в 30-40 пунктов. Еще один метод получения точного решения «задачи коммивояжера» приводится в работах [5, 100, 101, 108, 114]. В этих работах «задача коммивояжера» изложена как задача целочисленного программирования. Основная идея этого подхода заключается в дополнении основной системы линейных уравнений дополнительными ограничениями, которые определяют условие целочисленности переменных и отсутствие подциклов в оптимальном решении задачи.
Использование метода «ветвей и границ» для решения «задачи коммивояжера» впервые описано в работе [51]. Здесь процесс построения оптимального плана осуществляется следующим образом. На каждом шаге все множество путей коммивояжера разбивается на два непересекающихся подмножества, и для каждого подмножества определяется нижняя граница решения. Одно подмножество путей образуют пути, которые включают дугу i-j, а другое - пути, которые эту дугу не включают. Таким образом, в процессе решения строится «дерево» вариантов, имеющее в каждой вершине два ветвления. Если соответствующий одному из ветвей «дерева» вариант обхода пунктов имеет длину пути не большую, чем нижняя граница любого из неразбитых подмножеств, то этот путь является оптимальным. Если какое-либо неразбитое подмножество имеет нижнюю границу меньшую, чем длина найденного пути, то полученное решение и его нижняя граница запоминаются, а решение продолжается с того подмножества, которое имеет минимальную нижнюю границу. Процесс вычислений продолжается пока не будет найден путь, длина которого не превышает нижних границ неразбитых подмножеств или пройдены все пути.
Алгоритм упорядоченного перебора пунктов транспортной сети
Выполнив соответствующие действия, представленные на рис.2.4, для каждого і (/ = 1,ЛГ), находят все кратчайшие маршруты.
При запуске процедуры поиска вызывается процедура GetDivision, которая выполняет первичное разбиение: исходя из грузоподъемности автомобиля и необходимого объема перевозок грузов, определяется необходимое число маршрутов движения автомобиля для выполнения задания на поставки. Таким образом, осуществляется разбиение общего количества пунктов - получателей на несколько натуральных чисел всеми возможными способами (числа будут обозначать количество пунктов в одном маршруте). При этом необходимо учитывать то что, если сумма груза по любым к пунктам больше грузоподъемности автомобиля, то разбиения, включающие в себя число, большее или равное к, можно не перебирать. Кроме того, если известно, что сумма груза по к + I пунктам всегда меньше грузоподъемности, то разбиения, включающие одновременно числа к и /, также можно отбросить. Без учета этих ограничений алгоритм выглядит следующим образом.
Далее для каждого разбиения числа N - 1 на несколько натуральных чисел N], ..., Nk нужно перебрать все способы, которыми можно выбрать N\, ..., Nk пунктов из общего числа, т.е. проводится рекурсивный перебор всех возможных вариантов длин маршрутов с учетом количества пунктов перевозок. При этом учитывается, что два варианта (например, таких) не имеют принципиальных отличий, т.к. порядок, в котором выполняются маршруты, не существенен. Затем для каждого из вариантов запускается процедура GetSelectionl, которая на основании сформированных циклов рекурсивно перебирает все возможные комбинации пунктов перевозок по циклам (т.е. какие пункты входят в конкретный маршрут). Эта процедура разбивает пункты на подмножества с числом элементов N\, ..., Nk, но если среди JV[, ..., Nk есть равные числа, то соответствующие подмножества не разделяются. Чтобы разбить множество на подмножества заданной мощности, процедура GetSelectionl отбирает первое из подмножеств, а затем вызывает себя. В свою очередь процедура GetSelection2 выполняет разделение нескольких равных по мощности подмножеств. Отличие от процедуры GetSelectionl состоит в том, что 1-ый элемент из оставшихся выбирается всегда, для того чтобы исключить перестановки. После этого для каждой из этих комбинаций проверяется наличие превышения максимального объема перевозимого груза (вызывается процедура IncorrectSelection), т.е. находится суммарный объем требуемых грузов по каждому из циклов и сравнивается с грузоподъемностью автомобиля. Если полученная сумма не превосходит грузоподъемности автомобиля, то запускается процедура оптимизации последовательности объезда пунктов методом «ветвей и границ». Для каждого из вариантов рассчитывается суммарная длина маршрута. Это делается следующим образом: выбрать из матрицы расстояний {DV } наименьший элемент (Dy попарные расстояния между элементами подмножества с учетом кратчайших маршрутов). Пусть наименьший элемент - Ду; из остальных элементов выбрать тот, для которого сумма Dki + Д, минимальна. Пусть минимум достигается при / = т. Теперь элементы с номерами к, /, т образуют цикл; каждый следующий элемент включается в цикл по алгоритму представленному на рис. 2.6. После окончания перебора полученные комбинации маршрутов сортируются в порядке возрастания суммарной длины и результаты выводятся на экран. Основная трудность заключается в реализации данного алгоритма, т.е. обеспечении неповторяемости перебираемых вариантов, а также написании процедуры отсеивания заранее неподходящих вариантов (с превышением грузоподъемности). В описываемом выше алгоритме на каждом уровне применения рекурсии функция может модифицировать лишь фиксированный набор параметров. При этом функция непосредственно изменяет лишь один параметр, а для изменения остальных вызывает саму себя, но уже с запретом модифицировать параметр, который она изменила сама, т.е. рекурсия заключается в вызове функции самой себя с измененными параметрами. Для решения второго вопроса был разработан алгоритм, который осуществляет оптимизацию последовательности объезда пунктов всех возможных комбинаций маршрутов движения грузового автомобиля при использовании разновидности наиболее перспективного метода «ветвей и границ», который дает за конечное число итераций точное решение. Данный метод получил широкое распространение для решения «задачи коммивояжера». Суть метода заключается в упорядоченном переборе возможных вариантов транспортной сети и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов. Пусть задана некоторая транспортная сеть - допустимый план X и целевая функция L(R) - суммарная длина маршрутов движения грузового автомобиля, которую требуется минимизировать. Метод «ветвей и границ» поиска оптимального плана (маршрута) состоит в следующем.
Условия внутригородских перевозок мелких партий грузов
Точность любого из приближенных методов решения «задачи развозки» не является постоянной величиной, - разные задачи могут быть решены одним и тем же методом с разной степенью приближения к объективному оптимуму задачи. Чтобы колебания точности решений при статистической обработки информации не были восприняты за проявление влияния какого-либо из факторов, в данном эксперименте использован наиболее стабильный по точности решений метод.
Базовым методом для разработки методики решения «задачи развозки» принят метод Литтла-Кэрола-Мурти [51]. Основной процедурный механизм заключается в пошаговом слиянии двух фрагментов маршрутов в один. Слияние осуществляется путем соединения фрагментов дугой. При этом дуга может соединять только внешние точки из цепочки пунктов, образующих фрагмент маршрута. На каждом шаге образуется только один новый фрагмент. Существует строгое правило отбора фрагментов для образования нового — рассматривается только тот вариант слияния фрагментов, который отмечен нулевым элементом во вновь редуцированной матрице кратчайших расстояний. Преимуществом этого метода является возможность представления в явной форме всех ограничений задачи и простые способы проверки их выполнения, поскольку все расчетные операции производятся над матрицей кратчайших расстояний, которая наиболее полно и объективно отображает текущую информацию. Кроме того, принятая в этом методе процедура пошагового улучшения системы маршрутов позволяет на каждом шаге путем простых соотношений проверять допустимость намечаемых преобразований, поскольку в каждый момент вся система маршрутов представлена набором фрагментов, а правила преобразования системы допускают слияния фрагментов только со стороны свободных концов соответствующих цепочек пунктов. В этом случае характеристики укрупненного фрагмента легко рассчитываются через характеристики составляющих его фрагментов, поскольку внутри них никаких перестроений не производится.
В экономизирующем методе [41, 105] принят такой же способ пошагового улучшения системы маршрутов, но при этом все манипуляции производятся над матрицей выигрышей. Поэтому для проверки ограничений требуется хранение и матрицы кратчайших расстояний, что связано с дополнительными расходами памяти ПК. В этом отношении метод Литтла-Кэрола-Мурти предельно экономичен.
Однако, предусмотренный этим методом порядок анализа вариантов, опирающийся на схему метода «ветвей и границ», требует запоминания всех промежуточных шагов решения и предполагает возврат на несколько шагов назад по «дереву» вариантов для проверки оптимальности решения или для нахождения нового решения. Такой порядок решения требует дополнительных затрат времени и памяти ПК. Но для современных компьютеров это представляется вполне возможным. Еще один недостаток заключается в том, что метод «ветвей и границ» не дает возможности получать маршруты в случае, когда грузоподъемность автомобиля меньше суммарного объема перевозок по всем пунктам. Он может быть использован только при оптимизации последовательности объезда пунктов в случае, когда известен набор пунктов в каждом из маршрутов движения автомобиля.
Для устранения этого недостатка осуществлена разработка методики оптимизации развозочных маршрутов, которая в первую очередь предусматривает перебор всех возможных вариантов маршрутов, на основе разработанного алгоритма упорядоченного перебора пунктов транспортной сети при помощи процедуры рекурсии (см. глава 2), а затем уже для определения порядка объезда пунктов непосредственно используется метод «ветвей и границ».
Множество решений (планов) разбивается последовательно на подмножества, которые представляют между собой три категории. Подмножества первой категории удается отбросить заранее (не анализируя, каждый входящий в него план), как не содержащие оптимальных решений, либо допустимых решений. Для подмножеств второй категории находят наилучшее (для рассмотренных подмножеств) допустимое решение. Подмножества третьей категории, не входящие ни в одну из вышеуказанных, делятся на более мелкие подмножества для того, чтобы свести их к подмножеству одной из двух первых категорий. Процесс последовательного дробления и отбрасывания подмножеств продолжается до тех пор, пока множество подмножеств третьей категории не окажется пустым. Сравнивая, полученные для подмножеств второй категории наилучшие решения, получают оптимальное решение.
Заключение об отсутствии в некотором подмножестве оптимального решения основывается на использовании оценок снизу минимального значения функции цели на данном подмножестве. Пусть имеется некоторое допустимое решение х, и для некоторого подмножества Х\ решений можно указать такое число L, что L min Цх). Если L (х), то Х\ не содержит оптимальное решение и может быть отброшено. Вывод об отсутствии допустимых решений в некотором подмножестве делается в том случае, если хотя бы для одного из условий (2.12) нельзя найти в этом подмножестве допустимое решение. Такая проверка осуществлялась в соответствии с математическим алгоритмом [45]. Формализовано это выглядит следующим образом. Определяют подмножество Х2 как совокупность таких планов, у которых некоторые компоненты зафиксированы, остальные произвольны (О или 1). Для всех К, для которых Yk 0, проверяется выполнение условия: множество индексов нефиксированных компонент-планов подмножества Х2.
Если хотя бы для одного К условие не выполняется, в подмножестве Хг нет ни одного допустимого плана.
Каждому подмножеству ставят в соответствие вершину дерева решений, а дуги будут отображать деление подмножества на составляющие части. При такой интерпретации процесс поиска оптимального решения представляют как перемещение по вершинам дерева. В настоящем алгоритме, используется односторонний обход дерева, то есть после спуска по некоторой ветви происходит возвращение по этой ветви до тех пор, пока не встретится вершина, имеющая хотя бы одну необследованную ветвь, и вновь осуществляется спуск. Такой способ обхода дерева позволяет организовать компактное хранение информации, используемой при решении задачи. Основную часть памяти ПК занимают сведения о просмотренных (или не просмотренных) участках дерева. В данном случае достаточно хранить вершины одной главной ветви, на которой не может содержаться больше N + 1 вершин. Кроме того, для каждой вершины главной ветви необходимо хранить сведения о наличии неисследованных ветвей, исходящих из этой вершины.
Обработка экспериментальных данных по выявлению влияния факторов на главный критерий оптимизации
По графикам, представленным на рис. 4.2. - 4.5. видно, что квартальный размах (где сосредоточено 50% наблюдений) относительного изменения суммарной длины развозочных маршрутов полученных при рассмотрении сочетаний маршрут составленный в ходе моделирования работы оператора-диспетчера предприятия и маршрут составленный с использованием эвристических методов (метод «ветвей и границ», использование кратчайшей связывающей сети, метод суммирования по столбцам, метод Кларка - Райта) колеблется в пределах от -13% до +6% в зависимости от того, какой метод применялся для разработки маршрута движения. Т.е. использование вышеперечисленных эвристических методов планирования работы автомобилей позволяет сократить пробег транспортных средств. Но по результатам моделирования было выявлено, что наиболее перспективным для решения задач маршрутизации является метод «ветвей и границ», применяемый для планирования маршрутов движения. Т.к. среднее отклонение суммарной длины маршрутов при составлении маршрута оператором-диспетчером предприятия и составлении маршрута с использованием данного метода оказалось самым максимальным -7,83%. Следовательно, если применять метод «ветвей и границ» для последовательности объезда пунктов, когда известен набор пунктов в маршруты, то он дает оптимальный результат.
По графикам, представленным на рис. 4.6 - 4.8 видно насколько увеличивается суммарная длина маршрута при решении «задачи развозки» эвристическими методами (использование кратчайшей связывающей сети, метод суммирования по столбцам, метод Кларка - Райта) от решения «задачи коммивояжера» (метод «ветвей и границ»). Квартальный размах переменных составляет от 13% до 35%.
По графикам, представленным на рис. 4.9 - 4.12 видно, что квартальный размах (где сосредоточено 50% наблюдений) относительное изменение суммарной длины развозочных маршрутов полученных при рассмотрении сочетаний маршрут составленный с использованием разработанной методики оптимизации маршрутов движения автомобилей при перевозках мелких партий грузов и маршрут составленный с использованием экономико-математических методов (использование кратчайшей связывающей сети, метод суммирования по столбцам, метод Кларка - Райта) колеблется в пределах от - 21% до - 6% в зависимости от того, какой метод применялся для разработки маршрута движения. Т.е. анализ результатов показал, что доставка грузов мелкими партиями, планируемая диспетчером предприятия даже с применением эвристических методов имеет тенденцию к заметному сокращению пробега транспортных средств. Но, тем не менее, традиционные методы планирования и организации перевозок, не могут обеспечить оптимальное решение задач, возникающих при эксплуатации автомобильного транспорта.
Большие объемы информации, зарождающиеся в процессе выполнения перевозок, требуют срочной обработки как в целях учета, так и в целях анализа, необходимого для оперативного управления. В современных условиях решение задач маршрутизации перевозок грузов методом ручного счета крайне затруднено, а во многих случаях и просто неосуществимо.
По графику, представленную на рис. 4.13 видно, что квартальный размах абсолютного изменения суммарной длины маршрутов при решении «задачи развозки» с использованием методики оптимизации маршрутов движения автомобилей при перевозках мелких партий грузов и при решении «задачи коммивояжера» с использованием метода «ветвей и границ» составляет от -14% до -6%.
Таким образом, по результатам моделирования наиболее эффективным методом разработки маршрутов движения автомобилей при перевозках мелких партий грузов признана предлагаемая методика оптимизации развозочных маршрутов. У этой методики наименьшие: суммарная длина маршрутов по всем результатам моделирования (характеристика точности метода), сумма процентов отклонений (характеристика стабильности метода). Имеется еще один факт существенного преимущества разработанного алгоритма, - он дает наименьшее из всех методов количество маршрутов, - который может оказаться решающим условием для выбора того или иного плана перевозок. Следовательно, для ежедневной организации перевозок необходимо использовать автоматизированную систему управления.
В соответствии с разработанной методикой оптимизации рациональных развозочных маршрутов были выявлены зависимости влияния факторов на минимальный пробег автомобилей и количество комбинаций маршрутов. Рассматривались следующие факторы, характеризующие условия перевозок, с точки зрения их возможного влияния на окончательное решение «задачи развозки»: число пунктов завоза груза; соотношение числа пунктов завоза груза и числа звеньев транспортной сети; суммарный объем вывоза груза; грузоподъемность автомобиля; число маршрутов. В табл. 4.4 приведены основные характеристики теоретических зависимостей, полученных при использовании разработанной компьютерной программы по определению рациональных развозочных маршрутов (см. приложение 1) На графиках, представленных на рис. 4.14, 4.16, 4.18 отражены зависимости суммарной длины маршрутов от грузоподъемности автомобиля, суммарного объема вывоза груза, количества пунктов завоза груза. Данные зависимости представляют полиномиальные модели, охарактеризованные уравнением шестого порядка. На рис. 4.19 отражена зависимость суммарной длины маршрутов от числа пунктов завоза груза и числа звеньев транспортной сети, которая может быть описана логарифмической моделью. Зависимость количества комбинаций маршрутов от грузоподъемности автомобиля (рис. 4.15) представляет полиномиальную модель, охарактеризованную уравнением четвертого порядка. Зависимость количества комбинаций маршрутов от суммарного объема вывоза груза от отправителя (рис.4.17) может быть описана логарифмической моделью. И зависимость количества комбинаций маршрутов от числа пунктов завоза груза и числа звеньев транспортной сети представляет экспоненциальную модель. На рис. 4.21 отражена зависимость абсолютного изменения суммарной длины маршрута от количества маршрутов движения автомобиля. Данная зависимость может быть описана логарифмической моделью.
