Содержание к диссертации
Введение
Глава 1. Обзор и анализ проблем на автомобильном транспорте 9
1.1. Современное состояние автомобильной отрасли в РФ 9
1.2. Понятие и сущность мелкопартионных перевозок 19
1.3. Логистические показатели мелкопартионных перевозок 26
1.4. Выводы по главе 45
Глава 2. Состояние теории мелкопартионных перевозок 46
2.1. Методы решения задачи маршрутизации 46
2.2. Анализ алгоритма Кларка-Райта 64
2.3. Выводы по главе 83
Глава 3. Усовершенствование алгоритма Кларка-Райта для решения задачи маршрутизации мелкопартионных перевозок 84
3.1. Описание объекта исследования 84
3.2. Усовершенствованный алгоритм Кларка-Райта 91
3.3. Оценка эффективности усовершенствованного алгоритма Кларка-Райта . 120
3.4. Выводы по главе 130
Заключение 132
Литература 135
Приложения 148
- Понятие и сущность мелкопартионных перевозок
- Анализ алгоритма Кларка-Райта
- Усовершенствованный алгоритм Кларка-Райта
- Оценка эффективности усовершенствованного алгоритма Кларка-Райта
Введение к работе
Актуальность темы исследования. Произошедшие изменения в характере спроса на транспортные услуги привели к тому, что на сегодняшний день в структуре грузооборота грузового автомобильного транспорта 80% составляют мелкопартионные грузы, перевозимые преимущественно по развозочным маршрутам. При этом оперативное планирование развозочных маршрутов сопряжено с необходимостью учета большого количества технологических ограничений и обработки исходной информации значительного объема. Возникающая при этом ситуация является задачей маршрутизации.
Решение задачи маршрутизации по-прежнему особенно актуально в целях уменьшения транспортных затрат при массовой перевозке сырья или готовой продукции.
Одновременно существует недостаток хорошо зарекомендовавших себя на практике методик по эффективному решению задачи маршрутизации. Это обуславливает необходимость разработки достаточно простых и реализуемых на практике за разумное время алгоритмов оптимизации логистических показателей перевозок мелкопартионных грузов на автомобильном транспорте.
Степень разработанности темы исследования. На формирование положений диссертационного исследования оказали влияние фундаментальные и прикладные научные работы отечественных и зарубежных авторов в области оптимизации логистических показателей мелкопартионных перевозок на автомобильном транспорте. В области экономики автомобильного транспорта - Бронштейн Л.А., Воркут А.И., Гудков В.А., Канторович Л.В., Квитко Х.Д.; в области логистики - Бауэрсокс Д., Безель Е.П., Вельможин А.В., Дуболазов В.А., Клосс Д., Миротин Л.Б.; в области экономико- математических методов управления производством - Бабаев А.А., Глухов В.В., Кобзев
-
В., Козловский В.А., Тютюкин В.К.; в области математических моделей и методов решения задачи маршрутизации - Аникеич А.А., Беллман Р., Геронимус Б.Л., Грибов А.Б., Данциг Г., Дейкстра Э., Житков В.А., Кормен Т., Лейзерсон Ч., Литтл Д., Уоршалл
-
, Флойд Р., Хелд М., Штайн К., Clarke G., Wright J.W.
Цель и задачи исследования. Цель работы состоит в том, чтобы повысить эффективность перевозок мелкопартионных грузов автомобильным транспортом на основе разработки методики оптимизации логистических показателей системы перевозки.
Для достижения поставленной цели в диссертационной работе были сформулированы и решены следующие основные задачи:
1) рассмотрено современное состояние автомобильной отрасли в РФ, выявлена количественная связь между грузооборотом грузового автомобильного транспорта и
валовым внутренним продуктом России;
2) уточнено определение мелкопартионных перевозок, дана классификация мелкопартионных перевозок;
-
-
исследованы критерии оптимальности задачи маршрутизации и выбрана система логистических показателей перевозки мелкопартионных грузов;
-
проведен анализ и систематизация экономико-математических методов применяемых для решения задачи маршрутизации;
-
разработана методика оптимизации логистических показателей перевозки мелкопартионных грузов на базе усовершенствованного метода Кларка-Райта;
-
разработан программный продукт для практической реализации предлагаемой методики;
-
рассчитан экономический эффект от использования предлагаемой методики на примере транспортной подсистемы конкретного предприятия.
Объект исследования - предприятие пищевой промышленности, применяющее грузовой автомобильный транспорт для перевозки мелкопартионных грузов.
Предмет исследования - логистические процессы, протекающие в транспортной подсистеме промышленного предприятия.
Теоретическую и методологическую базу исследования составляют работы отечественных и зарубежных авторов по методологии оптимизации логистических показателей мелкопартионных перевозок с помощью математических методов.
В ходе исследования были использованы методы: сравнительный, монографический, статистический, расчетный.
Основные результаты и научная новизна. В диссертационном исследовании получены следующие основные научные результаты, которые выносятся на защиту.
-
-
-
Доказана количественная связь между ВВП РФ и грузооборотом грузового автомобильного транспорта, отличительной особенностью которой является возможность долгосрочного прогнозирования влияния роста грузооборота грузового автомобильного транспорта на ВВП РФ.
-
Предложено новое определение мелкопартионных перевозок, позволяющее построить классификации мелкопартионных перевозок.
-
Доказана количественная связь между расходами грузового автомобильного транспорта и потреблением дизельного топлива и бензина, отличительной особенностью которой является возможность анализа последствий сокращения потребления топлива для транспортной отрасли.
-
Определена система логистических показателей эффективности перевозки мелкопартионных грузов на грузовом автомобильном транспорте, отличительной особенностью которой является практическая применимость и возможность разработки методики по оптимизации логистических показателей мелкопартионных перевозок на грузовом автомобильном транспорте.
-
Проведён анализ и предложена классификация экономико-математических методов, используемых в транспортной отрасли для решения задачи маршрутизации, отличительной особенностью классификации является возможность выбора наиболее перспективного метода для его последующего усовершенствования.
-
Разработан новый приближенный алгоритм для решения задачи маршрутизации «Усовершенствованный Кларк-Райт», отличающийся от классического алгоритма Кларка- Райта сокращением протяженности и времени маршрутов.
Теоретическая значимость заключается в создании нового метода (усовершенствованного алгоритма Кларка-Райта) для решения задачи маршрутизации класса VRP (Vehicle Routing Problem) . Соответственно, расширилась сфера применения приближенных алгоритмов для решения трудноразрешимых задач.
Практическая значимость. Предложенная методика может применяться организациями, осуществляющими в своей деятельности перевозку мелкопартионных грузов. Применение методики позволит уменьшить транспортные расходы, оптимизировать численность логистической службы предприятия, соответственно, уменьшить себестоимость продукции и, тем самым, увеличить финансовый результат предприятия и эффективность его деятельности.
Реализация и внедрение результатов работы. Основные результаты исследования приняты к практическому внедрению следующими предприятиями г. Санкт-Петербурга: ОАО «Хлебный завод «Арнаут», ООО «Сладкоежка». Материалы диссертации используются в учебном процессе ФГБОУ ВПО «СПбГТЭУ» при теоретической и практической подготовке бакалавров по направлениям 080100.62 «Экономика» по дисциплине «Экономика организации» и 080200.62 «Менеджмент» по дисциплине «Экономика фирмы». Материалы диссертации реализованы при разработке учебно- методического комплекса по дисциплине «Логистика» для студентов НОИР специальности 080502 «Экономика и управление на предприятии». Результаты исследований были использованы в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы» по теме «Анализ, прогнозирование и регулирование социальной устойчивости регионов» при оценке современного состояния автомобильной отрасли в РФ, разработке системы логистических показателей мелкопартионных перевозок и усовершенствовании алгоритма Кларка-Райта.
Апробация результатов исследования. Основные результаты диссертационного исследования были обсуждены и одобрены на одной международной научно-практической
конференции (Пенза, 2008г.), на одной всероссийской научно-практической конференции (Пенза, 2008г.) и одной научно-методической конференции (СПб, 2012г.).
Публикации результатов исследования. По проблемам, рассматриваемым в диссертационном исследовании, автором опубликовано 17 печатных работ, в том числе 8 в изданиях, входящих в перечень ВАК.
Область исследования соответствует следующим пунктам Паспорта специальности 08.00.13. - Математические и инструментальные методы экономики:
1.2. Теория и методология экономико-математического моделирования, исследование его возможностей и диапазонов применения: теоретические и методологические вопросы отображения социально-экономических процессов и систем в виде математических, информационных и компьютерных моделей.
2.1. Развитие теории, методологии и практики компьютерного эксперимента в социально-экономических исследованиях и задачах управления.
Структура исследования. Работа состоит из введения, трех глав, заключения, списка используемых источников и приложений. Она изложена на 188 страницах, содержит 51 таблицу, 17 рисунков, 9 приложений. Список литературы включает 130 источников.
Понятие и сущность мелкопартионных перевозок
В соответствии с целью исследования детально рассматривается понятие « мелкопартионные перевозки».
Отметим, что еще Л.В. Канторович в [39] рекомендовал классифицировать перевозки - «необходимо разработать единую для всех видов классификацию грузов, согласованную с номенклатурой межотраслевого баланса».
С 1975 г. Леонид Витальевич Канторович руководил Научным советом АН СССР по транспорту, поэтому вопросы совершенствования транспортной отрасли были близки нашему первому и пока единственному нобелиату в области экономики.
А.И. Воркут в [18] говорит: «к партионным перевозкам относятся перевозки партий грузов, размер которых меньше грузоподъемности наиболее эффективных транспортных средств, допускаемых предельными осевыми нагрузками и габаритными регламентациями на дорогах». И далее он уточняет: «перевозка небольших партий грузов считается мелкопартионной».
Ю.М. Неруш в [56] предлагает считать мелкопартионными перевозками для автомобильного транспорта « массой до 5 т».
В. А. Житков в [34] дает следующее определение мелкопартионных перевозок. «На практике отправители и получатели груза выставляют одно важное условие, которое во многом определяет специфику задач маршрутизации. Это условие заключается в том, что завоз или вывоз груза должен осуществляться возможно более крупными партиями. Требовательность к выполнению этого условия возрастает с уменьшением количества груза к единовременному получению (отправлению) в каждом пункте и при таком уменьшении партии груза, когда он может быть завезен (вывезен) автомобилем за один прием, это требование становится всегда обязательным к выполнению. Такие партии груза называются мелкими...»
В настоящий момент однозначного определения мелкопартионных перевозок не существует. Критерий партионности, названный в [19] - партия груза меньше грузоподъемности транспортного средства. Следовательно, если мы принимаем данный критерий, отталкиваться надо от грузоподъемности автомобиля. Рассмотрим получающийся при таком подходе результат.
Так, например, Туревский И.С. в [81] называет мелкопартионными перевозками такие перевозки, «при которых масса партии груза не превышает половины грузоподъемности подвижного состава». Резонно предположить, что перевозка становится просто партионной (или массовой), когда вес груза для одного грузополучателя составляет от 50 до 100% грузоподъемности транспортного средства. И это возможно, например, для хлебобулочной продукции. Когда финский концерн «Fazer», специализирующийся в нашей стране на хлебобулочной продукции, начинал осваивать рынок Москвы, из СПб в Москву отправлялись полностью груженые хлебобулочной продукцией КАМАЗы. Маршрут был маятниковый: Санкт-Петербург-Москва-Санкт-Петербург. Продукция выгружалась у одного грузополучателя.
Наиболее распространены мелкопартионные перевозки в следующих сферах:
1) торговля продовольственными товарами (хлебобулочная продукция, мясная, молочная);
2) общественное питание (доставка в школы готовых блюд)
3) коммунальное хозяйство (вывоз мусора);
4) почтовые перевозки (доставка отправлений получателям «EMS Почта России»);
5) промышленность и строительство (перевозка проката, метизов).
В данном исследовании в качестве примера рассматриваются мелкопартионные перевозки хлебобулочной продукции в Санкт-Петербурге и Ленобласти.
Мелкопартионные перевозки являются значительно более дорогостоящими, чем перевозки массовых грузов. По оценке Житкова В.А. и Кима К.В. при 2% обшей транспортной работы, приходящейся на перевозки мелких партий грузов, на их долю приходится более 32% транспортных затрат [33]. Эта оценка 1984г., сейчас на долю мелкопартионных перевозок приходится 80% грузооборота.
Следовательно, пополняя, уточняя и анализируя информацию по мелкопартионным перевозкам, мы способствуем оптимизации транспортных затрат в масштабе всего народного хозяйства.
Отталкиваясь от грузоподъемности транспортного средства (далее ТС), оценим примерный вес мелкопартионной перевозки. При этом воспользуемся подходом Туревского И.С., согласно которому для мелкопартионной перевозки «масса партии груза не превышает половины грузоподъемности подвижного состава». Структура парка грузовых автомобилей в РФ за 2008г. приведена в [78]. Тягачи, самосвалы и иномарки мы рассматривать не будем (табл.1.8.).
Итак, для автомобильного грузового транспорта мы можем оценить мелкопартионную перевозку как перевозку, вес которой находится в пределах от 0,25т (для ИЖ-2715) до 3,0 тонны (для ЗИЛ-130, КАМАЗ-4310). Это означает, что машина пойдет в рейс заполненной менее чем наполовину, такое положение дел не устраивает грузоперевозчика. Нам представляется, что наиболее важный критерий мелкопартионности следующий - наличие нескольких грузополучателей, вследствие чего маршрут становится развозочным. Перевозка мелких партий грузов на маятниковых маршрутах неэффективна, поскольку для таких маршрутов нужны автомашины малой грузоподъемности. Уточним определение развозочного маршрута. А.И. Воркут в [18] предлагает такое определение: «Развозочным называется такой маршрут, на котором происходит постепенная разгрузка грузов».
Более точное определение дает Житков В.А. в [34]: «... важен тот момент, что у отправителя автомобиль заполняется грузом сразу двух (или более) пунктов и по очереди доставляет им груз. Это типичное явление для развозочных маршрутов, и задачи построения таких маршрутов называются задачами развозки».
На необходимость применения развозочных маршрутов для реализации мелкопартионных перевозок указывал также Воркут А.И. в [18] -«...транспортный процесс партионных перевозок рассматривается в наиболее общей постановке - при доставке грузов на развозочных маршрутах».
В соответствии с вышесказанным, мы можем уточнить определение мелкопартионной перевозки, данное Туревским И.С. в [81].
«Мелкопартионная перевозка на грузовом автомобильном транспорте - это такая перевозка, при которой маршрут развозочный, вес груза для одного грузополучателя не превышает половины грузоподъемности ТС, минимальное число грузополучателей два».
Если предположить, что вес груза для одного получателя колеблется в пределах [0,25; 0,5] грузоподъемности ТС, то общий вес мелкопартионной перевозки будет в пределах [0,5; 1,0] грузоподъемности ТС. Здесь мы уточнили ограничение по весу груза для одного получателя таким образом, что автомашина пойдет в рейс заполненной более, чем наполовину. Поэтому предложенный диапазон выглядит более рациональным для мелкопартионных перевозок. Но этот вариант близок к идеальному. Действительность опровергает его, так как максимальное число грузополучателей зависит от экономической эффективности доставки груза. Например, для хлебобулочного производства обыденным является случай, когда одному грузополучателю везут всего 5 лотков с продукцией. Особенно это характерно для кондитерской продукции и сдобы, как наиболее дорогостоящей в ассортименте продукции хлебных заводов. Тогда для той же автомашины «Газель», вместимость которой 120 лотков типоразмера №3, число грузополучателей может доходить до 24. Следовательно, для автомашины «Газель» в случае развозки кондитерской и сдобной продукции число пунктов развозочного маршрута мелкопартионной перевозки может составлять от 2 до 24, не считая грузоотправителя.
Легко оценить верхнюю границу длины развозочного маршрута. Рассмотрим это на примере мелкопартионных перевозок хлебобулочной продукции. По данным Госкомстата РФ средняя эксплуатационная скорость движения грузовых автомобилей примерно 20 км/час [79].
Анализ алгоритма Кларка-Райта
Алгоритм Кларка-Райта был разработан одновременно двумя английскими учеными Г. Кларком (G. Clark) и Дж.В. Райтом (J.W. Wright) [97].
Алгоритм Кларка-Райта является одним из первых приближенных алгоритмов решения задачи маршрутизации. Достоинствами метода являются его простота, надежность и гибкость, что позволяет учитывать целый ряд дополнительных факторов, влияющих на конечное решение задачи. Алгоритм Кларка-Райта является одним из алгоритмов классической эвристики. Точное решение задачи маршрутизации можно найти только методом полного перебора всех вариантов маршрутов. Соответственно, нет методов нахождения точного решения задачи маршрутизации за полиномальное время (точный алгоритм на основе метода ветвей и границ применим для малого числа пунктов). Поэтому возникли приближенные (не имеющие строгого математического обоснования) эвристические алгоритмы. Эвристика работает гораздо быстрее, чем метод полного перебора. Начиная с 90-ых годов 20 века появляются метаэвристики, назначение которых - основа для построения законченной эвристики. Т.е. метаэвристика - это метод для построения классического эвристического алгоритма.
Идея применения алгоритма Кларка-Райта заключается в следующем. Рассчитываются экономии (функции выгоды) по формуле (13):
Строится система из п радиальных маршрутов вида {0Д,0}. Решается задача развозки мелкопартионных грузов. Условие мелкопартионности (число автомашин меньше числа получателей):
Для задачи развозки справедливо условие - спрос любого из получателей, как правило, меньше вместимости автомашины:
Система радиальных маршрутов удовлетворяет условиям (5)-(7) задачи маршрутизации, но включает в себя слишком много мелких маршрутов. Эта система будет преобразовываться посредством постепенного объединения маршрутов, при этом будет проверяться справедливость условий (5)-(7) по отношению к новым системам.
В основе объединения маршрутов лежит задача максимального снижения длины маршрутов. Для этого последовательно рассматриваются функции выгоды в порядке их убывания и соответствующие пары получателей включаются в маршрут.
Такой процесс завершится после рассмотрения всех функций выгоды. Если начальная система будет трансформирована в систему, для которой условия (5)-(7) будут выполняться, то задача решена.
Рассмотрим на примере алгоритм Кларка-Райта более подробно.
Исходные данные получены по материалам хлебного завода ОАО «Хлебный завод «Арнаут» г. Санкт-Петербурга.
Есть 10 получателей Петроградского района. Сформирована матрица расстояний 11x11, так как мы учитываем и сам завод отправитель (табл.2.2).
Матрица симметричная (поэтому заполним только ее, например, верхний треугольник), так как предполагается, что возможен проезд автомашин как из пункта і в пункт j, так и обратно, причем по тому же самому пути. Зачастую это не соответствует реалиям жизни.
Располагая матрицей расстояний, легко сформировать матрицу экономии. Как отмечено выше, в методе Кларка-Райта два радиальных маршрута объединяются и рассчитывается полученный выигрыш.
Экономия (функция выгоды) при применении кольцевого маршрута вместо двух радиальных составит величину, рассчитанную по формуле (13).
Так, например, по исходной матрице расстояний выигрыш при объединении получателей 3 и 6 составит:
Аналогично рассчитываются выигрыши при объединении других радиальных маршрутов в кольцевые маршруты.
Формируется матрица экономии. Она также симметричная (табл.2.3). Соответственно, мы ограничимся заполнением только нижнего треугольника, так как треугольник выше главной диагонали будет идентичный.
Известен вектор спроса - сколько лотков следует доставить тому или иному получателю (табл.2.4). Следует отметить, что этот вектор спроса может меняться, так как заказ получателя меняется изо дня в день. Возможен также случай, когда заказ равен 0. Тем не менее, получатель остается в матрице расстояний. Не исключено, что проезд мимо этого получателя позволит сократить длину маршрута.
Учитываем ограничения, которые накладывают особенности работы хлебного завода (табл.2.5). Парк автомашин хлебного завода состоит, прежде всего, из «Газелей». Соответственно, все данные табл.2.5 относятся именно к применению этих автомашин.
Эти ограничения можно учесть следующим образом.
1) В среднем на погрузку готовой продукции и на выгрузку из машины тары (пустых лотков) требуется г=0,5+0,25=0,75 часа (см. табл.2.5, строки 2 и 3).
Следовательно, рабочий день водителя (8 часов) сразу же уменьшается на эту цифру и становится равным 7,25 часа.
2) После погрузки готовой продукции оформляются документы на уже загруженную продукцию, так как в процессе загрузки какого-то наименования хлебобулочной продукции может не хватить. Если же документы (счета-фактуры, транспортные накладные и пр.) были оформлены предварительно, придется их переделывать (в случае нехватки какой-либо продукции).
Это время оформления на загруженную продукцию рассчитывается по формуле
3) Время оформления готовой продукции, которую приняли п получателей, рассчитывается по формуле
4) Средняя скорость выгрузки лотков у получателя - 100 лотков/час (см. табл.2.5, строка 5). Средняя скорость погрузки пустых лотков в том же количестве, что и были выгружены - 200 лотков/час (см. табл.2.5, строка 7). Тогда суммарное время на выгрузку готовой продукции и погрузку пустых лотков по маршруту Rk (k=l:m) составит
Усовершенствованный алгоритм Кларка-Райта
Алгоритм Кларка-Райта характеризуется быстротой и относительной простотой реализации. Но «жадность» алгоритма означает, что не всегда мы придем к оптимальному решению. Известен ряд попыток усовершенствования алгоритма Кларка-Райта. Рассмотрим их.
В 1967 году Гаскелл в [103] ввел параметр А, (названный параметром формы маршрута), который управляет относительной важностью формы дуги между получателями і и j в вышеназванном вычислении экономии е у
В 1988г. Паесенс в [116] включил в выражение функции выгоды новую компоненту вместе с весовым параметром ц, который учитывает "асимметрию" по расстоянию от склада до каждого из двух "слитых" клиентов. Результирующая формула экономии такая:
В 1998 году Голден предложил использовать генетический алгоритм для настройки параметров алгоритма Кларка-Райта [108]. Была реализована двухэтапная процедура и, соответственно, два разных генетических алгоритма для определения значения параметра лагранжевых релаксаций для задачи маршрутизации.
В 2002 году Пеппер предложил использовать метод отжига для настройки параметров алгоритма Кларка-Райта [119].
В 2003 году Чандран применил генетический алгоритм в одноэтапной процедуре настройки параметров алгоритма Кларка-Райта [94].
В 2005 году Алтинел и Онкан в [90] также применили одноэтапную процедуру, базирующуюся на генетическом алгоритме. В данном подходе реализуется расширение алгоритма Кларка-Райта большим количеством разных векторов параметров метода. К уже имеющимся параметрам X и \х они добавили параметр v и рассматривали различные комбинации трех независимых параметров (к, ц, v).
Алтинел и Онкан представили третью весовую компоненту в формуле выигрыша, чтобы сосредоточиться на спросах клиента, согласно идее «больший комбинированный маршрут является лучшим»:
Новое выражение требует настройки трех независимых параметров (к, ц, v).
Итоговый вычислительный алгоритм оказался лучше, чем оригинальный эвристический Кларка-Райта.
Рассматривая предложенные методы алгоритма Кларка-Райта, можно отметить, что суть их сводится к уточнению формулы выигрыша и последующей настройке независимых параметров. При этом используются генетический алгоритм и метод отжига.
Мы предлагаем усовершенствовать алгоритм Кларка-Райта алгоритмами Флойда-Уоршалла (приложение 5) и Дейкстры (приложение 6). Здесь применяется главная функция этих алгоритмов - поиск кратчайшего пути между заданной начальной вершиной и заданной конечной вершиной графа.
В общем случае матрица расстояний может учитывать только прямые связи между пунктами. Эти маршруты далеко не всегда кратчайшие. При включении в маршрут новой вершины длина маршрута может стать меньше.
Например, для ориентированного графа на рис.9
По матрице расстояний между вершинами 1 и 3 расстояние 30, в то время как маршрут 1-5-3 дает расстояние 20. Поясним, почему в данном случае не выполняется неравенство треугольника. На рис.9 представлен ориентированный граф G (V,E) у которого все дуги имеют положительный вес.
В общем случае под весом дуги может пониматься всё, что угодно, не только евклидово расстояние между вершинами, но и, например, плата за проезд (время, энергия и др.). Вес дуг может быть положительным, отрицательным, нулевым. Отталкиваясь от платы за проезд, поясним понятие «дуга отрицательного веса». Как правило, перевозчик платит за проезд - это дуга положительного веса. Если же вдруг перевозчику платят за проезд по данной дуге, то это дуга отрицательного веса, так как эта дуга приносит доход. Если же проезд бесплатный, то это дуга нулевого веса.
В условиях города дуга орграфа обладает «весом», который в общем случае не является евклидовым расстоянием между получателями, так как в условиях города практически невозможно добраться от одного получателя до другого именно по прямой линии. Поэтому вполне возможен вариант треугольника из вершин №№1,3,5, изображенный на рис.9.
Имеет смысл провести предварительную оптимизацию матрицы расстояний, так как компьютерная программа, реализующая алгоритм Кларка-Райта, не «знает», что исходная матрица расстояний обязательно матрица кратчайших расстояний. Этой информацией владеет только пользователь программы, так как именно он будет составлять и менять матрицу расстояний. В условиях большого города зачастую расстояния между получателями отделом логистики определяются путем объезда на машине.
Алгоритм Роберта Флойда и Стивена Уоршалла (далее - алгоритм Флойда-Уоршалла) позволит нам найти в предложенной матрице расстояний между получателями кратчайшие пути между получателями продукции. При этом нам известно, что в полученной матрице будут только значения этих кратчайших путей, без полного указания самого пути. Исторически сначала минимальное расстояние между пунктами было найдено алгоритмом Флойда-Уоршалла, но этот алгоритм не указывает промежуточные пункты маршрута. Однако этот алгоритм позволяет работать, если в графе есть дуги отрицательного веса.
Для того чтобы определить сам путь, т.е. последовательность промежуточных получателей, через которых будет проходить этот кратчайший путь, мы применим алгоритм Дейкстры. Для вывода развернутого маршрута, где указываются промежуточные пункты, используются результаты алгоритма Дейстры. Тем самым становится известным путь минимального расстояния. Но алгоритм Дейкстры не работает, если в графе есть дуги отрицательного веса.
Отметим, что алгоритм Дейкстры работает с ориентированными графами. Особенности комбинации алгоритмов Флойда-Уоршалла и Дейкстры представлены в табл.3.4.
Рассматриваемая матрица расстояний характеризуется следующими свойствами.
1. Для всех i, j є N существует путь от получателя і к получателю j (получатели і и j связаны маршрутом). Если рассматривать транспортную сеть получателей Петроградского района СПб как граф, то это связный граф.
2. В рассматриваемой транспортной сети возможен проезд по ребру графа в обе стороны, при этом расстояние не меняется. Соответственно, каждое неориентированное ребро можно заменить парой ориентированных рёбер (дуг) с противоположной ориентацией и равного веса. В данном случае под весом подразумевается расстояние. Это преобразование неориентированного графа в ориентированный позволяет применить алгоритм Дейкстры.
3. Рассматриваемые маршруты не имеют петель (см. гл.2). Если исследовать транспортную сеть получателей Петроградского района СПб как неориентированный граф, то это связный неориентированный ациклический граф или дерево.
4. В транспортной сети получателей Петроградского района СПб нет петель и любая пара вершин соединена не более чем одним ребром. Соответственно, это простой граф.
Оценка эффективности усовершенствованного алгоритма Кларка-Райта
Произведем оценку эффективности усовершенствованного алгоритма Кларка-Райта. Рассмотрим экономическую эффективность внедрения компьютерной программы.
Для этого сравним длину маршрутов получателей Петроградского района СПб, полученных тремя методами - методом Кларка-Райта, усовершенствованным методом Кларка-Райта, методом ручной маршрутизации.
Для реализации алгоритма Кларка-Райта нами также была написана программа (см. приложение 4) на языке C++ в среде MS Visual Studio 2005. Язык C++ выбран по причине того, что в этом случае используется только один алгоритм (Кларка-Райта) и требуется меньше визуализации, чем в случае с усовершенствованным алгоритмом Кларка-Райта.
Наша программа для реализации классического алгоритма Кларка-Райта выдаст по получателям Петроградского района следующие маршруты (табл.3.15).
Полученные данные позволяют сравнить результаты классического и усовершенствованного алгоритмов Кларка-Райта (табл.3.16). Предварительно сравним итоговые результаты классического алгоритма Кларка-Райта и усовершенствованного алгоритма Кларка-Райта. После чего проведем сравнение по каждому отдельному маршруту, для того чтобы выявить оптимизацию основных логистических показателей - пробега и времени маршрута.
Применение усовершенствованного алгоритма Кларка-Райта в среднем позволяет сократить протяженность маршрутов получателей Петроградского района СПб на 5,9%. Рассмотрим новые и старые маршруты порознь (табл.3.17).
Применение алгоритма Кларка-Райта уже дает 7,0% экономии по сравнению с ручной маршрутизацией и сокращает количество транспортных единиц на 16,7%. Но для реализации алгоритма Кларка-Райта уже есть компьютерные программы, следовательно, в применении этого метода не будет научной новизны. Применение же усовершенствованного алгоритма Кларка-Райта несет с собой и научную новизну, и существенную экономию. Сравним усовершенствованный алгоритм Кларка-Райта и ручную маршрутизацию (табл.3.19).
Применение усовершенствованного алгоритма Кларка-Райта позволяет сократить протяженность маршрутов получателей хлебного завода ОАО «Арнаут» Петроградского района СПб на 12,4% и, соответственно, на 7,9% время маршрутов. Экономия по времени позволяет вместо 6 машин заказать 5 машин. Можно сказать, что возникает синэргетический эффект, когда оптимизация логистических показателей приводит к значительному эффекту.
При заказе новой машины пришлось бы оплатить определенное минимальное время, даже если бы машина была задействована в небольшой промежуток времени, как это видно на нашем примере. Например, общее время маршрутов 42 часа 15 мин. Следовательно, шестая машина будет работать только 2 часа 15 мин (рабочее время водителя не более 8 часов), а заплатить придется за 4 часа. Мы же, в результате сокращения протяженности маршрутов, уменьшаем трудозатраты и тем самым число заказанных машин.
Во второй главе были показаны такие важные логистические показатели мелкопартионных перевозок, как время и протяженность маршрута. Мы видим, что применение усовершенствованного алгоритма Кларка-Райта позволяет оптимизировать эти логистические показатели.
Оценим экономический эффект от применения усовершенствованного алгоритма Кларка-Райта. Отметим, что следует учесть экономический эффект по двум направлениям:
1) сокращение транспортных расходов;
2) сокращение трудозатрат диспетчеров.
Прежде всего оценим экономический эффект от сокращения транспортных расходов (табл.3.20). Для этого воспользуемся данными хлебного завода ОАО «Арнаут» за 2012г. По итогам каждого месяца, квартала, полугодия, года отдел логистики рассчитывает фактические цифры транспортных затрат и проводит сравнение этих цифр с плановыми транспортными затратами. Отклонения анализируются и делаются соответствующие выводы.
Применив данные хлебного завода ОАО «Арнаут» за 2012г., мы получим оценку экономического эффекта от сокращения транспортных затрат в размере 7 242 тыс. руб. в год. Соответственно, эффективность деятельности (рентабельность продаж) вырастет на 1,46%.
Для достижения данного эффекта следует осуществить ряд следующих мероприятий.
1. Провести микрорайонирование с учетом требований программы. Разбить получателей по административным районам города.
2. Для каждого района составить матрицу расстояний. Здесь возможны два пути. Либо прямой метод - объезд получателей и измерение расстояний между ними. Тогда для района с 60 получателями придется осуществить (60х60)/2=1800 поездок. Это затратное мероприятие. Второй путь - более быстрый и дешевый. Приобрести систему «TopLogistic» компании «TopPlan», позволяющую находить расстояния между получателями. Сразу оговоримся, у фирмы «TopPlan» нет программного обеспечения, позволяющего решить задачу маршрутизации. Проложить маршрут между двумя получателями программа «TopLogistic» может, но решить задачу маршрутизации для нескольких десятков получателей (одного района города) не в состоянии.
3. Составить векторы спроса по каждому району.
4. В случае добавления в район нового получателя (получателей) требуется увеличивать матрицу расстояний и вектор спроса. При наличии системы «TopLogistic» для уже имеющейся матрицы расстояний 60x60 добавление нового получателя займет 3-5 минут. В случае, если получатель не дал заказ на рассматриваемый день, достаточно поставить 0 в векторе спроса.
5. Следует обучить персонал работе с новой программой. Диспетчер будет последовательно импортировать в программу матрицу расстояний и вектор спроса соответствующего района. Вектор спроса будет заполняться автоматически, туда будут поступать данные из отдела продаж по результатам сделанного заказа за день. Маршруты будут выдаваться для каждого района. Ожидается существенное сокращение трудозатрат. Это позволит высвободить часть персонала отдела логистики.
Сокращение трудозатрат диспетчеров В настоящее время в диспетчерской работают по два диспетчера. Работа происходит посменно - два дня через два дня по 12 часов. Самая высокая интенсивность труда приходится на период с 21.00 до 10.00 следующего дня. Объяснение этого следующее - каждый получатель стремится получить хлебобулочные изделия пораньше, чтобы покупатель уже с утра мог купить свежевыпеченный хлеб. После 10.00 загружаются автомашины для получателей, у которых 2 или 3 завоза в сутки, и тех получателей, которым отдел продаж не может выделить утренний график завоза хлебобулочных изделий и ставит им время завоза днём или вечером.
В настоящее время хлебный завод представлен в 11 районах города. В среднем число получателей в сутки колеблется от 660 до 700. В среднем - по 60 получателей на один район Санкт-Петербурга. Два диспетчера за свою рабочую смену (12 часов) составляют маршруты и оформляют необходимые документы на 660-700 получателей (табл.3.21).
Похожие диссертации на Оптимизация логистических показателей мелкопартионных перевозок на автомобильном транспорте
-
-
-
