Оптимизация логистических показателей мелкопартионных перевозок на автомобильном транспорте тема диссертации по экономике, полный текст автореферата

Автореферат диссертации по теме "Оптимизация логистических показателей мелкопартионных перевозок на автомобильном транспорте"

На правах рукописи

Никоноров Валентин Михайлович

ОПТИМИЗАЦИЯ ЛОГИСТИЧЕСКИХ ПОКАЗАТЕЛЕЙ МЕЛКОПАРТИОННЫХ ПЕРЕВОЗОК НА АВТОМОБИЛЬНОМ

ТРАНСПОРТЕ

Специальность: 08.00.13 - Математические и инструментальные методы экономики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата экономических наук

1В МАЙ ¿013

005058998

Санкт-Петербург - 2013

005058998

Работа выполнена на кафедре экономической кибернетики экономического факультета федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет»

НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор экономических наук, профессор

Тютюкин Виктор Константинович

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

Дуболазов Виктор Андреевич

доктор экономических наук, профессор Санкт-Петербургский государственный политехнический университет, заведующий кафедрой «Предпринимательство и коммерция»

Бабаев Александр Александрович

кандидат технических наук, доцент Санкт-Петербургский государственный университет, кафедра информационных систем в экономике

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: ФГБОУ ВПО «Санкт-Петербургский

государственный экономический университет»

Защита состоится « 30 » мая 2013 г. в 14.00 часов на заседании диссертационного совета Д 212.229.23 при ФГБОУ ВПО «Санкт-Петербургский государственный политехнический университет» по адресу: 195251, Санкт-Петербург, ул. Политехническая, д. 29, III учебный корпус, ауд. 506.

С диссертацией можно ознакомиться в фундаментальной библиотеке ФГБОУ ВПО «Санкт-Петербургский государственный политехнический университет»

Автореферат разослан «_«_201 Зг. и размещен на сайте ФГБОУ ВПО

«СПбГПУ»: http://www.spbstu.ru/science/counsil_dcfcnds.html

Ученый секретарь диссертационного совета

доктор экономических наук, профессор и- Сулоева Светлана Борисовна

I-ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Произошедшие изменения в характере спроса на транспортные услуги привели к тому, что на сегодняшний день в структуре грузооборота грузового автомобильного транспорта 80% составляют мелкопартионные грузы, перевозимые преимущественно по развозочным маршрутам. При этом оперативное планирование развозочных маршрутов сопряжено с необходимостью учета большого количества технологических ограничений и обработки исходной информации значительного объема. Возникающая при этом ситуация является задачей маршрутизации.

Решение задачи маршрутизации по-прежнему особенно актуально в целях уменьшения транспортных затрат при массовой перевозке сырья или готовой продукции.

Одновременно существует недостаток хорошо зарекомендовавших себя на практике методик по эффективному решению задачи маршрутизации. Это обуславливает необходимость разработки достаточно простых и реализуемых на практике за разумное время алгоритмов оптимизации логистических показателей перевозок мелкопартионных грузов на автомобильном транспорте.

Степень разработанности темы исследования. На формирование положений диссертационного исследования оказали влияние фундаментальные и прикладные научные работы отечественных и зарубежных авторов в области оптимизации логистических показателей мелкопартионных перевозок на автомобильном транспорте. В области экономики автомобильного транспорта - Бронштейн Л.А., Воркут А.И., Гудков В.А., Канторович Л.В., Квитко Х.Д.; в области логистики - Бауэрсокс Д., Безель Е.П., Вельможин A.B., Дуболазов В.А., Клосс Д., Миротин Л.Б.; в области экономико-математических методов управления производством - Бабаев A.A., Глухов В.В., Кобзев

B.В., Козловский В.А., Тютюкин В.К.; в области математических моделей и методов решения задачи маршрутизации - Аникеич A.A., Беллман Р., Геронимус Б.Л., Грибов А.Б., Данциг Г., Дейкстра Э., Житков В.А., Кормен Т., Лейзерсон Ч., Литтл Д., Уоршалл

C., Флойд Р., Хелд М„ Штайн К., Clarke G., Wright J.W.

Цель и задачи исследования. Цель работы состоит в том, чтобы повысить эффективность перевозок мелкопартионных грузов автомобильным транспортом на основе разработки методики оптимизации логистических показателей системы перевозки.

Для достижения поставленной цели в диссертационной работе были сформулированы и решены следующие основные задачи:

1) рассмотрено современное состояние автомобильной отрасли в РФ, выявлена количественная связь между грузооборотом грузового автомобильного транспорта и

I

валовым внутренним продуктом России;

2) уточнено определение мелкопартионных перевозок, дана классификация мелкопартионных перевозок;

3) исследованы критерии оптимальности задачи маршрутизации и выбрана система логистических показателей перевозки мелкопартионных грузов;

4) проведен анализ и систематизация экономико-математических методов применяемых для решения задачи маршрутизации;

5) разработана методика оптимизации логистических показателей перевозки мелкопартионных грузов на базе усовершенствованного метода Кларка-Райта;

6) разработан программный продукт для практической реализации предлагаемой методики;

7) рассчитан экономический эффект от использования предлагаемой методики на примере транспортной подсистемы конкретного предприятия.

Объект исследования - предприятие пищевой промышленности, применяющее грузовой автомобильный транспорт для перевозки мелкопартионных грузов.

Предмет исследования - логистические процессы, протекающие в транспортной подсистеме промышленного предприятия.

Теоретическую и методологическую базу исследования составляют работы отечественных и зарубежных авторов по методологии оптимизации логистических показателей мелкопартионных перевозок с помощью математических методов.

В ходе исследования были использованы методы: сравнительный, монографический, статистический, расчетный.

Основные результаты и научная новизна. В диссертационном исследовании получены следующие основные научные результаты, которые выносятся на защиту.

1. Доказана количественная связь между ВВП РФ и грузооборотом грузового автомобильного транспорта, отличительной особенностью которой является возможность долгосрочного прогнозирования влияния роста грузооборота грузового автомобильного транспорта на ВВП РФ.

2. Предложено новое определение мелкопартионных перевозок, позволяющее построить классификации мелкопартионных перевозок.

3. Доказана количественная связь между расходами грузового автомобильного транспорта и потреблением дизельного топлива и бензина, отличительной особенностью которой является возможность анализа последствий сокращения потребления топлива для транспортной отрасли.

4. Определена система логистических показателей эффективности перевозки мелкопартионных грузов на грузовом автомобильном транспорте, отличительной

особенностью которой является практическая применимость и возможность разработки методики по оптимизации логистических показателей мелкопартионных перевозок на грузовом автомобильном транспорте.

5. Проведён анализ и предложена классификация экономико-математических методов, используемых в транспортной отрасли для решения задачи маршрутизации, отличительной особенностью классификации является возможность выбора наиболее перспективного метода для его последующего усовершенствования.

6. Разработан новый приближенный алгоритм для решения задачи маршрутизации «Усовершенствованный Кларк-Райт», отличающийся от классического алгоритма Кларка-Райта сокращением протяженности и времени маршрутов.

Теоретическая значимость заключается в создании нового метода (усовершенствованного алгоритма Кларка-Райта) для решения задачи маршрутизации класса 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 источников.

II. ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

1. Доказана количественная связь между ВВП РФ и грузооборотом грузового автомобильного транспорта, отличительной особенностью которой является возможность долгосрочного прогнозирования влияния роста грузооборота грузового автомобильного транспорта на ВВП РФ.

Тест Йохансена показал, что между временными рядами «грузооборот грузового автомобильного транспорта» и «ВВР РФ» существует коинтеграция (табл.1).

Таблица 1. Результат теста Йохансена для временных рядов «ВВП РФ» и

«грузооборот грузового автотранспорта» за 2000-2011г.г.

Показатель Значение

Тип модели 1 2 3 4

Тгасе-статистика 0 0 0 1

Max-Eig-статистика 0 0 0 1

Критерий Акаике 20.23324 20.21576 20.21939 19.72888*

Критерий Шварца 20.55442 20.57710 20.62087 20.17051*

Полученные результаты не противоречат друг другу - и по критерию Акаике, и по критерию Шварца лучшей оказалась модель четвертого типа.

Наличие причинно-следственной связи позволяет определить с помощью

коинтеграционного соотношения долгосрочную количественную связь между временными рядами «грузооборот грузового автомобильного транспорта» и «ВВП РФ». Эта связь выглядит так

«ВВП РФ»= 109,7656 «грузооборот»+69,24919t (1)

где t- номер уровня временного ряда.

Следовательно, увеличение грузооборота грузового автомобильного транспорта может оказать существенное положительное влияние на развитие экономики РФ. Здесь наблюдается значение грузового автомобильного транспорта в макроэкономическом аспекте.

В диссертации подробно рассматривается оптимизация логистических показателей мелкопартионных перевозок на грузовом автомобильном транспорте, для чего изучаются как сами мелкопартионные перевозки, так и логистические показатели.

2. Предложено новое определение мелкопартиониых перевозок, позволяющее построить классификации мелкопартиониых перевозок.

Мелкопартионная перевозка на грузовом автомобильном транспорте - это такая перевозка, при которой минимальное число грузополучателей - два, маршрут -развозочный, вес груза для одного грузополучателя не превышает половины грузоподъемности транспортного средства. На базе этого определения построена классификация мелкопартионных перевозок (табл.2).

Таблица 2. Классификация мелкопартиониых перевозок

№ Признак классификации Вид мелкопартионной перевозки

1 Число грузополучателей 1) малая - от 2 до 10; 2) средняя - от 10 до 20; 3) большая - более 20

2 Длина маршрута 1) короткая - от 10 до 50 км; 2) средняя - от 50 до 100 км; 3) длинная - более 100 км

3. Доказана количественная связь между расходами грузового автомобильного транспорта и потреблением дизельного топлива и бензина, отличительной особенностью которой является возможность анализа последствий сокращения потребления топлива для транспортной отрасли.

Тест Йохансена показал, что между временными рядами «расходы грузового автотранспорта» и «потребление ДТ» существует коинтеграция (табл.3).

Таблица 3. Результат теста Йохансена для временных рядов «расходы грузового автотранспорта» и «потребление ДТ» за 1999-2010г.г.

Показатель Значение

Тгасе-статистика 0 0 0 1

Max-Eig-статистика 0 0 0 1

Критерий Акаике 1.378038 1.400011 1.428018 1.069507*

Критерий Шварца 1.699222 1.761343 1.829498 1.511135*

Наличие причинно-следственной связи позволяет определить с помощью коинтеграционного соотношения долгосрочную количественную связь между временными рядами «расходы грузового автотранспорта» и «потребление ДТ». Эта связь выглядит так

«Расходы»= 8,779259 х «потребление ДТ» + 0,151723 х t (2)

Соответственно, сокращение потребления топлива уменьшает расходы грузового автомобильного транспорта.

4. Определена система логистических показателей эффективности перевозки мелкопартионных грузов на грузовом автомобильном транспорте, отличительной особенностью которой является практическая применимость и возможность разработки методики по оптимизации логистических показателей мелкопартионных перевозок на грузовом автомобильном транспорте.

В диссертации проведен анализ логистических показателей грузовых автомобильных перевозок на примере исследований Геронимуса Б.Л., Кожина А.П., Бобарыкина В.А., Воркута А.И., Васильева Н.М., Квитко Х.Д., Ефремова A.B., Горева А.Э., Майбороды М.Е., Туревского И.С., Поченко А.Я., Канторовича JI.B.

Так как в структуре грузооборота на сегодняшний день 80% составляют мелкопартионные грузы, то полученные в диссертации результаты будут применимы, прежде всего, к мелкопартионным перевозкам.

Потребление топлива определяется пробегом, пробег зависит от выбранного маршрута. Минимизация пробега (маршрута) позволит сократить расходы на топливо и уменьшить расходы грузового автотранспорта. Минимизацию маршрутов обеспечивает решение задачи маршрутизации. Расходы грузового автотранспорта также зависят от времени работы транспортного средства. Выявлены основные логистические показатели мелкопартионных перевозок на автомобильном транспорте - пробег и время работы транспортного средства.

5. Проведён анализ и предложена классификация экономико-математических методов, используемых в транспортной отрасли для решения задачи маршрутизации, отличительной особенностью классификации является возможность выбора наиболее перспективного метода для его последующего усовершенствования.

Задачу маршрутизации можно сформулировать в общем виде следующим образом -требуется доставить однородный груз от отправителей всем получателям данным числом автомашин наиболее эффективно (с минимальной протяженностью маршрута). При этом учитывается вместимость автомашины, время её работы, время разгрузо-погрузочных работ.

Когда речь идет о доставке груза от отправителей получателям, то эти задачи маршрутизации принято называть задачами развозки.

Формализуя, задачу развозки можно задать следующим образом.

1. Для перевозок выделено ш а/машин грузовместимостью Рк , тонн (к=1 :ш).

2. Ы=У/5=1,2,...,п} - множество всех пунктов получателей в задаче, а пункт под номером ]'=0-это отправитель.

3. ^ =| ]|к ,...Огк ,•■•, ^ I - маршрут к-ой автомашины, (к=1 :ш)

где >к - номер пункта, посещаемого к-ой автомашиной в г-ю очередь.

Считается, что автомашина выезжает от отправителя (пункт под номером 0) и в него же

■Л _ -Л _п

возвращается: .(о — — ■ Это кольцевой маршрут.

вк - длина маршрута Як в количестве пунктов, вк > 1 Як - размещение из п по вк.

4. Требуется построить систему кольцевых маршрутов И={ III Дг , - Дт! таких, что

п1

(3)

к=1

Условие (3) означает, что автомашины объедут всех получателей продукции, объединение всех маршрутов есть все пункты транспортной сети.

К-гПК-к =0 (г,к=1:т;г£к) (4)

Условие (4) означает, что два различных маршрута не пересекаются.

Зк =2Д; (к=,:т),

(5)

г=1

где ц - потребность ]-го пункта, Ок- суммарный спрос всего маршрута

Условие (5) есть ограничение на формирование маршрута для к-го автомобиля (не превышение его грузовместимости Рк).

5. Данная система маршрутов, кроме того должна быть самой короткой, т.е. выполняется следующее условие: т

^У/,, —> ггип , \к - \к — о .

к= 1 г=0

где /д - расстояние между пунктами \ и ^ (¡о=0:п) В (6) внутренняя сумма есть длина маршрута Як:

ЬСК-к) = (7)

г=О

Решение задачи маршрутизации для мелкопартионных перевозок обеспечивает минимальные транспортные затраты, так как общий пробег минимизируется.

В диссертационном исследовании проведен анализ и предложена классификация математических методов решения задачи маршрутизации (табл.4).

Таблица 4. Математические методы решения задачи маршрутизации (неполный

перечень)

№ Название метода Авторы Дата возникнове ния

Методы, обеспечивающие получение оптимального решения

I Динамическое программирование Беллман Р., Хелд М., Карп Р. 1964

II Целочисленное линейное программирование Миллер С., ТаккерА., Землин Р. 1960

III Метод «ветвей и границ» Литтл Дж., Мурти К., Шапиро Ф. 1965

Методы, обеспечивающие получение приближенного решения

I Эвристические методы, в т.ч.

1 Экономизирующий метод Кларк Г., Райт Дж. 1964

2 Модификация Гаскелла метода Кларка-Райта Gaskell T.J. 1967

3 Модификация Паесенса метода Кларка-Райта Paessens Н. 1988

4 Модификация Альтинела метода Кларка-Райта Altinel I.K. 2005

5 Метод «метлы» Gillet В., Miller L. 1974

II Метаэвристики

1 Метод генетических алгоритмов Д.Х. Холланд 1975

2 Алгоритм муравьиных колоний (ACO) М. Дориго 1992

3 Метод имитации отжига А. Осман 1993

III Теория расписаний Орлов Д.М. 1968

IV Имитационное моделирование Миротин Л.Б., Гольдин А.Г 1989

По результатам анализа математических методов, что наиболее эффективным среди эвристических методов является алгоритм Кларка-Райта.

Идея применения метода Кларка-Райта заключается в следующем.

Рассчитываются экономии (функции выгоды) по следующей формуле:

вц= 1а + 1щ-1ц (8)

Строится система из п радиальных маршрутов вида {0,1,0}. Решается задача развозки мелкопартионных грузов. Система радиальных маршрутов удовлетворяет условиям (3)-(5) задачи маршрутизации, но включает в себя слишком много мелких маршрутов. Эта система будет преобразовываться посредством последовательного объединения маршрутов.

В основе объединения маршрутов лежит задача максимального снижения длины маршрутов. Для этого последовательно рассматриваются функции выгоды в порядке их убывания и соответствующие пары получателей включаются в маршрут. Такой процесс завершится после рассмотрения всех функций выгоды.

Алгоритм Кларка-Райта подробно рассмотрен в диссертации на примере данных хлебного завода Санкт-Петербурга ОАО «Хлебный завод «Арнаут» (10 получателей Петроградского района г. СПб).

Ограничение по времени работы к-го водителя (8 часов) выглядит так

Т(к> =1<»а+1(к)ь+1,к)с+Л<7,25 ,

где 1(к) а - время оформления документации на хлебном заводе на загруженную в к-ую автомашину продукцию;

1<к)ь- время оформления документации на выгруженную у получателя продукцию;

1|к|с- время выгрузки продукции и погрузки тары у получателя;

(к!

г \т время автомашины на маршруте.

Тк =0,13хс + 3(£ягУ200 + ЦКк)/15<7,25

Ограничение по вместимости автомашины запишется следующим образом

< Рк = 120 (10)

Детальное рассмотрение алгоритма Кларка-Райта позволило выявить определенные недостатки классического алгоритма.

1. Пункты, уже вошедшие в сформированный маршрут, исключаются из дальнейшего рассмотрения (условие (4)). Маршруты, сформированные классическим алгоритмом Кларка-Райта, как и требуется в модели, не пересекаются. В то же время для минимизации длины нового маршрута зачастую имеет смысл миновать (не разгружаясь в нем) один из уже рассмотренных пунктов, принадлежащих уже сформированному маршруту.

2. Реальные условия вовсе не означают, что мы имеем дело с матрицей кратчайших расстояний. Поэтому интересен вопрос предварительной оптимизации входных данных.

3. Существующие методы решения задачи маршрутизации предполагают, что вес дуги графа - это расстояние между получателями (соответствующими вершинами графа). В то же время, вес дуги графа может иметь смысл отличный от расстояния.

6. Разработан новый приближенный алгоритм для решения задачи маршрутизации «Усовершенствованный Кларк-Райт», отличающийся от классического алгоритма Кларка-Райта сокращением протяженности и времени маршрутов.

В качестве объекта исследования рассмотрен хлебный завод ОАО «Хлебный завод «Арнаут». Для данного объекта исследования будет решена классическая задача маршрутизации.

Известны попытки усовершенствования алгоритма Кларка-Райта (Gaskell, Golden, Paessens, Altinel, Oncan, Chandran). Суть этих усовершенствований сводится к уточнению формулы выигрыша и последующей настройке независимых параметров, предложенных вышеназванными исследователями.

Автор предлагает усовершенствовать алгоритм Кларка-Райта алгоритмами Флойда-Уоршалла и Дейкстры. Здесь применяется главная функция этих алгоритмов - поиск кратчайшего пути между заданной начальной вершиной и заданной конечной вершиной графа.

В условиях города дуга орграфа обладает «весом», который в общем случае не является евклидовым расстоянием между получателями, так как в условиях города практически невозможно добраться от одного получателя до другого именно по прямой линии. Поэтому вполне возможен вариант треугольника из вершин №№1,3,5, изображенный на рис.1. Прямой путь из вершины 1 в вершину 3 равен 30, включение промежуточной вершины 5 позволит сократить этот путь до 20. Промежуточные (intermediate) вершины кратчайшего пути рассматривает алгоритм Флойда-Уоршалла.

Рис.1. Ориентированный граф в

Алгоритм Роберта Флойда и Стивена Уоршалла (далее - алгоритм Флойда-Уоршалла) позволит нам найти в предложенной матрице расстояний кратчайшие пути между

получателями продукции. Для того чтобы определить сам путь, т.е. последовательность промежуточных получателей, через которых будет проходить этот кратчайший путь, мы применим алгоритм Дейкстры.

Алгоритмы Флойда-Уоршалла и Дейкстры независимы, они обрабатывают исходную матрицу расстояний и результат получается идентичный, с той лишь разницей, что алгоритм Дейкстры дает развернутые маршруты, т.е. для алгоритма Дейкстры не нужен результат алгоритма Флойда-Уоршалла. Далее алгоритм Кларка-Райта пользуется полученными кратчайшими путями между получателями, ищет функцию выгоды и формирует маршруты -сначала сокращенные, затем развернутые (эту возможность предоставляет алгоритм Дейкстры).

Особенности комбинации алгоритмов Флойда-Уоршалла и Дейкстры представлены в табл.5

Таблица 5. Комбинация алгоритмов Флойда-Уоршалла и Дейкстры

Алгоритм Флойда-Уоршалла Алгоритм Дейкстры

Плюсы Минусы Плюсы Минусы

Работает с дугами отрицательного веса Не дает развернутого пути Дает развернутый путь Не работает с дугами отрицательного веса

В общем случае под весом дуги может пониматься всё, что угодно, не только евклидово расстояние между вершинами, но и, например, плата за проезд. Когда перевозчик платит за проезд - это дуга положительного веса. Если же вдруг перевозчику платят за проезд по данной дуге, то это дуга отрицательного веса, так как эта дуга приносит доход.

Также выбор комбинации алгоритмов Флойда-Уоршалла и Дейкстры объясняется минимальной временной сложностью данных алгоритмов (табл.6)

Таблица 6. Алгоритмы поиска кратчайшего пути между вершинами графа

№ Алгоритм Отрицательный вес дуг Временная сложность

1 Дейкстры Алгоритм не работает

2 Флойда-Уоршалла Алгоритм работает О (п1), для графа с неотрицательной матрицей весов экономия времени по сравнению с алгоритмом Дейкстры 50%

3 Беллмана-Форда Алгоритм работает О (п4) - поиск кратчайших путей между всеми парами вершин для произвольной матрицы весов

4 Левита Алгоритм не работает 0(п3)

5 Джонсона Алгоритм работает О (п^ ^(п)+пЕ), где Е- число ребер графа

Блок-схема усовершенствованного алгоритма Кларка-Райта показана на рис.2.

Начало

Ввод входных данных

Генерация кратчайших путей между получателями

Входные данные:

- продолжительность рабочего дня

- время погрузки-разгрузки единицы продукции

- время на подготовительно-заключительные работы на хлебном заводе

- время на подготовительно-заключительные работы у получателей на маршруте

- скорость машины ( 15 км/час)

- вместимость машины (120 лотков)

- количество получателей

- матрица расстояний

- вектор спроса

Для генерации кратчайших путей между получателями применяется алгоритм Флойда-Уоршалла

---

Создание финальных маршрутов

+

- .

Распределение маршрутов по машинам

V___)

Вывод выходных данных

Конец

Для каждого маршрута составляется краткий и развернутый маршрут. Считается длина, время и загрузка маршрута.

Листинг маршрутов в коротком и развернутом виде. Также листинг распределения маршрутов по машинам.

Рис.2. Блок-схема усовершенствованного алгоритма Кларка-Райта

Для реализации усовершенствованного алгоритма Кларка-Райта создана соответствующая компьютерная программа «Усовершенствованный Кларк-Райт» (свидетельство о государственной регистрации программы для ЭВМ№ 2013613119 от 26 марта 2013г.). Решение программы реализовано на С++ (срр), интерфейс на С# (си-шарп). Языковая среда MS Visual Studio 2005. При составлении программы задействовано объектно-ориентированное программирование. Для проведения эксперимента рассмотрены получатели хлебного завода ОАО «Хлебный завод «Арнаут» Петроградского района в количестве 58 шт.

Программа для реализации усовершенствованного алгоритма Кларка-Райта выдаст по

получателям Петроградского района следующие маршруты (табл.7).

Таблица 7. Маршруты по получателям Петроградского района СПб сформированные усовершенствованным алгоритмом Кларка-Райта

Но мер Маршрут R Длина маршрута L, км Время маршрута т, час:минут Число лотков в маршруте q, ед Развернутый маршрут R (номера пунктов всех получателей)

1 1,53,48,3,50,59, 15, 1 14,405 4:10 112 1,5, 53,48,3, 50,59, 15,36,5, 1

2 1,5,4, 14, 49, 35, 16, 54, 1 10.635 4:10 120 1,5,37, 9, 4, 14, 49,35, 16, 54, 1

3 I, 34, 17,58,47, 10, 13, 1 12.344 4:01 112 1,5,34, 17,58,47, 10,13, 1

4 1,2,44, 28,56,23, 19, 1 10,937 3:56 112 1,2, 44,28,56, 23, 19, 1

5 1, 11, 18,41,7, 27, 32, 1 9,006 3:55 120 1, И, 18,41,7, 27,32, 5, 1

6 1,57, 8,38,31,52, 20, 1 9,453 3:55 118 1,57, 8,38,31,52, 20, 1

7 1,6,45,25,24,29, 21, 1 8,276 3:52 120 1,6, 45,25, 24, 29,21, 1

8 1,26,39,36,42, 30, 1 8,824 3:43 116 1,5, 26, 39,36,42,36, 30, 1

9 1,22,46, 12,43,33, 1 8,371 3:35 109 1,22,46, 12,43, 12, 33, 1

10 1,55,51,9,40, 37, 1 9,745 3:32 100 1,5, 55,51,9,40,9,37, 5, 1

Итого: 101,996 38:55:00 1139 -

При детальном рассмотрении развернутых маршрутов наблюдается повторение вершин. Для классического алгоритма Кларка-Райта это невозможно, так как по условию (2) маршруты не пересекаются. Для усовершенствованного - в порядке вещей, так как программа сначала ищет (посредством алгоритма Флойда-Уоршалла) кратчайшие пути между вершинами графа (получателями транспортной сети) и именно эти кратчайшие пути обрабатывает алгоритм Кларка-Райта. При этом алгоритм Кларка-Райта корректно

воспринимает предлагаемые ему для обработки кратчайшие пути, так как общие вершины (одна и та же вершина принадлежит разным маршрутам) в них скрыты. Применение алгоритма Дейкстры позволяет развернуть эти кратчайшие расстояния и выявить общие вершины. Работу усовершенствованного алгоритма Кларка-Райта можно описать следующим образом.

1. Алгоритм Флойда - Уоршалла ищет кратчайшие пути между получателями заданной матрицы расстояний, при этом формируется матрица расстояний, которая содержит действительно кратчайшие пути. Первоначально имеющаяся матрица расстояний может не соответствовать этому требованию. Алгоритм Флойда - Уоршалла определяет веса кратчайших путей, но не последовательность получателей в кратчайшем пути.

2. Алгоритм Дейкстры определяет последовательность всех получателей в кратчайшем пути.

3. Алгоритм Кларка-Райта формирует маршруты, пользуясь кратчайшими путями, полученными алгоритмом Флойда-Уоршалла. Получатели, указанные в этом маршруте, предназначены для отгрузки им продукции.

4. Развертка маршрута обеспечивается благодаря работе алгоритма Дейкстры. В развернутом маршруте ранее скрытые получатели предназначены не для отгрузки продукции, а для минимизации маршрута. Автомашина проезжает этих получателей, не разгружаясь, за счет прохождения маршрута через этих получателей сокращается длина всего маршрута.

5. Условия классической задачи маршрутизации соблюдены для маршрутов, состоящих из фактических получателей. Если же рассматривать развернутые маршруты, то получается новый метод решения задачи маршрутизации, так как развернутые маршруты пересекаются.

Программа позволяет распечатать маршруты по отдельности. Также в программе, реализующей усовершенствованный алгоритм Кларка-Райта, учтены расходы времени на погрузку-выгрузку продукции, оформление документов и продолжительность рабочего дня водителя. Это позволяет распределить маршруты по машинам.

Итак, предложенный усовершенствованный алгоритм Кларка-Райта позволяет формировать развернутые маршруты, закреплять их за машинами и выдерживать ограничения по времени работы водителя, грузовместимости машины.

Рассчитан экономический эффект от использования предлагаемого усовершенствованного алгоритма Кларка-Райта на примере транспортной подсистемы конкретного предприятия.

Экономический эффект от реализации усовершенствованного алгоритма Кларка-Райта складывается из двух составляющих.

Прежде всего возникает сокращение транспортных затрат (табл.8).

Таблица 8. Оптимизация логистических показателей при применении усовершенствованного алгоритма Кларка-Райта

№ Сравнение методов экономия протяженности маршрутов экономия времени маршрутов

1 Усовершенствованный алгоритм Кларка-Райта по отношению к ручной маршрутизации 12,4% 7,9%

2 Усовершенствованный алгоритм Кларка-Райта по отношению к алгоритму Кларка-Райта 5,9% 1,1%

Применение усовершенствованного алгоритма Кларка-Райта в условиях ОАО «Хлебный завод «Арнаут» дает экономический эффект (предварительная оценка) в размере 7 242 тыс. руб. в год и позволяет повысить экономическую эффективность (рентабельность продаж) на 1,5%.

Также применение программы маршрутизации, основанной на усовершенствованном алгоритме Кларка-Райта, позволит уменьшить трудозатраты диспетчеров отдела логистики на 50% и, соответственно, высвобождать 50% диспетчеров.

III. ОСНОВНЫЕ НАУЧНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ Статьи в изданиях, входящих в перечень ВАК

1. Никоноров В.М. Влияние грузового автомобильного транспорта на экономику страны // «Российское предпринимательство». 2011.-№6.-С.117-123 (0,3 п.л.)

2. Никоноров В.М. Логистические показатели мелкопартионных автомобильных перевозок // «Экономические науки». 2011,-№5.-С.362-366 (0,4 п.л.)

3. Никоноров В.М. Показатели эффективности грузовых автомобильных перевозок // «Вопросы современной науки и практики». 2011.-№4.-С.87-94 (0,4п.л.)

4. Никоноров В.М. Экономическая эффективность грузовых автомобильных перевозок // «Научно-технические ведомости СПбГПУ». 2011.-№5.-С.245-250 (0,5 пл.)

5. Никоноров В.М. Математические методы решения задачи маршрутизации мелкопартионных перевозок // «Научно-технические ведомости СПбГПУ». 2011.-№6.-С.222-226 (0,4 п.л.)

6. Никоноров В.М. Усовершенствование метода Кларка-Райта для решения задачи маршрутизации автомобильных мелкопартионных перевозок // «Научно-технические ведомости СПбГПУ». 2012.-№1.-С.295-298 (0,3 п.л.)

7. Никоноров В.М. Реализация усовершенствованного метода Кларка-Райта для решения задачи маршрутизации автомобильных мелкопартионных перевозок // «Научно-технические ведомости СПбГПУ». 2012.-№2.-С.210-215 (0,5 п.л.)

15

8. Никоноров В.М., Тютюкин В.К. Особенности усовершенствованного метода Кларка-Райта для решения задачи маршрутизации // «Научно-технические ведомости СПбГПУ». 2012.-№6.-С.203-206 (0,3 пл.)

Статьи и тезисы

1. Никоноров В.М. Метод «ветвей и границ» и его применение для оптимизации логистических показателей развозки // Проблемы развития предприятий: теория и практика: Материалы международной научно-практической конференции. - Пенза: РИО ПГСХА, 2008.-С. 174-177 (0,2 п.л.)

2. Никоноров В.М. «Жадный» алгоритм и его применение для оптимизации логистических показателей развозки // Проблемы развития предприятий: теория и практика: Материалы международной научно-практической конференции. - Пенза: РИО ПГСХА, 2008.-С.177-179(0,2 п.л.)

3. Никоноров В.М. Метод Кларка-Райта и его применение для оптимизации логистических показателей развозки // Конкурентоспособность предприятий и организаций: Материалы VI Всероссийской научно-практической конференции. - Пенза: РИО ПГСХА, 2008.-С.25-27 (0,2 п.л.)

4. Никоноров В.М. Генетический алгоритм и его применение для оптимизации логистических показателей развозки // Конкурентоспособность предприятий и организаций: Материалы VI Всероссийской научно-практической конференции. - Пенза: РИО ПГСХА, 2008.-С.28-30 (0,2 п.л.)

5. Никоноров В.М. Теория графов и ее применение для оптимизации логистических показателей развозки // Журнал «Образование, экономика, общество». 2008.-№6.-С.40-44 (0,2 п.л.)

6. Никоноров В.М. Экономико-математические методы в транспортной науке // Журнал «Образование, экономика, общество». 2010.-№6.-С.34-37 (0,4 п.л.)

7. Никоноров В.М. Роль транспорта в России // Журнал «Образование, экономика, общество». 2011.-№1.-С. 36-40 (0,2 п.л.)

8. Никоноров В.М. Метаэвристики для решения задачи маршрутизации на примере генетического алгоритма // Журнал «Образование, экономика, общество». 2012.-№1.-С.38-40. (0,3 п.л.)

9. Никоноров В.М. Грузовой автомобильный транспорт и ВВП России // Модернизация и переход к инновационному развитию. Проблемы и решения: Сборник трудов участников конференции профессорско-преподавательского состава и аспирантов / СПбГТЭУ. - СПб.: ГТЭУ, 2012.-С.95-96 (0,2 п.л.)

Подписано в печать 18.04.2013. Формат 60x84/16. Печать цифровая. Усл. печ. л. 1,0. Тираж 100. Заказ 10582Ь.

Отпечатано с готового оригинал-макета, предоставленного автором, в типографии Издательства Политехнического университета. 195251, Санкт-Петербург, Политехническая ул., 29. Тел.:(812)550-40-14 Тел./факс: (812)297-57-76