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

Ученая степень
кандидата экономических наук
Автор
Филиппов, Дмитрий Вячеславович
Место защиты
Москва
Год
2012
Шифр ВАК РФ
08.00.05

Автореферат диссертации по теме "Управление и оптимизация процесса формирования маршрутов поставок потребительских товаров в распределительных центрах"

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

ФИЛИППОВ ДМИТРИЙ ВЯЧЕСЛАВОВИЧ

УПРАВЛЕНИЕ И ОПТИМИЗАЦИЯ ПРОЦЕССА ФОРМИРОВАНИЯ МАРШРУТОВ ПОСТАВОК ПОТРЕБИТЕЛЬСКИХ ТОВАРОВ В РАСПРЕДЕЛИТЕЛЬНЫХ ЦЕНТРАХ

Специальность 08.00.05 - Экономика и управление народным хозяйством

(логистика)

АВТОРЕФЕРАТ

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

1 7 МАМ 2012

Москва-2012

005044442

005044442

Диссертационная работа выполнена на кафедре логистики Государственного университета управления

Научный руководитель:

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

Волочиенко Владимир Антонович

доктор экономических наук, профессор (Государственный университет управления / кафедра прикладной математики, профессор)

Стерлигова Алла Николаевна доктор экономических наук, профессор (Национальный исследовательский университет «Высшая школа экономики» / кафедра общего и стратегического менеджмента, професа

аэрокосмический университет имени академика С.П. Королева

Официальные оппоненты:

Гатауллин Тимур Малютович

Ведущая организация:

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

Защита состоится «22» мая 2012 года в 1400 часов на заседании Диссертационного совета Д 212.049.02 в Государственном университете управления по адресу: 109542, г. Москва, Рязанский проспект, 99, зал заседаний Ученого совета.

С диссертацией можно ознакомиться в библиотеке Государственного университета управления, с авторефератом - на сайте ГУУ http://www.guu.ru

Автореферат разослан « » съ

2012 г.

Ученый секретарь Диссертационного совета кандидат экономических наук, доцент

Н.В. Казанцева

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

Вопросам развития теоретических и практических основ логистики в сфере перевозок и, в частности, маршрутизации посвящены работы видных отечественных и зарубежных ученых, таких как, Б.А. Аникин, Д. Бауэрсокс, В.В. Дыбская, Р. Мерфи, Ю.М. Неруш, Т.А. Родкина, В.И. Сергеев, Ю. Шапиро, Д. Уотерс и ряда других. Известны результаты исследуемых проблем совершенствования маршрутизации с применением современных информационных технологий, новых подходов к организации логистических процессов, применения моделей и методов исследования операций.

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

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

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

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

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

• предложить методику для оптимизации и управления процессом формирования маршрутов поставок потребительских товаров в распределительных центрах на основе общей платформы множества остовных деревьев с использованием базовых моделей и методов решения оптимизационных задач транспортной логистики и информационных технологий;

• разработать на базе эволюционной метаэвристики алгоритмы решения следующих задач маршрутизации товарных потоков: построение сборно-развозочных незамкнутых маршрутов поставок товаров с обобщением для циклических маршрутов; маршрутизация консолидированных грузов; маршрутизация с рациональным размещением товаров в транспортных средствах и соблюдением технологических условий разгрузки;

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

• разработать на базе созданной методики и алгоритмического обеспечения модуль управления логистической информационной системы, предназначенный для: анализа транспортной ситуации; определения множества маршрутов и планов загрузки-разгрузки транспортных средств в текущей ситуации; выбора рационального маршрута в условиях нестабильной распределительной среды;

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

Объектом исследования являются товарные потоки в цепях поставок распределительных центров.

Предметом исследования является оптимизация и управление процессом формирования маршрутов поставок потребительских товаров в распределительных центрах.

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

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

Научные результаты, полученные лично автором и обладающие научной новизной:

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

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

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

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

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

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

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

Основные научные и практические результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Международной конференции «Computer Science and Information Technologies» (Уфа 2007), Интернет конференции «Информационные технологии и телекоммуникации в образовании, экономике и управлении регионом» (Тюмень 2007), международной научно-практической конференции «Изменяющаяся Россия. Социально-экономические инновации» (Челябинск, 2008), Зимней школе аспирантов

и молодых ученых (Уфа 2008, 2009), научно-практической конференции «Управление качеством» (Москва 2008).

Результаты диссертационного исследования используются в учебном процессе Уфимского государственного авиационного технического университета при проведении занятий по учебным дисциплинам «Математические методы и модели транспортной логистики», по направлению подготовки дипломированного специалиста 010500 «Прикладная математика и информатика», специальности 010501 «Прикладная математика и информатика» и «Математические модели и методы логистики», по направлению подготовки магистра 010200.68 «Математика и компьютерные науки» профиль подготовки магистра «Математическое и компьютерное моделирование».

Публикации автора. По теме диссертации опубликовано 14 научных работ общим объемом 3,45 печатных листа, в том числе пять из них в рецензируемых журналах из списка ВАК - в объеме 1,22 печатных листов.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложений. Работа содержит 171 страницу основного текста, список литературы из 106 наименований, 19 таблиц, 41 рисунок.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

прогнозирования, проектирования и управления маршрутами позволили выявить особенности распределительных центров розничной и оптовой торговли продуктами потребления, его структуры и связи с поставщиками и клиентами. Оценка современной ситуации по данному вопросу дана с теоретической и практической точек зрения Д. Вишней, О. Высоцким, К. Ковалевым, Ф. Кот-лером, С. Уваровым, П. Щегловым.

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

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

В базовой задаче маршрутизации необходимо определить для каждого транспортного средства (ТС) маршрут доставки продукта некоторому подмножеству клиентов. Такой маршрут должен начинаться в депо и каждый клиент должен быть обслужен только одним ТС. Суммарная стоимость проезда по всем маршрутам должна быть минимальна. На практике требуется учитывать в модели дополнительные организационные и технологические ограничения, которые не всегда удается задать параметрически. Учет ограничений находит отражение в расширении классической модели.

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

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

ции: это маятниковые маршруты, которые составляются по другим, отличным от применяемых в данной работе, законам. «Многие ко многим» требуют применения оптимизационных или приближенных методов. Среди этих моделей различаются кольцевые (замкнутые) маршруты и открытые развозочные, которые составляют основу для исследования и разработки алгоритмической платформы в данной работе.

Среди оптимизационных методов для решения задач маршрутизации можно выделить переборный алгоритм «ветвей и границ», недостатком которого является ограниченность размерности (количества клиентов) задачи и унифицированную методику на базе целочисленного программирования у которого в сгенерированном множестве допустимых маршрутов не обязательно содержится оптимум. Метод потенциалов на базе линейного программирования оптимально решает транспортную задачу. Она отличается от задачи маршрутизации, которую принято решать после получения решения транспортной задачи, и ее результаты не гарантируют оптимальности. Таким образом, совершенного оптимизационного метода решения задач маршрутизации в настоящее время не существует.

В работе предлагается и исследуется единая методика оптимизации и управления процессом формирования маршрутов поставок потребительских товаров при комплексном решения задачи с учетом рационального и технологичного размещения товаров в транспортных средствах, отличающаяся от известных использованием множества остовных деревьев, позволяющая находить лучшие маршруты (из множества допустимых) различного типа и соответствующие планы загрузки в нестабильной распределительной среде при организации цепи поставок. Кроме того, составляющие ее разработанные модели, методы и алгоритмы в совокупности с известными методами для решения различных задач маршрутизации и размещения грузов в транспортных средствах составляют основу для оптимизационного ядра модуля управления логистической информационной модели. Использование, которой на логистических предприятиях и распределительных центрах осуществляющих транспортировку товаров, позволяет решать задачу формирования в комплексе с задачей загрузки транспортных средств. Это позволяет учитывать технологичность загрузки ТС и формировать ее в соответствии с маршрутом. Кроме этого, достоинством предлагаемой методики является быстрое формирование множества рациональных маршрутов рекордной длины. Анализ текущего состояния транспортной сети, состояние и наличие транспортных средств, приоритетов в обслуживании клиентов и т.п., позволит выбрать наиболее подходящие на данный момент. А использование качественных методов расчета гарантирует сокращение длины маршрутов и количества используемых ТС.

Сравнительный анализ и характеристика эволюционных метаэвристик показали предпочтительность очень быстрого одноточечного алгоритма, который был предложен Рехтенбергом в 70-е годы для непрерывных задач, а для задач дискретной оптимизации успешно применялся П.А. Борисовским в 2004 г. Поэтому разработанная методика оптимизации и управления процессом фор-

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

1-й уровень метаэвристики [перебор о

Транспортная сеть, заказы

р остовных

деревьев)

2-й уровень (,перебор "рааВЖШИИ^ последовал!

е/гь-ностей товаров)

Построение остовного дерева

дерево

]

Декомпозиция дерева на маршруты

_ —«—^ маршруты сг

Совмещение (синтез) маршрутов с учетом вместимости ТС |

Плотная загрузка ТС с учетом технологичной загрузки-разгрузки (последовательности посещения клиентов)

план загрузни

Определение ТС, корректировка маршрутов

Рисунок 1. Общая схема методики формирования маршрутов поставок потребительских товаров с учетом загрузки-разгрузки транспортных средств

Эволюционная метаэвристика применяется на двух уровнях: при выборе остовного дерева и рациональной последовательности товаров. Первый уровень метаэвристики просматривает маршруты, построенные на переборе множества остовных деревьев. Т.е на каждой итерации строится новое случайное дерево несильно отличающиеся от предыдущего, и процесс повторяется, полученное решение сравнивается с рекордным значением протяженности маршрута и меньшее значение принимается в качестве нового рекорда. Таких итераций выполняется 1000, 10 000 и т.д. в зависимости от размерности сети, времени отведенного на расчеты и т.п. Время расчета от доли секунды до 3-х минут. 2-й уровень - реализуется при построении различных последовательностей продуктов. Таким образом, осуществляется перебор допустимых решений, построенных на остовных деревьях и выбор лучшего маршрута. После расчета маршрутов и плана размещения товаров в ТС, осуществляется обеспечение поставок:

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

Методика формирования маршрутов с рациональным и технологичным размещением в транспортных средствах основана на разработанных методах:

- эволюционным метод множества остовных деревьев с алгоритмами декомпозиции (разложения) дерева на маршруты и алгоритмом совмещения маршрутов с учетом вместимости ТС;

- модификации мультиметодной технологии для технологичной и плотной загрузки ТС.

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

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

В качестве основной математической модели транспортной логистики, как правило, принимается классическая транспортная задача, в которой решается вопрос о доставке продукта из пунктов его складирования в пункты потребления. При этом перевозки осуществляются по реальной транспортной сети, которая легко интерпретируется на графах Г(К, 5). Каждому узлу сети соответствует вершина у,- е V, а звену - дуга 5 = (г,, ). В рассматриваемой основной задаче сеть состоит из т узлов и п звеньев. Для каждого узла г заданы вещественные числа Ь^, /' = 1, т, к = \,д. Если Ь^ > 0, то в г-ом узле расположен склад, располагающий товаром к-го вида в количестве Ь¡^. Если же Ьц, < 0, то в г'-ом узле расположен потребитель (клиент) и его заказ на товар ¿-го вида составляет |. В случае если Ь^ = 0, /-ый узел промежуточный. Для каждого звена задано вещественное число (!<., которое может иметь различный смысл, например: протяженность звена, время прохождения звена ТС, стоимость провоза по звену единицы товара, пропускная способность звена. Требуется составить план развоза товара, минимизирующий значение целевой функции £ с!,.. Обычно выбирается одна из целевых функций и для нее решается задача. Если нужно учесть несколько критериев оптимальности, то задача решается по каждому из них и выбирается одно, подходящее к каждому критерию, решение. При этом модели могут быть различными. В случае критериев протяженности или стоимости, базовой является транспортная модель, а в случае временного критерия или пропускной способности, используется модель сетевого планиро-

вания. В диссертации рассматривается критерий протяженности или стоимости суммарного пути маршрутов. Эта модель относится к классу многопродуктовых сетевых транспортных моделей. Ее частным случаем является однопродук-товая модель, которая состоит в следующем.

Задача Т. Требуется минимизировать суммарную протяженность пути л

¿ = 2Х

s=1

на множестве {£)} остовных деревьев и планов развозки груза клиентам

х = (x\,x2,—,xs,...,xn), где xs - объем груза, перевозимого по звену j е D, удовлетворяющих условиям

2X - 2Х =bt, i = \,m

s<=Ni seNf

где Nj~ - множество звеньев s, входящих в узел i, Nf - множество звеньев s, выходящих из i. При этом

т

2>=о.

1=1

Для решения транспортной задачи Л.В. Канторович в 1938 году предложил метод потенциалов, который представляет собой конкретизацию линейного программирования для решения транспортной задачи. Однако само по себе решение транспортной задачи не обеспечивает получение оптимальных маршрутов. Задачи маршрутизации появились параллельно развитию линейного программирования. К настоящему времени выделены следующие направления в проектировании рациональных маршрутов:

- Метод Форда-Фалкерсона поиска на сети кратчайших путей в глубину и ширину. Для крупных сетей, даже городского типа, метод слишком громоздкий. С целью сокращения размерности сети Е.В. Панкратьев и A.M. Чеповский предложили подход исключения из сети неотмеченных вершин с продолжением поиска решения с помощью эвристики.

- B.C. Лукинский, Т.А. Родкина и другие авторы предлагают решать задачу маршрутизации в два этапа: на первом этапе решается транспортная задача, а на втором ее решение преобразуется в совокупность маршрутов. При этом оптимум в транспортной задаче не обязательно соответствует кратчайшим маршрутам и наоборот кратчайшим маршрутам отвечает допустимое, но не обязательно оптимальное решение транспортной задачи.

- Ю.М. Неруш предложил метод «минимального» остовного дерева (с минимальной суммарной протяженностью его дуг) и это дерево преобразовывается в совокупность маршрутов на другом этапе. Найденная совокупность маршрутов не всегда является оптимальной.

Второй и третий случаи иллюстрируются на рис. 2. На этом рисунке жирными линиями обведены ветви остовного дерева, которые указывают пути из

вершины 0 в вершины 1, 2 и 3; где Ьд - суммарная длина дуг дерева, Ьп - суммарная длина путей. В случае рис.1, а имеем кратчайшие пути общей протяженности 69, дерево той же протяженности не является оптимальным для представленной сети. В случае рис. 2, б имеем оптимальное дерево протяженности 44, а протяженность кратчайших путей не является оптимальной. В случае рис. 2, в имеем протяженность совмещенных путей 52< 115 - общей протяженности путей. При совмещении путей, остается один путь из вершины 0 в вершину 2, он совмещает в себе и пути в вершину 3 и в вершину 1. Если позволит вместимость транспортных средств, то предпочтение следует отдать случаю рис. 2, в. Приведенные подходы целесообразно применять при использовании однопроходных эвристик.

Рисунок 2. а) дерево кратчайших путей ¿¿ = £„ = 69; б) кратчайшее дерево путей Ьд =44, Ьп = 78; в) = 52; Ь„ =115; длина совмещенных путей Ьс„ = 52

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

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

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

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

Алгоритм разложения остовного дерева на маршруты.

Обозначим: S/ - файл фрагментов маршрутов; Sm - файл множества маршрутов; Sv. - файл множества вершин.

Вход: Остовное дерево D.

Шаг 1. Начало: Выбирается одна исходная вершина г0 û Sv и помещается в Sv. Дуга .sq = (/g, 7o)jo помещается в Sf. j0 - добавляется в Sv. Если таких дуг несколько, то они размещаются в Sf, а инцидентные им вершины в Sv.

Шаг 2. Выбор очередной дуги. Пусть фрагмент очередного маршрута содержит к дуг. Последняя дуга sk = [is/ç, j4 ). Находим в дереве D дугу sk+ï, с

началом = j4 и концом j4+l £ Sv. Если таких дуг несколько, то каждую

добавляем к последнему непустому фрагменту, получая несколько новых фрагментов. Иначе, если такой дуги нет то маршрут построен и он переносится из файла Sf в Sm. Если Sf Ф 0, то шаг 2 выполняется для последнего фрагмента

из sf , иначе если |SV| ф т, то на шаг 1, иначе, если |5V| = m, то на шаг 4.

Шаг 3. Совмещение маршрутов. Если в Sm существуют два таких маршрута, что один из них является фрагментом второго, то этот маршрут исключается из Sm и объемы xs перевозимого груза корректируются. Таким образом, количество маршрутов уменьшается. В противном случае переход к шагу 4.

Шаг 4. Конец. Файл Sm содержит список всех маршрутов. Подсчет суммарной протяженности маршрутов.

Выход: список Sm маршрутов; L{Sm) - суммарная протяженность маршрутов.

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

Алгоритм совмещения консолидированных маршрутов. Алгоритм состоит из выполнения (р+1) этапов. На каждом этапе выполняются идентичные процедуры поиска маршрута перевозки для продукта k = l,p; на (р+1)-ом этапе некоторые из маршрутов совмещаются. Для выполнения совмещения выбирается самый длинный по числу звеньев маршрут. Он объявляется «ведущим». Среди остальных маршрутов отыскиваются те, которые представляют связанные части «ведущего» маршрута, они объединяются с ним. Для фиксирования объемов развозок по каждому звену s используется векторная запись

X — (х^ , Xj^,..., Хр ) .

Перестановки различных товаров в процессах «разложения» остовного дерева и «совмещения» маршрутов приводят к различным результатам. Поэтому следует выполнить процедуры разложения дерева и совмещения маршрутов

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

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

На входе имеем транспортную сеть. Одна итерация метода остовного дерева состоит из выполнения следующих шагов.

Шаг 1. Построение остовного дерева Б. Выполняется алгоритм Прима.

Шаг 2. Решение системы уравнений £ + Р = 0 > и корректировка дерева

с целью получения > 0,5 = 1 ,п, ¡5 = - вес г'-ой вершины

(наличие/запас клиента); х8 - количество товара, перевозимого по звену 5.

Шаг 3. Разложение остовного дерева на маршруты.

Шаг 4. Совмещение (частичное объединение) маршрутов. Маршруты совмещаются, если один из них является подмаршрутом другого, объемы товара складываются. Оставшаяся вместимость ТС корректируется.

4.1. Поиск пары маршрутов из списков 1 и 2, подходящих для совмещения. Пусть это М1 и Л/2 и один из них является подмножеством другого.

4.2. Маршруты

и М2 совмещаются и объемы товаров с учетом вместимости ТС складываются.

4.3. Подготовка информации для загрузки следующего в списке (к+2)-то товара. Если (к+1)=р, то переход на шаг 5.

Выполняется заданное количество р итераций алгоритма синтеза двух маршрутов. На (Аг+1)-ой итерации происходит совмещение подходящих маршрутов и сложение объемов к видов продуктов с (£+1)-ым продуктом, если это позволяет сделать оставшаяся вместимость ТС, иначе этот продукт остается до выполнения следующей итерации.

Шаг 5. Расчет суммарной протяженности маршрутов и сравнение с рекордной.

Шаг 6. Конец итерации. На выходе имеем совокупность маршрутов рекордной протяженности, для звеньев в которых указаны объемы загрузки товаров.

Шаг 7. Корректировка исходной информации. Если количество нижних итераций исчерпано, то переход на Шаг 1, иначе для дерева Б переход на шаг 2 для вектора р, соответствующего следующему продукту.

На выходе формируется совокупность маршрутов для консолидированных перевозок.

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

маршрута используется прием замыкания развозочного пути, предложенный Ю.М. Нерушем. Предположим, что задача построения незамкнутых маршрутов решена и мы имеем список маршрутов. Для каждого из развозочных маршрутов построим кратчайший путь из последней вершины маршрута к первой, исходной вершине. Для этого используется алгоритмом Дейкстры. Учитывая, что любой подпуть кратчайшего пути является кратчайшим путем, можно утверждать, что «замкнутый маршрут, полученный замыканием оптимального незамкнутого развозочного маршрута, является оптимальным». При поиске рационального незамкнутого маршрута можно гарантировать получение близкого к оптимальному замкнутого маршрута (цикла).

С помощью экспериментального программного продукта реализующего эволюционный метод множества остовных деревьев были проведены многочисленные (порядка 1000 примеров) вычислительные эксперименты. Результаты экспериментов и сравнительный анализ, подтвердили высокое качество предложенных, обоснованных и описанных в диссертации методов и алгоритмов, возникающих в процессах товародвижения. Тестирование проходило с различными параметрами: количество пунктов-клиентов, потребности товара в пунктах, количество регионов, объем, грузоподъемность ТС. Среднее улучшение (уменьшение длины маршрута относительно длины полученной алгоритмом «ближайшего соседа») по всем примерам составляет 8,35%, наихудшее отклонение 0,99%, наилучшее - 15,58%.

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

Задача плотного размещения грузов является важным звеном при планировании товародвижения. Для учета технологии загрузки и разгрузки грузов предложено использовать мультиметодную технологию, которая позволяет учитывать условие загрузки в порядке, обратном посещению клиентов согласно маршрута. Это гарантирует разгрузку каждого клиента непосредственно с торца отсека транспортного средства. Загрузка сводится к решению задачи об упаковке прямоугольных предметов в контейнеры. Она является ИР-трудной и для ее решения известны различные метаэвристики. Автором работы предложено объединить требования плотности загрузки и технологичности разгрузки. Технологичность разгрузки достигается с помощью декодера на базе мультиметодной технологии, предложенной И.П. Норенковым и развитой Ю.И. Валиахметовой.

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

Таким образом, предлагается в комплексе рассматривать задачи маршрутизации и рационального и технологичного размещения грузов в транспортных средствах с применением эвристик. Для качественного решения комплекса взаимосвязанных задач требуется создание модуля управления с оптимизационным ядром для логистической информационной системы (ЛИС), осуществляющего выбор и решение оперативных задач маршрутизации, которое позволяет получать рациональные решения с их оценкой и учетом организационных и технологических ограничений.

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

Совокупность известных и разработанных моделей, методов и алгоритмов составляет основу для построения модуля управления товародвижением в среде логистической информационной системы (ЛИС) с оптимизационным ядром. Он позволяет реализовать анализ текущей ситуации транспортной сети, устанавливать взаимосвязь между элементами (моделями, методами, алгоритмами) модуля и осуществлять управление процессом формирования рациональных маршрутов и планов загрузки.

Модуль управления ЛИС с оптимизационным ядром выполняет функции анализа ситуаций и расчета транспортных маршрутов и планов загрузки. Основной фрагмент модуля управления с оптимизационным ядром, его структурное и функциональное наполнение представлено на рис. 4.

Модуль управления и оптимизации процесса формирования маршрутов с учетом загрузки транспортных средств, включает в себя несколько оптимизационных и эвристических алгоритмов, направлен на принятие одного из возможных решений. Содержание ядра составляют: транспортные модели; алгоритмы решения транспортной задачи; алгоритмы расчета рациональных маршрутов; алгоритмы рационального размещения груза. Ввод исходной информации, ее анализ на различных этапах и принятие решений осуществляется через модуль управления. На рисунке 4 цветом выделены блоки, разработанные в данном диссертационном исследовании, остальные - подробно рассмотрены.

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

Модуль управления ЛИС на базе созданного алгоритмического обеспечения предназначен для совершенствования процесса маршрутизации. Схема модуля управления позволяет, осуществлять анализ и идентификацию состояний элементов; переход к следующему уровню анализа и, находить подходящий блок расчета который формирует рациональный маршрут с плотной загрузкой

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

Рисунок 4. Модуль управления с оптимизационным ядром формирования маршрутов с учетом загрузки транспортных средств

Анализ 1. Информационные транспортные модели. Основная задача транспортировки задается взвешенной транспортной сетью. В результате анализа принимает решение о соответствии информационной модели реальной обстановке на сети. Если соответствие отсутствует, то применяется корректировка модели с использованием соответствующего метода. Так, для перехода от общей сети к упрощенной, в которой фигурируют только потребители и поставщики товаров, применяется алгоритм для поиска кратчайших путей. В случае целесообразности использования зональной транспортной сети, исходная цепь - общая или упрощенная, подвергается декомпозиции на зоны. Если данная сеть сложна, например, представляет большой район, связывающий участками дорог множество узлов и только небольшая часть из них используется, то целесообразно рассматривать упрощенную сеть.

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

Анализ 3. Методы построения маршрутов. Этот уровень предназначен для получения одним из методов допустимого дерева и преобразования его в совокупности маршрутов. Предусмотрено применение точных и эвристических методов для построения деревьев. Метод потенциалов - дает минимальное дерево решений транспортной задачи. Методы построения минимального остов-ного дерева так же позволяют получить оптимальное решение этого этапа. На следующем этапе - преобразование полученного дерева в маршруты. В качестве эвристик используются варианты эволюционных алгоритмов, как самостоятельного метода, так и в совокупности с разработанным методом остовных деревьев. Применяемые алгоритмы быстрые, они удобны для использования в реальном времени. В задаче коммивояжера вместо дерева имеем цепь. Для ее решения известен метод ветвей и границ, различные эвристики, в том числе и эволюционные.

Анализ 4. Методы размещения грузов в ТС. На этом уровне можно выделить две цели: плотность размещения и технологичность погрузки и разгрузки. Для обеспечения плотности можно применить любой известный алгоритм оптимизации двух или трехмерного размещения. Эти задачи хорошо изучены, но эффективных методов полиномиальной сложности для их решения не известно в связи с ^-трудностью задач. В условиях логистической среды требуется получать решение в реальном времени. С этой целью применимы любые эвристики, однако известные методы не закрывают проблему технологичной погрузки и разгрузки. Поэтому выделен разработанный модифицированный мультиме-тодной алгоритм. Он справляется со своей задачей и размещает грузы в порядке, обратном к последовательности посещения ТС клиентов. Предусмотрены варианты режима решения задачи размещения: решения задачи плотного размещения без учета технологии разгрузки; с учетом технологии разгрузки на готовом маршруте; решение комплексной задачи маршрутизации с размещением груза в транспортных средствах. Составляется план размещения товаров в ТС и план их выгрузки в пунктах назначения.

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

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

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

этом анализировались два метода построения маршрутов: «ближайшего соседа» - способ, используемый на предприятии, и разработанный эволюционный с множеством остовных деревьев. Для проведения сравнительного анализа были исследованы маршруты движения транспортных средств, пройденные за один месяц. Общее снижение издержек на перевозку грузов составило 9889 руб. в месяц, за год увеличение прибыли может составить до 118668 руб. Для парка из 35 аналогичных машин регионального распределительного центра экономия составит около 1384460 рублей в год.

Факторами, обуславливающими повышение эффективности функционирования распределительного центра за счет внедрения ЛИС с разработанным оптимизационным модулем управления, являются: сокращение затрат рабочего транспортного отдела; быстрый обмен данными между отделами; быстрый поиск необходимых документов; сокращение времени на составление маршрута и загрузки ТС; снижение себестоимости поставок и минимизация их сроков.

Проведен расчет экономической эффективности внедрения ЛИС. Он осуществлен в соответствии с ГОСТ 24.702-85. Затраты времени на разработку проекта определяются на основе фактических данных с использованием метода хронометража. Основные результаты расчета приведены в таблице 2. Срок окупаемости капитальных вложений составляет чуть более трех месяцев.

Таблица 2

Показатели расчетов Значение, руб

Затраты на создание системы, руб. 369477,5

Текущие затраты на содержание и эксплуатацию ЛИС (выполнение процесса) по базовому варианту, руб. 42781,51

Текущие затраты на содержание и эксплуатацию ЛИС (выполнение процесса) по внедряемому варианту 40508,15

Ожидаемая условно-годовая экономия, руб. 1386733,36

Ожидаемый годовой экономический эффект, руб. 1264805,36

Расчетный коэффициент экономической эффективности капитальных вложений 3,75

Расчетный срок окупаемости капитальных вложений, год 0,27

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

2. Предложен оригинальный эволюционный метод множества остовных деревьев для построения сборно-развозочных маршрутов консолидированных грузов с алгоритмами разложения (декомпозицией) дерева на маршруты и совмещения, отличающийся двухуровневым исполнением и формированием маршрутов не на исходной транспортной сети, а на множестве покрывающих ее остовных деревьях, что позволяет значительно снизить размерность комбинаторной задачи, осуществлять поиск кратчайших маршрутов на множестве допустимых решений, что приводит к экономии при транспортировки в цепи поставок потребительских товаров распределительного центра. Его применение позволяет существенно снизить время расчетов и уменьшить протяженность маршрутов в среднем на 8,35% (наибольшее - 15,58%) по сравнению с классическим способом «ближайшего соседа». При этом процедура поиска совмещенных маршрутов позволила улучшить организационно-экономические аспекты реализации поставок в среднем на 6%.

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

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

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

5. Проведен анализ предложенной методики оптимизации и управления процессом формирования маршрутов поставок потребительских товаров. Ее применение позволяет сократить транспортные издержки за счет уменьшения протяженности маршрутов и плотности загрузки транспортных средств. При этом совмещение маршрутов позволяет улучшить организационно-экономические аспекты реализации поставок в среднем на 6%. Проведен расчет экономической эффективности внедрении ЛИС с оптимизационным модулем управления, использующий разработанный метод комплексного решения задачи маршрутизации на основе множества остовных деревьев: ожидаемая условно-годовая экономия - 1386733 руб.; ожидаемый годовой экономический эффект - 1264806 руб.; расчетный коэффициент экономической эффективности капитальных вложений - 3,75; расчетный срок окупаемости капитальных вложений - 3 мес.

Основные положения диссертации изложены в следующих публикациях:

1. Мухачева Э.А., Бухарбаева Л.Я., Филиппов Д.В., Карипов У.А. Оптимизационные проблемы транспортной логистики: оперативное размещение контейнеров при транспортировке грузов. //-М.: Информационные технологии. №7. 2008. С. 17-22 (0,75 пл., автору - 0,2) - список ВАК.

2. Филиппова A.C., Филиппов Д.В., Карипов У.А. Алгоритм рационального размещения грузов в транспортных средствах Н-М. Логистика. №1. 2008. С. 25 (0,13 п.л., автору - 0,07) - список ВАК.

3. Филиппова A.C., Филиппов Д.В. Гильманова H.A. Задачи маршрутизации в транспортных логистических системах: локальный поиск оптимальных решений //-М.: Информационные технологии. №2,2009. С. 59-63 (0,6 п.л., автору - 0,25) - список ВАК.

4. Бухарбаева Л.Я., Филиппов Д.В., Д.П. Брусиловский Д.П. Прогнозирование и управление цепью поставок в логистической среде товарно-производственных комплексов // -Челябинск. Вестник ЧГУ. №3 (141). Экономика (вып. 19). 2009. С. 92-99 (0,8 п.л„ автору - 0,3) - список ВАК.

5. Филиппов Д.В. Метод маршрутизации консолидированных поставок в логистической среде распределительного центра с применением двухуровневой метаэвристики Н-М.: МЭСИ. Экономика, статистика и информатика. Вестник УМО. 2010. №2. С. 61-64 (0,4 п.л., автору - 0,4) - список ВАК.

6. Bukharbaeva L.Y., Filippov D.V., Gilmanova N.A., Karipov U.A. Information-Based Approaches to Local Search for Rational Solutions of Transportation and Bin-packing Complex Problems // Материалы конференции «Computer Science and Information Technologies (CSIT'2007)». Том 2./ - Уфа: УГАТУ. 2007. С. 34-39 (0,6 п.л., автору-0,15).

7. Филиппов Д.В. Качество обслуживания при транспортировке заказов в интегрированной цепи поставок. // II-ая Межрегиональная научно-практическая Интернет конференция «Информационные технологии и телекоммуникации в образовании, экономике и управлении регионом». / - Тюмень. 2007. http://conference.utmn.ru/?reports=show&rid=104 (0,15 п.л.).

8. Карипов У.А., Филиппов Д.В. Планирование оперативной упаковки контейнеров при транспортировке товаров // Принятие решений в условиях неопределенности. Выпуск 4. /-Уфа: УГАТУ. 2008. С. 151-155 (0,3 п.л, автору-0,15).

9. Филиппов Д.В., Гильманова Н.А. Экстремальные задачи транспортной логистики. // Изменяющаяся Россия. Социально-экономические инновации: материалы XXV международной научно-практической конференции,4.II. / -Челябинск: Урал, соц.-экон. ин-т АТиСО. 2008. С. 413-417 (0,25 п.л, автору -0,15).

10. Филиппов Д.В. Качество обслуживания при транспортировке заказов в интегрированной цепи поставок. // Сборник материалов седьмой Всероссийской научно-практической конференции «Управление качеством» / -М.: «МАТИ». -2008. С.189-190 (0,13 п.л.).

11. Гильманова Н.А, Карипов У.А, Филиппов Д.В. Оптимизационные задачи транспортно-упаковочного комплекса в логистике поставок // Сборник статей третьей всероссийской зимней школы-семинара аспирантов и молодых ученых. Экономика. Социология и гуманитарные науки. Том 3. / -Уфа. 2008. С. 56-62 (0,45 п.л, автору - 0,20).

12.Гильманова Н.А, Карипов У.А, Филиппов Д.В.. Оптимизационные задачи в транспортных логистических системах. // Принятие решений в условиях неопределенности. Выпуск 9. / -Уфа. УГАТУ. 2009. С. 168-173 (0,4 п.л, автору -0,15).

13. Бухарбаева Л.Я, Филиппова А.С, Филиппов Д.В. Моделирование интегрированной цепи поставок в индустриальной среде // Logistika vykonneho podniku. Коллектив авторов под редакцией Петера Сакала. / Словацкий технический университет Братиславы. Словакия. 2009. С. 325-348 (2,9 п.л, автору - 1,0).

14. Филиппова А.С, Бухарбаева Л.Я, Филиппов Д.В. Стохастические подходы решения задач транспортной логистики // Materialy VII Miedzynarodowej nauko-wi-praktycznej konferencji „Dynamika naukowych badan - 2011" Voume 3. Ekonomiczne nauki.: Przemysl. /Nauka I studia. 2011. 19-22 p (0,25 п.л, автору -0,15).

Подп. в печ. 18.04.2012. Формат 60x90/16. Объем 1,0 п.л.

Бумага офисная. Печать цифровая.

_Тираж 50 экз. Заказ № 273_

ФГБОУВПО «Государственный университет управления» Издательский дом ФГБОУВПО «ГУУ»

109542, Москва, Рязанский проспект, 99, Учебный корпус, ауд. 106

Тел./факс: (495) 371-95-10, e-mail: diric@guu.ru

www.guu.ru

Диссертация: текстпо экономике, кандидата экономических наук, Филиппов, Дмитрий Вячеславович, Москва

61 12-8/2255

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

ФИЛИППОВ Дмитрий Вячеславович

УПРАВЛЕНИЕ И ОПТИМИЗАЦИЯ ПРОЦЕССА ФОРМИРОВАНИЯ МАРШРУТОВ ПОСТАВОК ПОТРЕБИТЕЛЬСКИХ ТОВАРОВ В РАСПРЕДЕЛИТЕЛЬНЫХ ЦЕНТРАХ

Специальность 08.00.05 - Экономика и управление народным хозяйством

(Логистика)

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

Научный руководитель д-р экон. наук, профессор Волочиенко В.А.

Москва 2012

ОГЛАВЛЕНИЕ

Стр.

Введение................................................................................ 4

ГЛАВА 1. ПРОБЛЕМЫ МАРШРУТИЗАЦИИ В УСЛОВИЯХ РАСПРЕДЕЛИТЕЛЬНОГО ЦЕНТРА: АНАЛИТИЧЕСКИЙ ОБЗОР ЗАДАЧ И МЕТОДОВ ИХ РЕШЕНИЯ.......................................... 12

1.1. Задачи маршрутизации в свете тенденций развития распределительной логистики................................................................... 13

1.2. Составляющие интегрированной цепи поставок в распределительной среде....................................................................................................................................................20

1.3. Распределительные центры как объекты логистического распределения потребительских товаров................................................... 25

1.4. Логистика в формате развития розничной торговли .................... 35

1.5. Транспортное обеспечение: маршрутизация движения транспортных средств при поставке потребительских товаров.............................. 43

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

1.7. Структура и основные функции логистических информационных

систем.................................................................................. 71

Выводы по главе 1 ................................................................. 74

ГЛАВА 2. МОДЕЛИ, МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ОСНОВНЫХ ЗАДАЧ ТРАНСПОРТНО-УПАКОВОЧНОГО КОМПЛЕКСА......................................................................... 77

2.1. Модели и методы транспортного обеспечения............................ 77

2.2. Задача незамкнутой маршрутизации и метод ее решения ............................81

2.3. Краткая характеристика эволюционных алгоритмов ......................................97

2.4. Исполнение маршрутов: плотная загрузка грузовых отсеков, с учетом технологии загрузки и разгрузки ......................................................................................99

2.5. Численный эксперимент..............................................................................................................110

Выводы по главе 2........................................................................................................................................123

ГЛАВА 3. МЕТОДИЧЕСКИЕ РАЗРАБОТКИ И РЕКОМЕНДАЦИИ ПО ПРИМЕНЕНИЮ РАЗРАБОТАННЫХ МОДЕЛЕЙ И АЛГОРИТМОВ В ЛОГИСТИЧЕСКОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ ФОРМИРОВАНИЯ ТРАНСПОРТНЫХ МАРШРУТОВ...................... 126

3.1. Логистическая информация: назначение и принципы организации ... 127

3.2. Структура логистической информационной системы .................. 129

3.3. Оптимизационное ядро модуля управления формированием транспортных маршрутов.................................................................. 134

3.4. Экономическая эффективность внедрения ЛИС с оптимизационным

ядром на основе разработанных моделей и алгоритмов..................... 140

Выводы по главе 3........................................................................................................................................159

ЗАКЛЮЧЕНИЕ..............................................................................................................................................160

СПИСОК ЛИТЕРАТУРЫ .................................................................................163

ПРИЛОЖЕНИЕ..............................................................................................................................................172

ВВЕДЕНИЕ

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

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

тимизационное ядро логистической информационной системы (ЛИС).

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

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

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

Вопросам развития теоретических и практических основ логистики в сфере перевозок и, в частности, маршрутизации посвящены работы видных отечественных и зарубежных ученых, таких как, Б.А. Аникин, Д. Бауэрсокс, В.В. Дыбская, Р. Мерфи, Ю.М. Неруш, Т.А. Родкина, В.И. Сергеев, Ю. Шапиро, Д. Уотерс и ряда других. Известны результаты исследуемых проблем совершенствования маршрутизации с применением современных информационных технологий, новых подходов к организации логистических процессов, применения моделей и методов исследования операций.

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

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

составляет оптимизационное ядро модуля управления ЛИС. Использование ЛИС с оптимизационным ядром позволит снизить издержки в производственно-коммерческой деятельности распределительных центров.

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

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

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

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

• предложить методику для оптимизации и управления процессом формирования маршрутов поставок потребительских товаров в распределительных центрах на основе общей платформы множества остовных деревьев с использованием базовых моделей и методов решения оптимизационных задач транспортной логистики и информационных технологий;

• разработать на базе эволюционной метаэвристики алгоритмы решения следующих задач маршрутизации товарных потоков: построение сборно-развозочных незамкнутых маршрутов поставок товаров с обобщением для циклических маршрутов; маршрутизация консолидированных грузов; маршрутизация с рациональным размещением товаров в транспортных средствах и соблюдением технологических условий разгрузки;

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

• разработать на базе созданной методики и алгоритмического обеспечения модуль управления логистической информационной системы, предназначенный для: анализа транспортной ситуации; определения множества маршрутов и планов загрузки-разгрузки транспортных средств в текущей ситуации; выбора рационального маршрута в условиях нестабильной распределительной среды;

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

Объектом исследования являются товарные потоки в цепях поставок распределительных центров.

Предметом исследования является оптимизация и управление процессом формирования маршрутов поставок потребительских товаров в распределительных центрах.

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

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

Научные результаты, полученные лично автором и обладающие научной новизной:

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

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

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

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

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

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

Основные научные и практические результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Международной конференции «Computer Science and Information Technologies» (Уфа 2007), Интернет конференции «Информационные технологии и телекоммуникации в образовании, экономике и управлении регионом» (Тюмень 2007), международной научно-практической конференции «Изменяющаяся Россия. Социально-экономические инновации» (Челябинск, 2008), Зимней школе аспирантов и молодых ученых (Уфа 2008, 2009), научно-практической конференции «Управление качеством» (Москва 2008).

Результаты диссертационного исследования используются в учебном процессе Уфимского государственного авиационного технического университета при проведении занятий по учебным дисциплинам «Математические методы и модели транспортной логистики», по специальности 010501 «Прикладная математика и информатика» и «Математические модели и методы логистики», по направлению подготовки магистра 010200.68 «�