Задача поиска оптимального плана доставки продукции торгового предприятия

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

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

Задача поиска оптимального плана доставки продукции торгового предприятия

Выпускная квалификационная работа - БАКАЛАВРСКАЯ РАБОТА

по направлению подготовки 38.03.01 Экономика

Пермь 2016

Аннотация

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

В исследовании анализируется как детерминированная, так и стохастическая ЗМТ на примере оптимизации маршрутов водителей торговой фирмы ООО «Фабрика еды», находящейся в городе Пермь. В работе используются современные эвристические методы решения задачи, рассматривается механизм пересчета маршрутов водителей (позиционное управление логистикой), а также проводится сценарный анализ дорожных пробок в г. Пермь. Одним из практических результатов исследования является сокращение транспортных расходов компании на 25 - 35 тыс. рублей в месяц, что составляет 15 % от суммарных транспортных затрат.

How can a firm optimize routes for drivers with satisfaction of customers' constraints and cost minimization? The answer to this question is the solution of the vehicle routing problem (VRP), which aims to find the shortest time route for drivers through all clients. The study examines both deterministic and stochastic VRP on the example of optimizing drivers' routes for commercial firm Fabrika Edy Ltd., located in the city Perm. In the research we use modern heuristics for solving vehicle routing problems. Moreover, we apply mechanism of route transformation (positional logistic management) and scenario analysis of traffic congestion in the city Perm. One of the vital results of the study is the reduction of company's transportation costs by 25 - 35 thousand rubles per month, which is equal to 15 % of total transportation costs.

Оглавление

Введение

1. Теоретическое обоснование

2. Постановка исследовательской проблемы

3. Данные и методология

4. Описание результатов

Заключение

Список литературы

Приложения

Введение

С точки зрения экономической теории, понятие транспортной логистики рассматривается как планирование оптимальных маршрутов грузоперевозок с минимизацией затрат, что является особенно актуальным для торговых компаний, ежедневно доставляющих продукцию покупателям. В связи с растущей загруженностью автомобильных дорог, водители предприятий часто опаздывают в установленные временные интервалы доставки, что приводит к возвратам продукции, росту неудовлетворенности клиентов, и, в конечном счете, к потерям выручки и убыткам. Существует ряд моделей, применив которые, фирма может существенно сократить транспортные расходы и оптимизировать последовательность посещения контрагентов. Одна из них - классическая задача коммивояжера (КЗК), решением которой является кратчайший замкнутый маршрут водителя, проходящий через всех покупателей по одному разу. Задача была поставлена английскими математиками У. Гамильтоном и Т. Киркманом в середине ХIХ века. В течение последующих десятилетий ученые из разных стран изучали КЗК, разрабатывая новые математические постановки задачи и алгоритмы их решения. Так появились точные и приближенные методы достижения оптимальных маршрутов (Бронштейн, Заико, 2010). К точным методам относятся алгоритм полного перебора и метод ветвей и границ, а к приближенным (позволяют найти маршрут близкий к точному решению задачи) - метод имитации отжига, алгоритм муравьиной колонии и др.

Несмотря на популярность классической задачи коммивояжера, она редко решается на практике, поскольку ее ограничения не учитывают, например, маршрутизацию нескольких машин в автопарке компании, пробки на дорогах и временные интервалы доставки покупателям. Желая приблизить теоретическую задачу к реальности, Данциг и Рамсер, предложили разновидность КЗК, включив в нее ограничение на количество автомобилей и назвав ее - задачей маршрутизации транспорта (ЗМТ) (Danzig,

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

В настоящем исследовании рассматривается одна из областей применения задачи маршрутизации транспорта - логистика. В работе осуществляется поиск решения ЗМТ на примере пермской торговой фирмы ООО «Фабрика еды», занимающейся оптовой торговлей мясопродуктами. Компания имеет двух водителей, отвечающих за доставку продукции контрагентам. Летом 2015 года у предприятия возникли трудности с развозом продукции покупателям: в связи с увеличивающимся количеством заявок, водители часто опаздывали в желаемое время поставки, установленное покупателями, за что были оштрафованы возвратом продукции в полном размере. Общие непредвиденные транспортные расходы по вине двух водителей составляли от 25 до 35 тыс. в месяц, что послужило причиной поиска их минимизации. В исследовании предполагается, что решив задачу маршрутизации транспорта, торговая компания сократит свои логистические расходы. Отметим, что в работе рассматривается модифицированная ЗМТ, которая учитывает специфику бизнеса: в задачу добавляется ограничение на грузоподъемность транспортных средств, а также два условия, устанавливающие временные окна покупателей. Описываемая задача анализируется на реальных данных торговой компании (рассматривается день с 51 покупателем). ЗМТ решается современными математическими алгоритмами: муравьиным методом и алгоритмом поиска с запретами. Применяемые методы являются эвристическими (приближенными) способами нахождения оптимального решения задачи.

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

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

Задачами работы являются:

1) Анализ предметной области исследования;

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

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

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

5) Сбор данных, необходимых для математического моделирования;

6) Применение ряда методов в современных программных пакетах (Умные маршруты, Муравьиная логистика) на данных компании;

7) Формирование маршрутов развоза продукции водителями фирмы ООО «Фабрика еды» с учетом временных ограничений покупателей и грузоподъемности автомобилей;

8) Оценка и анализ полученных результатов.

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

Выпускная квалификационная работа состоит из введения, четырех разделов, заключения и списка литературы. В первом разделе подробно рассматривается ряд существующих работ по исследуемой теме. Теоретическое обоснование структурно разделено на две части: первая часть посвящена классической задаче коммивояжера, а вторая - задаче маршрутизации транспорта с временными окнами и ограничением на грузоподъемность автомобилей (capacitated vehicle routing problem with time windows - CVRPTW). Отметим, что последняя задача является обобщением первой, следовательно, необходимо провести как совместный, так и сепаратный анализ двух задач. Второй раздел, описывает предметную область (компанию), ограничения и предпосылки, возникающие в ходе моделирования. Рассматривается математическая постановка исследуемой задачи. В третьем разделе подробно описываются используемые данные и алгоритмы решения задачи. Также в третьей части проводится сравнительный анализ основных методов решения по ряду критериев. Большое внимание уделяется муравьиному методу и алгоритму «поиска с запретами». Последний раздел подразумевает обсуждение основных результатов исследования. В данной части работы в программных пакетах реализуются математические методы нахождения оптимальных маршрутов водителей торгового предприятия, строятся сетевые модели планирования и управления, проводится пересчет маршрутов в случае непредвиденных дорожных ситуаций, а также решается классическая задача об оптимальной загрузке автомобиля. Полученные результаты обобщаются в виде выводов, а также даются рекомендации по практическому применению моделей и внедрению их в компании.

1. Теоретическое обоснование

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

Начнем с подробного описания и изучения классической задачи коммивояжера - КЗК («задача странствующего торговца»), поскольку не проанализировав данную задачу, понять более сложную ее модификацию не представляется возможным (Макконнелл, 2004). Отметим, что КЗК представляет собой одну из самых известных математических задач XX века. С экономической точки зрения решением задачи является самый выгодный маршрут, проходящий через указанные города (точки на карте) по одному разу, с возвращением в исходный. В условиях данной задачи традиционно указываются какие-либо критерии оптимальности (наименьшее расстояние или время). Говоря об актуальности исследования задачи, которая появилась в середине ХVIII века, подчеркнем, что с 1959 по 2008 годы около 1 000 научных журналов публиковали статьи про задачу коммивояжера на первых страницах. Более того, научная литература на тему КЗК растет экспоненциально каждый год со скоростью 6% (Baldacci, et al., 2012).

Представим классическую задачу коммивояжера в виде модели на графе. Пусть имеется ориентированный конечный граф в котором N - множество вершин, А - множество ребер (Хайруллин, 2014). Тогда длина ребра будет являться его весом и будет связывать вершины . Граф должен быть полным, поскольку необходимо учесть все возможные ребра. Таким образом, решение задачи коммивояжера - это такой маршрут, который является ориентированным полным остовным циклом (проходит через все вершины) минимального веса (сумма всех расстояний между вершинами) в графовой модели. Предполагается, что переменная является бинарной, то есть принимает значение 1, если ребро графа включено в оптимальный маршрут, проделанный коммивояжером, и 0, если не включено.

Математическая постановка классической задачи коммивояжера выглядит следующим образом:

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

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

Приведем наиболее значимые работы о КЗК расположив их в хронологическом порядке. Первым упоминанием о классической задаче коммивояжера (traveling salesman problem - TSP) стали труды английских математиков У. Гамильтона и Т. Киркмана в середине ХIХ века

(Laporte, 1992). В то время авторы не имели необходимых методов для решения задачи и могли сформулировать только вид предполагаемого решения - маршрут коммивояжера, проходящий через каждый город только один раз (необходимо объехать все города без исключения). Описываемый путь торговца получил название гамильтонов цикл. С развитием такого направления науки как комбинаторная оптимизация, исследователи стали придавать задаче коммивояжера теоретический смысл. На основе КЗК были разработаны такие известные методы дискретной оптимизации, как «жадный» алгоритм, метод ветвей и границ, а также ряд современных эвристик (Moon, et al., 2012). Спустя столетие после постановки классической задачи коммивояжера, ее решением занялись американские сотрудники RAND Corporation, в том числе, Д. Фалкерсон. Применив метод ветвей и границ, ученый нашел маршрут для 21 города США и доказал его оптимальность (Toth, Vigo, 2002). В середине 70-х годов ХХ века КЗК активно применялась в биологии, информатике и медицине. Через два десятилетия Д. Апплегейт и У. Кук создали «библиотеку» стандартизированных постановок и модификаций классической задачи коммивояжера - TSPLIB, куда вошли экземпляры, содержащие более 10 000 точек на карте (Applegate, Cook, 1993). В середине 2010 года европейские математики решили КЗК, включающую тысячу вершин. Используя методы кластеризации, удалось доказать, что полученное решение всего на 1% отличается от оптимального (Schneider, et al., 2010).

По данным электронных библиотек, в научной литературе существует более 6 000 исследований, связанных с задачей коммивояжера. Рассмотрим наиболее значимые из них. Кроуз в 1958 году в своей работе продемонстрировал несколько возможных способов упрощения вычислительной сложности задачи (Croes, 1958). Один из них - использование неориентированного графа при построении модели (матрица расстояний - симметрична). Математик обосновал, что симметричную КЗК решать значительно легче по сравнению с асимметричной. Автор показал на практике, что задача с неориентированными дугами графа на практике становится менее реалистичной. Более того, ученый считал, что для упрощения процедуры нахождения оптимального решения, необходимо использовать только линейные условия, добавляя в постановку ограничение элиминирующее подциклы в маршруте коммивояжера (Croes, 1958). Заметим, что преследуя цель нахождения оптимального решения КЗК, на первой итерации необходимо получить допустимое решение. Впоследствии, итеративное улучшение решения, путем ряда перестановок в исходной последовательности городов, приведет к образованию наилучшего решения задачи. Рассмотрим другую немаловажную работу, посвященную решению классической задачи коммивояжера. Лин в 1973 году впервые проанализировал простейший эвристический алгоритм нахождения решения КЗК - «жадный» метод. Автор исследовал вычислительное время задачи и продемонстрировал, что «жадный» алгоритм способен его существенно сократить (Lin, Kernighan, 1973). Подчеркнем, что решение, получаемое в ходе использования «жадного» алгоритма не всегда будет оптимальным, а значит, необходимы дополнительные перестановки в полученной последовательности городов. Переходя к современным статьям о КЗК, отметим, что несмотря на развитие эвристических алгоритмов, многие ученые на протяжении XX века продолжали решать задачу точными методами. Многие ученые были убеждены, что задачу коммивояжера необходимо решать методом ветвей и границ. Заметим, что описываемый алгоритм был популярен в научном сообществе и положил начало большому количеству статей, реализующих его на разном количестве городов (вершин на графе). Метод заключался в разделении множества маршрутов на подмножества, в каждом из которых производился поиск «нижней границы»- кратчайшего маршрута в подмножестве. Наилучший маршрут соединялся из всех «нижних границ» подмножеств (Toth, Vigo, 2002). Осознав необходимость применения задачи на практике, только к концу ХХ века ученые стали решать классическую задачу коммивояжера при помощи приближенных алгоритмов, таких как: алгоритм минимального остовного дерева, локального поиска и др.

Классическая задача коммивояжера решается в логистической практике редко, поскольку ее ограничения не включают, например, моделирование дорожных пробок, маршрутизацию нескольких машин в автопарке и, конечно, временные интервалы доставки покупателям. Поэтому Данциг и Рамсер предложили разновидность КЗК, дополнив задачу ограничением на количество автомобилей и назвав ее задачей маршрутизации транспорта (ЗМТ). В своей статье исследователи поставили вопрос оптимального развоза бензина на автозаправочные станции в городе N, предложив математическую постановку задачи и решив ее эвристическим алгоритмом. Данциг и Рамсер придали ЗМТ следующую форму задачи математического программирования, которая будет анализироваться в следующем разделе работы (Danzig, Ramser, 1959):

Отметим, что с математической точки зрения ЗМТ (6) - (11) отличается от классической задачи коммивояжера (1) - (6), наличием индекса k над переменной , который отвечает за номер транспортного средства в задаче. Несмотря на незначительное нововведение в математическую постановку, алгоритмическая сложность задачи существенно увеличивается.

Через несколько лет после публикации статьи Данцига и

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

Райт (1964) впервые предложили проводить оптимизацию маршрутов, решая ЗМТ как последовательно, так и параллельно, доказав, что одновременный выезд автомобилей из начальной точки приводит к более эффективному решению задачи (Clarke, Wright, 1964). Вышеупомянутая статья имела огромный успех, что и привлекло ученых из разных стран к анализу как постановок, так и алгоритмов касающихся стандартной задачи маршрутизации транспорта (обобщение задачи коммивояжера без усложнений и дополнительных ограничений).

Существенное внимание в первых работах о ЗМТ уделялось вычислительной сложности задачи. Так, Кан и Ленстра (1975) определили масштаб и характер задачи маршрутизации транспорта с математической точки зрения, описав новые алгоритмы решения ЗМТ, связывающие точные и эвристические методы. Авторы доказали, что задача маршрутизации транспорта является NP-сложной (как и задача коммивояжера), что говорит о ее неразрешимости за полиномиальное время (Kan, Lenstra, 1975). Тем не менее, многие исследователи конца ХХ века продолжали решать задачу маршрутизации транспорта точными методами.

В своей обзорной статье Лапорт (1992) детально проанализировал ряд работ, связанных с точными алгоритмами решения ЗМТ (полный перебор, метод ветвей и границ и др.) (Laporte, 1992). Ученый выяснил, что огромное количество задач остались нерешенными из-за длительности обработки данных описываемыми методами. Более того, в большинстве статей рассматривались задачи малых размерностей. Таким образом, необходимость углубленного исследования эвристических алгоритмов и новых модифицированных постановок задачи росла с каждым годом.

Отметим, что одной из первых и основных разновидностей классической задачи маршрутизации транспорта стало добавление в математическую постановку ограничения на грузоподъемность автомобилей, которое позволило оптимально распределять грузы между машинами, не превышая суммарную нагрузку на каждое транспортное средство. Как и стандартная ЗМТ, ее модификация с грузоподъемностью в литературе в основном решается классическими методами оптимизации (методом имитации отжига, жадным алгоритмом, и др.). Важно заметить, что задача маршрутизации транспорта с ограничением только на грузоподъемность редко используется на практике, поскольку оптимизация реальных бизнес процессов подразумевает введение и анализ таких ограничений как: временные интервалы поставки, пробки на дорогах в конкретном городе в определенное время дня и др. Такие ограничения неизбежно возникают, когда задача решается для конкретных организаций, которые занимаются транспортировкой людей или доставкой товаров (продукции). К примеру, Дерошье в своей статье ввел понятие «жестких» и «мягких» временных интервалов доставки грузов, что существенно изменило взгляд на ЗМТ, образовав новую математическую постановку задачи - с временными окнами и ограничением на грузоподъемность (capacitated vehicle routing problem with time windows - CVRPTW) (Desrochers, et al., 1992). Основным отличием «жестких» временных окон от «мягких» является возможность отгрузки продукции покупателю в случае нарушения временного интервала: если водитель опаздывает к покупателю с «жесткими» временными окнами - продукция будет непринята в полном размере (в случае с «мягкими» интервалами водитель получит штраф, но сможет произвести отгрузку). Более того, Дерошье в 1992 году обосновал, что решение задачи будет оптимальным, если автомобиль не имеет возможности приехать к покупателю позже заданной правой границы «жесткого» временного окна, в отличие от случая с «мягкими» временными интервалами.

В конце ХХ века большинство научных работ посвящались именно задаче маршрутизации транспорта с «жесткими» временными окнами, поскольку она в большей степени применяется на практике, начиная от деятельности инкассаторов и почтовых работников до маршрутизации школьных автобусов (Irnich, 2008). Математик выяснил, что на современных компьютерах, точные методы решают вышеописанную задачу с 50 - 60 точками на карте более чем за 50 часов, что недопустимо для оптимизации реальных логистических процессов. Так, Соломон в 1987 году рассмотрел первый эвристический алгоритм, позволяющий решить ЗМТ с временными интервалами и грузоподъемностью транспортных средств за существенно меньшее время, по сравнению с точными методами (Solomon, 1987). Эвристика была основана на алгоритме сбережений Кларка и Райта (1964) для классической задачи маршрутизации транспорта и улучшала текущее решение на каждой итерации, позволяя решать задачу на ориентированном графе (матрица расстояний между каждой точкой на карте асимметрична). Более того, Соломону удалось ускорить процесс решения задачи почти в 2 раза (Solomon, 1987).

Помимо эвристических методов, в современных статьях появилась новая категория алгоритмов - метаэвристики (обобщенные способы решения задачи коммивояжера) (Пантелеев, Метлицкая, Алешина, 2013). Одним из наиболее популярных метаэвристических методов является алгоритм муравьиной колонии, который будет использоваться в настоящем исследовании в разделе Данные и методология. Рассмотрим его подробно. Впервые в литературе М. Дориго сформулировал и реализовал алгоритм муравьиной колонии, который эмпирически решает ЗМТ быстрее, в сравнении с другими существовавшими и доступными алгоритмами конца ХХ века (Dorigo, 1999). В работах отмечается, что муравьиный алгоритм эффективен для количества вершин больше 20, то есть позволяет учесть временные ограничения в маршруте у наибольшего количества покупателей, в отличие от других методов оптимизации (гнездовой метод Монте-Карло, модифицированный генетический алгоритм и др.) (Курейчик, Мартынов, 2014). Более того, алгоритм муравьиной колонии меньше подвержен неоптимальным начальным решениям по сравнению с обычными эвристическими алгоритмами. Маршрут строится случайным образом и колония при выборе каждой следующей вершины опирается на память всех предшествующих муравьев, а не нескольких, в отличие от алгоритмов, построенных по принципу марковских процессов (текущее состояние системы зависит только от предыдущего). Итак, алгоритм муравьиной колонии основан на поведении множества искусственных муравьев, которые кооперируются для нахождения решения задачи путем обмена феромонами, находящимися на дугах графа (дороги в городе). Как известно, муравьи способны находить наилучший маршрут от источника еды до муравейника, оставляя след из феромона, по которому будут двигаться муравьи-последователи. Поскольку на самом выгодном маршруте феромона будет скапливаться больше, чем на других, через определенный момент времени, вся колония предпочтет его. Данный процесс получил название коллективное обучение (Dorigo, 1999). Необходимо отметить, что алгоритм муравьиной колонии учитывает как пространственные, так и временные характеристики задачи. С его помощью планируется найти решение, близкое к оптимальному.

Говоря о работах, связанных с подробным рассмотрением получаемых решений ЗМТ, отметим, что многие авторы считают недостаточным одного лишь решения задачи без последующего анализа. Экономисты утверждают, что для оптимизации логистики также необходимо обращать внимание на сам процесс формирования заказов, который может быть не оптимальным. Описываемая ситуация моделируется в виде задачи о ранце 0-1 (0-1 knapsack problem) (Toth, Vigo, 2002), которая имеет следующую математическую постановку:

где: - цена j-го заказа;

- вес j-го заказа;

- переменная, отвечающая за нахождение j-го заказа в автомобиле;

- суммарная грузоподъемность транспортного средства.

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

В научных статьях существует огромное количество модификаций и алгоритмов решения данной задачи (Иглин, 2003). Существуют задачи о многомерном ранце, целочисленная задача о рюкзаке, задача о рюкзаке с мультивыбором и др. Заметим, что задача о ранце (как и задача коммивояжера) является NP-сложной и не решается ни одним полиномиальным алгоритмом за мыслимое время (Макконнелл, 2004). В выпускной квалификационной работе частично затрагивается процесс фильтрации покупателей в случае возникновения излишнего спроса на продукцию фирмы. Подчеркнем, что решение задачи о рюкзаке не является целью настоящего исследования и будет рассмотрено в дополнение к анализу решения задачи маршрутизации транспорта с ограничением на грузоподъемность и временными окнами покупателей в разделе Описание результатов.

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

2. Постановка исследовательской проблемы

В выпускной квалификационной работе задача маршрутизации транспорта с временными окнами и ограничением на грузоподъемность транспортных средств рассматривается на примере пермской торговой фирмы ООО «Фабрика еды». Компания занимается оптовой торговлей скоропортящейся продукцией: мясопродуктами, курицей, а также полуфабрикатами. В июне 2015 года в фирме появился второй водитель, который также как и первый, отвечает за развоз продукции к покупателям. Фактическим адресом фирмы является ул. Академика Курчатова 9, что находится в 12 минутах езды до центра города Пермь и, следовательно, накладывает определенные сложности на быстроту доставки продукции контрагентам. Прием заявок осуществляется офисом, который находится по вышеупомянутому адресу, за день до отгрузки (доставки). В заявке покупателей указывается желаемое время отгрузки с 11:00 до 20:00 (время работы водителя). Обозначаемый в заявке временной интервал должен быть не меньше 30 минут (для того, чтобы водитель успел доставить продукцию в отдаленные районы). Цех предприятия начинает работу с 6:00 утра каждый день, для того чтобы максимально удовлетворить все текущие заявки покупателей. Среднее количество контрагентов, ожидающих поставку в случайный день, представлено на графике:

Рис. 1. Среднее количество покупателей на одного водителя

В определенный момент времени, а именно, осенью 2015 года, у компании возникли сложности с доставкой продукции покупателям: в связи с увеличивающимся количеством заявок один из двух водителей ездил не оптимально, не попадая в желаемое время отгрузки, за что покупатели штрафовали предприятие, делая возврат в полном объеме. Несмотря на то, что некоторые контрагенты были лояльны к времени отгрузки и опозданиям, ООО «Фабрика еды» каждый месяц несла потери в виде возвращенной (не принятой) продукции на 25 - 35 тыс. рублей по вине как первого, так и второго водителя.

Описывая типичный рабочий день водителей, необходимо отметить, что они развозят продукцию на машинах ИЖ-2717, которые оборудованы специальными рефрижераторами для скоропортящихся продуктов. В среднем один из водителей не успевал к одному контрагенту в неделю (потеря продукции на 4 - 5 тыс. рублей). Из причин, на которые ссылались водители, выделим одну наиболее значимую: «Производя доставку более приоритетным покупателям в центре города, практически невозможно успеть вовремя в отдаленные районы, которые также желают получить продукцию в определенный срок». Таким образом, предприятие хотело, по возможности, уменьшить свои транспортные расходы, определив строгую последовательность посещения заказчиков двумя водителями.

Данный процесс развоза продукции для одного водителя можно смоделировать в виде задачи коммивояжера, представленной системой ограничений (1) - (6). Итак, в один из дней работы исследуемой фирмы имеется N покупателей. Водитель, выезжает один раз в начале рабочего дня с предприятия в 11:00 (предварительно загрузив продукцию). Он доставляет заказы всем контрагентам (соответственно, побывав у каждого один раз) и возвращается после максимального удовлетворения всех заявок на предприятие (не обязательно в 20:00). В задаче будет находиться наименьшее время, а не расстояние, поскольку у водителя основной целью является успеть во временные окна как можно к большому числу покупателей (увеличение или уменьшение расстояния на несколько километров не приведет к существенным потерям для фирмы, по сравнению с возвратом продукции). Если водитель возвращается в фирму раньше окончания рабочего дня, он может заниматься, например, доставкой продукции от поставщиков. Таким образом, задача водителя заключается в определении последовательности объезда покупателей, которая будет минимизировать его путь, а также удовлетворять временному интервалу, установленному каждым покупателем (Lorini, 2011). Заметим, что в исследовании для нас представляет интерес не только задача коммивояжера, но, в большей степени, задача маршрутизации транспорта (6) - (11). Вторая является обобщением первой задачи. В работе используется модифицированная постановка ЗМТ - задача маршрутизации транспорта с временными интервалами и ограничением на грузоподъемность транспортных средств:

Переменные задачи: - бинарная неотрицательная переменная, принимающая значение 1, если водитель под номером k едет от покупателя i к контрагенту j, и значение 0 в остальных случаях; - показывает фактическое время прибытия водителей к покупателям; - неотрицательная переменная, предотвращающая распадение гамильтонова цикла на подциклы. Отметим, что две последние переменные не зависят от номера водителя (k), поскольку данные переменные непосредственно связаны с покупателями, а не с водителями фирмы (например, в задаче не задается какой именно водитель приедет к пятому покупателю в 12:00, а учитывается сам факт приезда одного из водителей в конкретное время). ЗМТ с временными окнами и грузоподъемностью автомобилей - (6) - (11), (15) - (17) является обобщением КЗК (1) - (6) и ЗМТ (6) - (11), и именно поэтому будет подробно рассмотрена ниже. (7) - целевая функция задачи - означает, что суммарное время водителей через всех покупателей должно быть наименьшим. (15) - обозначает, что суммарный спрос на продукцию (в кг) не должен превышать максимальную грузоподъемность каждого транспортного средства. (8) и (9) показывают, что оба водителя после отгрузки продукции покидают каждого покупателя только один раз и приезжают к другому контрагенту для поставки только один раз. Поскольку, решением задачи коммивояжера являются замкнутые маршруты водителей, так называемые гамильтоновы циклы, ограничение (10) означает невозможность распадения данного цикла на подциклы (объезд всего нескольких покупателей из всей заявки). Ограничение (11) указывает на то, что переменные задачи являются бинарными и неотрицательными, а (6) означает, принадлежность переменных к множеству вещественных чисел. Большой интерес в данной постановке представляют два последних ограничения. В повседневной деятельности, предприятие заключает договоры поставки с новыми контрагентами, которые склонны к оппортунистическому поведению, а именно к сокращению желаемого времени доставки продукции (которое прописано в контракте) в новых ежедневных заявках. Торговому предприятию зачастую приходится подстраиваться под своих покупателей для того, чтобы их сохранить, а следовательно, встает необходимость удовлетворения заявок контрагентов именно в желаемое для них время, что ведет к модификации традиционной логистической задачи ЗМТ (Moon, et al., 2012). С математической точки зрения, в задачу маршрутизации транспорта необходимо добавить ряд дополнительных предпосылок, основной из которых будет ограничение на временные интервалы, в которые покупатели ожидают доставку товара.

Важным свойством задачи маршрутизации транспорта с временными интервалами и ограничением на грузоподъемность транспортных средств является то, что минимальные по времени маршруты начинаются из ООО «Фабрика еды» в 11:00, в дальнейшем проходя через все вершины (покупателей) только один раз, в течение соответствующих временных интервалов и заканчиваются в точке начала маршрута. Исходя из этого, каждому покупателюв дневной заявке будет поставлено в соответствие «жесткое» временное окно , где границы интервала будут обозначать начало ожидаемого времени поставки и его окончание соответственно. Временные интервалы покупателей должны устанавливаться во время работы водителей, которое обозначим - [0, ]. Отметим, что как опытному, так и новому водителю, необходимо определенное время для того, чтобы обслужить i-го покупателя. В модифицированной задаче, у каждого ребра весом будет являться время проезда от одного покупателя к другому (). Таким образом, в задачу (6) - (11), наряду с ограничением на грузоподъемность, добавятся два новых ограничения (16) и (17). (16) - задает временные окна у каждого покупателя, в которые водителю необходимо отгрузить продукцию. Ограничение (17) показывает временную взаимосвязь между последовательными покупателями в маршруте. Рассмотрим двух контрагентов к которым водитель приезжает напрямую (). Очевидно, что время приезда к покупателю j будет больше либо равно сумме времени приезда к покупателю i, времени разгрузки у контрагента i, а также времени проезда от i к j: . Однако такое ограничение справедливо только для тех пар клиентов i и j, которых хотя бы один из водителей посещает последовательно. Поэтому описываемое ограничение (17) становится нелинейным, что накладывает определенные сложности в выборе алгоритма решения данной логистической проблемы. Таким образом, решив детерминированную задачу (6) - (11), (15) - (17), фирма достигнет своей логистической цели - успеть вовремя ко всем покупателям в их временные интервалы, получив минимальные по времени маршруты водителей.

В работе, помимо описываемой детерминированной задачи, затрагивается стохастическая постановка ЗМТ, в которой целевая функция направлена на минимизацию риска возникновения потерь продукции. Предположим, что решив задачу (6) - (11), (15) - (17), водитель приезжает к пятому покупателю в 11:58, а правая граница временного окна - 12:00. Очевидно, что в случае, например, затора на дороге или задержки у предыдущего покупателя, водитель не успеет доставить продукцию в желаемый интервал отгрузки. Для фирмы более осмысленной представляется задача минимизации математического ожидания потерь, связанных с доставкой продукции позже указанного срока:

, (18)

где: - вероятность недоставки продукции i-му покупателю;

- выручка от i-го контрагента.

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

Рис. 2. Вероятность недоставки продукции покупателям

В исследовании подразумевается, что вероятность непринятия продукции i-ым покупателем при принимает значение 0,2. Данное значение было получено на основе статистического анализа неотгруженных заказов.

Таким образом, ограничение (18) можно представить в виде:

(18.1)

где: k и c - параметры линейной убывающей функции.

После изменения функционала задачи, возникает стохастическая постановка - (6), (8) - (11), (15) - (17), (18.1), решение которой, с экономической точки зрения, позволит снизить риск недоставки продукции путем наиболее раннего приезда водителей к покупателям. Очевидно, что описываемая модификация ЗМТ с временными окнами и грузоподъемностью автомобилей неединственная. Данную задачу можно преобразовать под любые особенности бизнеса, например, введя ограничения на случайный размер заказа или на обслуживание одного покупателя несколькими транспортными средствами. Оказалось, что исследуемая компания не ставит цель наиболее раннего приезда ко всем контрагентам (есть покупатели с временными окнами длинной в 6 часов и фирме без разницы: приедет водитель за 2 или за 3 часа до конца интервала). В ходе анализа расходных накладных и личных интервью с водителями ООО «Фабрика еды» было установлено, что минимальная разность (позволяющая максимально снизить риск недоставки) между правой границей временного окна у каждого покупателя и приездом водителя должна составлять 10 минут, что приведет к трансформации линейной убывающей функции в кусочно-линейную невозрастающую:

Рис. 3. Вероятность недоставки продукции ООО «Фабрика еды»

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

(19)

Таким образом, в выпускной квалификационной работе будет анализироваться детерминированная ЗМТ (6) - (11), (15) - (17), решение которой (кратчайшие по времени маршруты для двух водителей, удовлетворяющие всем временным окнам покупателей) путем изменения параметра надежности (временного резерва) будет приближено к решению стохастической задачи. Оптимальные по времени маршруты водителей будут удовлетворять специфике реального бизнеса и минимизировать транспортные расходы компании при математическом ожидании риска недоставки продукции равном нулю. Отметим, что, несмотря на относительную простоту постановки задачи (6) - (11), (15) - (17), решать ее достаточно сложно, поскольку необходимо не только сформировать определенный набор данных с учетом различных характеристик предприятия, но и подобрать для них алгоритмы нахождения оптимального решения (Rodriguez, Ruiz, 2012).

3. Данные и методология

Информационной базой исследования являются данные бухгалтерского и управленческого учета фирмы ООО «Фабрика еды». На первой стадии их сбора анализировались все дневные заказы покупателей начиная с лета 2015 года (когда у фирмы появился второй водитель) по настоящее время. На основании расходных накладных и счет фактур, которые формировались в программе 1С: Предприятие 8.2, было выяснено, что у фирмы имеются ежемесячные «проблемные» поставки клиентам. Количество покупателей в описываемых заявках варьируется от 20 до 32 на одного водителя и зависит от времени года (осенью и зимой количество клиентов больше, чем летом). В настоящем исследовании рассматривается один из «проблемных» дней с 52 контрагентами (включая фирму-поставщика). Заявки данных покупателей выполнялись 18 сентября 2015 года. Анализируемый день был проблемным для предприятия, поскольку компания несла убытки по вине одного из водителей в размере 14 560 рублей. Фактические маршруты водителей в рассматриваемом дне представлены в таблицах 1 и 2, а их реальные адреса доставки в Приложении 13.

Таблица 1

Фактический маршрут 1-го водителя в исследуемый день*

* - в таблицах представлены реальные данные компании ООО «Фабрика Еды», поскольку решение ЗМТ рассматривается на примере описываемой фирмы.

Таблица 2

Фактический маршрут 2-го водителя в исследуемый день

В таблицах отражен 51 контрагент (с помощью видеорегистраторов производилась фиксация реального времени проезда от одного клиента к другому, а также время обслуживания каждого покупателя), которым водитель должен доставить заказ с 11:00 до 20:00 в установленное временное окно. В последнем столбце таблицы приведено фактическое время, которое водители тратили на разгрузку заказов у каждого клиента, а также на оформление необходимых документов. Отметим, что в рассматриваемом дне деятельности фирмы первый водитель не успел к контрагенту № 19, который находится в г. Добрянка (примерно 70 км от центра города). Сумма продукции для данного покупателя в исследуемой заявке составляла 14 560 рублей. Водитель, не успев к данному покупателю на 16 минут, был оштрафован возвратом продукции в полном размере. Компания пыталась сделать данный заказ приоритетным, что привело к опозданиям к последующим покупателям в центре города. Таким образом, фирма сталкивается со следующими проблемами, которые будут решены в ходе анализа ЗМТ:

а) Формирование последовательности обслуживания покупателей;

б) Сокращение потерь продукции, как в исследуемой заявке, так и в ряде других;

в) Оптимальное распределение загруженности водителей.

Таким образом, для математического решения логистической задачи на следующей итерации сбора данных формировались матрицы расстояний и времени между 52 точками на карте г. Пермь (покупателями и фирмой). Каждое из 2 704 расстояний/времени проезда между контрагентами рассчитывалось в современных онлайн-картах Google Maps, в которых имеется возможность учесть дорожную ситуацию (пробки, заторы), а также специфику автомобильного движения в г. Пермь (большое количество дорог с односторонним движением). С помощью этих сервисов были собраны расстояния (в км) и время проезда (в мин) между покупателями, максимально близкие к реальным. Таким образом, удалось получить асимметричные матрицы расстояний и времени между всеми покупателями.

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