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

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