close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Экономика
МЕТОД МАРШРУТИЗАЦИИ КОНСОЛИДИРОВАННЫХ
ПОСТАВОК В ЛОГИСТИЧЕСКОЙ СРЕДЕ
РАСПРЕДЕЛИТЕЛЬНОГО ЦЕНТРА С ПРИМЕНЕНИЕМ
ДВУХУРОВНЕВОЙ МЕТАЭВРИСТИКИ
УДК 656.073
Дмитрий Вячеславович Филиппов
Соискатель кафедры «Логистика»
Государственного
университета
управления
Тел.: (499) 140-07-49
E-mail: mari009@rambler.ru
Рассматривается логистическая среда
распределительного центра в составе
транспортной сети, связывающей центр
со складами и потребителями.
Предложены новые методы и алгоритмы
поиска оптимальных маршрутов
транспортировки консолидированной
продукции. Методы основаны на
применении
двухуровневой
метаэвристики.
Ключе вые слова: маршрутизация,
транспортировка, консолидированные
грузы, метаэвристика.
Dmitry Vjacheslavovich Filippov
The competitor of faculty Logistics of the
State university of management
Number: (499) 140-07-49
E-mail: mari009@rambler.ru
METHOD OF ROUTING OF THE
CONSOLIDATED DELIVERIES IN THE
LOGISTICAL ENVIRONMENT OF A
DISTRIBUTION CENTRE WITH APPLICATION
OF TWO-LEVEL METAHEURISTICS
The logistic area of the distributive centre that
includes a transportation net connecting the
center with warehouses (stores) and
consumers (customers) is unde r
consideration. New models and algorithms for
searching optimal routes of consolidated goods
transportation are suggested. The above
methods are based on the way the two-level
metaheuristics is applied.
Keywords: routi ng, transportation,
consolidated cargoes, metaheuristics.
1. Введение
Рассматриваемый в качестве примера региональный распределительный центр
использует для перемещения грузов автотранспорт различной вместимости и
грузоподъемности, осуществляет доставку продуктов от своего складского комплекса по территории, ограниченной административным округом, т.к. является
региональным дистрибьютором на отведенной территории. Выбор средства доставки товаров обусловлен следующими преимуществами автотранспорта в существующей логистической среде: большой маневренностью и подвижностью,
высокой скоростью доставки грузов, возможностью доставки без промежуточных перегрузок, сравнительно небольшими капитальными вложениями в освоение малого товарооборота на короткие расстояния. Клиентская база включает
более 1000 торговых точек с различной торговой площадью от небольших продуктовых магазинов до супер- и гипермаркетов. Ассортимент товара насчитывает более 2500 наименований и является разнородным как по весу, объему, срокам
хранения, так и по условиям перевозки. Сложность при составлении маршрутов
заключается в соблюдении требуемых условий перевозки для подобного ассортимента и времени доставки в торговые точки.
Проблемы маршрутизации и другие вопросы логистической цепи поставок
изучались различными авторами [1,2]. Включение неадаптированных математических методов в программные модули не приносит желаемых результатов, необходима разработка логистико-ориентированных методов решения оптимизационных задач, инвариантных к составу грузов и особенностям транспортных средств,
которые могут применяться для распределительных центров в разных сферах деятельности.
2. Задачи и методы транспортной логистики
2.1. Краткий обзор базовых проблем транспортировки. Приведем базовые методы, они применяются в транспортной логистике для решения локальных проблем или в качестве отдельных модулей.
Построение кратчайшего пути. Задана транспортная сеть, состоящая из m
узлов и n звеньев. Для каждого звена s задана длина d S . Рассматривают следующие задачи о кратчайшем пути: поиск пути от одного узла до другого, от одного
узла до всех остальных; между каждой парой узлов. Для решения этих задач известен и широко применяется алгоритм Дейкстры [3,4].
Построение остовного дерева. Задан граф Г, отвечающий транспортной сети.
Остовным деревом называют подграф графа Г, являющийся деревом и содержащий все вершины исходного графа. Остовное дерево сети содержит подмножество звеньев сети, в котором существует путь между каждой парой узлов. Известен алгоритм Прима для построения остовного дерева с любым или минимальным весом [3,4].
Однопродуктовая транспортная задача на сети. Требуется организовать
перевозку однородного продукта по звеньям сети. Для ее решения в конце 30-х
годов был предложен Л.В.Канторовичем метод потенциалов, предвосхитивший
появившееся позднее линейное программирование. Допустимому базисному
решению этой задачи отвечает остовное дерево. Поиск оптимального решения
реализуется в процессе направленного перебора на множестве остовных деревьев.
Задача коммивояжера. На транспортной сети требуется найти кратчайший
цикл, содержащий все вершины. Эта задача является NP-трудной. Наряду с точными переборными алгоритмами (метод ветвей и границ) применяются различные
метаэвристики [4]. Для моделирования задачи коммивояжера транспортную сеть
целесообразно разделять на зоны обслуживания одним транспортным средством.
С этой целью применяются методы распознавания образов, в частности метод
ближайшего соседа.
Поиск маршрутов в ширину и глубину. Требуется определить порядок посещения узлов транспортной сети, минимизирующий длину пути.
Экономика, Статистика и Информатика
61
№2, 2010
Экономика
Поиск в ширину. Выбирается произвольно узел V0 сети, затем посетим
всех его соседей, например узлы V1, V2,..
. Далее начинается обход всех соседей
узла V1 и т.д. Если пометить дугу, соединяющую посещенный узел с ранее посещенным узлом, то помеченные дуги
образуют остовное дерево сети; если
же дуги имеют одинаковую длину, то
остовное дерево является деревом кратчайших путей V0 во все остальные узлы.
Поиск в глубину. Выбираем произвольно вершину V0, а затем следуем по
ребру в узел V1, из этого узла следуем
по ребру в узел V2 и т.д.
Для решения задачи маршрутизации консолидированых поставок предложены новые алгоритмы декомпозиции дерева и синтеза маршрутов.
3. Задача маршрутизации консолидированных грузов
3.1. Основная модель. В качестве
основной приведем модель организации поставок консолидированных товаров. Задана транспортная сеть, состоящая из m узлов и n звеньев, связывающих пары узлов. Для каждого звена s
заданы вещественные числа ds, s 1, n ,
имеющие смысл протяженности звена.
Для узлов заданы числа bik, i 1, m ,
k 1, p . Если bik>0, то в i-ом узле расположен склад, располагающий товаром k-го вида в количестве bik. Если же
bik<0, то в i-ом узле расположен потребительский объект и его заказ на товар
k-го вида составляет bik , т.е. для узла i
задан p-мерный вектор. Вершины, помеченные положительными числами
называют начальными (источниками),
отрицательными конечными (стоками). Требуется на сети составить план
перевозки консолидированных (совмещенных) товаров, минимизирующий
суммарный пробег транспортных
средств. План содержит множество
маршрутов, каждый из которых предназначен для движения одной или нескольких единиц транспортных средств
с целью выполнения заказов клиентов
с минимальными транспортными расходами. Одновременно нужно составить план загрузки и выгрузки различных товаров с учетом вместимости
транспортных средств.
3.2. Декомпозиция остовного дерева на маршруты. На этапе реализации
решения необходимо составить план
маршрутов на сети, т.е. найти их совокупность, по которым будут передвигаться транспортные стредства. В отличие от алгоритма маршрутизации в
ширину или глубину на сети, предло-
№2, 2010
жен метод декомпозиции остовного
дерева на маршруты. Учитывая, что
остовное дерево является деревом путь,
предлагается искать оптимальные маршруты на множестве остовнах деревьев для этого используем эволюционную метаэвристику [5] с декодером декомпозиции дерева на маршруты. Алгоритм декомпозиции состоит в последовательном формировании маршрутов, начиная с дуги дерева, одна из вершин которой является исходной. Процесс продолжается пока не будут пройдены все вершины дерева. Если при
этом существуют два таких маршрута,
что один из них является фрагментом
второго, то этот маршрут исключается,
а объемы перевозимого груза суммируются. Остается подсчитать протяженность всех маршрутов и сравнить ее с
достигнутым рекордом. Процесс останавливается при достижении границы
или заданного количества итераций.
Приведем алгоритм декомпозиции для
случая перевозки одного вида товара.
Алгоритм разложения (декомпозиции) остовного дерева на маршруты. На входе имеем остовное дерево,
дугам s которого отвечают объемы перевозок x s . Обозначим: Ф фрагменты маршрутов; М множество маршрутов; В множество вершин.
Шаг 1. Начальный фрагмент. Выбирается дуга s0 , одна из вершин которой is 0 является исходной. Дуга
s0 is0 , js0 помещается в файл Ф.
Вершины is0 , js0 помещаются в файл
В. Если для j0 js0 существует дуга s1 ,
связывающая j0 i1 с некоторой вершиной j1 B , то она добавляется в
файл Ф; а вершина j1 добавляется в
B. Иначе, фрагмент из Ф является маршрутом и он помещается в М.
Шаг 2. Текущий фрагмент. Фиксируем в Ф первый непустой фрагмент.
Пусть это будет: sk , sk 1 ,..., sk e . Если
возможно, к фрагменту добавляем дугу
sk e 1 , иначе он переходит в следующую
свободную позицию файла М, а его
последняя вершина помещается в файл
В.
Шаг 3. Если В содержит все вершины дерева, то переход на шаг 5, иначе
возврат к исходной или другой начальной вершине.
Шаг 4. Сложение маршрутов.
Если в М существуют два таких маршрута, что один из них является фрагментом второго, то этот маршрут исключается из М и объемы xs перевозимого груза корректируются. Таким образом, количество маршрутов уменьша-
62
ется, иначе переход к шагу 5.
Шаг 5. Конец. Файл М содержит
список всех маршрутов. Подсчет суммарной протяженности маршрутов.
3.3. Общий алгоритм решения задачи маршрутизации консолидированных грузов. Каждый клиент, как правило, заказывает различный товар и желает получить его единовременной поставкой. Метод декомпозиции применяется тогда для каждого вида товара,
затем полученные маршруты складываются. В качестве общего алгоритма
используется простая эволюционная
метаэвристика двухуровнего исполнения. На верхнем уровне реализуется
случайный перебор остовных дервьев.
Для каждого остовного дерева решаются задачи декомпозиции и синтеза. При
этом нижний уровень эволюционного
алгоритма реализуется в задаче синтеза: на каждой итерации решения задачи
выбирается случайная последовательность размещения товаров. Применение метаэвристики обеспечивает поиск
экстремума в достаточно большой области допустимых решений.
Общий алгоритм. На входе имеем
транспортную сеть. Одна итерация состоит из выполнения следующих шагов.
Шаг 1. Построение остовного дерева D. Выполняется алгоритм Прима.
Шаг 2. Решение системы уравнений
(b1 , b2 ,..., bi ,..., bm ),
0,
xs
s D
bi - вес i-ой вершины; xs - количество товара, перевозимого по звену s.
Шаг 3. Декомпозиция остовного
дерева на маршруты.
Шаг 4. Синтез маршрутов. После
выполнения k итераций имеем: список1
совмещенных маршрутов с указанием
объема каждого из товаров, поставляемых каждому клиенту и оставшейся
вместимости транспортных средств;
список2 маршрутов поставки (k+1)-го
товара.
4.1. Поиск пары маршрутов из списков 1 и 2, подходящих для совмещения,
пусть это M1 и M2 и один из них является подмножеством другого.
4.2. Маршруты M1 и M2 совмещаются и объемы товаров с учетом вместимости транспортных средств складываются.
4.3. Подготовка информации для загрузки следующего в списке (k+2)-го товара. Если (k+1) = p, то переход на шаг 5.
Выполняется заданное количество p
итераций алгоритма синтеза двух маршрутов. На (k+1)-ой итерации проис-
Экономика
ходит сложение подходящих маршрутов
и объемов k видов продуктов с (k+1)ым продуктом, если это позволяет сделать оставшаяся вместимость транспортных средств, иначе этот продукт остается до выполнения следующей итерации.
Шаг 5. Расчет суммарного пробега транспортных средств и сравнение
с рекордным.
Шаг 6. Конец итерации. На выходе
имеем рекордную совокупность маршрутов, для звеньев в которых указаны
объемы поставки продуктов каждому
клиенту.
Шаг 7. Корректировка исходной
информации. Если количество нижних
итераций исчерпано, то переход на Шаг
1, иначе случайное изменение последовательности товаров и на Шаг 4.
4. Заключение
Для решения многопродуктовой
задачи маршрутизации в целом предложена двухуровневая метарэвристика
с разработанными алгоритмами «декомпозиции дерева» и «синтеза марш-
рутов». Предлагаемые в статье методы
и алгоритмы поиска рациональных
маршрутов транспортировки консолидированной продукции являются инвариантными к составу грузов и особенностям транспортных средств.
Литература
1.Бауэрсокс Д, Клосс Д. Логистика.
Интегрированная цепь поставок.
Logistical Management: The Integrated
Supply Chain Process / Пер. с англ. - М.:
ЗЛО «Олимп-Бизнес», 2006. - 640 с.
2. Лукинский В.С., Плетнева Н.Г.
Транспортная логистика: алгоритмы
многокритериального выбора маршрута перевозки // Вестник ИНЖЕКОНА.
Вып. 4(5).: СПбГИЭУ. 2004. С.156-162.
3. Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы / Пер. с англ. Нижний
Новгород: Изд-во Нижегородского госуниверситета им. Н.И. Лобачевского,
2004. 330 с.
4.Сигал И.Х., Иванова А.П. Введение
в прикладное дискретное программирование // М.: Физматлит. 2002. -237с.
Экономика, Статистика и Информатика
5. Ворисовский П.А., Еремеев А.В.
О сравнении некоторых эволюционных
алгоритмов // Автоматика и телемеханика. 2004. №3. С. 3-9.
References
1. Bauersoks D., Kloss D. Logistical
Management: The Integrated Supply
Chain Process /Translated from Eng. M.:
ZLO Olimp-Business , 2006. p.640.
2.
Lukinsky V.S., Pletneva N.G.
Transporting logistics: algorithms for
multi-criteria choice of transporting routes
// INGECONA collectin. Vol.4(5).:
SPbGIEU. 2004. pp. 156-162.
3.Hu T.CH., Shing M.T. Combinatorial
algorithms. / Translated from Eng.
Nihzniy Novgorod: Nihzegorodskiy State
University in the name of Lobachevsky
N.I., 2004. P. 330.
4.Sigal I.H., Ivanova A.P. Introduction
to applied discrete programming // M.:
Phizmatlit. 2002. P. 237.
5.
VorisovskiyP.A., Eremeev A.V.
About some evolutional algorithms
comparing. 2004. № 3. pp. 3 - 9.
63
№2, 2010
1/--страниц
Пожаловаться на содержимое документа