Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Задача VRP и подходы к её решению

1.1 Постановка задачи VRP

1.2 Точные методы решения задачи VRP

1.3 Эвристические алгоритмы, применимые в решении задач VRP

Глава 2. Анализ сетей распределения современных транспортных и дистрибьюторских компаний на примере ООО «АДМ»

2.1 Краткая характеристика ООО «АДМ»

2.2 Анализ эффективности существующих маршрутов автотранспортной доставки товаров ООО «АДМ» в Санкт-Петербурге и Ленинградской области

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

Глава 3. Анализ результатов планирования и предложение перспектив к улучшению процесса планирования грузоперевозок в ООО «АДМ» в г. Санкт-Петербург

3.1 Планирование грузоперевозок в ООО «АДМ» с помощью программы «Деловая Карта»

3.2 Планирование грузоперевозок в ООО «АДМ» с помощью программы «БИТ:УТЛ»

3.3 Разработка рекомендаций по внедрению АИС для планирования маршрутов автотранспортной доставки грузов в компании ООО «АДМ» в г. Санкт-Петербург

Заключение

Список использованных источников

Приложение



Введение

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

В связи с так называемой «проблемой последней мили» автомобильный транспорт играет в логистике грузоперевозок витальную роль - последнюю милю (километр) практически любой товар за редким исключением, проезжает на автомобиле в связи с тем, что данный транспорт является самым манёвренным наземным видом транспортировки. Именно поэтому так важно оптимизировать цепочку поставки в моменте последней мили, то есть при автомобильной доставке. Как правило, это мелкопартионная перевозка в условиях крупных городов или агломераций.

На настоящий момент самым распространённым решением для этого выступают ГИС - Географические Информационные Системы - они служат для ускорения и упрощения работ по маршрутизации транспортных средств (ТС). Как и другие распространённые информационные системы КИС-класса или более узконаправленные системы типа TMS, WMS, CRM и т.п., ГИС ставят перед собой цель оптимизировать оперируемый ими бизнес-процесс, благодаря автоматизации решения соответствующих задач с учётом имеющихся ограничений.

Поставленные множественные условия соблюдаются благодаря метаэвристическим алгоритмам, на принципах которых основаны алгоритмы вычислений ГИС, применяемый для решений задачи маршрутизации ТС (Vehicle Route Planning - VRP), являющейся более продвинутой версией задачи Коммивояжёра, в которой присутствует ряд дополнительных исходных параметров и ограничений.

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

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

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

Теоретические вопросы, связанные с транспортной и распределительной логистикой, задачами VRP были разработаны такими учёными как А.А. Бочкарёв, В.В. Дыбская, В.С. Лукинский, В.М Курейчик и другие. Среди иностранных учёных можно выделить Ж. Блантона, Б. Булленхаймера, Й. Матсуяму, B. Османа и прочих. Стоит отметить, что вопросы, связанные с выбором ГИС и их преимуществами над классическими методами маршрутизации с помощью решения задач линейного программирования рассмотрены в крайне малом объёме, что также прибавляет актуальности данной теме.

Целью данной работы является анализ современного состояния и перспектив развития географических информационных систем, предназначенных для планирования автотранспортной доставки грузов, и определение лучшего варианта ГИС для внедрения в компании ООО «АДМ» - Санкт-Петербург.

Данная цель будет достигнута по мере решения следующих задач:

? рассмотреть различные алгоритмы решения задачи VRP и математические алгоритмы планирования маршрутизации;

? проанализировать эффективность планирования доставок в ООО «АДМ» в г. Санкт-Петербург;

? определить наиболее оптимальные ГИС для внедрения в ООО «АДМ» в г. Санкт-Петербург;

? решить задачу VRP помощью предложенных вариантов ГИС и математических алгоритмов;

? сопоставить результаты работы эвристик и точных методов решения задачи VRP.

? разработать рекомендации по внедрению ГИС для ООО «АДМ» в Санкт-Петербурге.

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

Методологию исследования составили общенаучные методы: анализ, классификация, формализация, моделирование, в качестве эмпирического метода данного исследования можно выделить компьютерный эксперимент, связанный с изучением возможностей программ «Деловая карта», «БИТ: Управление Транспортной Логистикой» а также использованием программных продуктов STATISTICA и MS Excel.

Настоящая работа состоит из трёх глав. Первая глава содержит теорию о самой задаче VRP, её математической постановке и разновидностях, вариантах решения. Во второй главе будет представлена характеристика компании ООО «АДМ», проведён анализ эффективности планирования маршрутов доставки в данной компании. Соответственно, будет определены пути оптимизации планирования грузоперевозок в данной компании через автоматизацию процесса маршрутизации. Третья глава представлена расчётами практической задачи по с помощью различных ГИС и с помощью математических методов, сравнением полученных результатов и рекомендациями на основе полученных итогов с рекомендациями для ООО «АДМ» в Санкт-Петербурге.



Глава 1. Задача VRP и подходы к её решению

1.1 Постановка задачи VRP

Vehicle Route Planning - или сокращённо VRP - задача маршрутизации транспортных средств. Данная аббревиатура являет собой обозначение обширного класса задач, которые связаны с составлением маршрутов движения автопарка, базирующегося в одном или нескольких депо (или на одном или нескольких складах), для обслуживания определённого множества клиентов с разными географическими координатами. В основе данных задач лежит задача коммивояжёра. [26]

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

Основными вариантами задачи маршрутизации ТС принято считать:

ѕ CVRP - Capacitated VRP - Задача Маршрутизации ТС с Учётом Ограничений;

ѕ VRPTW - VRP with Time Windows - Задача Маршрутизации ТС с Временными Окнами. [13, 24]

Первый из вышепредставленных подходов был впервые предложен в 1959 году исследователями Данцигом и Рамсером, которые учли грузовместимость транспортных средств при планировании их маршрутов. Данный фактор позволил снизить количество используемых в целом транспортных средств и сократить общее расстояние порожнего пробега. В основном, модели решения данной задачи предполагают, что количество доступных транспортных средств не ограничено, и, соответственно, минимизируют количество используемого транспорта и (или) общую стоимость перевозки. Это не в полной мере соответствует реальному подходу к решению задачи маршрутизации, в которой заранее задано ограничение на максимально возможное количество используемых транспортных средств. [26, 30]

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

Статья «A Multi Objective Approach to solve Capacitated Vehicle Routing Problems with Time Windows Using Mixed Integer Linear Programming» из журнала International Journal of Advanced Science and Technology предлагает математическую модель решения задачи VRP, которая объединяет в себе оба представленных варианта. Данная модель, соответственно, имеет название CVRPTW - Capacitated Vehicle Routing Problem with Time Windows. Объединяя два наиболее актуальных подхода, он даёт синергетический эффект в плане актуальности для практического применения. Алгоритм предполагает, что спрос будет удовлетворён путём привязки каждого автомобиля к одному маршруту, составленному исходя из его грузовместимости и тех временных промежутков, в которые должны быть доставлены заказы клиентам. Целью алгоритма является нахождение кратчайшего пути доставки груза с минимизацией количества ТС и общих затрат на перевозку. [28]

Данная задача формулируется с помощью графа G(N,T), где N - количество клиентов и склад (депо), T - количество сетевых соединений между ними, задающиеся временем прохождения этих соединений. Математическая постановка задачи представлена формулами (1)-(11).

где - множество клиентов;

- множество всех узлов, включая склад (депо);

- парк автомобилей;

- равно 1, когда между узлами i и j есть соединение с использованием транспортного средства k, в противном случае принимает значение 0: , с , , ;

- момент времени, когда транспортное средство k прибывает в узел i, , .Предполагается, что - это момент начала отсчета, то есть когда транспортное средство k отправляется из депо или со склада;

- это время в пути из пункта i в пункт j, для всех транспортных средств, ;

- временное окно для клиента i, ;

- спрос на продукцию клиента i, ;

- ограничение мощности транспортного средства k, ;

T - постоянный параметр, который во временном окне полагается стремящимся к .

Склад или депо представлены узлами 0 и n+1. Все учитываемые транспортные средства отправляются из узла 0 и прибывают в узел n+1. Если какое-то транспортное средство прибывает в узел n+1, пройдя пустой маршрут, то есть не обходя ни одного клиента, принимается решение о нецелесообразности использования данного транспортного средства.

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

Далее указаны ограничения. Формула (2) ограничивает посещение каждого клиента одним автомобилем. Формулы (3), (5) и (6) дают гарантию того, что каждое транспортное средство покидает нулевой узел, по прибытии к первому клиенту отгружает только часть перевозимого груза, а затем отправляется к следующий узел, в конечном итоге оказываясь в узле n+1, который, по сути, тем же нулевым узлом. Формула (4) ограничивает на грузовместимость транспортного средства. Формула (7) ограничивает модель от появления подциклов. Формула (8) определяет зависимость между временем отправления ТС от предыдущего клиента к следующему и временем прибытия к следующему клиенту, а формула (9) ограничивает временные окна для каждого клиента. Формулы (10) и (11) устанавливают ограничения на переменные величины. [28]

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

ѕ DCCVRP - Distance-Constrainedand Capacitated VRP - Задача Маршрутизации с ограничениями на вместимость ТС и максимальную возможную дистанцию пробега;

ѕ VRPB - VRP with Backhauls - Задача Маршрутизации, включающая рассмотрение обратного хода доставки, во время которого у заказчиков забираются использованные ёмкости. На практике, актуальна, например, для компаний, занимающихся доставкой воды. [37]

Подходов к решению задачи VRP также множество. Как правило, прибегают к приближенным эвристическим алгоритмам. Для их применения необходимо наличие графа, в котором будут отражены точки доставки наряду со складами, или же матрицы расстояний. Среди ограничений не задаётся точное количество транспортных средств, но указываются максимально допустимые показатели грузоподъёмности и\или длины маршрута. [35]

Задачи VRP класса по своей сущности схожи с задачей Коммивояжёра, но в отличие от них, при решении VRP значительно труднее применять точные алгоритмы при наличии исходных данных с большим объёмом точек доставки. Также задачи VRP, в отличие от простой задачи Коммивояжёра, при одинаковых начальных условиях, имеют большее количество вариантов решения. [19, 36]

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

Также задачу VRP можно решать и точными методами - в сущности она представляет из себя последовательное решение задачи кластеризации методом k-средних (если необходимо разбить клиентов на группы), затем решается задача раскладки грузов по имеющимся транспортным средствам, и наконец задачу коммивояжёра для каждого из имеющихся ТС. [38]

Более развёрнуто данные методы будут рассмотрены в следующих подпунктах настоящей главы/



1.2 Точные методы решения задачи VRP

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

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

Самыми распространёнными и наиболее точными методами разбиения грузополучателей на группы являются методы кластерного анализа, реализованные в таких программных решениях как STATISTICA, SPSS или MATLAB. [6, 18]

В первых двух вышеперечисленных программах реализован наиболее популярный метод k-средних, являющийся наиболее популярным в данного вида расчётах. Этот итеративный метод был предложен исследователем Г. Штейнгаузом. [10, 45]

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

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

Также данная программа позволяет проделать субтрактивную кластеризацию согласно методу Р. Ягера. Этот метод кластеризации, основываясь на плотности точек вокруг, проверяет каждую заданную точку на соответствие статусу потенциального центра кластера, затем проверяя способность других точек, окружающих проверяемую, олицетворять собой центр будущего кластера. После нахождения второй точки, которая может являться центром кластера, все точки, что находятся на определённом расстоянии от центра предыдущего вычисленного кластера, отсекаются в отдельный кластер и далее не анализируются. Этот процесс будет происходить до тех пор, пока все исходные точки не будут рассмотрены. Данный метод кластеризации применяется в тех случаях, когда нет единого верного предположения о центрах будущих кластеров. [10]

Если имеется достаточно обширная сеть доставки, включающая, возможно, не один склад, можно также с помощью программных средств воспользоваться методом дерева иерархии ради определения связи между точками доставки и выделения их в отдельные кластеры исходя из расстояний между ними. [10, 18, 32]

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



где сi,j- стоимость обслуживания i-го клиента j-ым автомобилем;

M - множество имеющихся грузополучателей равное [1;m];

N - множество имеющихся автомобилей равное [1;n];

xi,j - переменная, принимающая значение 1, если автомобиль используется и 0, если не используется для осуществления развозки грузов;

di - количество имеющегося груза;

qj - грузоподъёмность j-го автомобиля;

L - максимальное число клиентов в каждом рейсе.

Переменная L вводится для того, чтобы, по сути, установить ограничения на время работы транспорта, поскольку введение дополнительных формул, ограничивающих именно время рабочего дня значительно усложнило бы задачу. Таким образом, предполагается, что время движение от одного клиента к другому примерно одинаково, равно как и время погрузки каждого груза и их разгрузки. [6]

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

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

dij=|xi-xj|+|yi-yj|

где x и y - координаты точек;

d - расстояние между ними.

Сама же задача математически может быть представлена в виде формул (18)-(23). Графически она представлена на рисунке 1.

где li,j - расстояние между пунктами i и j;

xi,j = 1, если рассматриваемый участок является звеном выбранного маршрута, иначе xi,j = 0;

Ограничения, вводимые переменными ui и uj нужны для того, чтобы цикл xij был полным, то есть состоял из определённого задачей количества пунктов и путей между ними. [11]

Рисунок 1 - Графическое представление задачи коммивояжёра [11]

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

1.3 Эвристические алгоритмы, применимые в решении задач VRP

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

Задачи VRP также требуют предварительной кластеризации начальных условий в случае, если точек, из которых осуществляется доставка, несколько. Поскольку эвристики реализованы в программных продуктах, чаще всего прибегают к кластеризации по принципу здравого смысла, деля зоны прямо в ГИС по границам районов, микрорайонов, городов и областей. Однако, данный метод не является оптимизационным, поскольку он не гарантирует минимизации затрат. [6, 7, 35]

На сегодняшний день существуют три основных класса алгоритмов, применяемых для решения задач VRP:

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

ѕ кластерные - разбивают поставленную задачу на этап кластеризации точек доставки и этап решения задачи коммивояжёра для каждого полученного случая;

ѕ улучшающие - ведущие поиск решения с последующими попытками перетасовки вершин в каждом маршруте. [21, 35]

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

ѕ генетический алгоритм;

ѕ поиск с исключениями;

ѕ имитируемый отжиг (а также, имитируемы отжиг с детерминированным механизмом);

ѕ нейронные сети;

ѕ алгоритм на основе муравьиных колоний.

Самыми распространёнными являются эволюционные и генетические метаэвристические алгоритмы, построенные на примере происходящих в природе процессах отбора, наследования и мутаций. Эти алгоритмы являются представителям класса эволюционных вычислений. [12, 13, 29, 35]

В 1964 году учёные Рехенберг и Ганс-Пол предложили алгоритм эволюционных стратегий для решения сложных математических задач. В данном виде алгоритмов потомки в основном создаются посредством мутаций. Такие алгоритмы широко применяются к решению задач CVRP на этапах размещения грузов внутри ТС и выбора упаковки. [31]

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

Генетические алгоритмы являются самым распространённым вариантом решения транспортным задач используемым ныне. Но также стоит отметить, что данный алгоритм может применяться к достаточно большому кругу задач, поскольку не подразумевает наличие обширных знаний в предметной области нахождения решаемой задачи. Поэтому часто такого вида алгоритмы используют для решения задач, в ходе решения которых специализированные модели и методы не выдают удовлетворяющих результатов, даже в тех случаях, когда сами задачи плохо структурированы. [4, 13, 40]

Разработки и текущие исследования в области применения генетических алгоритмов имеют достаточно большой потенциал для создания оперативных методов решения задач класса VRP. Самые распространённые варианты применения данного алгоритма, подтверждающее это, - многочисленные методы решения задач VRPTWи CVRP. [3, 40]

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

В начале алгоритм генерирует случайным образом случайную популяцию хромосом P1={x11,…,xn1}. В VRP-задачах этой популяцией являются вершины графа исходных данных, при этом по условию последняя и первая вершины в цепочке хромосом будут сомкнуты. После этого на каждой итерации t = {1,2,…,T} k раз выполняется последовательность действий:

1. Выбор двух родительских хромосом (вероятностно наилучших вариантов) из Pt;

2. Порождение при помощи оператора скрещивания двух потомков на основе выбранных хромосом;

3. Выполнение операции мутации для каждого потомка;

4. Создание набора Pt+1, которое проводится через замену 2k наихудших решений в Pt2k новых потомков.

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

Результатом решения данной задачи будет являться наиболее оптимальное решение полученное за T итераций («поколений скрещивания»). [13]

Генетические алгоритмы также используются для решения задачи коммивояжёра. Но поскольку в VRP предполагается много маршрутов-решений задачи, в ответе будет многократно встречаться нулевой узел - склад или депо, который и будет служить разделителем между двумя разными предлагаемыми вариантами маршрутов. [19]

На примере задачи коммивояжёра можно объяснить принцип работы генетических алгоритмов, ведь она по сути является сильно упрощённым вариантом задачи VRP - исходные данные также можно представить в виде графа, коммивояжёр также не может проезжать через одну и ту же точку дважды и должен двигаться кратчайшим путём, минимизируя свои транспортные расходы. [13, 27]

В данном случае, задачу можно представить в виде формул (24)-(26). Стоит отметить, что в генетических алгоритмах оператором Fitness обозначается целевое значение функции. Формулы (12) и (13) служат дополнительными ограничениями, на случай, если граф не является полным. Они учитываются путём проставления метки бесконечности в незаполненные ячейки матрицы затрат - вместо информации об отсутствующих рёбрах.

где R(i, j) - матрица затрат при перемещениях по дугам графа;

ц - искомая перестановка элементов графа;

U - множество рёбер графа.

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

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

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

1. выбор точки разрыва для каждой пары хромосом;

2. сравнение частичной сходимости путей, ведущих из хромосом-родителей, и выбор кратчайших;

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

4. если образовался цикл, выбор другого пути;

5. повторение пунктов 2 и 3 до тех пор, пока не будет составлен гамильтонов цикл с минимальным суммарным весом рёбер.

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

Полученный результат обычно представляют либо в виде последовательности рёбер графа, либо в виде последовательности его вершин, то есть путей или точек, которые проходит коммивояжёр. Более распространённым является второй вариант в связи с его большей наглядностью и простотой восприятия. Также часто исход задачи представляется в матричном виде. В верхней строке и крайнем левом столбце находятся порядковые номера или названия точек, через которые проходит коммивояжёр, а единица на пересечении i-ой строки и j-го столбца означает, что коммивояжёр направляется по маршруту из i-го пункта в j-й. [13, 40]

Нейронные сети являются уже самообучающимися алгоритмами, в которых весовые коэффициенты будут подбираться до тех пор, пока не будет найдено удовлетворяющее решение. Они берут своё название из сходства с человеческим мозгом, поскольку также состоят из элементов, связанных множеством соединений. Изначально предполагалось использовать данные алгоритмы в моделировании задач, тем или иным образом связанных с человеческим интеллектом, но учёный Дж. Хопфилд впоследствии предложил применять данные алгоритмы в комбинаторике. [31, 33]

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

Классический метод нейронных сетей, первоначально применявшийся в области логистики в решении задачи Коммивояжёра, не давал таких точных результатов, насколько это требовалось. Это породило исследования в данной области, которые привели к появлению метода Самоорганизующейся карты и метода Эластичных сетей. [27, 31, 39]

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

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

На данный момент исследователи применяют следующий алгоритм для решения задачи CVRP:

1. Пока присутствуют исходные элементы самоорганизующейся карты:

1.1. обработка вершины и перемещение к следующей;

1.2. установка очередной выбранной вершины как текущей;

1.3. установка вероятности выборки каждого кольца;

1.4. выбор кольца в соответствии с установленной вероятностью;

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

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

С получением алгоритмом знаний об исследуемом графе постоянно изменяется вероятность выбора кольца. Изначально преимущественным значением обладает расстояние между текущей вершиной и выбранным элементом на кольце, но в ходе решения всё большее влияние оказывают ограничения грузоподъёмности для наиболее точного выбора следующей вершины. Как следствие, кольцам с каждым шагом становится всё сложнее приспособиться к вершинам графа и конечная выборка состоит только из тех колец, что не нарушают ограничений. [33, 39]

Часто этот способ сравнивается с поиском с исключениями, который основывается на оценочной функции, которая характеризует потенциальный шаг с учётом данных значений и ограничений целевой функции, а на каждом шаге выбирается решение, максимизируете оценочную функцию. То есть алгоритм последовательно идёт от x1 до xn, выбирая вариант xt+1 из окрестности N(xt) до тех пор, пока не выполнится условие остановки алгоритма.

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

ѕ запрещающей (задаёт список исключений)

ѕ освобождающей (задаёт, что необходимо удалять из списка исключений) [29, 32, 35]

Ещё один алгоритм, похожий на алгоритм нейронных сетей - алгоритм муравьиных колоний, имитирующий процесс поиска пищи муравьями. Значение его целевой функции сравним с показателем оценки качества пищи муравьём. [16]

Согласно формуле (27) данный алгоритм можно применить для решения задачи коммивояжёра. У каждой дуги (vi;vj) данного графа есть два присвоенных ей параметра: nij - видимость дуги, обратно пропорциональная её длине и Гij- след феромонов, постоянно меняющийся в течение работы алгоритма.

Гij=Гij+

где Гij - след феромонов, количество которых определяют важность дуги (vi;vj);

- коэффициент испарения феромонов, принимающий значения [0;1]. В конце каждой итерации из старого значения феромонов из их предыдущего значения отнимается величина (1-);

N - количество муравьёв

Lk - длина построенного муравьём k пути при условии использования им дуги (vi;vj);

Часто, но не всегда, данный метод даёт достойные результаты, хотя всё же не может сравниться с другими метаэвристическими алгоритмами, если не совмещать его применение с дополнительными методами локальной оптимизации. [16, 25]

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



Глава 2. Анализ сетей распределения современных транспортных и дистрибьюторских компаний на примере ООО «АДМ»

2.1 Краткая характеристика ООО «АДМ»

Рассмотрим распределительную сеть крупной компании федерального уровня на примере ООО «АДМ».

Компания «АДМ» является дистрибьютором канцелярских, хозяйственных и строительных товаров - в основном, упаковочных и укрепляющих материалов, таких как различного рода плёнки, пакеты, армирующие строительные товары и т.п. На настоящий момент ассортимент продаваемой продукции насчитывает более 11 категорий товаров и более 60 наименований.

Рассматриваемая компания представлена на рынке уже более 20 лет и является одним из лидеров рынка производства и поставки упаковочных материалов. Головной офис компании располагается в г. Санкт-Петербурге.

Компания «АДМ» при работе с клиентами использует индивидуальный подход к каждому и выделяет своими ценностями следующие аспекты:

ѕ Современное высокотехнологичное оборудование;

ѕ Квалифицированный персонал и качественное обслуживание;

ѕ Экологичное и безопасное сырье.

Доставка осуществляется из распределительных центров в Санкт-Петербурге и Москве, а также из 14 региональных складов, куда товары приходят из РЦ. В свою очередь, распределительные центры снабжаются из портов г. Санкт-Петербург и г. Владивосток в соотношении 90\10. На рисунке 2 представлена карта, отражающая географическое положение сети распределения компании «АДМ», а в таблице 1 - прикрепление региональных складов к соответствующим распределительным центрам.

Города Москва и Санкт-Петербург с соответствующими областями являются основными потребителями товаров АДМ с суммарным спросом 51% (38% - Москва и Московская область, 13% - Санкт-Петербург и Ленинградская Область). Зелёным цветом на рисунке 2 отмечены региональные склады, обеспечивающие удовлетворение спроса в местах, где он превышает 2,2% от суммарного, оранжевым цветом - удовлетворяющие не более 0,4% спроса.

Рисунок 2 - Карта сети распределения ООО «АДМ»

Таблица 1 - Закрепление филиальных складов за распределительными центрами ООО «АДМ»

Распределительный центр	Снабжаемые склады
Москва	Волгоград
	Воронеж
	Казань
	Краснодар
	Нижний Новгород
	Ростов-на-Дону
	Самара
	Уфа
Распределительный центр	Снабжаемые склады
Санкт-Петербург	Киров
	Красноярск
	Мурманск
	Новосибирск
	Омск
	Пермь

Компания «АДМ» предлагает для своих клиентов следующие логистические возможности:

ѕ выбор оптимальной схемы доставки товара до клиента;

ѕ отсутствие ограничений на вес и объем грузов;

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

ѕ доставка грузов «от двери до двери»;

ѕ прием/выдача груза, как по количеству, так и по наименованию;

ѕ экспедирование и контроль груза в пути;

ѕ оформление товарно-транспортной документации;

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

Компания осуществляет три вида перевозок:

ѕ местная развозка грузов - внутригородские и внутриобластные перевозки мелкопартионных грузов из региональных складов. Также к этому виду перевозок относятся междугородние перевозки в случаях, когда клиенты находятся в другом субъекте федерации нежели склад, с которого осуществляется доставка;

ѕ междугородние перевозки мелкопартионных грузов из распределительных центров клиентам разбросанным по различным субъектам РФ и находящимся в странах ближнего зарубежья;

ѕ межтерминальные перевозки укрупнённых партий грузов в региональные склады из распределительных центров Москвы и Санкт-Петербурга.

ООО «АДМ» контролирует достаточно большую долю рынка сбыта подобной продукции в Санкт-Петербурге и Ленинградской области. Клиенты компании - в большинстве своём розничные продавцы: супер- и гипермаркеты, профильные торговые сети.

Заказы вне зависимости от их веса и количества доставляются в розничные сети на европаллетах, напрямую розничным клиентам - в картонных коробках. Загрузка на складах начинается в 7:00 утра и может вестись одновременно на 10 среднетоннажных автомобилей. Как правило, погрузка осуществляется 20-30 минут, в зависимости от объёма перевозимого груза. Доставка осуществляется до 15:00 - в это время автомобили должны прибыть обратно в депо. Норматив для разгрузки на каждой точке доставки - 20 минут. Фактически, зачастую это время может быть превышено в случае большого размера заказа, но поскольку не все заказы доставляются розничным ритейлерам, то в целом время доставки не выходит за рамки установленных нормативом 8 часов.

В пределах Российской Федерации компания обслуживает 79 из 85 регионов. Согласно корпоративным стандартам обслуживание большинства регионов, а равно и потребителей в них, не должно превышать двухдневного срока, исключение составляют только самые отдалённые регионы России (север Сибири, Дальний Восток), а также Казахстан, для которых этот срок может увеличиваться до 7 дней. [46]

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



2.2 Анализ эффективности существующих маршрутов автотранспортной доставки товаров ООО «АДМ» в Санкт-Петербурге и Ленинградской области

Для понимания нынешнего состояния функционирования отдела доставки ООО «АДМ», проведём анализ эффективности существующих маршрутов доставки грузов в Санкт-Петербург и Ленинградскую Область по данным за октябрь 2015 года, предоставленным Санкт-Петербургским филиалом ООО «АДМ».

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

Сразу стоит отметить, что автотранспортная доставка по Санкт-Петербургу имеет определённые особенности:

1) большие расстояния между точками доставки. Например, при доставке в пригороды, являющиеся частью городской агломерации, точки доставки на одном маршруте могут располагаться на расстояниях в 10-20 км. В то же время невозможно объединить большое количество мелкопартионных заказов в связи с большим расстоянием между ними и пробками, особенно в центре города;

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

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

Проанализированные данные по показателям суммарного веса заказа, количества заказов, количества маршрутов, среднему количеству заказов на один маршрут, среднему весу заказа и средней загрузке ТС на маршруте представлены в таблицах 2-7.

Таблица 2 - Суммарный вес заказов, тонн

День Неделя	ПН	ВТ	СР	ЧТ	ПТ	СБ	ВС
1 неделя				35,657	26,562	0,000	0,000
2 неделя	22,225	31,155	29,684	33,238	30,085	6,634	0,000
3 неделя	37,631	26,545	41,116	41,125	36,259	0,000	0,000
4 неделя	31,225	38,678	32,821	41,711	43,501	8,751	0,000
5 неделя	42,614	35,040	49,465	68,600	71,041	4,036

Таблица 3 - Количество заказов, единиц

День Неделя	ПН	ВТ	СР	ЧТ	ПТ	СБ	ВС
1 неделя				116	114	0	0
2 неделя	154	110	136	121	141	27	0
3 неделя	193	113	139	132	129	0	0
4 неделя	210	106	116	164	165	14	0
5 неделя	204	129	163	229	226	29

Таблица 4 - Количество маршрутов, единиц

День Неделя	ПН	ВТ	СР	ЧТ	ПТ	СБ	ВС
1 неделя				14	12	0	0
2 неделя	14	15	15	14	17	1	0
3 неделя	15	12	15	13	14	0	0
4 неделя	15	17	14	15	15	1	0
5 неделя	18	15	19	17	18	2

Таблица 5 - Среднее количество заказов на один маршрут, единиц

День Неделя	ПН	ВТ	СР	ЧТ	ПТ	СБ	ВС
1 неделя				8,29	9,50	0,00	0,00
2 неделя	11,00	7,33	9,07	8,64	8,29	27,00	0,00
3 неделя	12,87	9,42	9,27	10,15	9,21	0,00	0,00
4 неделя	14,00	6,24	8,29	10,93	11,00	14,00	0,00
5 неделя	11,33	8,60	8,58	13,47	12,56	14,50

Таблица 6 - Средний вес одного заказа, кг

День Неделя	ПН	ВТ	СР	ЧТ	ПТ	СБ	ВС
1 неделя				0,307	0,233	0,000	0,000
2 неделя	0,144	0,283	0,218	0,275	213,369	245,704	0,000
3 неделя	194,979	234,912	295,799	311,553	281,078	0,000	0,000
4 неделя	148,690	364,887	282,940	254,335	263,642	625,071	0,000
5 неделя	208,892	271,628	303,466	299,563	314,341	139,172

Таблица 7 - Средняя загрузка ТС на маршруте, кг

День Неделя	ПН	ВТ	СР	ЧТ	ПТ	СБ	ВС
1 неделя				2546,929	2213,500	0,000	0,000
2 неделя	1587,500	2077,000	1978,933	2374,143	1769,706	6634,000	0,000
3 неделя	2508,733	2212,083	2741,067	3163,462	2589,929	0,000	0,000
4 неделя	2081,667	2275,176	2344,357	2780,733	2900,067	8751,000	0,000
5 неделя	2367,444	2336,000	2603,421	4035,294	3946,722	2018,000

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

Что же касается максимально и минимально загруженных дней, в их определении наблюдается стохастичность - по каждому из проанализированных параметров максимально и минимально загруженные дни варьируются. По количеству заказов в день - пиковой нагрузкой обладает понедельник со средним числом заказов в 190,25 в день, что примерно в 1,5 раза больше, чем в остальные будние дни в среднем, и почти в 14 раз больше, чем в субботу (см. рисунок 4). Такая ситуация может свидетельствовать о возможном факте переноса заявок, полученных в субботу и воскресенье на понедельник.

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

Рисунок 3 - Среднее количество заказов на один маршрут по дням недели, ед.

С другой стороны, возможно, что на воскресенье доставка продукции ООО «АДМ» не заказывается. Но это маловероятно, потому что компания работает во многом со строительными материалами, которые могут понадобиться в любой день недели. Хотя данное предположение может поддерживаться избирательностью работы по-субботам - на две из пяти в месяце не приходилось ни одой доставки, хотя по показателю среднего веса заказа - суббота показывает результат выше среднего (см. рисунок 5) и наивысший показатель средней загрузки одного маршрута в день, превышая аналогичные показатели будних зачастую почти в 1,5 раза.

Рисунок 4 - Среднее количество заказов и маршрутов по дням недели, ед.

Отдельно можно отметить показатель среднего суммарного веса заказов по дням недели (см. рисунок 6). По графику данного показателя видно, что заказы с выходных развозятся в понедельник, а далее идёт накопление тоннажа вплоть до четверга. Это может свидетельствовать об опозданиях в оформлении заявок. Подтверждается эта мысль тем, что количество заявок растёт непрерывно, не падая в пятницу, что видно на рисунке 4, в отличие от их суммарного веса. Вероятно, опоздания связаны с применением ручного планирования и отсутствием автоматизации при маршрутизации доставок.



Рисунок 5 - Средняя загрузка ТС на маршруте и средний вес одного заказа по дням недели, кг

В целом, анализ маршрутов автотранспортной доставки грузов ООО «АДМ» отличается неравномерностью объёмов доставок в разные дни недели, что, естественно, может приводить к нерациональной загрузке используемых транспортных средств. Средняя загрузка ТС на маршруте за обозреваемый период находится в рамках 1587,5 кг - 8751 кг. Известно, что компания имеет в своём распоряжении транспорт трёх видов - ГАЗ 3301, ГАЗ 52 и ГАЗ 3307. Грузоподъёмность последнего - 4,5 тонны, а это значит, что компания была вынуждена нанимать транспорт для перевозки особо крупных грузов, и за месяц такое происходило два раза, и это происходило в случае маятниковой доставки. А значит, имеют место также либо существенные перегрузы, что негативно сказывается на состоянии автопарка, и соответственно, потенцирует увеличение затрат на его содержание, либо простои автопарка в связи с аутсорсинговой деятельностью.



Рисунок 6 - Среднее количество суммарного веса заказа по дням недели, кг

Также данные показывают, что компания имеет проблемы в использовании грузоподъёмности используемого транспорта, рассчитываемому по формуле 27. В особенности при использовании транспорта с наибольшей грузоподъёмностью - среднее значение этого показателя равно 0,66, при условии, что для всех доставок с суммарным весом выше 2,5 тонн использовался только имеющийся в распоряжении компании транспорт и отсутствовали перегрузы, в противном случае данный коэффициент может быть ещё меньше. [15]

Также, как видно из анализа, за месяц было только три дня, в которые средняя загрузка ТС превышала 1500 кг менее чем на 500 кг, а значит, несмотря на сложность измерения конкретно показателя используемости грузоподъёмности, можно с уверенностью сказать, что имеющийся в распоряжении компании транспорт, представленный автомобилями типа ГАЗ 3301 невысок, что также может негативно сказываться на экономических показателях предприятия.



,

где - фактический объём перевозок

- возможный объём перевозок

Если рассматривать дни, в которые средняя загрузка транспортного средства на маршруте была выше 2500 кг, но ниже 4500 кг, то в данном случае, если принять за 100% возможной грузоподъёмности 4,5 тонны, то вышепредставленный коэффициент равен в среднем 0,85, что является хорошим показателем. С другой стороны, минимальное значение данного показателя составляет 0,64, что может служить основанием предполагать, что в компании прибегают к использованию более крупнотоннажного транспорта на аутсорсинге.

Таким образом, можно судить о достаточно неудовлетворительной загрузке ТС, используемых компанией, вследствие чего ООО «АДМ» несёт зачастую неоправданно высокие затраты.

Неопределённость и неравномерность результатов анализа в целом даёт основания судить о неоптимизированности управлением транспортировкой в компании. В качестве средства оптимизации предлагается внедрить на предприятии Географическую Информационную Систему (ГИС), для использования в ходе организации доставки мелкопартионных грузов в городах.

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

...