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

С точки зрения экономической теории, понятие транспортной логистики рассматривается как планирование оптимальных маршрутов грузоперевозок с минимизацией затрат, что является особенно актуальным для торговых компаний, ежедневно доставляющих продукцию покупателям. В течение последующих десятилетий ученые из разных стран изучали КЗК, разрабатывая новые математические постановки задачи и алгоритмы их решения. Несмотря на популярность классической задачи коммивояжера, она редко решается на практике, поскольку ее ограничения не учитывают, например, маршрутизацию нескольких машин в автопарке компании, пробки на дорогах и временные интервалы доставки покупателям. Летом 2015 года у предприятия возникли трудности с развозом продукции покупателям: в связи с увеличивающимся количеством заявок, водители часто опаздывали в желаемое время поставки, установленное покупателями, за что были оштрафованы возвратом продукции в полном размере. Отметим, что в работе рассматривается модифицированная ЗМТ, которая учитывает специфику бизнеса: в задачу добавляется ограничение на грузоподъемность транспортных средств, а также два условия, устанавливающие временные окна покупателей.Начнем с подробного описания и изучения классической задачи коммивояжера - КЗК («задача странствующего торговца»), поскольку не проанализировав данную задачу, понять более сложную ее модификацию не представляется возможным (Макконнелл, 2004). В условиях данной задачи традиционно указываются какие-либо критерии оптимальности (наименьшее расстояние или время). Говоря об актуальности исследования задачи, которая появилась в середине XVIII века, подчеркнем, что с 1959 по 2008 годы около 1 000 научных журналов публиковали статьи про задачу коммивояжера на первых страницах. Задача имеет экспоненциальную алгоритмическую сложность: коммивояжер в каждом городе встает перед выбором следующего из еще не посещенных, а значит, существует маршрутов для асимметричной (расстояние из города i в город j, не равно обратному) задачи, где n - число городов. За нахождение такого метода, американское математическое сообщество предлагает приз в миллион долларов, что говорит об огромном интересе к задаче как с теоретической, так и практической точки зрения.Обозначаемый в заявке временной интервал должен быть не меньше 30 минут (для того, чтобы водитель успел доставить продукцию в отдаленные районы). В определенный момент времени, а именно, осенью 2015 года, у компании возникли сложности с доставкой продукции покупателям: в связи с увеличивающимся количеством заявок один из двух водителей ездил не оптимально, не попадая в желаемое время отгрузки, за что покупатели штрафовали предприятие, делая возврат в полном объеме. В задаче будет находиться наименьшее время, а не расстояние, поскольку у водителя основной целью является успеть во временные окна как можно к большому числу покупателей (увеличение или уменьшение расстояния на несколько километров не приведет к существенным потерям для фирмы, по сравнению с возвратом продукции). В работе используется модифицированная постановка ЗМТ - задача маршрутизации транспорта с временными интервалами и ограничением на грузоподъемность транспортных средств: Переменные задачи: - бинарная неотрицательная переменная, принимающая значение 1, если водитель под номером k едет от покупателя i к контрагенту j, и значение 0 в остальных случаях; - показывает фактическое время прибытия водителей к покупателям; - неотрицательная переменная, предотвращающая распадение гамильтонова цикла на подциклы. Отметим, что две последние переменные не зависят от номера водителя (k), поскольку данные переменные непосредственно связаны с покупателями, а не с водителями фирмы (например, в задаче не задается какой именно водитель приедет к пятому покупателю в 12:00, а учитывается сам факт приезда одного из водителей в конкретное время).На первой стадии их сбора анализировались все дневные заказы покупателей начиная с лета 2015 года (когда у фирмы появился второй водитель) по настоящее время. На основании расходных накладных и счет фактур, которые формировались в программе 1С: Предприятие 8.2, было выяснено, что у фирмы имеются ежемесячные «проблемные» поставки клиентам. * - в таблицах представлены реальные данные компании ООО «Фабрика Еды», поскольку решение ЗМТ рассматривается на примере описываемой фирмы. В таблицах отражен 51 контрагент (с помощью видеорегистраторов производилась фиксация реального времени проезда от одного клиента к другому, а также время обслуживания каждого покупателя), которым водитель должен доставить заказ с 11:00 до 20:00 в установленное временное окно. На первом этапе анализа проверяется необходимость найма второго водителя фирмой - решается задача коммивояжера, в случае, если бы у фирмы имелся один водитель и он бы развозил 51 заявку индивидуально.Применив алгоритмы на реальных данных предприятия ООО «Фабрика еды», удалось решить задачу маршрутизации транспорта с временными окнами покупателей и ограничением на грузоподъемность автомобилей двумя сп

Оглавление

Введение

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

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

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

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

Заключение

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

Приложения

С точки зрения экономической теории, понятие транспортной логистики рассматривается как планирование оптимальных маршрутов грузоперевозок с минимизацией затрат, что является особенно актуальным для торговых компаний, ежедневно доставляющих продукцию покупателям. В связи с растущей загруженностью автомобильных дорог, водители предприятий часто опаздывают в установленные временные интервалы доставки, что приводит к возвратам продукции, росту неудовлетворенности клиентов, и, в конечном счете, к потерям выручки и убыткам. Существует ряд моделей, применив которые, фирма может существенно сократить транспортные расходы и оптимизировать последовательность посещения контрагентов. Одна из них - классическая задача коммивояжера (КЗК), решением которой является кратчайший замкнутый маршрут водителя, проходящий через всех покупателей по одному разу. Задача была поставлена английскими математиками У. Гамильтоном и Т. Киркманом в середине ХІХ века. В течение последующих десятилетий ученые из разных стран изучали КЗК, разрабатывая новые математические постановки задачи и алгоритмы их решения. Так появились точные и приближенные методы достижения оптимальных маршрутов (Бронштейн, Заико, 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). Отметим, что последняя задача является обобщением первой, следовательно, необходимо провести как совместный, так и сепаратный анализ двух задач. Второй раздел, описывает предметную область (компанию), ограничения и предпосылки, возникающие в ходе моделирования. Рассматривается математическая постановка исследуемой задачи. В третьем разделе подробно описываются используемые данные и алгоритмы решения задачи. Также в третьей части проводится сравнительный анализ основных методов решения по ряду критериев. Большое внимание уделяется муравьиному методу и алгоритму «поиска с запретами». Последний раздел подразумевает обсуждение основных результатов исследования. В данной части работы в программных пакетах реализуются математические методы нахождения оптимальных маршрутов водителей торгового предприятия, строятся сетевые модели планирования и управления, проводится пересчет маршрутов в случае непредвиденных дорожных ситуаций, а также решается классическая задача об оптимальной загрузке автомобиля. Полученные результаты обобщаются в виде выводов, а также даются рекомендации по практическому применению моделей и внедрению их в компании.