Дипломная работа на тему «Задача маршрутизации транспорта с временными окнами и ограничением на грузоподъемность транспортных средств рассматривается на примере пермской торговой фирмы ООО ‘Фабрика еды'»

Скачать пример Заказать работу Скачать пример Заказать работу

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Нужна помощь в написании диплома?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Сдача работы по главам. Уникальность более 70%. Правки вносим бесплатно.

Подробнее

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

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

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

Выпускная квалификационная работа состоит из введения, четырех разделов, заключения и списка литературы. В первом разделе подробно рассматривается ряд существующих работ по исследуемой теме. Теоретическое обоснование структурно разделено на две части: первая часть посвящена классической задаче коммивояжера, а вторая — задаче маршрутизации транспорта с временными окнами и ограничением на грузоподъемность автомобилей (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).

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

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

Таблица 1

Нужна помощь в написании диплома?

Заказать диплом

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

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Ресторан Нефертити	11:00	19:00	11:09	11:16	00:07	—	—
3	Кафе «Корица»	11:00	19:00	11:19	11:27	00:08	—	—
4	Ресторан «Горький»	11:30	12:00	11:32	11:36	00:04	—	—
5	ИП Ахметова Н.П.	11:00	12:00	11:56	12:04	00:08	—	—
6	Ресторан «Кама-Фиш»	12:00	12:30	12:23	12:29	00:06	—	—
7	ООО «ТД»	12:00	13:00	12:46	12:54	00:08	—	—
8	ООО «Веселый пекарь»	11:00	14:00	13:09	13:15	00:06	—	—
9	Ресторан «Пармезан»	12:30	15:30	13:23	13:31	00:08	—	—
10	ООО «Море рыбы»	12:00	16:00	13:38	13:44	00:06	—	—
11	Продуктовый магазин	12:00	16:00	13:54	14:03	00:09	—	—
12	Ресторан «Тсуру»	11:00	19:00	14:06	14:11	00:05	—	—
13	Ресторан «Casa Mia»	13:00	17:00	14:13	14:21	00:08	—	—
14	Кафе «Сковородка»	14:00	16:00	14:24	14:28	00:04	—	—
15	Бар «Лаундж»	11:00	19:00	14:30	14:35	00:05	—	—
16	Ресторан «Casa Mia»	11:00	20:00	14:40	14:43	00:03	—	—
17	Кафе «Кредо»	14:00	18:00	14:49	14:56	00:07	—	—
18	ООО «Гарант плюс»	15:00	16:30	15:00	15:03	00:03	—	—
19	ИП Кусакин А.В.	15:00	16:30	16:46	16:53	00:07	—	00:16
20	ТЦ «Евразия»	15:30	19:30	18:21	18:27	00:06	—	—
21	Продуктовый магазин	16:00	19:00	18:36	18:45	00:09	—	—
22	Столовая «Забава»	15:00	19:00	18:55	19:00	00:05	—	—
23	Пиццерия «Pizzaman»	17:00	19:30	19:03	19:06	00:03	—	—
24	ООО «Заполье»	17:00	19:30	19:13	19:18	00:05	—	—
25	ООО «Микс — Семья»	15:00	22:00	19:31	19:40	00:09	—	—
26	Продуктовый магазин	18:00	21:00	19:46	19:55	00:09	—	—
27	ООО «Компания ЦВР»	11:00	21:00	20:05	20:08	00:03	—	—
28	ООО «Фабрика еды»	—	—	20:15	20:15	—	—	00:15

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

Таблица 2

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

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелка №1»	11:00	11:30	11:12	11:19	00:07	—	—
3	Столовая «Тарелка №2»	11:00	12:00	11:25	11:28	00:03	—	—
4	Столовая «Тарелочка»	11:00	12:00	11:37	11:45	00:08	—	—
5	Ресторан «Хуторок»	12:30	13:00	12:20	12:33	00:03	00:10	—
6	Кафе «Ритм»	11:00	19:00	13:03	13:09	00:06	—	—
7	ОАО «ЭР-Телеком»	12:30	13:30	13:11	13:14	00:03	—	—
8	Кафе «Паста Гранде»	12:00	13:30	13:19	13:28	00:09	—	—
9	ЗАО «Пермторгтехника»	13:00	14:00	13:34	13:39	00:05	—	—
10	Кафе «Правила»	11:00	14:00	13:48	13:51	00:03	—	—
11	ООО «Паритет»	14:00	15:00	13:55	14:05	00:05	00:05	—
12	Ресторан «Охотничий»	13:30	15:30	14:08	14:15	00:07	—	—
13	Ресторан «Сакартвело»	13:30	17:30	14:20	14:28	00:08	—	—
14	Ресторан «Халва»	14:00	20:00	14:35	14:43	00:08	—	—
15	Ресторан «Партизан»	13:30	18:30	14:47	14:50	00:03	—	—
16	ООО «Цертина»	15:00	16:00	14:57	15:07	00:07	00:03	—
17	ООО «Эверест»	14:00	17:00	15:11	15:18	00:07	—	—
18	ТЦ «Столица»	13:00	18:00	15:30	15:35	00:05	—	—
19	ООО «ПМП»	15:00	19:00	16:50	16:54	00:04	—	—
20	Ресторан «Сакартвело»	12:00	18:00	17:06	17:11	00:05	—	—
21	Ресторан «Халва»	15:00	19:00	17:15	17:24	00:07	—	—
22	ООО «Пушкин»	11:00	19:00	17:28	17:36	00:08	—	—
23	Продуктовый магазин	16:00	19:30	17:41	17:46	00:05	—	—
24	ООО «Федерал»	18:00	20:00	17:51	18:05	00:05	00:09	—
25	Кафе «Ударник»	11:00	19:00	18:16	18:22	00:06	—	—
26	Ресторан «Тсуру»	17:00	20:00	18:29	18:37	00:08	—	—
27	ООО «Фабрика еды»	—	—	18:50	18:50	—	—	—

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

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

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

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

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

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

Точные методы решения логистических задач (полный перебор, метод ветвей и границ) позволяют найти глобальный оптимум — наилучший из всех возможных маршрутов и широко используются для решения задач маршрутизации без дополнительных ограничений. Доказано, что с увеличением количества вершин в задаче время ее решения точными методами увеличивается экспоненциально (Toth, Vigo, 2002). Вторая группа алгоритмов — эвристические методы. В отличие от точных методов решения задачи, они позволяют найти приближенные маршруты водителей (локальные оптимумы), которые, с теоретической точки зрения, не всегда являются наилучшими. На практике любая последовательность объезда покупателей, улучшающая текущий маршрут и удовлетворяющая временным интервалам, будет приемлемой для предприятия. В работе применяется один метод из данной категории: алгоритм муравьиной колонии, который рассматривался в теоретическом обосновании исследования. В данном разделе работы опишем алгоритм формально. Каждой дуге графа будет поставлено в соответствие два веса: мера привлекательности — , называемая феромоном, и мера актуальности — . В задаче маршрутизации транспорта матрицы расстояния и времени являются асимметричными, а следовательно, . Суть алгоритма заключается в том, что в самом начале процедуры муравьев находится в точке начала маршрута. Каждый муравей выбирает следующую вершину графа исходя из вероятностно-пропорционального правила (Dorigo, 1999):

,(20)

где: — вероятность перехода муравья под номером k из вершины i в вершину j;

Нужна помощь в написании диплома?

Заказать диплом

, алгоритм вырождается в «жадный», если , муравьи реагируют только на количество феромона).

Знаменатель формулы позволяет вероятности находиться в пределах единицы ( — множество еще не посещенных муравьями вершин, смежных с i. Таким образом, муравьи предпочитают выбирать каждую последующую вершину, исходя только из меры актуальности и количества феромона. После расчета вероятности перехода из одной вершины в другую, в алгоритме используется генератор случайных чисел от 0 до 100. Если найденная вероятность больше, чем случайное число, муравей передвигается в данную вершину, если нет, то рассматривается следующая вершина из еще не использованных в маршруте. Когда муравей проходит каждую последующую точку, количество феромона уменьшается. После прохождения всего маршрута одним из муравьев используется правило обновления феромона:

(21)

где: — случайное число, отвечающее за интенсивность испарения феромона (0<<1);- момент времени.

Алгоритм муравьиной колонии находит решение либо через фиксированное количество итераций, либо через определенное количество времени. Важным моментом в решении задачи муравьиным алгоритмом является связь расстояния и времени, которая будет моделироваться через параметр — актуальность посещения каждой конкретной вершины (разница между правой границей временного окна i-го покупателя и текущим моментом времени) (Лебедев, 2012):

,(22)

где: , является шириной временного интервала до начала обслуживания покупателя j;

— текущий момент прохождения маршрута, — левая и правая граница временного окна у покупателя под номером j;

— время проезда от контрагента i к j;

— коэффициент штрафующий за не включение j-ой вершины в маршрут (с экономической точки зрения показывает приоритет обслуживания j-го покупателя).

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

Используемый в исследовании алгоритм одновременного решения задачи (без деления на отдельные задачи коммивояжера для каждого водителя), является метаэвристическим и основан на алгоритме имитации отжига, а также механизмах функционирования краткосрочной памяти человека. На данный момент, эмпирически доказано, что поиск с запретами является наиболее эффективным методом решения описываемой задачи, а именно, он позволяет найти решение за наименьшее время (в сравнении с другими метаэвристиками) (Wiener, et al., 2009). Поиск с запретами начинает решать задачу с первоначального маршрута (, найденного, к примеру, «жадным» методом. На каждой итерации (t), алгоритм (путем случайной перестановки последовательности вершин графа) улучшает решение (), минимизируя целевую функцию. Итерации продолжаются до тех пор, пока не будет выполнен критерий остановки (конечное количество этапов алгоритма, либо заданное время). Метод поиска с запретами очень похож на алгоритм имитации отжига, следовательно необходимо описать последний для выявления расхождений.

В методе имитации отжига очередная последовательность вершин (точек на карте) также формируется случайным образом, путем незначительного изменения предыдущего маршрута. Один из самых распространенных в литературе вариантов изменения — перестановка двух случайно выбранных вершин графа. Если маршрут получился лучше всех предыдущих итераций, то он рассматривается как следующий для улучшения. Если же маршрут получается хуже, то один из вариантов — не использовать его. Придерживаясь описываемой логики, решение задачи может попасть в один из локальных экстремумов (минимумов), которых достаточно много в задаче маршрутизации транспорта. Именно исходя из данных предположений маршрут не отвергается (Лопатин, 2005). Вероятность его принятия рассчитывается по формуле:

,(23)

Нужна помощь в написании диплома?

Заказать диплом

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

Главным отличием алгоритма поиска с запретами от метода имитации отжига является то, что последним нельзя решить ЗМТ из-за слишком большого количества локальных минимумов, в то время как алгоритм поиска с запретами обладает краткосрочной памятью и имеет свойство «выходить» из локальных оптимумов задачи с помощью «листа табу», в который заносятся маршруты, сформированные на предыдущих итерациях после достижения одного из локальных экстремумов (Чеблоков, Ченцов, 2005). Таким образом, у алгоритма появляется возможность «не возвращаться» в предыдущие локальные оптимумы, а итерационно двигаться к следующему, вне зависимости от того, лучше он или нет. Наличие краткосрочной памяти позволяет алгоритму поиска с запретами запоминать все найденные экстремумы и на последней итерации выбирать тот, в котором значение целевой функции задачи маршрутизации транспорта минимальное. Описываемый алгоритм позволяет решить ЗМТ с различными ограничениями быстро и эффективно, по сравнению с другими методами нахождения оптимального маршрута. Более того, на данный момент, поиск с запретами — один из немногих алгоритмов, который имеет программное обеспечение и привязан к геоинформационным системам (ГИС), что позволяет решить задачу еще эффективнее. Таким образом, после обработки данных и выявления наиболее приемлемых как с теоретической, так и практической/программной точки зрения алгоритмов решения ЗМТ, рассмотрим вышеизложенную методологию в разрезе результатов исследования.

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

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

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

ООО «Фабрика еды» о найме второго водителя, поскольку одно транспортное средство фактически не могло развезти 51 заявку с 11:00 до 20:00 (см. Приложение 1). Муравьиный алгоритм, нашел решение задачи за

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

На следующем этапе были по отдельности оптимизированы реальные маршруты водителей, полученные при помощи видеорегистраторов транспортных средств и личных интервью (см. Приложения 2, 3). Данный вариант оптимизации логистики компании проводился для того, чтобы понять, действительно ли водители ездили не лучшим образом в исследуемом дне. Оказалось, что муравьиный алгоритм смог найти оптимальные решения для двух задач коммивояжера, улучшив фактические дневные планы водителей. Так, первый водитель избежал опоздания на 16 минут в г. Добрянка, что позволило сократить потери фирмы как в денежном, так и в количественном выражении. Отметим, что у водителя получился достаточно «плотный» график объезда покупателей (без учета различной дорожной ситуации, водитель превысил свое рабочее время на несколько минут). Для второго водителя удалось уменьшить простои (ожидания) перед началом временных окон некоторых покупателей, что также говорит о более рациональном решении задачи математическими методами, чем ее решение, основанное на личном опыте водителей.

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

В исследовании удалось оптимизировать логистику ООО «Фабрика еды» путем одновременного решения задачи маршрутизации транспорта с временными окнами и ограничением на грузоподъемность транспортных средств алгоритмом поиска с запретами. Результаты метода представлены в Приложениях 6, 10. Анализируя данные таблицы, заметим, что алгоритму поиска с запретами было задано конечное время итераций — 10 минут, за которое удалось получить оптимальное решение задачи. У первого водителя аннулировалось опоздание в г. Добрянка, а у второго общий дневной простой сократился до 5 минут, а также увеличилась нагрузка на автомобиль (стало больше покупателей в центре г. Пермь). Таким образом, в работе удалось решить детерминированную ЗМТ методом поиска с запретами, оптимизировав в первом приближении логистику фирмы ООО «Фабрика еды». Более того, после получения наилучших маршрутов, необходимо приблизить их к реальной недетерминированной жизни, снижая риск недоставки продукции (как было отмечено ранее, водителям достаточно иметь временной резерв минимум в 10 минут до конца временного окна у каждого покупателя). В данном случае, одним из способов достижения оптимальных маршрутов водителей является сокращение всех временных интервалов покупателей на 10 минут и повторное решение задачи. Проведя анализ первоначального решения ЗМТ (см. Приложения 6, 10), было выяснено, что только первый водитель имеет четырех покупателей, к которым приезжает меньше чем за 10 минут до конца временного окна. Второй водитель, несмотря на большее количество заявок, удовлетворяет описываемому ограничению, в виду значительного количества широких временных интервалов (минимальный резерв времени — 16 минут).

Подчеркнем, что в работе на примере водителя № 1 решается серия детерминированных задач, потому что только он опаздывал к клиентам в исходном решении (см. Приложение 6). С точки зрения математической теории, локальная оптимизация (решение серии задач только для первого водителя, не меняя оптимальный план для второго) сужает область допустимых значений, что может привести к отсутствию решения. Торговой фирме на первом этапе предлагается решить ЗМТ для двух водителей методом поиска с запретами. Затем, если решение найдено и удовлетворяет всем требованиям бизнеса, оно может считаться наилучшим. Если решение ЗМТ не удовлетворяет требованию временного резерва равного 10 минутам у одного из водителей, то оптимизация будет проводится локально, поскольку второй водитель уже может ехать по кратчайшему маршруту без дополнительных модификаций пути. Если решение для одного из водителей не может быть найдено, фирме необходимо перейти к глобальной оптимизации — сократить временные окна как у первого, так и у второго водителя одновременно. В работе помимо подробного рассмотрения локальной оптимизации задачи был учтен вариант сокращения временных окон покупателей для двух водителей одновременно. В описываемом случае, целевая функция ЗМТ возросла на 34 минуты для первого водителя, по сравнению с локальной оптимизацией маршрута (см. таблицу 3). Заметим, что увеличение произошло из-за изменившейся последовательности покупателей и их количества (у водителя № 1 стало на 3 покупателя больше по сравнению с локальной оптимизацией). Таким образом, фирме сначала необходимо попытаться оптимизировать маршрут одного из водителей (если второй маршрут оптимален) и только потом переходить к глобальной оптимизации, если первый вариант покажет свою несостоятельность. Решение детерминированной задачи без временных резервов алгоритмом поиска с запретами позволит изначально разделить покупателей на две группы между водителями, следовательно, возможна как локальная так и глобальная оптимизация задачи.

Итак, в ходе решения серии детерминированных задач с различными параметрами надежности ( было установлено, что максимальный временной запас у первого водителя может составлять не 10, а 12 минут:

Таблица 3

Оптимальный маршрут водителя № 1 (с учетом временного резерва — 12 минут)

Нужна помощь в написании диплома?

Заказать диплом

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелочка»	11:00	12:00	11:15	11:23	00:08	—	—
3	ИП Ахметова Н.П.	11:00	12:00	11:48	11:56	00:08	—	—
4	ООО «ТД»	12:00	13:00	12:13	12:21	00:08	—	—
5	Ресторан «Хуторок»	12:30	13:00	12:44	12:47	00:03	—	—
6	ОАО «ЭР-Телеком»	12:30	13:30	13:07	13:10	00:03	—	—
7	Кафе «Ритм»	11:00	19:00	13:23	00:06	—	—
8	Бар «Лаундж»	11:00	19:00	13:29	13:34	00:05	—	—
9	Кафе «Ударник»	11:00	19:00	13:42	13:48	00:06	—	—
10	Кафе «Сковородка»	14:00	16:00	13:52	14:04	00:04	00:08	—
11	Кафе «Кредо»	14:00	18:00	14:08	14:15	00:07	—	—
12	Ресторан «Охотничий»	13:30	15:30	14:19	14:26	00:07	—	—
13	ООО «Паритет»	14:00	15:00	14:29	14:34	00:05	—	—
14	Продуктовый магазин	12:00	16:00	14:48	14:57	00:09	—	—
15	ИП Кусакин А.В.	15:00	16:30	16:07	16:14	00:07	—	—
16	Ресторан «Сакартвело»	13:30	17:30	17:18	17:26	00:08	—	—
17	ТЦ «Столица»	13:00	18:00	17:42	17:47	00:05	—	—
18	ООО «Пушкин»	11:00	19:00	17:59	18:07	00:08	—	—
19	Кафе «Корица»	11:00	19:00	18:18	18:26	00:08	—	—
20	Продуктовый магазин	16:00	19:00	18:39	18:48	00:09	—	—
21	ТЦ «Евразия»	15:30	19:30	18:59	19:05	00:06	—	—
22	ООО «Микс — Семья»	15:00	22:00	19:13	19:22	00:09	—	—
23	Продуктовый магазин	18:00	21:00	19:29	19:38	00:09	—	—
24	ООО «Фабрика еды»	—	—	19:47	19:47	—	—	—

Отметим, что на первом этапе все временные окна были сокращены на 10 минут и найдено решение задачи. Затем, рассматривался максимально возможный параметр напряженности, который на третьей итерации составил 12 минут (именно данное решение анализируется далее в работе). Алгоритм за разумное время не выдает решения задачи с временным резервом в 13 минут и более, которое бы удовлетворяло всем ограничениям (например, водитель начинал опаздывать к различным покупателям, что является недопустимым для любой торговой фирмы). Подчеркнем, что маршрут водителя будет оптимальным только в том случае, если удовлетворяет всем временным интервалам покупателей. Используя описываемую процедуру, торговая компания сможет снизить вероятность недоставки продукции до минимума. Более того, компания может рассматривать установление разных временных резервов для покупателей (например, чем больше сумма заказа, тем больше резерв). Рассмотрим описываемый вариант решения задачи подробнее. Разделим всех клиентов, которым водитель № 1 доставлял продукцию, на 6 групп в зависимости от веса (в кг) (см. Рис. 4). На основе экспертных оценок водителя было установлено, что для первой группы клиентов из-за незначительного веса заказа

Рис. 4. Количество покупателей у водителя № 1 в зависимости от веса продукции (в кг)

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

параметр В работе для демонстративных целей предполагается, что

3 минуты. Таким образом, первый водитель будет приезжать ко всем покупателям не за 10 минут до конца временного окна, а за время, увеличивающееся в зависимости от размера заказа (к примеру, к контрагенту с весом продукции в 30 кг, водитель вынужден приехать за 15 минут до конца временного интервала). Отметим, что рассматриваемая эвристика может быть внедрена в любую торговую компанию путем изменения параметра Обобщенные сведения серии детерминированных задач к стохастической представлены ниже:

Таблица 4

Маршруты водителя № 1 в случае разных параметров надежности **

№ покупателя по порядку (см. Прил. 6)	Вариант № 1	Вариант № 2	Вариант № 3

ООО «Фабрика еды»	—	—	—
Кафе «Корица»	7:47	0:40	0:42
Столовая «Тарелочка»	0:25	0:45	0:45
ИП Ахметова Н.П.	0:02	0:12	0:12
Ресторан «Хуторок»	0:30	0:45	0:16
ООО «ТД»	0:05	0:05	0:47
ТЦ «Столица»	4:50	0:16	0:18
ОАО «ЭР-Телеком»	0:05	0:15	0:23
Кафе «Ритм»	5:25	5:35	5:43
Бар «Лаундж»	5:13	5:23	5:31
Кафе «Ударник»	5:00	4:40	5:18
Кафе «Сковородка»	1:50	1:30	2:08
Кафе «Кредо»	3:42	3:22	3:52
Ресторан «Охотничий»	1:01	1:40	1:11
ООО «Паритет»	0:21	0:52	0:31
Продуктовый магазин	1:02	1:10	1:12
ИП Кусакин А.В.	0:13	0:21	0:23
Ресторан «Сакартвело»	0:02	0:10	0:12
ООО «Пушкин»	1:14	0:59	1:01
ООО «Микс — Семья»	3:54	2:45	2:47
Продуктовый магазин	2:34	1:29	1:31
Продуктовый магазин	0:13	0:19	0:21
ТЦ «Евразия»	0:25	0:29	0:31
ООО «Фабрика еды»	—	—	—
Суммарное время водителя № 1 в пути	20:20	20:49	20:47

** — Вариант 1 — решение детерминированной задачи для водителя № 1 (без временных резервов) (см. Приложение 6), вариант 2 — решение детерминированной задачи для водителя № 1 с разными временными резервами в зависимости от размеров заказов (см. Приложение 7), вариант 3 — решение детерминированной задачи для водителя № 1 с максимальным временным резервом в 12 минут у каждого покупателя (см. таблицу 3). Сравнение резервов производится относительно варианта № 1.

Заметим, что оптимальный маршрут второго водителя представленный в Приложении 10, остался без изменений, поскольку априори удовлетворял ограничениям компании. Таким образом, в работе удалось приблизить решение серии детерминированных задач для водителя № 1 к стохастической путем установления различных временных резервов. Отметим, что наименьшее значение целевой функция достигается при параметре надежности равном 12 минутам у всех покупателей. Подчеркнем, что на первой итерации решения, задача рассматривалась для временного резерва в 10 минут. Затем временные окна покупателей сокращались на одну минуту, что привело к максимально возможному резерву времени — 12 минут. Вариант № 2 решения задачи (с временными резервами, зависящими от веса заказов) незначительно отличается от оптимального решения в терминах значений целевой функции. Заметим, что с точки зрения практического применения задачи, данный вариант не будет являться наилучшим, поскольку исследуемая фирма желает приезжать ко всем покупателям минимум за 10 минут до конца отгрузки (в описываемой модификации предполагается наличие меньших временных резервов). Тем не менее, вариант решения детерминированной задачи с различными временными резервами может применяться в других торговых компаниях, задавая приоритетность посещения покупателей в зависимости от параметра (см. таблицу 4, рис. 4).

После рассмотрения различных модификаций локального решения серии детерминированных задач для водителя №1, в работе предлагается разновидность ЗМТ с учетом дорожной ситуации в конкретный день рабочей недели для того, что максимально приблизить решение детерминированной ЗМТ для двух водителей к стохастической. Воспользуемся современными геоинформационными системами и сценарным анализом, предложив оптимизационную модель сетевого планирования для торговых предприятий. При помощи статистики Яндекс карт, которые фиксируют дорожную ситуацию в каждый момент времени в конкретный день, формируя хранилища информации о пробках на дорогах в разных городах России, удалось оптимизировать маршруты водителей в трех измерениях. С математической точки зрения, были взяты оптимальные планы доставки продукции покупателям у каждого водителя (см. таблицу 3, Приложение 10) и скорректированы на время проезда утром, днем и вечером. Фактически данный этап означал составление двух дополнительных асимметричных матриц расстояний на 2 704 ячейки каждая (первая матрица — утренняя, когда дорожная ситуация «благоприятная», вторая — вечерняя, в случае «неблагоприятных» пробок). «Умеренная» дорожная ситуация уже была получена и описана выше. В итоге, необходимо было решить 2 задачи маршрутизации транспорта с временными окнами покупателей и ограничением на грузоподъемность транспортных средств и получить 4 новых таблицы с маршрутами для двух водителей (см. Приложения 8, 9, 11, 12). Данный процесс автоматизирован в логистической программе «Умные маршруты» и позволяет решить вышеперечисленные задачи за небольшой промежуток времени. Таким образом, рассмотрев три сценария дорожной ситуации в г. Пермь в исследуемый день и скорректировав маршруты на коэффициенты пробок, посчитанные в Яндекс Картах, удалось наглядно представить результаты в виде сетевых графиков (см. Приложение 15, 16). Опишем вкратце две получившиеся сетевые модели, точнее их критические пути, поскольку алгоритм поиска с запретами уже сформировал оптимальные решения, которые получались бы при расчете критических путей в данных объемных сетевых диаграммах (с всеми возможными дорогами между каждым покупателем). На практике, водителям будут выдаваться именно разработанные в исследовании сетевые графики, представленные в Приложениях 15, 16, поскольку они являются не только удобными представлениями 6 решений оптимизационных задач коммивояжера, но и индивидуальными планами каждого водителя с собственными полными и свободными резервами времени. Отметим, что резервы времени рассчитываются каждым водителем индивидуально и самостоятельно по мере фактического посещения каждого контрагента в дневной заявке. Так, полный резерв времени, будет равен позднему времени отбытия от конкретного покупателя за вычетом раннего времени прибытия к данному контрагенту в случае «неблагоприятной» и «благоприятной» дорожной ситуации соответственно. Свободный резерв времени, подразумевает также вычет реального времени разгрузки у каждого покупателя. Таким образом, водитель будет знать и самостоятельно ориентироваться во времени между заказами в зависимости от разной дорожной обстановки утром (когда практически нет дорожных пробок), днем (когда они умеренные) и вечером (когда дорожная ситуация оценивается в 5 — 8 баллов). Характеризуя критические пути сетевых моделей, отметим, что у каждого покупателя имеется номер посещения водителем по порядку, среднее время проезда к нему в случае «умеренной» дорожной обстановки, раннее время прибытия при «благоприятных» пробках и позднее время отбытия при «неблагоприятной» дорожной ситуации. Более того, в сетевых моделях, представленных в Приложениях 15, 16, имеется время разгрузки у отдельно взятого покупателя (поскольку модели строились на примере конкретного дня). На практике, водитель не может знать и даже приблизительно оценивать сколько времени ему потребуется у каждого контрагента, поэтому полные и свободные резервы времени водитель сможет посчитать самостоятельно только после реальной доставки.

Отметим, что помимо сценарного анализа пробок, в работе приводится пример позиционного управления логистикой компании, который в отличие от программного управления, учитывает возникновение непредвиденных дорожных ситуаций. Алгоритм поиска с запретами обладает возможностью улучшать решение на каждой итерации, что на практике можно использовать для перерасчета маршрутов водителей, в случае если они выбиваются из графика. Рассмотрим данную особенность алгоритма на следующем примере. Представим, что водитель № 1, выезжая от контрагента № 16, в 15:07, столкнулся с дорожными работами, либо у него сел аккумулятор, подзарядка которого, как и проезд по объездной дороге, заняли бы в сумме 30 минут. Таким образом, водитель не успеет к покупателю № 17 в г. Добрянка и предприятие понесет потери продукции (возникает отрицательный свободный резерв времени):

Таблица 5

Пересчет маршрута в реальном времени (на примере водителя 1)

Нужна помощь в написании диплома?

Подробнее

№

Контрагент

Начало

Конец

Прибытие

Отбытие

Разгрузка

Простой

Опоздание

Продуктовый магазин

12:00

16:00

14:58

15:07

00:09

—

ИП Кусакин А.В.

15:00

16:30

16:17

16:24

00:07

—

Ресторан «Сакартвело»

13:30

17:30

15:54

16:02

00:08

—

ООО «Пушкин»

11:00

19:00

16:12

16:20

00:08

—

ООО «Микс — Семья»

15:00

22:00

16:32

16:41

00:09

—

Продуктовый магазин

16:00

19:00

16:52

17:01

00:09

—

ТЦ «Евразия»

15:30

19:30

17:19

17:35

00:06

—

Продуктовый магазин

18:00

21:00

17:48

17:57

00:09

—

ООО «Фабрика еды»

—

18:09

—

Несмотря на то, что водитель не выехал к контрагенту № 17, алгоритм поиска с запретами пересчитал последующий маршрут, изменив последовательность покупателей с № 21 по № 23 (для сравнения последовательности см. Приложение 6). Более того, фирма, возможно, успеет перепродать неотгруженную продукцию, так как водитель приедет в депо за 1:51 до конца рабочего дня. В итоге, произойдет оптимизация логистики в реальном времени (без данного решения водитель пытался бы доехать до

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

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

В результатах исследования, будет частично затронут процесс отбора заявок покупателей компанией ООО «Фабрика еды». Рассмотрим следующую ситуацию. В один из дней у фирмы имеется 40 заказов покупателей. Зная, что водитель максимум сможет развести только 30 (достаточно с плотным временным графиком доставки), необходимо каким-то образом сократить количество заявок до 30, максимизировав дневную выручку компании и загрузку автомобиля (по весу или объему). Очевидно, что в случае когда количество заявок у одного водителя не превышает 30, необходимость сокращения числа заказов априори отпадает — водитель с большой вероятностью сможет доставить всю заказанную продукцию (необходимо решить ЗМТ и предоставить водителю сетевые графики). Проблема отбора заявок возникает тогда, когда их больше 30 (например, возникает излишний спрос на мясопродукты ближе к выходным дням) и предприятию необходимо фильтровать покупателей в зависимости от суммы и размеров заказов. Именно после получения результатов ЗМТ, в данном исследовании удалось осознать необходимость решения задачи о ранце в дополнение к задаче коммивояжера и вкратце рассмотреть стандартную задачу о рюкзаке (12 — 14) в сфере логистики. Вернемся к предыдущему примеру, когда у ООО «Фабрика еды» за день до доставки имеется 40 заказов на одного водителя и представим один из вариантов их оптимального сокращения. Введем два основных предположения при решении стандартной задачи о ранце. Во-первых, заполняя автомобиль заказами, будем ориентироваться на цену и вес каждого заказа. Отметим, что в исследовании не случайно был взят именно вес, как один из параметров модели, а не объем заказа, поскольку габариты груза напрямую зависят от его веса (чем больше мясной продукции в заказе, тем больше объем). Во-вторых, в работе, решение задачи о рюкзаке не является основной целью, поэтому анализируется классическая формулировка задачи о ранце 0-1 (любой заказ может быть загружен в автомобиль только один раз) без дополнительных ограничений исходя из исключительно демонстративных целей. Отметим, что данную задачу можно так же подробно анализировать, как и задачу маршрутизации транспорта, применяя различные алгоритмы и рассматривая различные модификации задачи.

Для наглядности решения будем ориентироваться на суммарную грузоподъемность автомобиля равную 300 — 305 кг, поскольку эмпирически выяснено, что 300 кг продукции соответствует максимальному объему рефрижератора у транспортного средства для доставки охлажденного мяса. Более того, на практике было выяснено, что один водитель максимум может увести 30 заявок в день, не опаздывая ни к одному покупателю и не перерабатывая. Таким образом, экономико-математические ограничения являются не случайными, и диктуются реальными условиями работы фирмы ООО «Фабрика еды». Поскольку анализируемая задача является дополнением к общему процессу поиска оптимального плана перевозок торгового предприятия, решим ее достаточно простой эвристикой — «жадным алгоритмом», доказав оптимальность полученного решения. На первом этапе оптимизации, одному из двух водителей компании, был предложен список из 40 заказов, а также их веса и цены. Водителю необходимо было в течении 5 минут, отобрать к себе в автомобиль 30 заявок, которые бы максимизировали выручку фирмы и не превышали 300 — 305 кг. По истечении времени, водитель ООО «Фабрика еды», предоставил решение с выручкой равной

172 770 рублей и суммарным весом 326 кг, что было больше грузоподъемности автомобиля. В ходе решения задачи водитель использовал простейший алгоритм сортировки всех заказов по убыванию цены: отбирались первые 30 заявок в списке (с максимальной ценой), без учета веса (см. Приложение 19).

Следующим этапом решения стала, так называемая, «случайная эвристика» — заявки были расположены по мере их фактического поступления и были взяты первые 30 из списка. В результате выручка стала равна 149 350 кг, а вес стал меньше и составил 284 кг (см. Приложение 17). Заметим, что первые два вида решений задачи о рюкзаке являются неоптимальными поскольку не учитывают одновременно два входных параметра — вес и цену заказа, а учитывают их по отдельности. Рассмотрим решение задачи жадным алгоритмом, в основе которого лежит простая эвристика — необходимо поделить цену на вес заказа (получив стоимость 1 кг заявки в рублях) и отсортировать их по убыванию данного показателя, взяв первые 30. В итоге, выручка получилась 162 480 рублей, а вес 302 кг, что удовлетворяет всем ограничениям задачи (см. Приложение 18). Очевидно, что существуют различные алгоритмы решения задачи о рюкзаке, которые находят более точное и оптимальное решение, чем вышеописанное. Жадный алгоритм был использован для простоты и наглядности достижения лучшего решения задачи. Полученный список заявок является оптимальным, поскольку, он выгодней, чем список сформированный водителем на практике. Решение сотрудника фирмы, имея большую выручку, должно быть сокращено по весу, что приведёт к снижению дохода в среднем на 12 000 — 13 000, что является меньшим значением по сравнению с жадным алгоритмом.

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

Возвращаясь, к решению задачи маршрутизации транспорта с временными окнами и ограничением на грузоподъемность автомобилей, можно заметить, что не все контрагенты в исследуемом дне являются «проблемными» для фирмы. Оказалось, что существует закономерность между длинной временного интервала доставки у i-го покупателя и возвратами продукции (Azi, et al., 2012). Как отмечалось выше, в исследовании рассматривается случайно выбранный день в котором один из водителей опоздал в г. Добрянка к покупателю с временным окном отгрузки в 90 минут. Более того, работая с базой данных предприятия, а именно с реальными дневными отгрузками на протяжении 6 — 7 месяцев (с того момента, когда в фирме появился второй водитель), было выяснено, что возврат продукции осуществляется покупателями у которых временной интервал доставки менее двух часов. Отметим, что неудовлетворенность некоторых контрагентов, связанная с опозданием водителей, не коррелировала с местонахождением покупателей, поскольку у

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

В результатах данной работы предлагается способ оптимизации дизайна контракта торговой фирмы, путем создания сигналов для покупателей к расширению временных окон доставки. Таким образом, компания еще до начала формирования оптимальных маршрутов сможет оптимизировать транспортировку продукции. Предприятие может создать такие стимулы тремя способами: сделать скидку за расширение временного интервала доставки, ввести надбавку к цене за сокращение окна получения продукции или мотивировать покупателя не денежным способом. Рассмотрим каждую стратегию, выбрав наиболее состоятельную и эффективную. Представим, что ООО «Фабрика еды» делает минимальную скидку в размере 5 % от общей суммы заказа при установке временного интервала доставки продукции не менее 2 часов. Покупатели (рациональные экономические агенты), узнав о скидке изменят свои временные окна так, чтобы любым способом достичь даже незначительного уменьшения стоимости заказа. С другой стороны, фирме — поставщику, необходимо сравнить свои издержки от возвратов продукции, например, за месяц, с альтернативными издержками (упущенной выручкой при введении скидки). Для ООО «Фабрика еды», упущенные выгоды от использования скидки превышают издержки возвратов продукции покупателей в 4 — 5 раз, что является недопустимым для торгового предприятия. Анализируя стратегию повышения цены (суммы заказа) для покупателей, можно также прийти к ее неэффективности. В условиях современной экономической ситуации, а также наличия большого количество конкурентов на рынке мясной продукции, ООО «Фабрика еды» не сможет постоянно увеличивать цены выше рыночных. Придерживаясь стратегии «штрафования» покупателей за сужение временного окна доставки, фирма-поставщик будет либо «отпугивать» новых контрагентов, либо нести убытки из-за их отсутствия. Таким образом, два варианта оптимизации контракта, апеллирующие к цене продукции предприятия или к обще сумме заказа являются неэффективными, поскольку не приводят к изменению поведения контрагентов. Покупатели либо переключатся на другого поставщика из-за высокой конкуренции на рынке, либо будут продолжать устанавливать те интервалы доставки, которые им необходимы.

Рассмотрим возможность оптимизации контракта торговой фирмы не денежным способом. Приведём простой пример избегания дополнительных юридических издержек фирмой, заключающей неоклассический контракт с покупателем. Известно, что в контракте невозможно прописать все будущие разногласия сторон, поэтому в договор добавляется фраза: «Все конфликтные ситуации регулируются на основании законодательства Российской Федерации и решаются через суд», которая позволяет прояснить как способы действий покупателя, так и сократить юридические издержки фирмы. С точки зрения логистики, торговому предприятию также необходимо подобрать такие слова в контракте, которые бы косвенно повлияли на решение контрагента о сокращении временного окна доставки. Примером такой фразы для ООО «Фабрика еды» могут являться следующие предложения: «Покупатели, ожидающие доставку продукции в интервал длительностью менее двух часов, имеют вероятность 5 — 7 % опоздания водителя. Контрагенты, устанавливающие время отгрузки более двух часов, имеют близкую к максимальной вероятность доставки продукции вовремя». Таким образом, фирма будет сигнализировать покупателям, о возможности не доставки продукции в ожидаемый интервал, что создаст стимул для контрагентов расширить свои временные окна отгрузки. В результате данного анализа выяснилось, что для управления логистикой на предприятии недостаточно одного решения задачи маршрутизации транспорта и задачи об оптимальной загрузке транспортных средств. Фирме необходимо также проводить анализ своих покупателей, выявляя «проблемных» и оптимизировать контракты с ними.

Заключение

Нужна помощь в написании диплома?

Заказать диплом

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

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

В работе проводится анализ основных научных статей по теме. Выяснено, что первое упоминание о КЗК (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 тыс. рублей в месяц.

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

Нужна помощь в написании диплома?

Заказать диплом

) Решить более сложные модификации задачи о ранце 0-1, внедрив в нее различные ограничения;

) Рассмотреть подробно оптимизацию дизайна контрактов, описав функцию полезности покупателей;

) Оптимизировать процесс управления скоропортящимися запасами.

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

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

1) Бронштейн, Е.М., Заико, Т.А. (2010), «Детерминированные оптимизационные задачи транспортной логистики», Автоматика и телемеханика, №10, с. 133-147.

) Иглин, С.П. (2003), «Решение некоторых задач теории графов в MATLAB», Математика в приложениях, №4, с. 28-33.

) Костюк, Ю.Л. (2013), «Эффективная реализация алгоритма решения задачи коммивояжера методом ветвей и границ», Прикладная дискретная математика, Т. 20,№ 2, с. 78-90.

) Курейчик, В.М., Мартынов, А.В. (2014), «Об алгоритмах решения задачи коммивояжера с временными ограничениями», Информатика, вычислительная техника и инженерное образование, Т. 16, № 1, с. 1-13.

) Лебедев, Б.K., Лебедев, О.Б. (2012), «Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями», Известия ЮФУ. Технические науки, Т. 132, № 7, с. 27-34.

) Лопатин, А.С. (2005), «Метод отжига», Стохастическая оптимизация в информатике, Т.1. №1, с. 133-139.

) Макконнелл, Дж. (2004), Основы современных алгоритмов, М: Техносфера,с. 233-255.

) Пантелеев, А.В., Метлицкая, Д.В., Алешина, Е.А. (2013), Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы, Москва, с. 105-130.

) Хайруллин, Р.З. (2014), «Математическое моделирование развоза грузов по разветвленной сети автодорог», Вестник МГСУ, № 7, с. 184-191.

Нужна помощь в написании диплома?

Подробнее

) Чеблоков, И.Б., Ченцов, А.Г. (2012), «Об одной задаче маршрутизации с внутренними работами», Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, № 1, с. 96-119.

) Applegate D., Cook J. (1993), “Solving large-scale matching problems”, Network Flows and Matching, pp. 557-576.

) Azi, N., Gendreau, M. and Potvin, J.-Y. (2012), “A dynamic vehicle routing problem with multiple delivery routes”, Annals of Operations Research, pp. 1-10.

) Baldacci, R., Mingozzi, A. and Roberti, R. (2012), “Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints”, European Journal of Operational Research, Vol. 218, No. 1, pp. 11-26.

) Clarke, G., Wright, J.W. (1964), “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, No. 12, 568-581.

) Croes, G.A. (1958), “A method for solving traveling salesman problems”, Operations Research, No. 6, pp. 791-812.

) Dantzig, G. B., Ramser, J. H. (1959), “The truck dispatching problem”, Management Science, Vol. 6, No. 1, pp. 80-91.

) Desrochers, M., Desrosiers, J. and Solomon, M. (1992), “A new optimization algorithm for the vehicle routing problem with time windows”, Operations Research, No. 40,pp. 342-354.

) Dorigo, M. (1999), “Ant algorithms for discrete optimization”, Artificial life, Vol. 5, No. 2, pp. 137-172.

) Irnich, S. (2008), “Solution of real-world postman problems”, European Journal of Operational Research, Vol. 190, No. 1, pp. 52-67.

) Kan, A.R., Lenstra, J.K. (1975), “Some simple applications of the travelling salesman problem”, Operations Research, No. 26, pp. 717-734.

) Laporte, G. (1992), “The Vehicle Routing Problem: An Overview of Exact and Approximative Algorithms”, European Journal of Operational Research, Vol. 59, No. 3,pp. 345-358.

) Lin, S., Kernighan, B.W. (1973), “An effective Heuristic Algorithm for the TSP”. Operations Research, No. 21, pp. 498-516.

) Lorini, S., Potvin, J.-Y. and Zufferey, N. (2011), “Online vehicle routing and scheduling with dynamic travel times”, Computers & Operations Research, Vol. 38, No. 7,pp. 1086-1090.

) Moon, I., Lee, J. and Seong, J. (2012), “Vehicle routing problem with time windows considering overtime and outsourcing vehicles”, Expert Systems with Applications, Vol. 39, No.18, pp. 13202-13213.

) Rodriguez, A., Ruiz, R. (2012), “A study on the effect of the asymmetry on real capacitated vehicle routing problems”, Computers & Operations Research, Vol. 39, No. 9,. 2142-2151.

) Schneider, J.J., Bukur, T. and Krause, A. (2010), “Traveling salesman problem with clustering”, Journal of Statistical Physics, Vol. 141, No. 5, pp. 767-784.

) Solomon, M. M. (1987), “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operations Research, Vol. 35, No. 2, pp. 254-265.

) Toth, P. and Vigo D. (2002), The Vehicle routing problem, Society for Industrial and Applied Mathematics, p. 386

) Wiener, J. M., Ehbauer, N. N. and Mallot, H. A. (2009), “Planning paths to multiple targets”, Psychological Research, No. 73, pp. 644-658.

Приложение 1

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	ООО «Веселый пекарь»	11:00	14:00	11:05	11:11	00:06	—	—
3	Столовая «Тарелка №1»	11:00	11:30	11:22	11:29	00:07	—	—
4	Столовая «Тарелка №2»	11:00	12:00	11:41	11:44	00:03	—	—
5	Кафе «Паста Гранде»	12:00	13:30	11:52	12:09	00:09	00:08	—
6	Ресторан «Кама-Фиш»	12:00	12:30	12:13	12:19	00:06	—	—
7	Ресторан «Горький»	11:30	12:00	12:26	12:30	00:04	—	00:26
8	Кафе «Правила»	11:00	14:00	12:35	12:38	00:03	—	—
9	Столовая «Тарелочка»	11:00	12:00	12:46	12:54	00:08	—	00:46
10	ОАО «ЭР-Телеком»	12:30	13:30	13:04	13:07	00:03	—	—
11	ООО «ТД»	12:00	13:00	13:24	13:32	00:08	—	00:24
12	ТЦ «Столица»	13:00	18:00	13:45	13:50	00:05	—	—
13	ЗАО «Пермторгтехника»	13:00	14:00	14:06	14:11	00:05	—	00:06
14	ООО «Море рыбы»	12:00	16:00	14:18	14:24	00:06	—	—
15	ООО «Эверест»	14:00	17:00	14:34	14:41	00:07	—	—
16	Ресторан «Пармезан»	12:30	15:30	14:45	14:53	00:08	—	—
17	ООО «Цертина»	15:00	16:00	14:59	15:07	00:08	—	—
18	Ресторан «Охотничий»	13:30	15:30	15:15	15:22	00:07	—	—
19	ООО «Паритет»	14:00	15:00	15:26	15:31	00:05	—	00:26
20	Кафе «Кредо»	14:00	18:00	15:35	15:42	00:07	—	—
21	Кафе «Сковородка»	14:00	16:00	15:46	15:50	00:04	—	—
22	Ресторан «Casa Mia»	13:00	17:00	15:58	16:06	00:08	—	—
23	ООО «Гарант плюс»	15:00	16:30	16:10	16:13	00:03	—	—
24	Ресторан «Тсуру»	11:00	19:00	16:17	16:22	00:05	—	—
25	Продуктовый магазин	12:00	16:00	16:27	16:36	00:09	—	00:27
26	ООО «Пушкин»	11:00	19:00	16:40	16:48	00:08	—	—
27	Ресторан «Сакартвело»	13:30	17:30	16:54	17:02	00:08	—	—
28	Продуктовый магазин	16:00	19:30	17:07	17:12	00:05	—	—
29	Ресторан «Сакартвело»	12:00	18:00	17:16	17:21	00:05	—	—
30	15:00	19:00	17:25	17:32	00:07	—	—
31	Ресторан «Партизан»	13:30	18:30	17:38	17:41	00:03	—	—
32	Кафе «Корица»	11:00	19:00	17:48	17:56	00:08	—	—
33	Бар «Лаундж»	11:00	19:00	18:03	18:08	00:05	—	—
34	Кафе «Ударник»	11:00	19:00	18:14	18:20	00:06	—	—
35	ООО «ПМП»	15:00	19:00	18:30	18:34	00:04	—	—
36	ООО «Заполье»	17:00	19:30	18:38	18:43	00:05	—	—
37	Пиццерия «Pizzaman»	17:00	19:30	18:54	18:57	00:03	—	—
38	Кафе «Ритм»	11:00	19:00	19:01	19:07	00:06	—	00:01
39	Столовая «Забава»	15:00	19:00	19:14	19:19	00:05	—	00:14
40	Ресторан «Тсуру»	17:00	20:00	19:28	19:36	00:08	—	—
41	Ресторан «Casa Mia»	11:00	20:00	19:41	19:44	00:03	—	—
42	Ресторан Нефертити	11:00	19:00	19:50	19:57	00:07	—	00:50
43	ООО «Компания ЦВР»	11:00	21:00	20:04	20:07	00:03	—	—
44	ТЦ «Евразия»	15:30	19:30	20:18	20:24	00:06	—	00:48
45	Продуктовый магазин	16:00	19:00	20:34	20:43	00:09	—	01:34
46	ООО «Микс — Семья»	15:00	22:00	21:00	21:09	00:09	—	—
47	Ресторан «Халва»	14:00	20:00	21:19	21:27	00:08	—	01:19
48	ООО «Федерал»	18:00	20:00	21:50	21:55	00:05	—	01:50
49	Ресторан «Хуторок»	12:30	13:00	22:30	22:33	00:03	—	09:30
50	ИП Ахметова Н.П.	11:00	12:00	22:56	23:04	00:08	—	10:56
51	Продуктовый магазин	18:00	21:00	23:45	23:54	00:09	—	02:45
52	ИП Кусакин А.В.	15:00	16:30	01:31	01:38	00:07	—	09:01
53	ООО «Фабрика еды»	—	—	03:27	03:27	—	—	07:27

Приложение 2

Оптимизированный маршрут водителя № 1

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	ООО «Веселый пекарь»	11:00	14:00	11:05	11:11	00:06	—	—
3	Ресторан Нефертити	11:00	19:00	11:21	11:28	00:07	—	—
4	Ресторан «Горький»	11:30	12:00	11:35	11:39	00:04	—	—
5	ИП Ахметова Н.П.	11:00	12:00	11:57	12:05	00:08	—	—
6	Ресторан «Кама-Фиш»	12:00	12:30	12:25	12:31	00:06	—	—
7	ООО «ТД»	12:00	13:00	12:51	12:59	00:08	—	—
8	Ресторан «Casa Mia»	11:00	20:00	13:15	13:18	00:03	—	—
9	Продуктовый магазин	12:00	16:00	13:23	13:32	00:09	—	—
10	Кафе «Корица»	11:00	19:00	13:37	13:45	00:08	—	—
11	Кафе «Сковородка»	14:00	16:00	13:50	14:04	00:04	00:10	—
12	Ресторан «Тсуру»	11:00	19:00	14:11	14:16	00:05	—	—
13	Ресторан «Casa Mia»	13:00	17:00	14:20	14:28	00:08	—	—
14	Ресторан «Пармезан»	12:30	15:30	14:45	14:53	00:08	—
15	ООО «Гарант плюс»	15:00	16:30	15:00	15:03	00:03	—	—
16	ООО «Море рыбы»	12:00	16:00	15:10	15:16	00:06	—	—
17	ИП Кусакин А.В.	15:00	16:30	16:25	16:32	00:07	—	—
18	Кафе «Кредо»	14:00	18:00	17:50	17:57	00:07	—	—
19	Продуктовый магазин	16:00	19:00	18:05	18:14	00:09	—	—
20	ООО «Компания ЦВР»	11:00	21:00	18:20	18:23	00:03	—	—
21	Столовая «Забава»	15:00	19:00	18:27	18:32	00:05	—	—
22	Пиццерия «Pizzaman»	17:00	19:30	18:39	18:42	00:03	—	—
23	Бар «Лаундж»	11:00	19:00	18:50	18:55	00:05	—	—
24	ТЦ «Евразия»	15:30	19:30	19:10	19:16	00:06	—	—
25	ООО «Заполье»	17:00	19:30	19:26	19:31	00:05	—	—
26	Продуктовый магазин	18:00	21:00	19:42	19:51	00:09	—	—
27	ООО «Микс — Семья»	15:00	22:00	20:00	20:09	00:09	—	—
28	ООО «Фабрика еды»	—	—	20:20	20:20	—	—	00:20

Приложение 3

Оптимизированный маршрут водителя № 2

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелка №1»	11:00	11:30	11:08	11:15	00:07	—	—
3	Столовая «Тарелка №2»	11:00	12:00	11:27	11:30	00:03	—	—
4	Столовая «Тарелочка»	11:00	12:00	11:44	11:52	00:08	—	—
5	Ресторан «Хуторок»	12:30	13:00	12:22	12:33	00:03	00:08	—
6	ОАО «ЭР-Телеком»	12:30	13:30	13:09	13:12	00:03	—	—
7	Кафе «Паста Гранде»	12:00	13:30	13:22	13:31	00:09	—	—
8	Кафе «Правила»	11:00	14:00	13:38	13:41	00:03	—	—
9	ЗАО «Пермторгтехника»	13:00	14:00	13:56	14:01	00:05	—	—
10	ООО «Эверест»	14:00	17:00	14:09	14:16	00:07	—	—
11	ООО «Паритет»	14:00	15:00	14:26	14:31	00:05	—	—
12	Ресторан «Охотничий»	13:30	15:30	14:35	14:42	00:07	—	—
13	ООО «Цертина»	15:00	16:00	14:52	15:07	00:07	00:08	—
14	ООО «Пушкин»	11:00	19:00	15:14	15:22	00:08	—	—
15	Ресторан «Сакартвело»	13:30	17:30	15:27	15:35	00:08	—	—
16	Продуктовый магазин	16:00	19:30	15:41	16:05	00:05	00:19	—
17	Ресторан «Сакартвело»	12:00	18:00	16:09	16:14	00:05	—	—
18	Ресторан «Халва»	15:00	19:00	16:18	16:25	00:07	—	—
19	Ресторан «Халва»	14:00	20:00	16:32	16:40	00:08	—	—
20	Ресторан «Партизан»	13:30	18:30	16:49	16:52	00:03	—	—
21	Ресторан «Тсуру»	17:00	20:00	16:57	17:08	00:08	00:03	—
22	Кафе «Ударник»	11:00	19:00	17:15	17:21	00:06	—	—
23	ООО «ПМП»	15:00	19:00	17:31	17:35	00:04	—	—
24	ТЦ «Столица»	13:00	18:00	17:52	17:57	—	—
25	ООО «Федерал»	18:00	20:00	18:10	18:15	00:05	—	—
26	Кафе «Ритм»	11:00	19:00	18:30	18:36	00:06	—	—
27	ООО «Фабрика еды»	—	—	18:53	18:53	—	—	—

Приложение 4

Маршрут водителя № 1. Кластерный анализ

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Ресторан Нефертити	11:00	19:00	11:13	11:20	00:07	—	—
3	Столовая «Тарелка №2»	11:00	12:00	11:29	11:32	00:03	—	—
4	Ресторан «Горький»	11:30	12:00	11:42	11:46	00:04	—	—
5	Кафе «Правила»	11:00	14:00	11:52	11:55	00:03	—	—
6	Ресторан «Тсуру»	11:00	19:00	11:59	12:04	00:05	—	—
7	Ресторан «Кама-Фиш»	12:00	12:30	12:10	12:16	00:06	—	—
8	Кафе «Паста Гранде»	12:00	13:30	12:20	12:29	00:09	—	—
9	Ресторан «Casa Mia»	11:00	20:00	12:33	12:36	00:03	—	—
10	Кафе «Корица»	11:00	19:00	12:41	12:49	00:08	—	—
11	Продуктовый магазин	12:00	16:00	12:55	13:04	00:09	—	—
12	ООО «Пушкин»	11:00	19:00	13:08	13:16	00:08	—	—
13	Ресторан «Сакартвело»	13:30	17:30	13:21	13:38	00:08	00:09	—
14	Ресторан «Сакартвело»	12:00	18:00	13:45	13:50	00:05	—	—
15	Ресторан «Халва»	14:00	20:00	13:57	14:08	00:08	00:03	—
16	Ресторан «Casa Mia»	13:00	17:00	14:15	14:23	00:08	—	—
17	Ресторан «Партизан»	13:30	18:30	14:28	14:31	00:03	—	—
18	ООО «Гарант плюс»	15:00	16:30	14:35	15:03	00:03	00:25	—
19	ООО «Цертина»	15:00	16:00	15:11	15:18	00:07	—	—
20	ИП Кусакин А.В.	15:00	16:30	17:02	17:09	00:07	—	00:32
21	Ресторан «Халва»	15:00	19:00	18:52	18:59	00:07	—	—
22	Ресторан «Тсуру»	17:00	20:00	19:04	19:12	00:08	—	—
23	Продуктовый магазин	16:00	19:30	19:20	19:25	00:05	—	—
24	Продуктовый магазин	18:00	21:00	19:40	19:49	00:09	—	—
25	ООО «Микс — Семья»	15:00	22:00	20:06	20:15	00:09	—	—
26	ООО «Фабрика еды»	—	—	20:31	20:31	—	—	00:31

Приложение 5

Маршрут водителя № 2. Кластерный анализ

Нужна помощь в написании диплома?

Заказать диплом

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелка №1»	11:00	11:30	11:08	11:15	00:07	—	—
3	Столовая «Тарелочка»	11:00	12:00	11:31	11:39	00:08	—	—
4	ИП Ахметова Н.П.	11:00	12:00	12:07	12:15	00:08	—	00:07
5	Ресторан «Хуторок»	12:30	13:00	12:38	12:41	00:03	—	—
6	ООО «ТД»	12:00	13:00	13:15	13:23	00:08	—	00:15
7	ОАО «ЭР-Телеком»	12:30	13:30	13:40	13:43	00:03	—	00:10
8	ЗАО «Пермторгтехника»	14:00	13:57	14:02	00:05	—	—
9	ООО «Веселый пекарь»	11:00	14:00	14:10	14:16	00:06	—	00:10
10	ООО «Паритет»	14:00	15:00	14:35	14:40	00:05	—	—
11	Кафе «Сковородка»	14:00	16:00	14:45	14:49	00:04	—	—
12	Ресторан «Охотничий»	13:30	15:30	14:55	15:02	00:07	—	—
13	Ресторан «Пармезан»	12:30	15:30	15:12	15:20	00:08	—	—
14	ООО «Море рыбы»	12:00	16:00	15:32	15:38	00:06	—	—
15	Продуктовый магазин	16:00	19:00	15:44	16:09	00:09	00:16	—
16	ТЦ «Евразия»	15:30	19:30	16:19	16:25	00:06	—	—
17	ООО «Эверест»	14:00	17:00	16:34	16:41	00:07	—	—
18	Столовая «Забава»	15:00	19:00	16:48	16:53	00:05	—	—
19	ТЦ «Столица»	13:00	18:00	17:02	17:07	00:05	—	—
20	Кафе «Ритм»	11:00	19:00	17:16	17:22	00:06	—	—
21	Пиццерия «Pizzaman»	17:00	19:30	17:26	17:29	00:03	—	—
22	Кафе «Кредо»	14:00	18:00	17:36	17:43	00:07	—	—
23	Бар «Лаундж»	11:00	19:00	17:47	17:52	00:05	—	—
24	Кафе «Ударник»	11:00	19:00	17:57	18:03	00:06	—	—
25	ООО «Заполье»	17:00	19:30	18:15	18:20	00:05	—	—
26	ООО «ПМП»	15:00	19:00	18:24	18:28	00:04	—	—
27	ООО «Федерал»	18:00	20:00	18:45	18:50	00:05	—	—
28	ООО «Компания ЦВР»	11:00	21:00	19:09	19:12	00:03	—	—
29	ООО «Фабрика еды»	—	—	19:24	19:24	—	—	—

Приложение 6

Решение ЗМТ («умеренная» дорожная ситуация) для водителя № 1

без учета резерва времени в 10 минут

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Кафе «Корица»	11:00	19:00	11:13	11:21	00:08	—	—
3	Столовая «Тарелочка»	11:00	12:00	11:35	11:43	00:08	—	—
4	ИП Ахметова Н.П.	11:00	12:00	11:58	12:06	00:08	—	—
5	Ресторан «Хуторок»	12:30	13:00	12:30	12:33	00:03	—	—
6	ООО «ТД»	12:00	13:00	12:55	13:03	00:08	—	—
7	ТЦ «Столица»	13:00	18:00	13:10	13:15	00:05	—	—
8	ОАО «ЭР-Телеком»	12:30	13:30	13:25	13:28	00:03	—	—
9	Кафе «Ритм»	11:00	19:00	13:35	13:41	00:06	—	—
10	Бар «Лаундж»	11:00	19:00	13:47	13:52	00:05	—	—
11	Кафе «Ударник»	11:00	19:00	14:00	14:06	00:06	—	—
12	Кафе «Сковородка»	14:00	16:00	14:10	14:14	00:04	—	—
13	Кафе «Кредо»	14:00	18:00	14:18	14:25	00:07	—	—
14	Ресторан «Охотничий»	13:30	15:30	14:29	14:36	00:07	—	—
15	ООО «Паритет»	14:00	15:00	14:39	14:44	00:05	—	—
16	Продуктовый магазин	12:00	16:00	14:58	15:07	00:09	—
17	ИП Кусакин А.В.	15:00	16:30	16:17	16:24	00:07	—	—
18	Ресторан «Сакартвело»	13:30	17:30	17:28	17:36	00:08	—	—
19	ООО «Пушкин»	11:00	19:00	17:46	17:54	00:08	—	—
20	ООО «Микс — Семья»	15:00	22:00	18:06	18:15	00:09	—	—
21	Продуктовый магазин	18:00	21:00	18:26	18:35	00:09	—	—
22	Продуктовый магазин	16:00	19:00	18:47	18:56	00:09	—	—
23	ТЦ «Евразия»	15:30	19:30	19:05	19:11	00:06	—	—
24	ООО «Фабрика еды»	—	—	19:20	19:20	—	—	—

Приложение 7

Решение ЗМТ («умеренная» дорожная ситуация) для водителя № 1

с различными резервами времени (зависимость от веса)

№КонтрагентНачалоКонецПрибытиеОтбытиеРазгрузкаПростойОпоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелочка»	11:00	12:00	11:15	11:23	0:08	—	—
3	ИП Ахметова Н.П.	11:00	12:00	11:48	11:56	0:08	—	—
5	Ресторан «Хуторок»	12:30	13:00	12:15	12:33	0:03	0:15	—
4	ООО «ТД»	12:00	13:00	12:55	13:03	0:08	—	—
6	ОАО «ЭР-Телеком»	12:30	13:30	13:15	13:18	0:03	—	—
7	Кафе «Ритм»	11:00	19:00	13:25	13:31	0:06	—	—
8	Бар «Лаундж»	11:00	19:00	13:37	13:42	0:05	—	—
12	Ресторан «Охотничий»	13:30	15:30	13:50	13:57	0:07	—	—
13	ООО «Паритет»	14:00	15:00	14:08	14:13	0:05	—	—
9	Кафе «Ударник»	11:00	19:00	14:20	14:26	0:06	—	—
10	Кафе «Сковородка»	14:00	16:00	14:30	14:34	0:04	—	—
11	Кафе «Кредо»	14:00	18:00	14:38	14:45	0:07	—	—
14	Продуктовый магазин	12:00	16:00	14:50	14:59	0:09	—	—
15	ИП Кусакин А.В.	15:00	16:30	16:09	16:16	0:07	—	—
16	Ресторан «Сакартвело»	13:30	17:30	17:20	17:28	0:08	—	—
17	ТЦ «Столица»	13:00	18:00	17:44	17:52	0:05	—	—
18	ООО «Пушкин»	11:00	19:00	18:01	18:09	0:08	—	—
19	Кафе «Корица»	11:00	19:00	18:20	18:28	0:08	—	—
20	Продуктовый магазин	16:00	19:00	18:41	18:50	0:09	—	—
21	ТЦ «Евразия»	15:30	19:30	19:01	19:07	0:06	—	—
22	ООО «Микс — Семья»	15:00	22:00	19:15	19:24	0:09	—	—
23	Продуктовый магазин	18:00	21:00	19:31	19:40	0:09	—	—
24	ООО «Фабрика еды»	—	—	19:49	19:49	—	—	—

Приложение 8

Решение ЗМТ («благоприятная» дорожная ситуация) для водителя № 1

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелочка»	11:00	12:00	11:13	11:21	00:08	—	—
3	ИП Ахметова Н.П.	11:00	12:00	11:43	11:51	00:08	—	—
4	ООО «ТД»	12:00	13:00	12:06	12:14	00:08	—	—
5	Ресторан «Хуторок»	12:30	13:00	12:34	12:37	00:03	—	—
6	ОАО «ЭР-Телеком»	13:30	12:55	12:58	00:03	—	—
7	Кафе «Ритм»	11:00	19:00	13:04	13:10	00:06	—	—
8	Бар «Лаундж»	11:00	19:00	13:15	13:20	00:05	—	—
9	Кафе «Ударник»	11:00	19:00	13:27	13:33	00:06	—	—
10	Кафе «Сковородка»	14:00	16:00	13:37	14:04	00:04	00:23	—
11	Кафе «Кредо»	14:00	18:00	14:08	14:15	00:07	—	—
12	Ресторан «Охотничий»	13:30	15:30	14:18	14:25	00:07	—	—
13	ООО «Паритет»	14:00	15:00	14:28	14:33	00:05	—	—
14	Продуктовый магазин	12:00	16:00	14:45	14:54	00:09	—	—
15	ИП Кусакин А.В.	15:00	16:30	16:01	16:08	00:07	—	—
16	Ресторан «Сакартвело»	13:30	17:30	17:12	17:20	00:08	—	—
17	ТЦ «Столица»	13:00	18:00	17:32	17:37	00:05	—	—
18	ООО «Пушкин»	11:00	19:00	17:49	17:57	00:08	—	—
19	Кафе «Корица»	11:00	19:00	18:06	18:14	00:08	—	—
20	Продуктовый магазин	16:00	19:00	18:25	18:34	00:09	—	—
21	ТЦ «Евразия»	15:30	19:30	18:43	18:49	00:06	—	—
22	ООО «Микс — Семья»	15:00	22:00	18:56	19:05	00:09	—	—
23	Продуктовый магазин	18:00	21:00	19:11	19:20	00:09	—	—
24	ООО «Фабрика еды»	—	—	19:28	19:28	—	—	—

Приложение 9

Решение ЗМТ («неблагоприятная» дорожная ситуация) для водителя № 1

Нужна помощь в написании диплома?

Подробнее

№КонтрагентНачалоКонецПрибытиеОтбытиеРазгрузкаПростойОпоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелочка»	11:00	12:00	11:17	11:25	00:08	—	—
3	ИП Ахметова Н.П.	11:00	12:00	11:55	12:03	00:08	—	—
4	ООО «ТД»	12:00	13:00	12:20	12:28	00:08	—	—
5	Ресторан «Хуторок»	12:30	13:00	12:51	12:54	00:03	—	—
6	ОАО «ЭР-Телеком»	12:30	13:30	13:15	13:18	00:03	—	—
7	Кафе «Ритм»	11:00	19:00	13:26	13:32	00:06	—	—
8	Бар «Лаундж»	11:00	19:00	13:38	13:43	00:05	—	—
9	Кафе «Ударник»	11:00	19:00	13:51	13:57	00:06	—	—
10	Кафе «Сковородка»	14:00	16:00	14:01	14:05	00:04	—	—
11	Кафе «Кредо»	14:00	18:00	14:09	14:16	00:07	—	—
12	Ресторан «Охотничий»	13:30	15:30	14:20	14:27	00:07	—	—
13	ООО «Паритет»	14:00	15:00	14:31	14:36	00:05	—	—
14	Продуктовый магазин	12:00	16:00	14:51	15:00	00:09	—	—
15	ИП Кусакин А.В.	15:00	16:30	16:13	16:20	00:07	—	—
16	Ресторан «Сакартвело»	13:30	17:30	17:26	17:34	00:08	—	—
17	ТЦ «Столица»	13:00	18:00	17:51	17:56	00:05	—	—
18	ООО «Пушкин»	11:00	19:00	18:10	18:18	00:08	—	—
19	Кафе «Корица»	11:00	19:00	18:31	18:39	00:08	—	—
20	Продуктовый магазин	16:00	19:00	18:54	19:03	00:09	—
21	ТЦ «Евразия»	15:30	19:30	19:16	19:22	00:06	—	—
22	ООО «Микс — Семья»	15:00	22:00	19:32	19:41	00:09	—	—
23	Продуктовый магазин	18:00	21:00	19:51	20:00	00:09	—	—
24	ООО «Фабрика еды»	—	—	20:10	20:10	—	—	00:10

Приложение 10

Решение ЗМТ («умеренная» дорожная ситуация) для водителя № 2

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелка №1»	11:00	11:30	11:08	11:15	00:07	—	—
3	Столовая «Тарелка №2»	11:00	12:00	11:27	11:30	00:03	—	—
4	Ресторан «Горький»	11:30	12:00	11:42	11:46	00:04	—	—
5	Кафе «Правила»	11:00	14:00	11:59	12:02	00:03	—	—
6	Ресторан «Кама-Фиш»	12:00	12:30	12:12	12:18	00:06	—	—
7	Кафе «Паста Гранде»	12:00	13:30	12:24	12:33	00:09	—	—
8	Ресторан Нефертити	11:00	19:00	12:48	12:55	00:07	—	—
9	ООО «Компания ЦВР»	11:00	21:00	13:08	13:11	00:03	—	—
10	ЗАО «Пермторгтехника»	13:00	14:00	13:25	13:30	00:05	—	—
11	ООО «Веселый пекарь»	11:00	14:00	13:44	13:50	00:06	—	—
12	ООО «Море рыбы»	12:00	16:00	14:07	14:13	00:06	—	—
13	ООО «Эверест»	14:00	17:00	14:23	14:30	00:07	—	—
14	Ресторан «Пармезан»	12:30	15:30	14:45	14:53	00:08	—	—
15	ООО «Цертина»	15:00	16:00	15:00	15:07	00:07	—	—
16	Ресторан «Casa Mia»	11:00	20:00	15:11	15:14	00:03	—	—
17	Ресторан «Тсуру»	11:00	19:00	15:19	15:24	00:05	—	—
18	Ресторан «Casa Mia»	13:00	17:00	15:28	15:36	00:08	—	—
19	Ресторан «Партизан»	13:30	18:30	15:41	15:44	00:03	—	—
20	ООО «Гарант плюс»	15:00	16:30	15:48	15:51	00:03	—	—
21	Ресторан «Халва»	14:00	20:00	16:00	16:08	00:08	—	—
22	Ресторан «Сакартвело»	12:00	18:00	16:15	16:20	00:05	—	—
23	Продуктовый магазин	16:00	19:30	16:29	16:34	00:05	—	—
24	Ресторан «Халва»	15:00	19:00	16:40	16:47	00:07	—	—
25	Ресторан «Тсуру»	17:00	20:00	16:55	17:08	00:08	00:05	—
26	Столовая «Забава»	15:00	19:00	17:15	17:20	00:05	—	—
27	Пиццерия «Pizzaman»	17:00	19:30	17:31	17:34	00:03	—	—
28	ООО «Заполье»	17:00	19:30	17:44	17:49	00:05	—	—
29	ООО «ПМП»	15:00	19:00	18:02	18:06	00:04	—	—
30	ООО «Федерал»	18:00	20:00	18:18	18:23	00:05	—	—
31	ООО «Фабрика еды»	—	—	18:30	18:30	—	—	—

Приложение 11

Решение ЗМТ («благоприятная» дорожная ситуация) для водителя № 2

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелка №1»	11:00	11:30	11:12	00:07	—	—
3	Столовая «Тарелка №2»	11:00	12:00	11:20	11:23	00:03	—	—
4	Ресторан «Горький»	11:30	12:00	11:30	11:34	00:04	—	—
5	Кафе «Правила»	11:00	14:00	11:45	11:48	00:03	—	—
6	Ресторан «Кама-Фиш»	12:00	12:30	11:56	12:06	00:06	00:04	—
7	Кафе «Паста Гранде»	12:00	13:30	12:15	12:24	00:09	—	—
8	Ресторан Нефертити	11:00	19:00	12:31	12:38	00:07	—	—
9	ООО «Компания ЦВР»	11:00	21:00	12:46	12:49	00:03	—	—
10	ЗАО «Пермторгтехника»	13:00	14:00	13:00	13:05	00:05	—	—
11	ООО «Веселый пекарь»	11:00	14:00	13:15	13:21	00:06	—	—
12	ООО «Море рыбы»	12:00	16:00	13:30	13:36	00:06	—	—
13	ООО «Эверест»	14:00	17:00	13:45	14:07	00:07	00:15	—
14	Ресторан «Пармезан»	12:30	15:30	14:20	14:28	00:08	—	—
15	ООО «Цертина»	15:00	16:00	14:40	15:07	00:07	00:20	—
16	Ресторан «Casa Mia»	11:00	20:00	15:11	15:14	00:03	—	—
17	Ресторан «Тсуру»	11:00	19:00	15:18	15:23	00:05	—	—
18	Ресторан «Casa Mia»	13:00	17:00	15:27	15:35	00:08	—	—
19	Ресторан «Партизан»	13:30	18:30	15:40	15:43	00:03	—	—
20	ООО «Гарант плюс»	15:00	16:30	15:46	15:49	00:03	—	—
21	Ресторан «Халва»	14:00	20:00	15:56	16:04	00:08	—	—
22	Ресторан «Сакартвело»	12:00	18:00	16:10	16:15	00:05	—	—
23	Продуктовый магазин	16:00	19:30	16:21	16:26	00:05	—	—
24	Ресторан «Халва»	15:00	19:00	16:33	16:40	00:07	—	—
25	Ресторан «Тсуру»	17:00	20:00	16:50	17:08	00:08	00:10	—
26	Столовая «Забава»	15:00	19:00	17:13	17:18	00:05	—	—
27	Пиццерия «Pizzaman»	17:00	19:30	17:27	17:30	00:03	—	—
28	ООО «Заполье»	17:00	19:30	17:40	17:45	00:05	—	—
29	ООО «ПМП»	15:00	19:00	17:52	17:56	00:04	—	—
30	ООО «Федерал»	18:00	20:00	18:04	18:09	00:05	—	—
31	ООО «Фабрика еды»	—	—	18:15	18:15	—	—	—

Приложение 12

Решение ЗМТ («неблагоприятная» дорожная ситуация) для водителя № 2

№КонтрагентНачалоКонецПрибытиеОтбытиеРазгрузкаПростойОпоздание
1	ООО «Фабрика еды»	—	—	11:00	11:00	—	—	—
2	Столовая «Тарелка №1»	11:00	11:30	11:10	11:17	00:07	—	—
3	Столовая «Тарелка №2»	11:00	12:00	11:29	11:32	00:03	—	—
4	Ресторан «Горький»	11:30	12:00	11:44	11:48	00:04	—	—
5	Кафе «Правила»	11:00	14:00	12:02	12:05	00:03	—	—
6	Ресторан «Кама-Фиш»	12:00	12:30	12:15	12:21	00:06	—	—
7	Кафе «Паста Гранде»	12:00	13:30	12:30	12:39	00:09	—	—
8	Ресторан Нефертити	11:00	19:00	12:53	13:00	00:07	—	—
9	ООО «Компания ЦВР»	11:00	21:00	13:12	13:15	00:03	—	—
10	13:00	14:00	13:27	13:32	00:05	—	—
11	ООО «Веселый пекарь»	11:00	14:00	13:44	13:50	00:06	—	—
12	ООО «Море рыбы»	12:00	16:00	14:01	14:07	00:06	—	—
13	ООО «Эверест»	14:00	17:00	14:20	14:27	00:07	—	—
14	Ресторан «Пармезан»	12:30	15:30	14:40	14:48	00:08	—	—
15	ООО «Цертина»	15:00	16:00	14:56	15:07	00:07	00:04	—
16	Ресторан «Casa Mia»	11:00	20:00	15:14	15:17	00:03	—	—
17	Ресторан «Тсуру»	11:00	19:00	15:24	15:29	00:05	—	—
18	Ресторан «Casa Mia»	13:00	17:00	15:39	15:47	00:08	—	—
19	Ресторан «Партизан»	13:30	18:30	15:54	15:57	00:03	—	—
20	ООО «Гарант плюс»	15:00	16:30	16:04	16:07	00:03	—	—
21	Ресторан «Халва»	14:00	20:00	16:14	16:22	00:08	—	—
22	Ресторан «Сакартвело»	12:00	18:00	16:29	16:34	00:05	—	—
23	Продуктовый магазин	16:00	19:30	16:47	16:52	00:05	—	—
24	Ресторан «Халва»	15:00	19:00	16:59	17:06	00:07	—	—
25	Ресторан «Тсуру»	17:00	20:00	17:13	17:21	00:08	—	—
26	Столовая «Забава»	15:00	19:00	17:31	17:36	00:05	—	—
27	Пиццерия «Pizzaman»	17:00	19:30	17:44	17:47	00:03	—	—
28	ООО «Заполье»	17:00	19:30	17:58	18:03	00:05	—	—
29	ООО «ПМП»	15:00	19:00	18:09	18:13	00:04	—	—
30	ООО «Федерал»	18:00	20:00	18:24	18:29	00:05	—	—
31	ООО «Фабрика еды»	—	—	18:42	18:42	—	—	—

Приложение 13

Адреса доставки продукции

№	Контрагент	Адрес доставки	Временное окно		Вес (кг)
1	ООО «Фабрика еды»	г. Пермь, ул. Курчатова, 9	11:00	20:00	—
2	ИП Ахметова Н.П.	г. Пермь, ул. Заречная, 140	11:00	12:00	6
3	Кафе «Сковородка»	г. Пермь, ул. Ленина ,65	14:00	16:00	17
4	Столовая «Забава»	г. Пермь, ул. Левченко, 1ш	15:00	19:00	10
5	ООО «Веселый пекарь»	г. Пермь, ул. Тбилисская, 9а	11:00	14:00	10
6	Ресторан «Casa Mia»	г. Пермь, Комсомольский пр-т, 7	13:00	17:00	9
7	ООО «Микс — Семья»	г. Пермь, ул. Революции, 13	15:00	22:00	7
8	Ресторан «Горький»	г. Пермь, ул. М. Горького, 34	11:30	12:00	13
9	Продуктовый магазин	г. Пермь, ул. Лодыгина, 46/1	16:00	19:00	5
10	ТЦ «Евразия»	г. Пермь, ул. Героев Хасана, 56	15:30	19:30	7
11	Ресторан «Тсуру»	г. Пермь, Комсомольский пр-т, 15	11:00	19:00	14
12	Продуктовый магазин	г. Пермь, ул. Красногвардейская, 7/2	18:00	21:00	15
13	ООО «Море рыбы»	г. Пермь, ул. Курчатова, 79	12:00	16:00	6
14	Ресторан «Пармезан»	г. Пермь, Комсомольский пр-т, 90	12:30	15:30	17
15	Пиццерия «Pizzaman»	г. Пермь, ул. Малкова, 14	17:00	19:30	8
16	ИП Кусакин А.В.	г. Добрянка, ул. Некрасова, 10	15:00	16:30	30
17	Ресторан «Кама-Фиш»	г. Пермь, Комсомольский пр-т, 54	12:00	12:30	14
18	Ресторан «Casa Mia»	г. Пермь, ул. Революции, 46	11:00	20:00	7
19	Кафе «Кредо»	г. Пермь, ул. Ленина, 57	14:00	18:00	5
20	Бар «Лаундж»	г. Пермь, ул. Ленина, 98	11:00	19:00	16
21	Продуктовый магазин	г. Пермь, ул. Пушкина, 23	12:00	16:00	13
22	Ресторан «Нефертити»	г. Пермь, ул. Полины Осипенко, 59	11:00	19:00	15
23	ООО «Гарант плюс»	г. Пермь, ул. Куйбышева, 2	15:00	16:30	20
24	Кафе «Корица»	г. Пермь, ул. Луначарского, 62	11:00	19:00	12
25	ООО «Заполье»	г. Пермь, ул. Деревообделочная 3, к2	19:30	9
26	ООО «ТД»	г. Пермь, ул. 3-й Белоярский переулок, 1	12:00	13:00	7
27	ООО «Компания ЦВР»	г. Пермь, ул. Клары Цеткин, 14	11:00	21:00	19
28	ООО «Паритет»	г. Пермь, ул. Луначарского, 96	14:00	15:00	10
29	ООО «ПМП»	г. Пермь, ул. Деревообделочная, 3л	15:00	19:00	9
30	Кафе «Правила»	г. Пермь, ул. Петропавловская, 37	11:00	14:00	11
31	Кафе «Ритм»	г. Пермь, ш. Космонавтов, 114	11:00	19:00	16
32	ООО «Эверест»	г. Пермь, ул. Куйбышева, 106	14:00	17:00	13
33	Ресторан «Охотничий»	г. Пермь, ул. Пермская, 200	13:30	15:30	10
34	Столовая «Тарелка №1»	г. Пермь, ул. Саранская, 3	11:00	11:30	5
35	Столовая «Тарелка №2»	г. Пермь, бул. Гагарина, 74	11:00	12:00	10
36	Столовая «Тарелочка»	г. Пермь, ул. Ленина, 53	11:00	12:00	6
37	Ресторан «Партизан»	г. Пермь, ул. Окулова, 4	13:30	18:30	7
38	Кафе «Паста Гранде»	г. Пермь, ул. Тимирязева, 63	12:00	13:30	7
39	ЗАО «Пермторгтехника»	г. Пермь, ул. Лодыгина, 3	13:00	14:00	8
40	ООО «Пушкин»	г. Пермь, ул. Пушкина, 15	11:00	19:00	7
41	Ресторан «Сакартвело»	г. Пермь, ул. М. Горького, 58	13:30	17:30	7
42	ТЦ «Столица»	г. Пермь, ул. Мира, 41/1	13:00	18:00	6
43	Ресторан «Тсуру»	г. Пермь, ул. Ленина, 66а	17:00	20:00	16
44	Кафе «Ударник»	г. Пермь, ул. Петропавловская, 185	11:00	19:00	16
45	ООО «Федерал»	г. Пермь, ул. Энергетиков, 38	18:00	20:00	5
46	Ресторан «Халва»	г. Пермь, ул. Ленина, 46а	15:00	19:00	13
47	Ресторан «Халва»	г. Пермь, ул. Монастырская, 2	14:00	20:00	20
48	Ресторан «Хуторок»	г. Пермь, ул. Кировоградская, 66	12:30	13:00	24
49	ООО «Цертина»	г. Пермь, ул. Героев Хасана, 1	15:00	16:00	14
50	ОАО «ЭР-Телеком»	г. Пермь, ш. Космонавтов, 111	12:30	13:30	7
51	Ресторан «Сакартвело»	г. Пермь, ул. Ленина, 24	12:00	18:00	9
52	Продуктовый магазин	г. Пермь, ул. Ленина, 18	16:00	19:30	7

Приложение 14

Нужна помощь в написании диплома?

Цена диплома

Таблица 1

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
22	Кафе «Ударник»	11:00	19:00	14:15	14:21	00:06	—	—
23	ООО «ПМП»	15:00	19:00	14:35	15:04	00:04	00:25	—
24	ТЦ «Столица»	13:00	18:00	15:20	15:25	00:05	—	—
25	ООО «Федерал»	18:00	20:00	15:40	15:45	00:05	—	—
26	Кафе «Ритм»	11:00	19:00	16:00	16:06	00:06	—	—
27	ООО «Фабрика еды»	—	—	16:20	16:20	—	—	—

Маршрут с незапланированным простоем

Таблица 2

Пример пересчета маршрута в случае незапланированного простоя

№	Контрагент	Начало	Конец	Прибытие	Отбытие	Разгрузка	Простой	Опоздание
22	Кафе «Ударник»	11:00	19:00	14:15	14:21	00:06	—	—
23	ТЦ «Столица»	13:00	18:00	14:40	14:45	00:05	—	—
24	Кафе «Ритм»	11:00	19:00	15:05	15:11	00:06	—	—
25	ООО «ПМП»	15:00	19:00	15:25	15:29	00:04	—	—
26	ООО «Федерал»	18:00	20:00	15:45	15:50	00:05	—	—
27	ООО «Фабрика еды»	—	—	16:05	16:05	—	—	—

Приложение 15

Задача о рюкзаке (фактическая дневная заявка)

Номер контрагента	Вес заказа (кг)	Цена заказа (руб)	Цена/Вес
1	10	5 850	585
2	8	3 700	463
3	15	8 000	533
4	6	2 750	458
5	7	3 500	500
6	20	12 150	608
7	14	6 400	457
8	5	3 200	640
9	25	14 100	564
10	15	7 080	472
11	18	10 340	574
12	6	3 260	543
13	7 170	598
14	7	3 400	486
15	5	2 640	528
16	6	2 490	415
17	3	1 400	467
18	10	6 320	632
19	4	1 930	483
20	5	1 600	320
21	7	2 300	329
22	6	3 700	617
23	5	2 460	492
24	10	4 600	460
25	11	5 950	541
26	14	7 300	521
27	7	3 400	486
28	10	5 490	549
29	9	5 120	569
30	4	1 750	438
31	3	1 360	453
32	6	2 700	450
33	3	1 600	533
34	17	9 100	535
35	14	6 700	479
36	8	3 600	450
37	9	4 700	522
38	13	6 300	485
39	9	4 250	472
40	5	2 370	474

Приложение 16

Решение задачи о рюкзаке «жадным алгоритмом»

Номер п/п	Номер контрагента	Вес заказа (кг)	Цена заказа (руб)	Цена/Вес
1	8	5	3 200	640
2	18	10	6 320	632
3	22	6	3 700	617
4	6	20	12 150	608
5	13	12	7 170	598
6	1	10	5 850	585
7	11	18	10 340	574
8	29	9	5 120	569
9	9	25	14 100	564
10	28	10	5 490	549
11	12	6	3 260	543
12	25	11	5 950	541
13	34	17	9 100	535
14	3	15	8 000	533
15	33	3	1 600	533
16	15	5	2 640	528
17	37	9	4 700	522
18	26	14	7 300	521
19	5	7	3 500	500
20	23	5	2 460	492
21	14	7	3 400	486
22	27	7	3 400	486
23	38	13	6 300	485
24	19	4	1 930	483
25	35	14	6 700	479
26	40	5	2 370	474
27	39	9	4 250	472
28	10	15	7 080	472
29	17	3	1 400	467
30	2	8	3 700	463
31	24	10	4 600	460
32	4	6	2 750	458
33	7	14	6 400	457
34	31	3	1 360	453
35	36	8	3 600	450
36	32	6	2 700	450
37	30	4	1 750	438
38	16	6	2 490	415
39	21	7	2 300	329
40	20	5	1 600	320

Приложение 17

Решение задачи о рюкзаке. Эксперимент с водителем. Цена по убыванию

Номер п/п	Номер контрагента	Вес заказа (кг)	Цена заказа (руб)	Цена/Вес
1	9	25	14 100	564
2	6	20	12 150	608
3	11	18	10 340	574
4	34	17	9 100	535
5	3	15	8 000	533
6	14	7 300	521
7	13	12	7 170	598
8	10	15	7 080	472
9	35	14	6 700	479
10	7	14	6 400	457
11	18	10	6 320	632
12	38	13	6 300	485
13	25	11	5 950	541
14	1	10	5 850	585
15	28	10	5 490	549
16	29	9	5 120	569
17	37	9	4 700	522
18	24	10	4 600	460
19	39	9	4 250	472
20	22	6	3 700	617
21	2	8	3 700	463
22	36	8	3 600	450
23	5	7	3 500	500
24	14	7	3 400	486
25	27	7	3 400	486
26	12	6	3 260	543
27	8	5	3 200	640
28	4	6	2 750	458
29	32	6	2 700	450
30	15	5	2 640	528
31	16	6	2 490	415
32	23	5	2 460	492
33	40	5	2 370	474
34	21	7	2 300	329
35	19	4	1 930	483
36	30	4	1 750	438
37	33	3	1 600	533
38	20	5	1 600	320
39	17	3	1 400	467
40	31	3	1 360	453

Нужна помощь в написании диплома?

Заказать диплом

Предыдущий пример

Следующий пример