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

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

В работе проводится анализ основных научных статей по теме. Выяснено, что первое упоминание о КЗК (TSP) появилось в трудах У. Гамильтона и Т. Киркмана в середине ХIХ века. Математики не обладали необходимыми алгоритмами решения задачи и могли сформулировать лишь предполагаемый результат — маршрут торговца, проходящий через каждый город только один раз с возвращением в исходный (при этом необходимо объехать все города без исключения). Данный маршрут (цикл) получил название гамильтонов. По мере развития математики, а именно такого направления как комбинаторная оптимизация, ученые стали придавать задаче коммивояжера не только практический, но и теоретический смысл.

Литература

на тему КЗК росла экспоненциально и, к примеру, на 2016 год существует более 6 000 исследований, связанных с задачей коммивояжера.

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

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

4 — 5 тыс. рублей.

Решить данную проблему для компании удалось, рассмотрев ЗМТ, которая несмотря на относительную простоту постановки задачи, решалась достаточно сложно. В работе рассматривались как детерминированная, так и стохастическая постановки задачи. На основе ряда эвристик в исследовании показывается, что компания может решать серию детерминированных задач, приближая получаемые маршруты к реальности. Безусловно, для того чтобы решить описываемые задачи, необходимо было подобрать репрезентативные данные и выбрать эффективные методы нахождения наилучших маршрутов. Информационной базой исследования стали данные бухгалтерского и управленческого учета фирмы ООО «Фабрика еды». На первом этапе их сбора были изучены все дневные отгрузки продукции покупателям начиная с лета 2015 года (когда у фирмы появился второй водитель) по настоящее время. Для данного исследования был взят один из вышеуказанных дней с 51 покупателем. Заявки именно данных клиентов выполнялись 18 сентября 2015 года. Необходимо отметить, что в анализируемом дне деятельности предприятия первый водитель не успевал к контрагенту № 19, который находился в г. Добрянка (70 км от центра г. Пермь). Более того, предприятие понесло убытки по вине одного из водителей в размере 14 560 рублей (штраф в виде возврата продукции в полном размере). Предприятие пыталось поставить данный заказ в приоритет, что привело к неудовлетворению последующих заявок у нескольких покупателей в центре города. Таким образом, появилась необходимость при помощи математических методов сформировать такую последовательность обслуживания покупателей, чтобы сократить данные потери, как в исследуемой повторяющейся заявке, так и в ряде других.

В итоге, первым этапом анализа стало решение задачи коммивояжера, в имитационном случае: если бы у фирмы имелся один водитель и он бы развозил 51 заявку индивидуально. Данный эксперимент был проведен, поскольку необходимо математически проверить нужность второго водителя в фирме. Затем, фактические маршруты двух водителей были оптимизированы и решение было сравнено с реальным. На следующем этапе работы задача CVRPTW была разделена на 2 части и каждая решена по отдельности. В конечном счете, целая задача маршрутизации была решена с учетом трех сценариев дорожной ситуации в г. Пермь: «благоприятного», «умеренного», «неблагоприятного» и полученные результаты были обобщены в виде сетевой модели планирования и управления (PERT). На всех вышеперечисленных этапах работы использовались два основных метода решения задачи: муравьиный алгоритм и метод поиска с запретами.

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

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

(0−1 knapsack problem). Решив данную задачу, удалось отфильтровать заявки покупателей, что фактически привело к дополнительной оптимизации логистики.

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

Таким образом, применяя описываемые в работе способы оптимизации транспортной логистики, ООО «Фабрика еды», как и другая торговая фирма, сможет сократить свои транспортные расходы на 25 — 35 тыс. рублей в месяц.

Исследование можно развить в следующих направлениях:

• 1) Решить более сложные модификации задачи о ранце 0−1, внедрив в нее различные ограничения;
• 2) Рассмотреть подробно оптимизацию дизайна контрактов, описав функцию полезности покупателей;
• 3) Оптимизировать процесс управления скоропортящимися запасами.

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