Маршрутизация перевозок компании «Объединенные Пивоварни Хейнекен»

Морозов Сергей Игоревич

Маршрутизация перевозок компании «Объединенные Пивоварни Хейнекен»

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

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36445f1be77c40d58b03

UUID: f1aa1c86-facd-4747-9b6c-78f93604b044

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 198

Морозов Сергей Игоревич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 1793074 bytes

Поделиться работой

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Санкт-Петербургский государственный университет Институт «Высшая школа менеджмента» Маршрутизация перевозок компании «Объединенные Пивоварни Хейнекен» Выпускная квалификационная работа студента 4 курса бакалаврской программы, профиль – Логистика МОРОЗОВА Сергея Игоревича (подпись) Научный руководитель к. э. н., старший преподаватель ЧУРАКОВА Ийя Юрьевна (подпись) «СООТВЕТСТВУЕТ ТРЕБОВАНИЯМ» (подпись научного руководителя) « »________ Санкт-Петербург 2016 2016 г.

Заявление о самостоятельном выполнении курсовой работы Я, Морозов Сергей Игоревич, студент 4 курса направления 080200 «Менеджмент» (профиль подготовки – Логистика), заявляю, что в моей выпускной квалификационной работе на тему «Маршрутизация перевозок компании «Объединенные Пивоварни Хейнекен», представленной в службу обеспечения программ бакалавриата для публичной защиты, не содержится элементов плагиата. Все прямые заимствования из печатных и электронных источников, а также из защищённых ранее курсовых и выпускных квалификационных работ, кандидатских и докторских диссертаций имеют соответствующие ссылки. Мне известно содержание п. 9.7.1 Правил обучения по основным образовательным программам высшего и среднего профессионального образования в СПбГУ о том, что «ВКР выполняется индивидуально каждым студентом под руководством назначенного ему научного руководителя», и п. 51 Устава федерального государственного бюджетного образовательного учреждения высшего профессионального образования «СанктПетербургский государственный университет» о том, что «студент подлежит отчислению из Санкт-Петербургского университета за представление курсовой или выпускной квалификационной работы, выполненной другим лицом (лицами)». ____________________________________ (Подпись студента) ____________________________________ (Дата)

СОДЕРЖАНИЕ Введение............................................................................................................................. 5 Глава 1. О компании...........................................................................................................8 1.1. ООО «Объединенные Пивоварни Хейнекен»...................................................... 8 1.2. История компании...................................................................................................9 1.3. Обзор пивоваренного рынка в России................................................................ 10 1.4. Основные конкуренты на российском рынке.....................................................12 1.5. Стратегия компании..............................................................................................13 1.6. Транспортная логистика.......................................................................................13 1.6.1. Тарифы на перевозку..................................................................................... 14 1.6.2. Особенности маршрутизации....................................................................... 15 1.7. Анализ компании.................................................................................................. 16 Выводы..........................................................................................................................17 Глава 2. Выбор методов решения проблем....................................................................19 2.1. Анализ литературы............................................................................................... 19 2.2. Выбор инструментария для анализа компании..................................................23 2.2.1. Метод Кларка-Райта...................................................................................... 24 2.2.2. Двухфазный алгоритм................................................................................... 24 2.2.3. Алгоритм заметания...................................................................................... 24 2.2.4. Жадный алгоритм.......................................................................................... 25 2.2.5. Метод ветвей и границ.................................................................................. 25 2.2.6. Метод линейного программирования.......................................................... 27 Выводы..........................................................................................................................29 Глава 3. Решение управленческих проблем компании.................................................31 3.1. Применение методов............................................................................................ 31 3.1.1. Метод Кларка-Райта...................................................................................... 32 3.1.2. Алгоритм заметания...................................................................................... 34 3.1.3. Жадный алгоритм.......................................................................................... 35

3.1.4. Метод ветвей и границ.................................................................................. 36 3.1.5. Метод линейного программирования.......................................................... 38 3.2. Оценка использованных методов........................................................................ 40 3.3. Альтернативные транспортные тарифы............................................................. 41 Выводы..........................................................................................................................44 Заключение....................................................................................................................... 46 Список использованной литературы..............................................................................48 Приложения...................................................................................................................... 51 Приложение 1. Соответствие номеров клиентов и их местоположения................51 Приложение 2. Объемы грузов для доставки клиентам...........................................52 Приложение 3. Матрица расстояний между торговыми точками в километрах. . .53 Приложение 4. Матрица «сбережений».....................................................................54 Приложение 5. Метод Кларка-Райта.......................................................................... 55 Приложение 6. Метод ветвей и границ...................................................................... 57 Приложение 6.1. Определение минимальных элементов по строкам................57 Приложение 6.2. Редуцированная матрица по строкам.......................................58 Приложение 6.3. Оценка каждого нулевого значения.......................................... 59 Приложение 6.4. Исключение из маршрута перемещения (11,14)......................60 Приложение 6.5. Включение в маршрут перемещение (11,14)...........................61 Приложение 7. Метод линейного программирования..............................................62 Приложение 7.1. Дополнительные матрицы №1 и №2........................................62 Приложение 7.2. Основная матрица выбора перемещений для кластера №1...63

Введение Определение оптимального маршрута для доставки грузов является одной из главнейших задач, относящихся к транспортной логистике компании. В условиях мегаполиса на доставку грузов влияет множество различных факторов, таких как рассредоточенность клиентов по всему городу, загруженность автодорог, время ожидания приемки у клиента, которые могут сильно повлиять на эффективность бизнеса. Для того, чтобы учесть все факторы, влияющие на доставку грузов, необходимо предварительно осуществлять маршрутизацию перевозок, т.е. определять оптимальные маршруты перевозки грузов. Так маршрутизация позволит минимизировать пройденное расстояние автотранспортным средством, уменьшить время прохождения всего маршрута, сократить время нахождения автотранспортного средства на погрузке или разгрузке. Все это приведет к увеличению производительности автотранспортного средства в разы. Также маршрутизация повышает удовлетворенность клиентов за счет своевременного прибытия автотранспортного средства под выгрузку. В дальнейшем хорошие отношения с клиентами позволяют договариваться о комфортном времени для выгрузки. Однако, основная выгода от маршрутизации перевозок – это минимизация транспортных затрат компании. Транспортная логистика является одним из самых крупных центров затрат, наряду с производством, поэтому любой компании просто необходимо контролировать и минимизировать затраты, производимые данными подразделениями. В данной выпускной квалификационной работе будет рассмотрена маршрутизация перевозок компании «Объединенные Пивоварни Хейнекен». Всю доставку готовой продукции со склада компании HEINEKEN осуществляет транспортно-экспедиционная компания, однако все функции по маршрутизации и контролю за доставкой выполняет компания HEINEKEN. В настоящее время сотрудники транспортной логистики не занимаются определением оптимальных маршрутов для доставки готовой продукции. Координаторы объединяют торговые точки в маршрут, а водители сторонней транспортноэкспедиционной компании выбирают на свое усмотрение порядок посещения точек, входящих в маршрут. Также транспортный тариф компании HEINEKEN не зависит от времени прохождения маршрута и пройденного расстояния автотранспортным средством, что в свою очередь препятствует минимизации затрат в компании. Объектом выпускной квалификационной работы является транспортная логистика компании «Объединенные Пивоварни Хейнекен», а предмет исследования маршрутизация перевозок. 5

Тема маршрутизации перевозок является актуальной в настоящее время, т.к. компаниям необходимо в сжатые сроки формировать оптимальные маршруты для быстрой и качественной доставки грузов большому количеству клиентов, расположенных по всему городу. Также большое количество отечественных и зарубежных научных работ посвящено разработке различных методик определения оптимальных маршрутов для доставки грузов. Многие компании разрабатывают различное программное обеспечение, позволяющее автоматизировать процесс маршрутизации перевозок. Программное обеспечение также способно в реальном времени следить и координировать передвижение автотранспортного средства по маршруту. В связи с этим, целью данной выпускной квалификационной работы является разработка методики маршрутизации перевозок с целью повышения эффективности работы поставок и минимизации затрат компании «Объединенные пивоварни Хейнекен». Для достижения поставленной цели необходимо решить ряд задач, которые помогут сформировать решение поставленной управленческой проблемы в компании HEINEKEN. Задачи выпускной квалификационной работы:  Определение текущей ситуации в транспортной логистике, а именно выявление методов и процедур, позволяющих маршрутизировать автоперевозки;  Поиск различных методов маршрутизации перевозок в научной литературе;  Применение моделей, позволяющих определить оптимальный маршрут, на реальных транспортировках компании;  Оценка использования новых методов маршрутизации и их сравнение с текущей ситуацией в компании;  Составление рекомендаций по улучшению процесса маршрутизации транспорта компании. Выпускная квалификационная работа состоит из трех глав. В первой главе данной работы приведена общая информация по компании, а также проведен анализ компании, результатом которого являются сформированные управленческие проблемы. Во второй главе рассмотрены различные научные работы, посвященные маршрутизации перевозок. Также в этой главе подробно рассмотрен инструментарий для решения управленческих проблем в компании. В третьей главе выбранные методы применены к реальным данным и затем оценены в сравнении с исходными маршрутами. 6

В выпускной квалификационной работе используется два метода, позволяющих составить оптимальные маршруты по доставке готовой продукции компании HEINEKEN. Первым методом построения маршрута является метод Кларка-Райта, который одновременно позволяет сформировывать маршруты и определять последовательность посещения пунктов, входящих в маршрут. Вторым методом является двухфазный алгоритм. На первой фазе объединяются клиенты в маршрут, а на второй фазе определяется последовательность посещения клиентов. Последовательность посещения определяется с помощью трех методов. Данный выбор обусловлен тем, что они представляют собой три разных подхода к определению оптимальных маршрутов. Первый метод – это жадный алгоритм. Он самый простой из всех выбранных методов, который позволит определить необходимость маршрутизации перевозок в целом. Вторым методом является метод ветвей и границ. Метод ветвей и границ требует больше всего времени на определение оптимального маршрута, т.к. необходимо вручную перебирать большое количество альтернатив, хотя результат данного метода не всегда оптимальный. Третий метод – метод линейного программирования. Он позволяет с помощью использования программного обеспечения определять наиболее точный результат среди всех представленных методов. При подготовке выпускной квалификационной работы использовались информационные и реферативные базы данных JUSTOR, EBSCO, SCOPUS и другие. Также рассматривалось большое количество отечественных и зарубежных научных работ по теме исследования операций. 7

Глава 1. О компании 1.1. ООО «Объединенные Пивоварни Хейнекен» Концерн HEINEKEN N.V. является одним из лидирующих международных пивоваренных компаний. Штаб-квартира компании находится в Амстердаме. HEINEKEN N.V принадлежит 125 пивоваренных заводов более чем в 70 странах мира. 1 В 2015 году компания суммарно произвела 188,3 млн. гл. пива на всех производственных площадках в мире.2 Основными ценностями компании HEINEKEN являются уважение к людям и обществу, радость и позитивное отношение к жизни, стремление к высокому качеству и забота об окружающей среде. Данные ценности сформировались на стадии зарождения компании HEINEKEN, как семейного бизнеса. Компания HEINEKEN появилась на российском рынке в феврале 2002 года как ООО «Объединенные Пивоварни Хейнекен», когда она приобрела свой первый завод в Санкт-Петербурге. В настоящее время компании принадлежит 8 заводов, расположенных по всей территории Российской Федерации, на которых работает более 2400 сотрудников. Портфель брендов компании HEINEKEN на российском рынке насчитывает 29 торговых брендов, среди которых, как популярные национальные и региональные марки («Окское», «Шихан», «Степан Разин», «Амур-пиво» и др.), так и известные международные торговые марки («Amstel Premium Pilsner», «Guinness», «Heineken» и др.). На конец 2014 года доля компании HEINEKEN на российском рынке составляет 13%. 3 На всех пивоварнях компании внедрена система по управлению эффективностью производства - Total Productive Maintenance (TPM). Цель данной системы заключается в том, чтобы достичь предельной и комплексной эффективности производственной системы с помощью постоянных улучшений производственного процесса. Результатом введения данной системы управления эффективностью производства является предотвращение всех видов потерь на протяжении всего жизненного цикла производственной системы. Также компания HEINEKEN придерживается системы менеджмента качества в соответствии с требованиями ISO (ISO 9001:2008, ISO 22000:2005), с помощью которых компания оптимизирует свои бизнес-процессы и достигает высокого качества своей продукции. Также компания постоянно совершенствует свои производственные процессы тем самым 1 Концерн HEINEKEN [Электронный ресурс] // HEINEKEN Russia. — Режим доступа: http://www.heinekenrussia.ru/company/heineken_group (дата обращения: 16.04.2016). 2A summary of 2015 annual report [Electronic resource] // HEINEKEN Holding N. V. — Режим доступа: http://www.theheinekencompany.com/investors/performance-highlights-2015 (дата обращения: 16.04.2016). 3 Отчет о деятельности компании HEINEKEN в России в области устойчивого развития бизнеса [Электронный ресурс] // HEINEKEN Russia. — Режим доступа: http://sustainabilityrussia.ru/otchetnost/2014/about (дата обращения: 16.04.2016). 8

уменьшая ресурсо- и энергозатраты. Так компания HEINEKEN снизила потребление воды на 32% с 2008 года. Компания HEINEKEN реализует различные социальные проекты: проект «Я за себя отвечаю» направлен на подростков с целью профилактики употребления алкоголя несовершеннолетними, проект «Чистые берега Байкала» направлен на защиту окружающей среды озера Байкал, проект «АвтоТрезвость» направлен на снижение количества случаев вождения в нетрезвом состоянии и другие. В 2014 году общие социальные инвестиции компании HEINEKEN составили более 13 млн. руб. 1.2. История компании История компании HEINEKEN начинается в 1864 году. В этом году Жерард Адриан Хейнекен приобрел небольшую пивоварню в центре Амстердама. В 1868 году была построена новая пивоварня Buitensingel на окраине Амстердама. В 1869 году Жерард Хейнекен решает перейти на нетрадиционное для Голландии производство пива по методике низового брожения, которое было популярно в Баварии. Данное изменение позволяло производить более светлое и чистое пиво, которое к тому же дольше хранилось. В 1874 году была основана компания «Heineken's Bierbrouwerij Maatschappij N.V», которая объединила все существующие пивоварни, а затем к этой же компании присоединился новый современный завод в Роттердаме, где была организована лаборатория для контроля качества продукции. В 1880 году компания HEINEKEN становится крупнейшим экспортером пива во Францию. В 1886 году доктор Элион, бывший ученик Луи Пастера, вывел знаменитый сорт дрожжей «Heineken А», который используется в производстве пива и по сей день. Данный сорт невозможно купить у компании HEINEKEN, а также воспроизвести. В 1900 году компания импортирует первое пиво в Африку. В 1917 году Генри Хейнекен, сын Джерарда Хейнекена, становится руководителем компании. В 1933 году пиво Heineken становится доступным в Соединенных Штатах. Затем компания HEINEKEN размещает свои акции на голландском фондовом рынке в 1939 году. В 1940 году Альфред Генри Хейнекен начинает применять различные рекламные технологии для дальнейшего продвижения продукции компании HEINEKEN. Ранее продукция компании никак не продвигалась. В 1969 году происходит покупка своего конкурента Amstel и ряд других пивоваренных компаний. Начиная с 70 –х годов начинается активная политика лицензирования, при которой пивовары производили продукцию компании HEINEKEN по лицензионным соглашениям. В 1989 году на смену Альфреду Хейнекену приходит Карел Вурстеен. В 1991 году компания становится акционерной. В 2000 году при участии 9

компании было выпущено около 98 миллионов гектолитров пива. 4 В 2003 году австрийская пивоваренная компания Brau-Beteiligungs A. G. вошла в группу компаний HEINEKEN. В 2008 году компания приобретает Scottish & Newcastle, а в 2010 году – мексиканский пивоваренный бизнес FEMSA. 1.3. Обзор пивоваренного рынка в России В 2014 году общее количество пивоваренных заводов, расположенных на территории Российской Федерации, составило 857. 5 Данное число включает и крупнейшие пивоваренные группы: HEINEKEN, Carlsberg Group, Efes, AB InBev, SABMiller. Их суммарная доля на рынке составляет более 75% (см. рисунок 1). Остальные 22,6 процента занимают средние и малые региональные производители, расположенные по всей территории России. Рис. 1 Доли ведущих производителей пива на российском рынке за 2014 год Источник: Отчет об устойчивом развитии компании Балтика [Электронный ресурс] — Режим доступа: http://corporate.baltika.ru/baltika_otchet_ob_ustoychiwom_razwitii_2014.pdf По состоянию на 2014 год объем пивоваренного рынка в России снизился на 6,8% по сравнению с предыдущим периодом и составляет 77 млн. гл. Данная негативная динамика сохраняется на протяжении длительного периода времени (см. рисунок 2) и вызвана ухудшением общей макроэкономической ситуацией, ростом инфляции, увеличением законодательных ограничений в пивоваренной отрасли. Основными 4 История концерна HEINEKEN [Электронный ресурс] // HEINEKEN Russia. — Режим доступа: http://www.heinekenrussia.ru/company/heineken_group/history (дата обращения: 16.04.2016). 5 Число пивоварен в Европе удвоилось за семь лет [Электронный ресурс] // Ведомости. — Режим доступа: https://www.vedomosti.ru/business/articles/2015/11/06/615772-evropeiskii-pivovarennii-bum (дата обращения: 16.04.2016). 10

законодательными ограничениями за последнее время являются запрет на продажу пива в нестационарных торговых точках, ограничение времени продаж, ограничения для рекламных акций, ограничение несоложеных материалов в производстве пива не более 20%, запрет рекламы в различных средствах массовой информации и другие ограничения, которые создают неравные рыночные условия для пивоваренной отрасли. Рис. 2 Динамика рынка пива в России 2010-2014 годы Источник: Статистический справочник России 2014 год [Электронный ресурс] — Режим доступа: http://sustainabilityrussia.ru/otchetnost/2014/about Также акцизная политика государства оказывает сильное влияние на производителей пива. Так акциз на пивоваренную продукцию вырос в 6 раз за последние пять лет (с 3 до 18 рублей за литр) и начиная с 2010 года опередил крепкий алкоголь по поступлению акцизов в бюджет страны среди всей алкогольной продукции. Таким образом, увеличение стоимости пива за счет увеличения ставки акциза уменьшает объем потребления среди населения страны. Такая законодательная политика в области регулирования пивоваренной отрасли сильно бьет по положению пивоваренных компании на рынке. Так в начале 2015 года пивоваренная компания Балтика закрыла два своих завода, расположенных в Челябинске и Красноярске. Более того 33 завода, принадлежащие другим пивоваренным компаниям, работают при загрузке далекой от максимальной. 11

1.4. Основные конкуренты на российском рынке Как уже говорилось ранее, на российском рынке представлены все основные межнациональные корпорации, которые оказывают сильную конкуренцию компании HEINEKEN:  ООО «Пивоваренная компания “Балтика”» ООО «Пивоваренная компания “Балтика”» была основана в 1990 году в Санкт- Петербурге, как государственное предприятие. В 1992 году произошла реорганизация предприятия в открытое акционерное общество. Крупнейшим акционером компании становится Baltic Beverages Holding. В настоящее время Балтика принадлежит датской пивоваренной компании Carlsberg Group и является одной из самых крупных компаний в сфере производства товаров народного потребления в России. 6 Компания Балтика имеет восемь пивоваренных заводов, расположенных по все территории России, а штаб-квартира компании расположена в Санкт-Петербурге. Кроме того, Балтике принадлежит два солодовенных завода, один из которых построен совместно с французской фирмой Groupe Soufflet. Портфель брендов компании состоит из 40 пивных и 10 не пивных марок, которые нацелены на все сегменты российского рынка пива.  ОАО «САН ИнБев» ОАО «САН ИнБев» является подразделением бельгийского пивоваренного концерна Anheuser-Busch InBev. Компания была основана в 1999 году как стратегическое партнерство между группой САН и пивоваренной компанией InBev. Компании принадлежит сеть современных заводов, расположенных в российских городах: Волжск, Клин, Омск, Иваново и Саранск. Основные торговые марки пива, выпускаемого в России: «BUD», «Клинское», «Сибирская корона», «Lowenbrau» и другие.  ЗАО «Пивоварня Москва-Эфес» ЗАО «Пивоварня Москва-Эфес» - подразделение международной пивоваренной компании Anadolu Efes. В конце 2012 года к компании присоединился ЗАО «САБМиллер РУС», дочерняя компания SABMiller в России. Компания Эфес имеет шесть пивоваренных заводов, расположенных в Казани, Новосибирске, Уфе, Калуге, Владивостоке и Ульяновске. Портфель брендов компании состоит из 26 торговых марок, во главе которых стоит торговая марка «Efes Pilsener». 1.5. Стратегия компании 6 История пивоваренной компании «Балтика» [Электронный ресурс] // Пивоваренная компания «Балтика». — Режим доступа: http://corporate.baltika.ru/m/41/the_history_of_baltika_breweries.html (дата обращения: 16.04.2016). 12

Основной приоритет компании HEINEKEN заключается в устойчивом развитии компании, которое основано на стратегической программе HEINEKEN - «Варим пиво, делая мир лучше». Данная программа нацелена как на компанию, так и на общество в целом. Таким образом, компания старается уделять внимание острым социальным проблемам в обществе, а также состоянию окружающей среды. Стратегия «Варим пиво, делая мир лучше» имеет шесть направлений деятельности: сокращение выбросов углекислого газа в атмосферу; защита водных ресурсов; ответственное использование сырья и материалов; продвижение идей ответственного потребления алкогольной продукции; охрана труда и производственная безопасность и гармоничное развитие и взаимодействие с местными сообществами. 1.6. Транспортная логистика Все транспортировки грузов, материалов и прочего отданы на аутсорсинг сторонней организации. Выбор транспортно-экспедиционной компании (ТЭК), которая будет обеспечивать доставку грузов, производится на основании тендера на предоставление транспортных услуг. Отдел закупок формирует транспортные тарифы на новый период, исходя из тарифов предыдущего периода, и затем высылает участникам тендера. В процессе конкурентного отбора определяется ТЭК и транспортные тарифы, которые будут использоваться при оплате выполненных услуг транспортноэкспедиционной компании. При дальнейшем взаимодействии с ТЭК организуются различные встречи по корректировкам транспортных тарифов. На данный момент доставку всей готовой продукции по Санкт-Петербургу и Ленинградской области осуществляет одна транспортно-экспедиционная компания. Ей переданы в аренду пятнадцать малотоннажных грузовиков, которые находятся в собственности компании HEINEKEN, с целью минимизации затрат на обслуживание и содержание автохозяйства. В дальнейшем компания HEINEKEN планирует доставлять свою продукцию с помощью двух-трех ТЭК. Решение о доставке продукции несколькими ТЭК связано с увеличившимся количеством возвратов, которые вызваны некорректной работой единой государственной автоматизированной информационной системой (ЕГАИС). ЕГАИС – это система, которая предназначена для государственного контроля над объёмом производства и оборота этилового спирта, алкогольной и спиртосодержащей продукции.7 Целью данной системы является уменьшение контрафактной алкогольной продукции на рынке, а также контроль правильности начисления акциза. Так первого октября 2015 года был принят законопроект о том, что все производители пива с 7 Единая государственная автоматизированная информационная система [Электронный ресурс] // ФГУП «Центринформ». — Режим доступа: http://egais2016.ru/egais/ (дата обращения: 16.04.2016). 13

производственной мощностью более 300 тысяч декалитров в год должны подключиться к данной системе. Розничные продавцы же должны были подключиться к ЕГАИС в начале 2016 года. Данная система позволяет отслеживать движение алкогольной продукции в процессе его производства. Учет алкоголя происходит на различных этапах, начиная от производства и заканчивая продажей. При доставке готовой продукции клиенту компания HEINEKEN отправляет исходящий заказ клиенту через информационную систему. Затем при фактическом получении заказа клиент должен сверить реальное количество поставленного алкоголя с бумажной и электронной накладной. Если накладные не сходятся, то клиент вправе отказаться от данного заказа. Суть некорректной работы ЕГАИС, с которой сталкивается компания HEINEKEN при доставке, заключается в следующем – система зачастую не успевает присылать электронную накладную клиенту, который ожидает заказ. Таким образом, грузовик приезжает к клиенту и его не принимают, т.к. отсутствует электронная накладная. И как следствие компания тратит впустую деньги на излишнее перемещение грузов, которое нужно будет повторно реализовать на следующий день. 1.6.1. Тарифы на перевозку Стоимость транспортировки продукции клиенту складывается из следующих параметров: географическая зона, в рамках которой проходит маршрут движения автотранспорта; тип транспортного средства и сложность маршрута. Всего имеется три зоны, через которые могут проходить маршруты по доставке продукции компании. Данные зоны равноудалены от Санкт-Петербурга и охватывают сам город, пригород и область. Продукция компании HEINEKEN может доставляться различными автотранспортными средствами с разной грузоподъемностью. Подбор транспорта для доставки товаров осуществляется исходя из того, что загрузка автотранспорта должна быть максимальной при выполнении определенного маршрута. Под максимальной загрузкой транспорта понимается максимальный перевозимый вес груза, разрешенный к перевозке на данном типе транспортного средства. Грузоподъемность автотранспорта варьируется от 1,5 до 20 тонн. Соответственно, чем больше грузоподъемность нанимаемого авто средства, тем больше будет конечная стоимость маршрута. Основным параметром, который в большей степени влияет на финальную стоимость транспортировки, является сложность маршрута. Он определяется исходя из того сколько точек выгрузки имеет данное транспортное средство на маршруте. Также 14

каждый маршрут попадает в определенный диапазон, у которого есть ограничение по количеству точек выгрузки. Причем компания будет платить одну и ту же стоимость за маршрут, у которого от одной до четырех точек выгрузки. Например, имеется два идентичных маршрута, расположенных в одной зоне. Доставка осуществляется двумя идентичными грузовиками с одинаковой грузоподъемностью, но точек выгрузки у первого маршрута 5, а у второго – 8. В данном случае компания заплатит одну и ту же цену за два маршрута исходя из принятого ценообразования. В рамках данного ценообразования на маршруты не важно пройденное расстояние автотранспортом. Также можно предположить, что компания теряет деньги при заказе маршрута, у которого количество точек выгрузки находится на ближней границе интервала и выигрывает с максимальным количеством точек выгрузки у данного интервала. 1.6.2. Особенности маршрутизации По наработанному опыту один водитель в среднем может развезти товар по 14-15 точкам выгрузки, но если к данному маршруту добавляется одна сложная точка, то количество точек, по которым может быть развезен товар, уменьшается до 10-11. В данном случае сложной точкой может считаться любой крупный оптово-розничный магазин. Уменьшение производительности вызвано процессом приемки товара у самого клиента. Если имеется очередь на приемку к клиенту, то продукция компании HEINEKEN принимается в последнюю очередь, т.к. пиво не является скоропортящимся продуктом. Таким образом, время ожидания приемки у клиента может затянуться от 1 до 4 часов, в то время как у большинства магазинов время приемки заканчивается в пять-шесть часов вечера. Если же транспортное средство не прибудет к времени авизации у клиента, то транспортно-экспедиционная компания получит штраф, несмотря на то, что грузовик все равно бы не приняли из-за скопившейся очереди на приемке. Время авизации – это определенная дата и время, к которому автотранспортное средство должно прибыть в конкретный пункт. В последнее время сотрудники отдела транспортной логистики при составлении маршрутов движения автотранспорта стараются добавлять только 1-2 точки выгрузки к транспортировке со сложной точкой, т.к. участились случаи срыва всей транспортировки, когда автотранспортное средство ожидало долгое время выгрузки у сложной точки и затем не успевало завершить весь маршрут. Доставку всей продукции компании осуществляет транспортно-экспедиторская компания, поэтому некоторые водители не обладают достаточными знаниями города, для того чтобы успеть найти адреса клиентов с достаточно большой оперативностью и успеть ко всем точкам выгрузки согласно маршруту. Также условия мегаполиса вносят свои 15

коррективы в доставку готовой продукции клиентам. Довольно сложно быстро припарковать транспортное средство у точки выгрузки в центре города, не мешая основному транспортному потоку, и быстро его разгрузить. 1.7. Анализ компании Выявление и изучение основных управленческих проблем транспортной логистики происходило с первого июля по 31 июля 2015 года, когда автор данной работы проходил обязательную летнюю производственную практику в компании HEINEKEN. За время пребывания в компании автор изучил бизнес-процессы, связанные с транспортировкой грузов, и особенности маршрутизации автотранспорта в пределах Ленинградской области. Также автор данной работы рассмотрел базовые составляющие транспортного тарифа, с помощью которого компания оплачивает услуги по перевозке грузов транспортноэкспедиционной компании. Также во время написания данной работы организовывалось две дополнительные встречи с координаторами компании HEINEKEN и директором по транспортной логистике - Клиндуховой Ольгой. В рамках данных встреч обсуждались различные особенности транспортной логистики, а именно: возможность использования тарифов, зависящих от пройденного расстояния и времени, а также смешанных тарифов; основные сложности в процессе маршрутизации; возможности уменьшения затрат компании и т.д. Также обсуждались основные пути решений, которые позволят минимизировать затраты компании HEINEKEN на транспортную логистику. Основные управленческие проблемы, выявленные в процессе анализа компании HEINEKEN:  Частые срывы транспортировок из-за не эффективного перемещения автотранспорта. Рациональное перемещение автотранспорта по маршруту, в который входит большое количество торговых точек, затруднено, т.к. водитель сам выбирает последовательность перемещений;  Оптимальный маршрут для транспортировки готовой продукции никак не влияет на транспортные затраты компании. Данная проблема связана с тем, что транспортные тарифы не зависят от пройденного расстояния и времени в пути;  Компания несет равные затраты по двум транспортировкам, если они попадают в один диапазон тарифа. Таким образом, компания будет переплачивать за транспортировку, если количество точек выгрузки находится у ближней границы 16

диапазона и соответственно выигрывать при максимальном количестве точек выгрузки в пределах одного диапазона. После проведенных встреч директор по логистике предоставил файл со всеми транспортировками, проведенными за 13 февраля 2016 года. В данных транспортировках указаны: номер документа сбыта; номер транспортировки; количество точек выгрузки; зона, в которой проходит маршрут; тип автотранспортного средства; номенклатура отгружаемой продукции и адрес получателя. Также была предоставлена информация о последовательности прохождения маршрута автотранспортным средством, т.е. можно отследить в какой последовательности автотранспортное средство посещало торговые точки. Более того, были предоставлены транспортные тарифы, которые будут в дальнейшем использоваться в качестве текущих затрат. Дальнейшее взаимодействие с Ольгой Клиндуховой организовывалось с помощью электронной почты. Выводы В данной главе автор рассмотрел российский рынок пивоваренной продукции и привел основную информацию о компании HEINEKEN в целом, а также описал текущую ситуацию в отделе транспортной логистики компании. Так, обзор пивоваренного рынка в России показал, что спрос на пиво с каждым годом уменьшается. По состоянию на 2014 год объем пивоваренного рынка в России снизился на 6,8%. Данная негативная динамика связана в большей степени с законодательной политикой государства, которая ограничивает торговые точки и время продажи алкоголя, запрещает рекламу в различных средствах массовой информации и т.д. Более того, на стоимость готовой продукции сильно влияет величина акциза, которая выросла в шесть раз за пять лет. Такая акцизная политика значительно повышает конечную стоимость пива, что в свою очередь уменьшает объем потребления среди населения страны. Затем была рассмотрена основная деятельность отдела транспортной логистики в компании HEINEKEN. В подглаве, посвященной транспортной логистике, приведена следующая информация о действующей системе взаимодействия компании HEINEKEN с транспортно-экспедиционной компанией, которая обеспечивает доставку готовой продукции по Санкт-Петербургу и Ленинградской области; структуре транспортного тарифа, принятого в компании и особенностях маршрутизации в пределах города. Затем в подглаве «Анализ компании» были определены основные проблемы и трудности, возникающие в процессе доставки продукции клиенту. Так, в процессе проведенных встреч с директором по транспортной логистике и координаторами отдела транспортной логистики, было выделено три основные проблемы: частые срывы транспортировок из-за 17

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

Глава 2. Выбор методов решения проблем В данной главе будет проведен анализ литературы, который выявит основные методы решения управленческих проблем, выделенных в первой главе настоящей работы. Будут разобраны различные статьи, которые позволят ознакомиться с основными теориями и подходами к решению различных практических задач, связанных с маршрутизацией перевозок. Далее автор данной работы рассмотрит основные преимущества и недостатки каждого из методов для того чтобы подобрать наиболее эффективный инструмент маршрутизации перевозок. В конце данной главы наиболее подходящие методы решения управленческой проблемы будут рассмотрены более подробно. 2.1. Анализ литературы В работе Paolo Toth и Daniele Vigo под названием «The Vehicle Routing Problem» рассматривается классическая задача маршрутизации. Также авторы рассматривают различные вариации классической задачи маршрутизации, а именно: маршрутизация с ограничением грузоподъемности, маршрутизация с ограничением времени, маршрутизация с несколькими депо, маршрутизация с возвратом товаров, маршрутизация с различным транспортом, периодическая маршрутизация и другие. По каждой вариации задачи маршрутизации в работе представлена глава, в которой авторы описывают суть проблемы и приводят различные методы их решения. Основными способами решения задачи являются эвристические методы, т.к. они находят хорошее решение за приемлемое время, в отличие от точных методов. Более того, в работе рассматриваются практические примеры маршрутизации перевозок, применяемые в различных отраслях, которые доказывают актуальность маршрутизации перевозок. Применительно к компании HEINEKEN маршрутизацию автотранспорта возможно описать с помощью модели маршрутизации с ограничением грузоподъемности, т.к. при составлении маршрутов в компании ориентируются только на загрузку транспорта. В работе рассмотрен ряд методов для решения задачи маршрутизации с ограничением грузоподъемности. Из основных методов решения задачи можно выделить эвристические и мета-эвристические методы, которые используются в большинстве программного обеспечения по маршрутизации перевозок. В группу эвристических методов входят конструктивные методы (Метод сбережений) и двухфазные алгоритмы. При решении задачи двухфазным алгоритмом задача маршрутизации разделяется на две части. В первой части все множество точек доставки разделяется на группы, в рамках которых будет осуществляться доставка. Во второй части строится маршрут по каждой из частей. 19

Если рассматривать модель с ограничением времени применительно к маршрутизации в компании, то она не может быть применена, потому что время разгрузки у каждого клиента приблизительно одинаково за исключением крупных оптово-розничных клиентов, которые назначают время прибытия автотранспорта. Однако, данные клиенты не рассматриваются в рамках данной выпускной квалификационной работы. Различные типы моделей маршрутизации с возвратом товаров также не могут быть применены, т.к. при доставке готовой продукции возврат не предусмотрен. В рамках данного типа моделей возврат различных грузов от клиентов постоянен и, соответственно, возникает проблема свободного пространства в автотранспортном средстве. Если даже клиент отказывается от товара, то при доставке готовой продукции всегда найдется место для загрузки. В статье «A Concise Guide to the Traveling Salesman Problem» G. Laporte представлен разбор классической задачи коммивояжера с обзором различных методов решения задачи. Решение данной задачи представляет собой кратчайший путь, проходящий через все пункты. Работа содержит множество ссылок на работы, посвященные задаче коммивояжера. Автор приводит различные эвристические алгоритмы для решения симметричной и ассиметричной версии проблемы, которые легко применяются на реальных практических примерах. Однако методы, приведенные в данной статье, дают не точный результат. Более того, задача коммивояжера, рассмотренная в данной статье, не решает проблему маршрутизации, т.к. не учитывает множества ограничений необходимых для успешной доставки грузов. Задача не учитывает объемы спроса у каждого из клиентов, грузоподъемность автотранспортного средства, количество допустимых пунктов в маршруте и т.д. Тем не менее, при решении задачи маршрутизации двухфазным алгоритмом методы, используемые при решении задачи коммивояжера, могут быть применены, потому что все необходимые ограничения вводятся на первой фазе, а на второй остается только найти оптимальный маршрут. Статья William E. и Hardy Jr. «Vehicle Routing Efficiency: A Comparison of Districting Analysis and the Clarke-Wright Method» посвящена сравнительному анализу двух методов, которые могут использоваться для решения проблемы маршрутизации. Районный анализ представляет собой разделение всех пунктов посещения грузовика на определенные области. Количество областей определяется исходя из количества образовавшихся групп пунктов, которые находятся недалеко друг от друга. Дальнейшая маршрутизация происходит в пределах каждой из групп, а затем они соединяются в единую цепь с базой, т.е. в рамках данного метода грузовик после посещения каждой области должен возвращаться обратно на базу для загрузки. Второй метод - метод Кларка-Райта. Он 20

подразумевает собой объединение маятниковых маршрутов в кольцевые, которые используются в рамках первого метода. Таким образом, результатом работы William E. и Hardy Jr. является определение эффективности построения кольцевого маршрута в рамках маршрутизации перевозок. В итоге исследование маршрутов показало, что метод КларкаРайта является более эффективным, т.к. пройденное расстояние оказалось меньше, чем у районного анализа. В статье Смирнова А. А. «Оптимизация доставки готовой продукции и математический аппарат для ее достижения» приведены основные изменения, которые происходят после внедрения системы маршрутизации перевозок в любой компании. Маршрутизация перевозок позволяет уменьшать время выполнения каждого маршрута, снижать транспортные затраты на топливо, минимизировать количество опозданий к выгрузке у клиента и так далее. Автор работы приводит классификацию различных видов маршрутизации, которые зависят от конкретной системы доставки принятой в определенной компании. В классификацию входят: маршрутизация с ограничением по грузоподъемности, маршрутизация с ограничением по времени, маршрутизация с несколькими депо, маршрутизация с доставкой и возвратом товаров, маршрутизация с возвратом товаров и другие. В конце работы Смирнова А. А. приведена другая классификация наиболее часто используемых методов решения задач маршрутизации, которая сформирована исходя из первой классификации видов маршрутизации. В нее вошли следующие основные группы: простейшие методы, точные подходы, эвристические методы и мета-эвристики. Данные группы отличаются точностью решения и скоростью получения решения. Например, полный лексический перебор, входящий в группу простейших методов, является наиболее долгим методом, т.к. необходимо вручную перебрать все допустимые решения, которых может оказаться довольно большое количество. Также мета-эвристические методы дают более точный результат, чем обычные эвристические методы. В статье Зубарева А. К. «Планирование маршрутизации движения транспорта в условиях крупного города» рассматриваются различные методы решения проблем маршрутизации автотранспорта в пределах крупного города. Основная проблема маршрутизации, которую затрагивает автор в данной работе, связана с увеличивающимся количеством транспортных единиц на городских улицах. Транспортная инфраструктура крупных городов не позволяет быстро и с минимальными издержками перемещаться по оптимальному маршруту, т.к. развитие инфраструктуры происходит медленнее, чем увеличение транспорта на дорогах. В таких условиях задача маршрутизации может быть 21

решена с помощью построения кольцевого маршрута. Для его построения могут использоваться линейное программирование и эвристические методы. Основное различие данных методов заключается в том, что линейное программирование дает более точное решение, чем эвристические методы. В основной части работы Зубарев А. К. производит сравнительный анализ шести методов, которые позволяют найти кратчайший путь движения грузовика при условии, что грузовик посетит все точки один раз. В анализ включены следующие методы поиска решений: метод 2-опт, алгоритм имитации отжига, приемлемость предельного значения, алгоритм всемирного потопа, алгоритм разрушениявосстановления и нейронные сети. После проведенного анализа наилучший результат показал алгоритм всемирного потопа, который показал наименьшую длину маршрута во всем диапазоне изменения количества точек. Однако данный метод является эвристическим, поэтому результат может быть занижен относительно других методов. С другой стороны, расчет минимальной протяженности пути занимает меньше времени у эвристического метода по сравнению с точными методами. Профессор технической инженерии университета Арканзаса Хэмди А. Таха в своей работе под названием «Введение в исследование операций» рассматривает основные разделы теории исследования операций: теория принятия решений, математическое программирование (детерминированное и стохастическое, линейное и нелинейное), теория управления запасами, теория игр, имитационное моделирование и теория массового обслуживания. Помимо теории в работе представлены различные типы задач, которые решены с помощью представленных математических моделей. Также большое внимание в работе уделяется специальному классу задач, которые относятся к сетевым моделям целочисленного программирования, а именно: транспортная, распределительная задачи и задача о назначениях. Наиболее общей моделью является распределительная задача. В работе выделена целая глава под сетевые модели, но они не могут быть применимы в рамках поставленной управленческой проблемы, т.к. основная цель модели – определение объемов перевозок из пунктов предложения в пункты спроса с минимальной стоимостью транспортировки. Более того, в сетевой модели нет последовательного посещения точек спроса. В то время как управленческая проблема компании HEINEKEN представляет собой классическую задачу маршрутизации перевозок. Данная задача заключается в том, чтобы найти самый выгодный маршрут, удовлетворяющий всем необходимым ограничениям, который проходит последовательно через все точки спроса с последующим возвратом на исходное место. Причем все торговые точки автотранспортное средство должно посещать только 22

один раз. В работе Хэмди А. Таха присутствует раздел целочисленного линейного программирования с разбором решений задачи коммивояжера. В данном разделе изучается применение двух методов к решению задачи коммивояжера: метод ветвей и границ и метод отсекающих плоскостей. Как уже говорилось ранее методы решения задачи коммивояжера могут быть применены только в совокупности с двухфазным алгоритмом решения задачи маршрутизации перевозок, который вводит различные ограничения на транспортировки. В работе Зайцева М.Г. и Варюхина С.Е. «Методы оптимизации управления и принятия решений» рассматриваются основные методы и модели для оптимизации управления и принятия решений. Работа представляет собой набор теоретической информации по различным тематикам исследования операций, а также приемы для решения практических задач. Работа Зайцева М.Г. и Варюхина С.Е. включает в себя методы линейной оптимизации, планирование и анализ проектов, оптимальное управление запасами, а также методы, которые используются при принятии решений в условиях неопределенности. Транспортным задачам также выделена целая глава. В ней разбираются, как и самые простые транспортные задачи, где имеется шесть точек спроса и предложения и нужно определить из каких точек предложения нужно доставлять груз в точку спроса, для того чтобы минимизировать общие транспортные затраты, так и сложные, например, задача маршрутизации перевозок, решение которой будет использоваться в данной работе. 2.2. Выбор инструментария для анализа компании Как уже говорилось ранее, управленческая проблема в компании HEINEKEN напрямую связана с задачей маршрутизации перевозок, т.е. нужно определить самые выгодные маршруты, которые проходят через все торговые точки, где должна выгружаться продукция компании HEINEKEN. При чем, должны быть введены определенные ограничения на возможные объемы перевозимой продукции и количество посещаемых точек, во избежание срывов транспортировок из-за опоздания к времени выгрузки. Более того, при изменении длины маршрута компания не будет экономить деньги на транспортировках, т.к. транспортный тариф не зависит от длины маршрута и времени его прохождения. Для изменения данной ситуации в третьей главе будут рассмотрены различные транспортные тарифы, а затем они будут сравниваться с текущим тарифом с целью определения наиболее эффективного. 23

2.2.1. Метод Кларка-Райта Метод Кларка-Райта является одним из самых известных эвристических методов для решения задачи маршрутизации перевозок. Он основывается на понятии «сбережения», которое показывает снижение общей стоимости, получаемое при объединении двух маршрутов. Основная идея метода Кларка-Райта заключается в том, что происходит последовательное соединение мелких маршрутов в более крупные, пока не будут достигнуты различные ограничения. Мелкие маршруты представляют собой маятниковые маршруты, т.е. автотранспортное средство посещает одну точку и возвращается обратно в месторасположение базы. Затем их объединение формирует кольцевой маршрут, который и увеличивает «сбережения» от маршрутизации. Количество автотранспортных средств, доставляющих груз, определяется в процессе построения маршрутов движения. Сбережение, получаемое при объединении двух маятниковых маршрутов, определяется по формуле: sij =ci 0 +c 0 j−cij , где c i 0 – это расстояние от пункта i до месторасположения базы, c 0 j - расстояние от месторасположения базы до j пункта и c ij - расстояние от пункта i до пункта j. Для построения решения методом Кларка-Райта необходимо вычислить все «сбережения» между пунктами. Затем необходимо отсортировать «сбережения» в порядке убывания. После этого происходит формирование маршрутов, пока не будут достигнуты ограничения, введенные в модели. 2.2.2. Двухфазный алгоритм При решении задачи маршрутизации перевозок с помощью данного алгоритма решение разбивается на две фазы, а именно на фазу кластеризации и фазу построения маршрута. На первой фазе точки посещения автотранспортным средством объединяются в маршрут, который будет выполняться одним транспортным средством, причем точки, входящие в маршрут, не должны нарушать введенные ограничения. На второй фазе решается задача коммивояжера, а именно определяется последовательность посещения всех точек, входящих в кластер (маршрут). Кластеризация торговых точек будет осуществляться с помощью алгоритма заметания, а определение последовательности посещения точек с помощью жадного алгоритма, метода ветвей и границ и метода линейного программирования. 2.2.3. Алгоритм заметания При использовании алгоритма заметания кластеры группируются посредством поворота прямой исходящей из месторасположения базы, откуда будет производиться 24

доставка груза. Прямая начинает движение против часовой стрелки и все точки, которые затронет прямая объединяются в один кластер. Объединение продолжается до тех пор, пока не будет достигнуто определенное ограничение, поставленное перед проведением маршрутизации. После нахождения одного кластера движение прямой продолжается и новые точки объединяются в новый кластер. Также алгоритм позволяет производить дальнейшую оптимизацию кластеров, т.е. производить обмен точками между соседними кластерами. 2.2.4. Жадный алгоритм Жадный алгоритм относится к группе простейших алгоритмов и, соответственно, является самым простым к применению методом. Суть жадного алгоритма заключается в том, что на каждом этапе принятия решения выбирается локальное решение, которое является оптимальным на данном этапе. Однако не всегда данный алгоритм приводит к оптимальному решению задачи, т.к. принятие оптимальных решений на первых этапах приводит к тому, что на последних этапах выбирается не оптимальное решение. Главным преимуществом алгоритма является его простота. Для определения локальных решений не нужны дополнительные вычисления различных коэффициентов или параметров. Также поиск решения с помощью жадного алгоритма занимает немного времени из-за отсутствия анализа принимаемых решений. 2.2.5. Метод ветвей и границ Данный алгоритмический метод используется для решения целочисленных задач или частично целочисленных задач линейного программирования. Решение задачи коммивояжера может быть достигнуто путем простого перебора всех возможных маршрутов, по которым может проехать автотранспорт, но в рамках большого количества точек простой перебор будет неосуществим, т.к. количество вариантов маршрутов будет более двух тысяч. Для минимизации количества допустимых решений, которые будут заведомо хуже, чем оптимальное решение, можно использовать метод ветвей и границ. Основная идея данного метода заключается в том, что все множество допустимых решений будет последовательно отсекаться. Таким образом, на каждом шаге, когда мы выбираем путь от одной торговой точки до другой, элементы разбиения подвергаются анализу, т.е. определяется действительно ли, что данное перемещение автотранспорта из одной торговой точки в другую является оптимальным, по сравнению с другими перемещениями, которые могут быть произведены. При определении наилучшего перемещения из одной точки в другую будут сравниваться минимальные затраты, которые несет в себе данное перемещение. Если минимальные затраты увеличились на меньшее 25

число по сравнению с другой альтернативой, в которой не присутствует данное перемещение, то в итоговой транспортировке будет использоваться данное перемещение из одной торговой точки в другую. Процесс продолжается до тех пор, пока не будут просмотрены все элементы разбиения. Данный метод удобнее всего представлять в виде дерева решений, т.к. он наглядно показывает, какие перемещения будут приняты из всех допустимых. Для того, чтобы определить оптимальный маршрут с минимальными затратами, необходимо вначале построить исходную матрицу расстояний между всеми торговыми точками, которые были объединены в один маршрут. Диагональ матрицы, которая будет показывать перемещение автотранспортного средства из одного пункта в него же, будет иметь значение равное бесконечности. Бесконечность будет означать, что перемещение в один и тот же пункт не имеет смысла. Затем находятся минимальные значения расстояний по каждой строке и вычитаем данное значение из соответствующих строк. Такую редукцию производим и по столбцам. В итоге получается матрица расстояний, в которой некоторые значения равны нулю. Перемещения с нулевым значением являются оптимальными при выборе определенной вертикали или горизонтали, т.е. если автотранспортное средство будет выезжать со склада, то в строчке расстояний со склада найдется хотя бы одно оптимальное расстояние до торговой точки равное нулю. После этого все минимальные значения, выделенные во время первого этапа, по столбцам и строкам суммируются. Данное число будет показывать минимальное расстояние маршрута, которое является нижней границей ограничения. Также данное число будет являться в дальнейшем ориентиром при разбиении множества допустимых решений. Далее находится оценка для каждой нулевой клетки путем сложения минимального значения по строке и минимального значения по столбцу, в которых размещена нулевая клетка. Оценка показывает минимальную величину затрат расстояния, которая будет обязательно понесена в случае отказа от перемещения, для которого производилась оценка. После определения значений оценки выбирается нулевая клетка с самой большой оценкой. Затем производится анализ, который должен показать: нужно ли включать данное перемещение в общий маршрут или нет. Для начала рассмотрим вариант отклонения данного перемещения. Вместо нуля подставляем большое число, которое будет указывать на нецелесообразность данного перемещения. Далее определяем минимальные значения по строкам и столбцам, которые впоследствии суммируются и прибавляются к нижней границе ограничения расстояния маршрута. Затем рассматривается вариант, при котором перемещение из заданных пунктов будет обязательно выполнено. Для этого удаляется 26

строка и столбец, в которых находится рассматриваемое перемещение. Значение обратного перемещения меняется на большое число. После проведенных выше операций находится сумма минимальных значений по горизонтали и вертикали и прибавляется к нижней границе ограничения расстояния маршрута, полученной на первом этапе. Решение о включении перемещения в маршрут основывается на новых полученных границах, а именно чем меньше нижняя граница, тем более привлекательна альтернатива. После выбора альтернативы происходит повторение цикла. Данные циклы проводятся до того момента как определятся все перемещения автотранспортного средства по торговым точкам. 2.2.6. Метод линейного программирования Данный метод будет основан на применении надстройки «Поиск решения» в Microsoft Excel к поиску оптимального маршрута в рамках построенных кластеров. Несмотря на то, что задача коммивояжера является классическим примером применения метода динамического программирования, ее можно решить и с помощью целочисленного линейного программирования, которое позволяет решить задачу о коммивояжере без программирования кода. Для того, чтобы определить наиболее оптимальный маршрут передвижения автотранспорта, необходимо построить матрицу расстояний между всеми торговыми точками, которые объединены в единый маршрут. Цифры, проставленные в матрице, являются расстоянием в километрах от одной торговой точки до другой. Также наряду с торговыми точками имеется и база, из которой будет начинаться исходное движение автотранспорта и заканчиваться маршрут будет также в ней. Далее составляется таблица, которая идентична матрице состояний, за исключением того, что вместо расстояний в ней будут указываться переезды между торговыми точками. Таким образом, если в матрице переменных стоит значение равное единице, то данное перемещение будет выполняться, а если ноль, то перемещение не будет входить в маршрут. В итоге таблица переменных должна содержать в сумме столько единиц, сколько всего переездов на рассматриваемом маршруте. Затем определяется общее расстояние, которое проедет автотранспортное средство. Однако если применить «Поиск решения» к данной задаче он предложит не кольцевой маршрут, который требуется нам для решения задачи. Таким образом, необходимо дополнить модель несколькими таблицами и ограничениями. После первой попытки возникают дублирующие перемещения, т.е. автотранспортное средство совершает кольцевые перемещения в рамках двух точек. Для устранения дублирующих перемещений необходимо построить таблицу, которая 27

совпадает по размеру с матрицей перемещений и содержит суммы симметрично расположенных переменных из второй таблицы относительно диагонали. После этого необходимо добавить ограничения для данных сумм в «Поиск решений». Они должны быть меньше или равны единице. После запуска надстройки «Поиск решений» получается новое решение, но оно также не соответствует поставленной задаче. Теперь маршрут состоит не из одного кольцевого маршрута, а из нескольких кольцевых маршрутов, не связанных друг с другом. Для того, чтобы построить новое решение, которое бы нивелировало недостатки двух предыдущих решений, необходимо построить более громоздкое решение задачи коммивояжера. Построение нового решения возможно только при условии использования расширенной версии надстройки «Поиск решения» под названием Large-Scale LP Solver, т.к. при формулировке задачи количество переменных будет более двух тысяч. Расширенная версия позволяет использовать бесконечное количество переменных и ограничений в модели, в то время как в стандартной версии надстройки «Поиск Решения» может использоваться только до 200 переменных. Далее необходимо сформулировать основные требования к ограничениям и переменным. Первое требование – автотранспортное средство прибывает в первую торговую точку из базы. Второе требование – все последующие торговые точки должны посещаться из предыдущей по порядку посещения торговой точки. И последнее требование – весь маршрут должен заканчиваться на базе, т.е. после завершающей торговой точки автотранспортное средство приезжает обратно на базу. Математическая модель задачи линейного программирования выглядит следующим образом: n n minZ=min ∑ ∑ cij x ij , i =1 j=1 n ∑ xij=1, j=1,2 … n , i ≠ j, i−1 n ∑ xij=1 ,i=1,2 … n , i≠ j , j−1 ui−u j +n xij ≤ n−1,∀i , j ∈ { 1,2… n } ,i ≠ j , ui ≥ 0, i=1,2 … n , x ij ∈ { 0,1 } , ∀i , j ∈ { 1,2… n } , 28

где x ij – перемещение из точки i в точку j; с ij – понесенные затраты при выборе перемещения из i в j; n – количество точек в маршруте; ui – номер шага, на котором посетили точку i. Новая модель строится заново. Из старых моделей пригодится только матрица расстояний между торговыми точками. В начале строится основная таблица, в которой сводятся все данные по перемещениям между торговыми точками, и дополнительные таблицы, в которых выбирается последовательный порядок перемещения автотранспортного средства. Количество дополнительных таблиц будет таким же, как и количество торговых точек, не включая базы. Каждая дополнительная таблица относится к определенному этапу выбора перемещения, например, на первой дополнительной таблице выбирается первый и второй пункт посещения автотранспортным средством, на второй дополнительной таблице – третий и так далее. В основной таблице сводится вся информация из дополнительных таблиц так, чтобы при выборе одного перемещения оно отображалось в основной таблице. Затем строится еще одна таблица, подсчитывающая пройденное расстояние при выборе определенного маршрута. Таблица состоит из двух строк. В первой строке вычисляется пройденное расстояние после посещения первой торговой точки и так далее. Во второй – показывается последовательность посещения торговых точек, взятая из основной таблицы. В итоге, чтобы определить суммарное пройденное расстояние автотранспортным средством, необходимо сложить все значения первой строки. Это и будет являться целевой функцией, которую необходимо минимизировать. Когда модель полностью построена, в надстройке «Поиск решений» вводятся необходимые параметры модели. Выбирается целевая функция и переменные, которые находятся в дополнительных таблицах. Также необходимо ввести ограничение на переменные. Результатом проведенного метода будет являться построенный маршрут с минимальным расстоянием, которое пройдет автотранспортное средство. Выводы Во второй главе автор данной работы проанализировал различные источники отечественной и зарубежной литературы, посвященные решению различных управленческих проблем, связанных с маршрутизацией автотранспорта. В первой подглаве статья William E. и Hardy Jr показала, что маятниковый маршрут уступает кольцевому, т.к. протяженность маршрута транспортировки увеличивается. Также анализ литературы показал, что маршрутизация перевозок является необходимой функцией каждого современного предприятия, осуществляющего доставку продукции. Маршрутизация позволяет уменьшать общие затраты на транспортировку, повышать 29

уровень удовлетворенности клиентов, уменьшать время выполнения каждого маршрута и так далее. Анализ литературы также показал, что модели, которые позволяют находить оптимальный маршрут, имеют высокую степень разработанности в научной литературе. В зависимости от управленческой проблемы, решаемой в рамках транспортной логистики, могут быть подобраны соответствующие инструменты оптимизации. Для решения поставленных управленческих проблем в компании HEINEKEN мною было выбрано два метода, позволяющих определить оптимальный путь перемещения автотранспортного средства. Данные методы представляют различные подходы к решению задачи маршрутизации автотранспорта: метод Кларка-Райта и двухфазный алгоритм. Представленные методы являются эвристическими, что в свою очередь означает, что они позволяют получить хороший результат за приемлемое время. Метод Кларка-Райта позволяет формировать оптимальные маршруты и необходимое количество автотранспортных средств для доставки грузов. Построение маршрута с помощью двухфазного алгоритма выполняется в две фазы. На первой фазе объединяются торговые точки в кластеры, в рамках которых будет строиться маршрут. Построение кластеров осуществляется с помощью алгоритма заметания. Во время второй фазы определяется последовательность посещения точек с помощью следующих методов: жадный алгоритм, линейное целочисленное программирование, и метод ветвей и границ. Такой подбор методов обусловлен тем, что невозможно выделить хорошие или плохие методы для решения управленческой проблемы. В определенной ситуации каждый метод может оказаться лучшим. Например, в условиях ограниченного планирования наиболее эффективными методами будут являться эвристические подходы к решению задач маршрутизации, потому что поиск решения с помощью эвристического подхода занимает меньше времени. Применительно к компании HEINEKEN данные методы могут быть использованы. В следующей главе выбранные методы будут применены к реальной транспортировке с целью определения наилучшего маршрута доставки готовой продукции. 30

Глава 3. Решение управленческих проблем компании 3.1. Применение методов Построение обоих моделей, рассмотренных во второй главе, будет осуществляться на основе реальных заказов клиентов, поступивших 13 февраля 2016 года. Каждый заказ имеет определенный объем продукции, который должен быть доставлен к определенному месту. Всего насчитывается 49 клиентов, расположенных на окраине города СанктПетербург. Данный выбор критерия расположения клиентов обусловлен тем, что такой фактор как загруженность дорог будет оказывать минимальное влияние на перевозку грузов и, соответственно, можно будет точнее предсказать время прохождения всего маршрута. Все торговые точки являются магазинами шаговой доступности, поэтому выгрузка товара будет занимать не более тридцати минут. Доставка всей продукции будет начинаться и заканчиваться в месте расположения компании HEINEKEN. Карта расположения клиентов представлена на рисунке 3, где красные маркеры – это клиенты компании HEINEKEN, а зеленая звезда – это месторасположение компании, откуда будет начинаться и заканчиваться маршрут доставки готовой продукции. Рис. 3 Карта расположения клиентов компании HEINEKEN Как видно из рисунка 3 имеется несколько скоплений близко расположенных клиентов, а также клиентов, сильно разбросанных друг от друга, поэтому выбор последовательности посещения каждой торговой точки может сильно повлиять как на 31

пройденное расстояние, так и на время прохождения всего маршрута. Соответствие номеров клиентов и их местоположения приведено в приложении 1. Также в приложении 2 приведена информация по объему груза, который должен быть доставлен к определенному клиенту. Для подсчета расстояния между торговыми точками использовался Интернетресурс 2GIS.ru. Сайт предоставляет возможность рассчитывать кратчайшее расстояние по автомобильным дорогам между двумя точками по карте. Данные заказы клиентов были доставлены компанией HEINEKEN с помощью четырех грузовиков с грузоподъемностью равной 3,5 тонны. Общее расстояние, которое было пройдено всеми грузовиками составило 341 км. 3.1.1. Метод Кларка-Райта Перед построением решения задачи маршрутизации транспорта с помощью метода Кларка-Райта необходимо было составить матрицу расстояний между торговыми точками. Данная матрица расстояний приведена в приложении 3. В матрице указаны кратчайшие расстояния по дорогам общего пользования между торговыми точками, выраженные в километрах. Затем производится вычисление «сбережений», возникающих при объединении двух маршрутов. Все сбережения представлены в приложении 4. Дальнейшее построение маршрутов осуществляется на основе матрицы «сбережений». Для того, чтобы построить маршрут, необходимо найти в матрице «сбережений» наибольшее число, которое показывает километровый выигрыш при объединении двух пунктов. В нашем случае максимальное «сбережение» равняется 118 километрам, и оно получается при создании перемещения от клиента №11 к клиенту №10. Вся информация вписывается в таблицу (см. приложение 3). Затем данное перемещение проверяется на выполнение трех условий. Первое условие - пункты маршрута не должны входить в состав одного маршрута, который был рассмотрен ранее. Второе условие - объединение маршрутов происходит только с начальным или конечным пунктом маршрута. Третье условие – пункты, входящие в маршрут не должны быть использованы в других маршрутах. Если объединение двух торговых точек удовлетворяет всем условиям, то формируется перемещение из этих пунктов. Также формируется ограничение на объем перевозимой продукции, т.е. каждое автотранспортное средство может перевести определенный объем груза. Всю основную массу грузов компания HEINEKEN перевозит с помощью грузовиков с грузоподъемностью 3,5 тонны, которые переданы транспортно-экспедиционной компании 32

в аренду. В рамках исследования будут использоваться грузовики с точно такой же грузоподъемностью, т.к. средний объем спроса по клиентам составляет 250 килограмм, и грузовик может вместить груз, предназначенный для 14-16 клиентов. Количество клиентов, которое может входить в маршрут, было также ограничено 16 шт., т.к. при превышении данного числа возрастает вероятность не успеть к точкам, находящимся в конце маршрута. Таким образом, в приложении 5 на шаге 2 суммируются объемы продукции, которые должны быть доставлены к клиентам, входящим в маршрут. На шаге 3 каждому новому маршруту присваивается свой номер и составляется последовательность посещения точек, причем маршрут начинается и заканчивается в месторасположении базы. Далее рассматривается следующее по величине «сбережение». Данное «сбережение» равняется 112 километрам и получается при включении переезда от клиента №12 к клиенту №10. Выбранное перемещение удовлетворяет всем поставленным условиям, поэтому оно добавляется к основному маршруту. Теперь все варианты перемещений, включающие клиента №10 не выполнимы, поэтому в матрице «сбережений» удаляется строка и столбец клиента №10. Такой алгоритм повторяется до тех пор, пока не сформируются маршруты, которые будут содержать все торговые точки. После применения метода Кларка-Райта были получено четыре маршрута, которые охватывают все торговые точки. Вся информация по маршрутам представлена в таблице 1. Таблица 1 Результаты маршрутизации, полученные после применения метода Кларка-Райта Приблизительное время прохождения маршрута складывается из двух переменных, а именно: среднее время передвижения автотранспорта между пунктами и среднее время выгрузки товара у клиента. За среднее время выгрузки товара у клиента было принято брать 20-30 минут, а среднее время передвижения вычислялось исходя из средней скорости автотранспортного средства равной 40-50 км/ч. 3.1.2. Алгоритм заметания Для построения кластеров, в рамках которых автотранспортные средства будут доставлять готовую продукцию, необходимо сформировать ограничения, при достижении 33

которых будет начинаться новый кластер. Первым ограничением является грузоподъемность автомобиля. Основным средством доставки готовой продукции компании HEINEKEN является грузовик с грузоподъемностью 3,5 тонны, поэтому максимальный объем груза, перевозимый с помощью автотранспортного средства, не должен превышать 3,5 тонны. Второе ограничение – количество точек, входящих в маршрут не должно превышать 15-16 шт. Данное ограничение связано с тем, что при доставке заказов более 16 клиентам, автотранспортное средство не успевает к последним клиентам, т.к. время приемки заканчивается в 4-5 часов вечера. После определения ограничений были построены кластеры (см. рисунок 4). Рис. 4 Сформированные кластеры Загрузка автотранспортных средств, полученная во время построения кластеров, представлена в таблице 2. Общая утилизация транспортных средств составляет 79%. Данное значение вызвано достижением ограничения на количество точек, входящих в маршрут. Таблица 2 Загрузка автотранспортных средств Класте Объем груза, Утилизация 34

р кг. транспорта 1 3081 88% 2 2362 67% 3 3236 92% 4 2353 67% Далее поиск последовательности посещения торговых точек будет осуществляться последовательно на всех кластерах от первого до четвертого. После применения всех методов на кластерах будет вычислено пройденное расстояние и приблизительное время прохождения маршрута, которые позволят определить наиболее эффективный метод для поиска оптимального маршрута. 3.1.3. Жадный алгоритм Для применения жадного алгоритма необходима неполная матрица расстояний, которая была построена для использования в модели Кларка-Райта. В нее должны входить только те клиенты, которые попали в рассматриваемый кластер. Весь маршрут начинается на базе, поэтому на первом этапе, формирования жадного алгоритма, в строчке база ищется минимальное расстояние до определенной торговой точки. Когда кратчайшее расстояние найдено, по первой строчке определяется до какой торговой точки поедет автотранспортное средство. На первом этапе построения маршрута в кластере №1 автотранспортное средство поедет из месторасположения компании к клиенту №9. Затем на втором этапе выбирается торговая точка, которая будет посещена второй. Для этого по строке клиент №9 ищется минимальное расстояние до следующей торговой точки и определяется порядковый номер клиента. На втором этапе грузовик поедет на выгрузку к клиенту №6. Так продолжается до тех пор, пока маршрут не будет завершен на базе. При выборе кратчайшего расстояния основным ограничением является отсутствие выбранных перемещений по вертикали и горизонтали матрицы расстояний. Таким образом, после применения данного алгоритма ко всем кластерам получился следующий результат, представленный в таблице 3. Таблица 3 Маршруты, построенные с помощью жадного алгоритма 35

Полученный результат является неудовлетворительным, потому что при выборе наилучших альтернатив в конце остаются только перемещения с большими расстояниями. Также в процессе построения последовательности прохождения маршрута принимаемые решения о перемещениях от одного клиента к другому никак не оцениваются. 3.1.4. Метод ветвей и границ Построение маршрута с помощью метода ветвей и границ будет осуществляться на примере кластера №1. Для начала необходимо найти минимальное расстояние по каждой строчке среди всех торговых точек и затем вычесть его из всех значений по строкам (см. приложение 6.1). Такая же манипуляция производится и по столбцам (см. приложение 6.2). Далее определяется диапазон длины маршрута, в пределах которого будут изменяться значения маршрута. Нижняя граница диапазона равна сумме всех минимальных значений по строкам и столбцам и составляет 77,4 км. Верхней границей диапазона будет считаться решение жадного алгоритма. Так как перед нами стоит задача минимизации пройденного расстояния, решение, принимаемое на каждом этапе, будет оцениваться по нижней границе диапазона длины маршрута. Чем ближе полученное значение на каждом этапе, тем оно лучше. В полностью редуцированной матрице получаем, что в каждой строке и столбце имеется как минимум один ноль. Затем переходим к поиску оптимальных перемещений. На первом этапе определяется оценка каждого нулевого значения. Оценка перемещения складывается из двух наибольших значений по горизонтали и вертикали. Для этого по всем строкам и столбцам ищется второе наименьшее значение после нуля (см. приложение 6.3). Далее получаем, что перемещение от клиента №11 к клиенту №14 имеет наибольшую оценку, равную 5,5 км. Это означает, что при отказе от данного перемещения длина маршрута увеличится как минимум на 5,5 км. После этого проводится анализ перемещения от клиента №11 к клиенту №14. Рассматривается два варианта, при которых данное перемещение либо включено в маршрут, либо нет. Для начала рассмотрим вариант отсутствия перемещения в конечном маршруте. Вместо нулевого значения на пересечении клиента №11 и клиента №14 подставляется бесконечность. Она означает, что использование перемещения нецелесообразно. После этого суммируются получившиеся 36

минимальные значения по строкам и столбцам и прибавляются к нижней границе диапазона (см. приложение 6.4). Так нижняя граница диапазона длины маршрута для первого варианта составила 82,9 км. Далее рассмотрим вариант использования перемещения от клиента №11 к клиенту №14 в маршруте. Для этого удаляем строку клиента №11 и столбец клиента №14, т.к. выбор варианта перемещения с определенным расстоянием уже сделан. На пересечении строки клиент №14 и столбца клиент №11 вместо значения ставится бесконечность, потому что обратный маршрут не возможен. Затем, как и в первом варианте определяется сумма минимальных значений по столбцам и строкам и прибавляется к нижней границе диапазона, полученной перед первым этапом (см. приложение 6.5). В итоге не удалось определить наиболее предпочтительный вариант, т.к. нижние границы диапазонов равны, поэтому на данном этапе ни одна из альтернатив не будет отклонена. На рисунке 5 представлен результат, полученный после первого этапа. В вершине дерева находится все допустимое множество перемещений. Ниже расположены две альтернативы: X1 – включающая перемещение (11,14) и X2 – не включающая перемещение (11,14). Рис. 5 Альтернативные решения, полученные после первого этапа Далее на втором этапе будут рассматриваться две отдельные ветки X1 и X2. Для проведения второго этапа необходимо из измененных матриц расстояний вычесть полученные минимальные значения по строкам и столбцам. Затем повторяются аналогичные действия, выполненные на первом этапе. На этапе оценивания получается, что присутствие перемещения от клиента №14 к клиенту №11 дает меньшую нижнюю границу диапазона перемещений (рисунок 6), поэтому остальные альтернативы отвергаются и дальнейшее построение решения происходит относительно альтернативы X5. 37

Рис. 6 Альтернативные решения, полученные после второго этапа Так продолжается пока не закончатся все клиенты в матрице расстояний. Маршруты, построенные с помощью метода ветвей и границ, приведены в таблице 4. Таблица 4 Маршруты, построенные с помощью метода ветвей и границ Как видно из таблицы, общее пройденное расстояние и время прохождения маршрута значительно уменьшилось по сравнению с предыдущим методом. Это связано с тем, что в рамках метода, рассмотренного в данной подглаве, решение о выборе перемещения предварительно оценивается на основе затрат, которые могут быть понесены в случае отказа от данного перемещения. Общее пройденное расстояние автотранспортными средствами равняется 301 километру, а приблизительное время прохождения маршрута – 22,4 часа. 3.1.5. Метод линейного программирования Как уже говорилось ранее, метод линейного программирования будет применен к кластерам, которые были построены на первой фазе двухфазного алгоритма. В данном методе используется точно такая же матрица расстояний, выраженная в километрах, которая была использована в предыдущем методе ветвей и границ. Вся последовательность посещения торговых точек будет определяться на нескольких этапах, количество которых будет зависеть от количества пунктов посещения. На первом этапе выбирается первая и вторая торговая точка, которые будут посещены сразу же после выезда грузовика с базы (см. приложение 7.1). На втором этапе 38

будет определяться третья торговая точка, которую посетит грузовик. Так порядок выбора посещения торговых точек продолжается до последнего этапа, на котором выбирается последний пункт посещения автотранспортного средства, из которого грузовик направится обратно на базу. В итоге при составлении порядка посещения торговых точек в маршруте, состоящем из пятнадцати торговых точек, на первом и последнем этапах нам приходится выбирать по одному варианту перемещения из пятнадцати возможных, которые в сумме дают 30 переменных по двум этапам. А начиная со второго этапа, выбирается один вариант перемещения из 225 возможных, т.к. грузовик способен совершать перемещения из любой торговой точки в любую другую торговую точку. В сумме по всему маршруту получается 3180 переменных, на которые необходимо наложить определенные ограничения. Во-первых, данные переменные должны носить двоичный характер, потому что в каждой дополнительной матрице делается выбор перемещения, как в задаче о назначениях. Таким образом, при выборе определенного перемещения на каждом этапе в дополнительной матрице должна ставиться только одна единица, в то время как другие переменные, находящиеся в этой дополнительной таблице должны равняться нулю. Вовторых, суммы столбцов и строк, проведенные по каждой дополнительной матрице, должны равняться единице. В итоге получается 324 ограничения на переменные, не включая ограничений на двойственность. Все ограничения, которые используются в модели линейного программирования на переменные, а также параметры надстройки «Поиск решения» изображены на рисунке 7. Рис. 7 Окно настройки параметров надстройки «Поиск решений» 39

После запуска надстройки «Поиск решений» программа выдала решение, удовлетворяющее всем заданным ограничениям (см. приложение 7.2). Затем поиск последовательности посещения торговых точек был проведен на оставшихся трех кластерах. Полученные результаты, найденные с помощью линейной целочисленной оптимизации, для всех кластеров приведены в таблице 5, где отражена информация по длине маршрута, приблизительному времени его прохождения и последовательности посещения торговых точек. Таблица 5 Маршруты, построенные с помощью линейного программирования Общее пройденное расстояние по всем четырем маршрутам составило 289,6 километров, а суммарное время прохождения всех маршрутов – 22,1 часа. Данные результаты, полученные с помощью линейного программирования, являются наилучшими по сравнению с другими методами за счет того, что надстройка «Поиск Решений» перебирает всевозможные варианты прохождения маршрута. 3.2. Оценка использованных методов В данной подглаве будут рассмотрены результаты примененных методов к решению задачи маршрутизации транспорта компании HEINEKEN. За счет примененных методов удалось получить сокращение пройденного расстояния от 5 до 15% в зависимости от использованного инструментария (см. таблицу 6). Уменьшение пройденного расстояния позволяет увеличить эффективность использования автотранспортных средств, что в свою очередь позволяет уменьшать время прохождения маршрута. Время прохождения построенных маршрутов определяется на основе среднего времени выгрузки товара у клиента (около 20-30 минут) и среднего времени передвижения, которое вычисляется исходя из средней скорости автотранспортного средства равной 40-50 км/ч. Как видно из рисунка 7, использование двухфазного алгоритма позволяет снижать время нахождения автотранспортного средства на маршруте на 5%. В среднем на каждом маршруте экономится от 20 до 30 минут времени в зависимости от сложности маршрута. Данное снижение позволяет увеличивать эффективность перевозок и снижать количество случаев, когда водитель не успевает к последним клиентам на маршруте, потому что время 40

приемки у клиента заканчивается в 4-5 часов вечера. Прибавка в 20 минут может быть страховым запасом на случай различных заминок, возникающих при приемке товара или при неблагоприятной дорожной ситуации. Таблица 6 Сравнение использованных методов маршрутизации транспорта Для достижения таких же результатов на практике компании необходимо пересмотреть текущий подход к маршрутизации перевозок, а затем начать применять настроенное программное обеспечение, позволяющее в автоматическом режиме формировать маршруты с помощью похожих эвристических методов, приведенных в данной работе. Таким образом, формирование последовательности посещения торговых точек незначительно увеличит время на весь процесс маршрутизации при этом повышая эффективность использования транспортных средств. 3.3. Альтернативные транспортные тарифы В первой главе настоящей работы был рассмотрен транспортный тариф компании HEINEKEN на транспортировки в пределах Ленинградской области. Основным недостатком данного тарифа можно считать, что он не зависит от длины маршрута и времени его прохождения. Более того маршруты, попадающие в один тарифный диапазон, никак не дифференцируются по цене. Для устранения выявленных недостатков в ценообразовании тарифов на перевозки, в данной подглаве будут рассмотрены различные транспортные тарифы, зависящие от различных параметров. Стоимость перевозки грузов может варьироваться в зависимости от вида тарифа. Базовыми автотранспортными тарифами являются: повременной тариф; тариф, зависящий от пройденного расстояния; сдельный тариф и смешанный тариф. Суть смешанного тарифа заключается в том, что стоимость перевозки грузов формируется исходя из времени использования транспортного средства и пройденного расстояния. В основном смешанный тариф применяется при формировании стоимости междугородных транспортировок на большие расстояния. Также компании создают собственные специфические тарифы, которые могут быть оценены с помощью следующих факторов: 41

длина маршрута, время использования автотранспортного средства, масса груза, тип автомобиля, район доставки и другие. Для начала рассмотрим повременной тариф. Основной причиной использования повременного тарифа является невозможность расчета проходимого расстояния, а также времени доставки. Время доставки готовой продукции может значительно изменяться от случая к случаю и в основном зависит от времени выгрузки готовой продукции у клиента и загруженности дорог. Если у клиента возникнут вопросы по поводу сопроводительной документации или количество поставленной продукции не будет соответствовать заявленной, то процесс выяснения дальнейших действий может затянуться на долгое время. Как следствие водитель автотранспортного средства может не успеть выгрузиться у последних клиентов, находящихся в маршруте. Также загруженность дорог может негативно повлиять на скорость доставки готовой продукции. Однако, в рассматриваемом примере все маршруты проходят на окраине города, поэтому влияние данного фактора на скорость доставки минимизирована. Все приведенные выше факторы в значительной степени осложняют временное прогнозирование выполнения маршрута, поэтому все временные показатели, связанные с перевозками, будут приведены в приближенном виде. Если рассматривать полный рабочий день одного водителя, то за 11 часов он должен посетить 15 точек. Из этого следует, что водитель в среднем тратит 40-50 минут на путь до клиента и выгрузку. Однако многие водители проходят маршрут намного быстрее и заканчивают работу на 4-5 часов раньше. Данный маршрут осуществляет грузовик с грузоподъемностью 3,5 тонны, поэтому в качестве повременного тарифа будет использоваться значение равное 930 рублей в час. Также рассмотрим тариф, который зависит от пройденного расстояния автотранспортным средством. Основной причиной использования данного тарифа является невозможность точного прогнозирования времени движения автотранспортного средства. Для грузовика с грузоподъемностью 3,5 тонны тариф составляет около 70 рублей за километр пройденного расстояния. В данный тариф также включена наценка за месторасположение маршрута, т.к. он удален от центра города. В таблице 7 представлено сравнение различных методов на основе транспортных затрат компании. В ячейках представлены суммарные транспортные затраты по четырем маршрутам. При использовании транспортного тарифа компании HEINEKEN разницы между затратами нет, т.к. транспортный тариф компании не зависит от расстояния и времени. Однако если использовать повременной или покилометровый тариф, то транспортные затраты на транспортировку готовой продукции снижаются в среднем на 542

10%, что дает значительную экономию денежных средств. Лучший результат показал двухфазный алгоритм с последующим использованием линейного программирования. Снижение транспортных затрат составило 19% в сравнении с текущим тарифом, принятым в компании. Также при использовании повременного транспортного тарифа для коротких маршрутов, которые выполняются меньше чем за 6 часов, транспортные затраты значительно снижаются по сравнению с покилометровым тарифом. Таблица 7 Сравнение методов маршрутизации перевозок Таким образом, снижение затрат составит 4 728 рублей за 4 транспортировки, хотя за один день компания осуществляет минимум одиннадцать таких транспортировок, а в дни с пиковым спросом компания производит до 55 транспортировок. В случае, если компанией HEINEKEN будет осуществляться одиннадцать транспортировок в день, то в день экономия составит около 13 000 рублей и, соответственно, в месяц – 390 000 рублей. Для того, чтобы оценить значимость полученного снижения затрат, данная сумма будет сопоставлена с общими транспортными затратами на транспортировку готовой продукции по Санкт-Петербургу и Ленинградской области. В день компания тратит около 69 000 рублей на доставку готовой продукции. В месяц данная сумма составляет 2 070 000 рублей. В итоге компания будет экономить от 10 до 15% ежемесячно, в зависимости от сложности маршрутов, на транспортировки готовой продукции. Маршрутизация перевозок в совокупности с транспортным тарифом, зависящим от пройденного расстояния, позволят значительно снизить транспортные затраты, которые могут в дальнейшем быть использованными на разработку нового продукта или инвестиций в производство. Выводы 43

В данной главе автор применил методы, рассмотренные во второй главе настоящей работы, для решения задачи маршрутизации транспорта. Построение маршрутов осуществлялось на реальных заказах клиентов компании HEINEKEN за 13 февраля 2016 года. Всего было подобрано 49 заказов клиентов, которые находятся на удалении от центра города. Выбор критерия расположения клиентов обусловлен тем, что такой фактор, как загруженность дорог будет оказывать минимальное влияние на перевозку грузов и, соответственно, можно будет точнее предсказать время прохождения всего маршрута. Затем поочередно были построены маршруты для доставки готовой продукции с помощью метода Кларка–Райта и двухфазного алгоритма. Метод Кларка-Райта является одним из самых известных эвристических методов для решения задачи маршрутизации перевозок. Основной принцип формирования маршрутов при помощи данного метода заключается в том, что происходит последовательное соединение мелких маятниковых маршрутов в кольцевые маршруты. Формирование маршрутов происходит до тех пор, пока не будут достигнуты различные ограничения. Выбор последовательности посещения происходит исходя из понятия «сбережений», которое введено в модели Кларка-Райта. Оно показывает, сколько будет сэкономлено при выборе данного перемещения. В отличие от метода Кларка-Райта двухфазный метод разделен на две фазы, на которых сначала определяются кластеры, в рамках которых будут строиться маршруты, а затем определяется последовательность посещения торговых точек, входящих в кластер. Кластеризация осуществляется с помощью алгоритма заметания, после которого проводится дополнительная оптимизация кластеров путем обмена точками между соседними кластерами. На второй фазе последовательность посещения торговых точек строилась жадным алгоритмом, методом ветвей и границ и линейным программированием. Жадный алгоритм оказался наименее эффективным. Построенный маршрут оказался длиннее исходного на 27 километров. Далее было произведено сравнение использованных методов. Оценка производилась по критерию пройденного расстояния автотранспортным средством и времени прохождения всего маршрута. За счет примененных методов удалось получить сокращение пройденного расстояния от 5 до 15%, в зависимости от сложности маршрута, а время прохождения маршрута снизилось на 5% в сравнении с исходными маршрутами, которые были пройдены 13 февраля 2016 года. После этого были рассмотрены альтернативные транспортные тарифы, примененные к построенным маршрутам. При применении альтернативных тарифов к исходному маршруту экономия составила от 5 до 44

15% в зависимости от применяемых транспортных тарифов. В случае использования повременного и покилометрового тарифа к маршрутам, построенным с помощью методов, рассмотренных во второй главе, экономия транспортных затрат на доставку готовой продукции по Санкт-Петербургу и Ленинградской области составляет от 10 до 15% ежемесячно, в зависимости от сложности маршрутов. Таким образом, примененные методы в третьей главе в совокупности с альтернативными транспортными тарифами дают значительную экономию денежных средств на транспортировку готовой продукции. 45

Заключение В данной выпускной квалификационной работе автор разработал систему маршрутизации автомобильных перевозок компании «Объединенные Пивоварни Хейнекен», которая позволит повысить эффективность использования автотранспортных средств за счет уменьшения проходимого расстояния и времени нахождения грузовика на маршруте. Это в свою очередь поможет снизить транспортные затраты, которые составляют значительную часть от суммарных затрат компании. Более того, увеличение эффективности использования автотранспортных средств позволит уменьшить выбросы углекислого газа в окружающую среду и соответственно увеличить показатели, соответствующие стратегии устойчивого развития компании HEINEKEN. Также автор настоящей работы рассмотрел транспортные тарифы компании и определил, что они не дифференцируются в рамках одного тарифного диапазона, поэтому автором было предложено несколько вариаций транспортных тарифов, которые позволяют снизить затраты на транспортировки. В первой главе настоящей работы автор рассмотрел основные факторы, влияющие на деятельность компании HEINEKEN в России. Одним из наиболее влиятельных факторов за последнее время является ужесточение акцизной политики государством, поэтому пивоваренным компаниям необходимо минимизировать издержки для сохранения конкурентоспособной позиции на рынке. Также государство ограничивает розничную продажу алкогольной продукции в нестационарных торговых объектах. Все это дестабилизирует пивоваренную отрасль. Транснациональные компании закрывают свои производственные площадки в разных городах. Более того, производственные мощности многих производителей пива работают в половину мощности, поэтому компании HEINEKEN просто необходимо следить за уровнем затрат. Во второй главе была рассмотрена отечественная и зарубежная научная литература, посвященная изучению различных методов маршрутизации автотранспортных перевозок. Первичное ознакомление с научной литературой показало, что проблема маршрутизации перевозок широко освящена в научной литературе. Под определенную систему дистрибуции разработаны собственные модели маршрутизации, позволяющие определить оптимальные маршруты для доставки грузов. Также в процессе анализа научной литературы были выявлены преимущества и недостатки различных методов, на основе которых было подобрано два эвристических метода, представляющие различные подходы к решению задачи маршрутизации транспорта. Первым методом для решения задачи маршрутизации транспорта является метод Кларка-Райта, позволяющий формировать 46

маршруты исходя из полученных «сбережений». Количество автотранспортных средств, необходимых для доставки всей готовой продукции, определяется в процессе построения маршрута. Второй метод – двухфазный алгоритм, позволяющий за две фазы формировать группы заказов, по которым будет осуществляться доставка, а затем определять последовательность посещения торговых точек в рамках этих групп. В третьей главе рассмотренные ранее методы решения задачи маршрутизации транспорта были применены к реальным заказам клиентов, которые поступили 13 февраля 2016 года. Все заказы имеют определенный вес и местоположение клиента для доставки. Построенные маршруты показали лучший результат по сравнению с исходными маршрутами за исключением двухфазного алгоритма с дальнейшим применением жадного алгоритма, который не подразумевает анализ принимаемых решений. Пройденное расстояние уменьшилось на 5-15% в зависимости от сложности маршрута, а время прохождения всего маршрута снизилось на 5%, что дает в среднем 20-30 минут экономии времени на каждом маршруте. После этого было произведено сравнение текущего транспортного тарифа компании HEINEKEN и альтернативных транспортных тарифов. При применении повременного или покилометрового транспортного тарифа экономия составила от 10 до 15% денежных средств ежемесячно. Данная сумма составляет значительную часть транспортных затрат компании на доставку готовой продукции по Санкт-Петербургу и Ленинградской области, которая может быть сэкономлена и расходована на более необходимые нужды компании. Таким образом, данная система маршрутизации может быть применена в компании с помощью установки программного обеспечения по маршрутизации перевозок, которое использует похожие эвристические методы, использованные в данной выпускной квалификационной работе. Также необходимо пересмотреть текущий транспортный тариф, принятый в компании HEINEKEN, для того чтобы снизить общие транспортные затраты. 47

Список использованной литературы 1. Пожидаев, М. С. Алгоритмы решения задачи маршрутизации транспорта: автореф. дис. на соискание канд. тех. наук: 05.13.18 / Пожидаев Михаил Сергеевич. - Томск., 2010. – 19 с. 2. Таха, Хемди А. Введение в исследование операций / Хемди А. Таха. – 7-е изд.: пер. с англ. – М.: Вильямс, 2005. – 912 с. 3. Единая государственная автоматизированная информационная система [Электронный ресурс] // ФГУП «Центринформ». — Режим доступа: http://egais2016.ru/egais/ (дата обращения: 20.05.2016). 4. Задача маршрутизации транспорта [Электронный ресурс] // Санкт-Петербургский университет информационных технологий, механики и оптики — Режим доступа: http://rain.ifmo.ru/cat/view.php/theory/unsorted/vrp-2006 (дата обращения: 20.05.2016). 5. История концерна HEINEKEN [Электронный ресурс] // HEINEKEN Russia. — Режим доступа: http://www.heinekenrussia.ru/company/heineken_group/history (дата обращения: 20.05.2016). 6. История пивоваренной компании «Балтика» [Электронный ресурс] // Пивоваренная компания «Балтика». — Режим доступа: http://corporate.baltika.ru/m/41/the_history_of_baltika_breweries.html (дата обращения: 20.05.2016). 7. Кодекс поставщика [Электронный ресурс] // HEINEKEN Russia. — Режим доступа: http://www.heinekenrussia.ru/suppliers/supplier_code/ (дата обращения: 20.05.2016). 8. Концерн HEINEKEN [Электронный ресурс] // HEINEKEN Russia. — Режим доступа: http://www.heinekenrussia.ru/company/heineken_group (дата обращения: 20.05.2016). 9. Международные бренды / Heineken (Хейнекен) [Электронный ресурс] // HEINEKEN Russia. — Режим доступа: http://www.heinekenrussia.ru/brands/international_brands/heineken/ (дата обращения: 20.05.2016). 10. Метод Кларка-Райта. Оптимальное планирование маршрутов грузоперевозок [Электронный ресурс] // ООО «Инфостарт». — Режим доступа: http://infostart.ru/public/443585/ (дата обращения: 20.05.2016). 48

11. Чернышев, С. В. Модели, методы и алгоритмы эффективного решения задачи маршрутизации транспорта на графах больших размерностей: автореф. дис. на соискание канд. физ.-мат. наук: 05.13.18 / Чернышев Сергей Владленович. - М., 2011. – 22 с. 12. Зайцев, М.Г. Методы оптимизации управления и принятия решений: примеры, задачи, кейсы: учебное пособие / С.Е. Варюхин, М.Г. Зайцев – 2-е изд., испр. – М.: Издательство «Дело» АНХ, 2008. – 664 с. 13. Смирнова А. А. Оптимизация доставки готовой продукции и математический аппарат для ее достижения / А. А. Смирнова // Известия Санкт-Петербургского университета экономики и финансов. – 2009. - № 4. 14. Отчет о деятельности компании HEINEKEN в России в области устойчивого развития бизнеса [Электронный ресурс] // HEINEKEN Russia. — Режим доступа: http://sustainabilityrussia.ru/otchetnost/2014/about (дата обращения: 20.05.2016). 15. Отчет об устойчивом развитии компании Балтика [Электронный ресурс] // Пивоваренная компания «Балтика». — Режим доступа: http://corporate.baltika.ru/i/msg/7113/baltika_otchet_ob_ustoychiwom_razwitii_2014.pdf (дата обращения: 20.05.2016). 16. Зубарева А. К. Планирование маршрутизации движения транспорта в условиях крупного города / А. К. Зубарев // Современные проблемы транспортного комплекса России. – 2013. - № 3. 17. Статистический справочник России 2014 год [Электронный ресурс] // Федеральная служба государственной статистики. — Режим доступа: http://sustainabilityrussia.ru/otchetnost/2014/about (дата обращения: 20.05.2016). 18. Число пивоварен в Европе удвоилось за семь лет [Электронный ресурс] // Ведомости. — Режим доступа: https://www.vedomosti.ru/business/articles/2015/11/06/615772-evropeiskii-pivovarenniibum (дата обращения: 20.05.2016). 19. Laporte, G. A Concise Guide to the Traveling Salesman Problem [Electronic resource] / G. Laporte // JSTOR. – Режим доступа: http://www.jstor.org.ezproxy.gsom.spbu.ru:2048/stable/pdf/40540226.pdf? _=1460820285494 (дата обращения: 20.05.2016). 49

20. A summary of 2015 annual report [Electronic resource] // HEINEKEN Holding N. V. — Режим доступа: http://www.theheinekencompany.com/investors/performancehighlights-2015 (дата обращения: 20.05.2016). 21. Toth, Paolo The vehicle routing problem / Paolo Toth, Daniele Vigo - Society for Industrial and Applied Mathematics, 2002. – 367 p. 22. William E., Vehicle Routing Efficiency: A Comparison of Districting Analysis and the Clarke-Wright Method [Electronic resource] / E. William, Jr. Hardy // JSTOR. – Режим доступа: http://www.jstor.org.ezproxy.gsom.spbu.ru:2048/stable/pdf/1240210.pdf (дата обращения: 20.05.2016). 50

Приложения Приложение 1. Соответствие номеров клиентов и их местоположения 51

Приложение 2. Объемы грузов для доставки клиентам Номе р клие нта Клие нт №1 Клие нт №2 Клие нт №3 Клие В е с з а к а з а , к г . 1 1 3 , 4 1 1 6 , 1 1 8 7 , 3 3 Номер клиен та Клиен т №11 Клиен т №12 Клиен т №13 Клиен В е с з а к а з а , к г . 8 9 , 2 1 2 1 , 1 1 1 2 , 8 2 Ве с за ка за, кг. Номе р клие нта В е с з а к а з а, к г. Клиен т №21 49 4, 2 Клие нт №31 Клиен т №22 11 8, 0 28 ,5 55 Номер клиен та Клиен т №23 Клиен Номер клиент а Ве с за ка за, кг. 9 1, 3 Клие нт №41 18 4,6 Клие нт №32 1 6 4, 2 Клие нт №42 25 6,3 Клие нт №33 Клие 1 6 3, 4 4 Клие нт №43 Клие 71 8,3 16 52

нт №4 Клие нт №5 Клие нт №6 Клие нт №7 Клие нт №8 Клие нт №9 Клие нт №10 4 2 , 9 1 0 1 , 7 3 9 2 , 7 3 3 5 , 3 6 0 4 , 9 1 3 0 , 1 1 3 0 Клиен т №15 7 4 , 0 2 6 5 , 0 Клиен т №16 7 6 , 3 Клиен т №17 7 8 , 8 Клиен т №18 4 1 , 4 т №14 Клиен т №19 Клиен т №20 8 7 , 9 5 8 3 т №24 ,2 нт №34 Клиен т №25 40 0, 4 Клие нт №35 2 9, 4 Клие нт №45 76, 0 70 ,5 Клие нт №36 1 5 3, 4 Клие нт №46 20 4,3 Клие нт №37 2 0 7, 6 Клие нт №47 40 0,3 54 9, 8 Клие нт №38 6 2 0, 8 Клие нт №48 26, 3 43 9, 1 51 7, 3 Клие нт №39 Клие нт №40 2 3 8, 0 2 4 9, Клие нт №49 45, 1 Клиен т №26 Клиен т №27 Клиен т №28 Клиен т №29 Клиен т №30 13 9, 6 1, 5 нт №44 5,1 - 53

, 8 , 4 1 54

Приложение 3. Матрица расстояний между торговыми точками в километрах База Клиен т №1 Клиен т №2 Клиен т №3 Клиен т №4 Клиен т №5 Клиен т №6 Клиен т №7 Клиен т №8 Клиен т №9 Клиен т №10 Клиен т №11 Клиен т №12 Клиен т №13 Б аз а 21 ,6 18 ,7 22 ,4 19 22 ,6 15 ,1 16 21 ,8 15 ,6 59 ,7 65 56 ,8 19 ,3 1 2 3 4 5 6 7 8 9 10 11 4,5 1 4,5 3,7 2 4,2 1,7 5 1,2 4,4 8 5 7,7 6,2 8,2 7 2,7 6,5 4 7 3,4 1,5 4 1,4 3 2 6,4 5,4 6,8 4 6,7 5,2 7,2 2 2,7 5,3 24, 7 26, 2 20, 7 22, 2 25, 4 26, 9 25, 5 22, 2 23, 7 16, 5 23, 8 25, 3 18, 1 7,1 1 4 21, 8 21, 5 22, 8 29, 5 25, 6 20, 7 22, 1 29 15 19 15 20 20 2,1 2,4 2 2,1 2,5 5,5 4,5 24 27 9,8 10, 5 23, 6 … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … 41 42 55

Клиен т №14 Клиен т №15 Клиен т №16 Клиен т №17 Клиен т №18 Клиен т №19 Клиен т №20 … 65 26, 4 29 25, 5 29, 6 15 ,3 10 7,1 10 8,5 13 8,6 6 9,5 5,7 13 ,2 23 ,3 14 11 26, 6 22, 7 14, 7 26, 5 11 14 10 14 12 ,4 … 12, 1 … 8,3 … 12, 1 … 30 30, 3 27, 1 28, 6 3,3 6 8,6 5 9,4 3 3 7,4 4,2 11 14, 5 7,2 9 24 27 21, 2 21 11, 4 14, 5 12, 6 … 8 8,3 5,4 6,4 … … 9 … 25, 5 10, 5 12, 5 25, 1 12, 6 10, 7 … 9,4 22, 8 10, 2 6,7 … 9,2 3,7 35, 9 35, 3 31, 6 46, 6 37, 5 35, 6 … 29, 4 28, 2 33, 3 55, 4 34, 3 44, 4 … … … … … … … … … … … … … … … … … … … 56

Приложение 4. Матрица «сбережений» 2 Клиен т №1 Клиен т №2 Клиен т №3 Клиен т №4 Клиен т №5 Клиен т №6 Клиен т №7 Клиен т №8 Клиен т №9 Клиен т №10 Клиен т №11 Клиен т №12 Клиен т №13 Клиен 35, 8 40, 1 37, 7 39, 9 29, 7 24, 1 36, 3 30, 6 53, 8 10 2 92, 3 74 57, 3 36, 6 39, 4 36, 6 32, 7 28, 4 33, 8 33, 4 51, 3 99, 1 92, 8 73, 7 55, 4 37, 2 40, 4 30 24, 6 36, 4 30, 7 54, 6 10 3 10 7 74, 1 58, 5 37, 2 31, 5 27, 1 34, 8 32, 2 50, 6 98, 5 10 3 74 54, 6 29, 5 24, 1 35, 8 30, 2 54, 6 10 3 10 7 73, 6 58, 7 27, 7 31, 4 35, 4 49, 9 97, 8 10 2 70, 6 54, 8 32, 4 34, 7 49, 8 97, 7 10 2 71, 6 54 9 32, 1 53, 1 10 1 10 5 75, 1 57, 10 51, 5 99, 4 10 4 72, 1 55, 11 12 118 112 111 54, 3 75, 52, 5 80, … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … 42 43 57

т №14 Клиен т №15 Клиен т №16 Клиен т №17 Клиен т №18 Клиен т №19 Клиен т №20 … 9 70, 3 19, 7 12, 2 9,9 20, 3 11, 3 … 3 73, 2 22, 3 15, 2 13, 8 24, 3 15, 1 … 8 70, 3 18, 8 11, 5 10 20, 3 11, 3 … 7 71, 8 22, 6 15, 2 12, 5 22, 9 14, 4 … 8 69, 8 18, 9 11, 7 9,5 19, 8 10, 8 … 3 77 25, 3 19 15, 3 26, 3 74, 3 25, 3 17, 2 15, 5 26 18 17 … … 2 71, 7 20, 9 13, 7 11, 4 21, 7 12, 7 … 7 75, 3 24, 1 16, 8 13, 7 24, 1 16, 7 … 1 44, 4 6 50, 9 -7 0,1 5,4 7,1 -10 … … … … … … -19 … … 0 … … -12 -21 … … … … … … 3,2 … … 58

Приложение 5. Метод Кларка-Райта Шаг 1 Шаг 3 Шаг 2 На ча ль ны й объ ем, кг. S m ax Об ъе м до ба вл ен ия гр узо в, кг. № м а р ш р у т а Маршрут Об ъе м пе ре воз ки, кг. 11 + + + 131 + + + 220 89 12 1 + + + 341 12 1 + + + 462 11 10 2, 10 2, 77+ 75 ,3+ 75 ,1+ 74+ + + 265 + + 658 + + + + 113 718 18 7 39 3 13 0 60 5 64 1 0-11-10-0 220 1 0-11-10-12-0 341 1 0-11-10-12-5-0 462 1 0-3-11-10-12-5-0 649 2 0-15-6-0 658 2 0-9-15-6-0 788 3 1 0-13-8-0 0-8-13-3-11-10-12-5-0 718 136 59

,1 58 ,8+ 57 ,9+ 48 ,6+ 47 ,8+ 47 ,4+ 46+ 41 ,2+ 41 ,1+ 40 ,1+ 39 ,6+ 39 ,4+ 38 ,6+ 38 ,1+ 9 27 4 27 4 16 5 71 8 7 164 1 191 5 + + 136 7 164 1 + + 204 + + + + 369 108 8 116 4 + + 118 55 5 0-24-22-0 173 + + 173 41 5 0-18-24-22-0 215 + + 788 2 + + 816 1 0-23-9-15-6-0 0-6-15-9-23-8-13-3-11-10-12-514-1-0 816 273 2 + + 116 6 0-4-2-0 459 + + 29 28 19 15 34 3 16 4 7 0-35-32-0 194 + + 194 273 2 42 45 9 23 8 7 1 0-34-35-32-0 0-6-15-9-23-8-13-3-11-10-12-514-1-4-2-0 235 319 0 7 0-34-35-32-39-0 473 + + + + 37+ + + 35 ,6+ + + 235 1 0-8-13-3-11-10-12-5-14-0 1 0-8-13-3-11-10-12-5-14-1-0 4 0-46-44-0 4 0-43-46-44-0 76 20 8 4 0-43-46-44-45-0 4 0-43-46-44-45-37-0 369 108 8 116 4 137 1 60

32 ,9+ 32 ,5+ 32 ,3+ 30 ,7+ 30 ,1+ 28 ,1+ 27 ,7+ 27 ,3+ 27 ,3+ 26 ,5+ 25 ,3+ 23 ,5+ 22 ,5+ 21 ,7+ 19 ,4+ 18+ + + 249 + + + + 870 134 3 149 7 168 1 62 1 47 3 15 3 18 5 13 71 + + 88 + + 164 + + + + 163 305 2 + + 400 + + 243 + + 471 + + + + 685 118 0 70 33 5 21 5 49 4 58 3 + + + + 400 445 45 26 + + + + 8 0-38-40-0 8 0-34-35-32-39-38-40-0 8 0-34-35-32-39-38-40-36-0 8 8 0-34-35-32-39-38-40-36-41-0 0-34-35-32-39-38-40-36-41-3745-44-46-43-0 870 134 3 149 7 168 1 305 2 76 9 0-19-16-0 164 79 25 6 42 0 9 1 0 1 0 1 1 0-17-19-16-0 243 0-42-33-0 0-33-42-34-35-32-39-38-40-3641-37-45-44-46-43-0 420 347 2 0-25-26-0 471 9 1 1 1 1 1 1 1 2 1 0-17-19-16-7-0 578 0-26-25-18-24-22-0 0-26-25-18-24-22-21-20-0 685 118 0 176 3 0-49-47-0 0-49-47-48-0 445 472 0-26-25-18-24-22-21-0 61

,7 18 ,5+ + + 14 ,3+ + + 11+ 8, + 5, + 3, + 176 3 234 1 + + 472 + + 611 116 1 167 8 + + + + 57 8 91 14 0 55 0 51 7 43 9 2 1 1 1 1 1 2 1 2 1 2 1 2 0-26-25-18-24-22-21-20-17-1916-7-0 0-31-26-25-18-24-22-21-20-1719-16-7-0 234 1 243 3 0-49-47-48-27-0 611 116 1 167 8 211 7 0-28-49-47-48-27-0 0-30-28-49-47-48-27-0 0-29-30-28-49-47-48-27-0 62

Приложение 6. Метод ветвей и границ Приложение 6.1. Определение минимальных элементов по строкам База Клиен т №1 Клиен т №2 Клиен т №3 Клиен т №4 Клиен т №5 Клиен т №6 Клиен т №7 Клиен т №8 Клиен т №9 Клиен т №10 Клиен т №11 Б аз а 1 2 3 4 5 6 7 8 9 10 - 21, 6 18, 7 22, 4 19 22, 6 15, 1 16 21, 8 15, 6 - 4,5 1 3,7 1,7 8 7 1,5 6,8 59, 7 21, 5 4,5 2 5 5 2,7 4 4 4,2 1,2 7,7 6,5 1,4 6,7 4,4 6,2 4 3 5,2 8,2 7 2 7,2 3,4 6,4 2 5,4 2,7 21 ,6 18 ,7 22 ,4 4,5 1 4,5 19 3,7 2 4,2 1,7 5 1,2 4,4 8 5 7,7 6,2 8,2 7 2,7 6,5 4 7 3,4 1,5 4 1,4 3 2 6,4 5,4 6,8 4 6,7 5,2 7,2 2 2,7 5,3 20, 7 22, 1 24, 7 26, 2 20, 7 22, 2 25, 4 26, 9 25, 5 22, 2 23, 7 22 ,6 15 ,1 16 21 ,8 15 ,6 59 ,7 65 21, 5 22, 8 24 25, 6 27 5,3 23, 8 25, 3 24 20, 7 24, 7 20, 7 25, 4 25, 5 22, 2 23, 8 7,1 11 12 13 14 23 56, 8 29, 5 19, 3 65 18, 4 2,1 26, 4 6 29 2,4 29 5 15 2 19 2,1 15 2,5 20 5,5 27 20 4,5 23, 7 25, 3 16, 5 18, 1 7,1 9,8 65 22, 8 25, 6 22, 1 26, 2 22, 2 26, 9 10, 5 1 4 21, 8 23, 6 25, 5 29, 6 25, 5 30 30, 3 27, 1 28, 6 9,2 3,7 M IN 15 ,1 5,6 6,2 6,3 1, 4,2 5,5 2, 4,2 3,7 22, 5 24, 2 7, 3, 63

Клиен т №12 Клиен т №13 Клиен т №14 Клиен т №23 56 ,8 19 ,3 29, 5 29 15 19 15 20 20 16, 5 18, 1 9,8 2,1 2,4 2 2,1 2,5 5,5 4,5 1 4 21, 8 10, 5 23, 6 65 26, 4 29 25, 5 29, 6 25, 5 30 30, 3 27, 1 28, 6 9,2 3,7 18 ,4 6 5 5,6 6,2 6,3 4,2 5,5 4,2 3,7 22, 5 24, 2 16, 4 16, 4 14, 3 17 14, 3 17 27 4,1 27, 6 27 4,1 27, 6 9, 3, 3, 64

Приложение 6.2. Редуцированная матрица по строкам База Клиен т №1 Клиен т №2 Клиен т №3 Клиен т №4 Клиен т №5 Клиен т №6 Клиен т №7 Клиен т №8 Клиен т №9 Клиен т №10 Клиен т №11 Клиен Б аз а 1 2 3 4 5 6 7 8 9 - 6,5 3,6 7,3 3,9 7,5 0 0,9 6,7 0,5 - 3,5 0 2,7 0,7 7 6 0,5 5,8 2,5 0 3 3 0,7 2 2 3,2 0,2 6,7 5,5 0,4 5,7 2,4 4,2 2 1 3,2 7 5,8 0,8 6 1,4 4,4 0 2,7 0 20 ,6 16 ,7 21 ,4 2,5 0 3,5 17 1,7 0 2,2 0,5 3,8 0 3,2 6 3 5,7 4,2 6,2 4,3 0 3,8 1,3 4,3 0,7 0,5 3 0,4 2 1 5,4 4,4 4,8 2 4,7 3,2 5,2 0 0,7 3,3 14, 4 19, 1 19, 16, 9 21, 9 19, 13, 6 18, 4 5,2 17, 6 22, 5 9,2 13, 6 18, 5 5,2 18, 3 23, 2 10, 18, 4 23, 3 10, 15, 1 21 ,4 13 ,1 13 ,3 20 ,8 13 ,6 52 ,6 61 ,3 47 4,3 20 6,7 16, 7 21, 6 8,3 10 11 12 44, 6 20, 5 49, 9 21, 8 23, 6 21, 1 24, 2 41, 7 28, 5 22 19, 7 22, 7 19, 5 23, 4 22, 8 21, 2 21, 8 21 0 1,1 0,4 14 1 17 0,1 13, 8 1,3 18 3,5 17, 3 15, 5 16, 1 0 2,7 6,8 0,7 4,2 27 24, 9 24, 3 22, 7 23, 3 3,4 13 1,8 0 2 14, 7 19, 9 6,6 14 49, 9 25, 4 27 24, 5 27, 6 24, 3 28 27, 6 26, 1 26, 6 2,1 0 4,5 23 3,3 5 3 4,6 4,2 5,1 2,2 2,8 3,2 1,7 15, 4 20, 5 7,2 65

т №12 Клиен т №13 Клиен т №14 Клиен т №23 MIN 18 ,3 61 ,3 14 ,7 13 ,1 7 2 2 2 1,1 1,4 1 1,1 1,5 4,5 3,5 0 3 20, 8 22, 6 22, 7 25, 3 21, 8 25, 9 21, 8 26, 3 26, 6 23, 4 24, 9 5,5 0 2,3 1,3 1,9 2,5 2,6 0,5 1,8 0,5 0 18, 8 0 0 0 0 0,2 0 0,7 0 0 0 23, 3 20, 5 15, 4 10, 6 13, 3 0,4 23, 9 0 2,7 0 0 26 3,1 23, 9 1,7 66

Приложение 6.3. Оценка каждого нулевого значения База Клие нт №1 Клие нт №2 Клие нт №3 Клие нт №4 Клие нт №5 Клие нт №6 Клие О ц е н к а 0 , 2 0 , 5 Б аз а 1 2 3 4 5 6 7 8 9 10 11 12 13 14 23 - 6,5 3,6 7,3 3,9 7,3 0 0,2 6,7 0,5 44, 6 49, 9 39 4,2 49, 9 1,6 7, 5 - 3,5 0 2,7 0,5 7 5,3 0,5 5,8 20, 5 21, 8 25, 8 1,1 25, 4 3,3 3, 6 2,5 - 2,5 0 2,8 3 0 2 2 22 23, 6 24, 3 0,4 27 1,3 0 8, 3 0 3,5 - 3,2 0 6,7 4,8 0,4 5,7 19, 7 21, 1 11, 3 1 24, 5 2,9 0 24, 2 14, 3 0,1 27, 6 2,5 0 , 1 0 , 5 3, 9 1,7 0 2,2 - 2,2 4,2 1,3 1 3,2 22, 7 8, 3 0,5 3,8 0 3,2 - 7 5,1 0,8 6 19, 5 21 11, 1 1,3 24, 3 3,4 0 6 3 5,7 4,2 6 - 0,7 4,4 0 23, 4 24, 9 15, 3 3,5 28 0,5 0 0, 4,3 0 3,8 1,3 4,1 0,7 - 2,7 0 22, 24, 14, 1,8 27, 1,1 0 67

нт №7 Клие нт №8 Клие нт №9 Клие нт №10 Клие нт №11 Клие нт №12 Клие нт №13 Клие нт №14 Клие нт №23 Оцен ка 2 8 3 6 6 7, 7 0,5 3 0,4 2 0,8 5,4 3,7 - 4,3 21, 2 22, 7 12, 8 0 26, 1 1,5 0 , 4 0, 5 4,8 2 4,7 3,2 5 0 0 3,3 - 21, 8 23, 3 13, 4 2 26, 6 0 0 39 ,5 14, 4 16, 9 13, 6 17, 6 13, 4 18, 3 17, 7 15, 1 16, 7 - 0 0 14, 7 2,1 13, 7 0 48 ,2 19, 1 21, 9 18, 4 22, 5 18, 3 23, 2 22, 6 20 21, 6 3,4 - 4,1 19, 9 0 18, 8 33 ,9 19, 7 19, 2 5,2 9,2 5 10, 2 9,5 6,7 8,3 0 0,7 - 6,6 4,5 5,5 5, 2 1,1 1,4 1 1,1 1,3 4,5 2,8 0 3 20, 8 22, 6 12, 7 - 26 1,4 48 ,2 22, 7 25, 3 21, 8 25, 9 21, 6 26, 3 25, 9 23, 4 24, 9 5,5 0 7,9 23, 3 - 22, 2 1, 6 2,3 1,3 1,9 2,5 2,4 0,5 1,1 0,5 0 18, 8 20, 5 10, 6 0,4 23, 9 - 0, 2 0,5 0 0 1,1 0,5 0 0 0,4 0 3,4 0 4,1 0,1 2,1 0,5 3 , 4 0 , 7 1 5 , 5 0 , 4 68

Приложение 6.4. Исключение из маршрута перемещения (11,14) Ба за База Клиен т №1 Клиен т №2 Клиен т №3 Клиен т №4 Клиен т №5 Клиен т №6 Клиен т №7 Клиен т №8 Клиен т №9 Клиен т №10 - 6,5 7,5 3,6 3,6 7,3 3,5 2,5 8,3 1,7 8,3 0,5 7,3 0,2 6,7 0,5 2,7 0,5 5,3 0,5 5,8 2,5 3,5 3,9 3,9 2,8 3,2 2,2 3,8 0 2,2 10 11 44, 49, 20, 21, 25, 23, 24, 22 6,7 4,8 4,2 1,3 0,4 3,2 3,2 5,1 0,8 5,7 4,2 0,7 4,4 1,3 0,2 4,3 3,8 4,1 0,7 7,7 0,5 0,4 0,8 5,4 0,5 4,8 4,7 3,2 39, 5 14, 16, 13, 17, 13, 18, 17, Клиен т №11 48, 2 19, 21, 18, 22, 18, 23, 22, Клиен 33, 19, 19, 5,2 9,2 10, 9,5 5,7 3,7 4,3 3,3 15, 20 6,7 13 39 4,2 8,3 0,4 49, 25, 27 21, 24, 22, 24, 14, 21 11,1 23, 24, 15, 22, 24, 14, 21, 22, 12, 26, 21, 23, 13, 26, 11,3 16, 21, 1,1 14 19, 19, 2,7 12 0,1 1,3 3,5 1,8 14, 3,4 4,1 0,7 27, 24, 28 27, 2,1 19, 6,6 23 1,6 0 3,3 0 1,3 0 2,9 0 2,5 0 3,4 0 0,5 0 1,1 0 1,5 0 0 13, 18, 4,5 M I N 5,5 0 3 , 4 0 69

т №12 Клиен т №13 Клиен т №14 Клиен т №23 MIN 9 5,2 1,1 1,4 48, 2 22, 25, 1,6 2,3 1,3 0 20, 1,1 1,3 4,5 2,8 21, 25, 21, 26, 25, 23, 1,9 2,5 2,4 0,5 1,1 0,5 24, 22, 5,5 18, 12, 7,9 20, 10, 26 23, 0,4 1,4 22, 23, 0 0 0 2,1 70

Приложение 6.5. Включение в маршрут перемещение (11,14) Б аз а База Клиен т №1 Клиен т №2 Клиен т №3 Клиен т №4 Клиен т №5 Клиен т №6 Клиен т №7 Клиен т №8 Клиен т №9 Клиен т №10 Клиен т №12 Клиен 1 2 3 4 5 6 7 8 9 7, 5 3, 6 8, 3 3, 9 8, 3 6,5 3,6 7,3 3,9 7,3 0 0,2 6,7 0,5 3,5 0 2,7 0,5 7 5,3 0,5 5,8 2,5 0 2,8 3 0 2 2 3,2 0 6,7 4,8 0,4 5,7 2,2 4,2 1,3 1 3,2 7 5,1 0,8 6 0 0, 2 7, 7 0, 5 39 ,5 33 ,9 5, 0,7 4,4 0 2,7 0 2,5 0 3,5 1,7 0 2,2 0,5 3,8 0 3,2 6 3 5,7 4,2 6 4,3 0 3,8 1,3 4,1 0,7 0,5 3 0,4 2 0,8 5,4 3,7 4,8 14, 4 19, 7 1,1 2 16, 9 19, 2 1,4 4,7 13, 6 3,2 17, 6 5 13, 4 0 17, 7 3,3 15, 1 16, 7 5,2 1 9,2 1,1 5 1,3 0 18, 3 10, 2 4,5 9,5 2,8 6,7 0 8,3 3 4,3 10 44, 6 20, 5 22 19, 7 22, 7 19, 5 23, 4 22, 8 21, 2 21, 8 0 20, 11 49 ,9 21 ,8 23 ,6 21 ,1 24 ,2 21 24 ,9 24 ,3 22 ,7 23 ,3 0 0, 7 22 12 13 23 M IN 39 25, 8 24, 3 11, 3 14, 3 11, 1 15, 3 14, 6 12, 8 13, 4 4,2 1,6 0 1,1 3,3 0 0,4 1,3 0 1 2,9 0 0,1 2,5 0 1,3 3,4 0 3,5 0,5 0 1,8 1,1 0 0 1,5 0 2 14, 7 0 13, 7 0 6,6 5,5 1,4 0 0 0 12, 0 71

т №13 Клиен т №14 Клиен т №23 MIN 2 48 ,2 1, 6 0 8 22, 7 25, 3 21, 8 25, 9 21, 6 26, 3 25, 9 23, 4 24, 9 2,3 0 1,3 0 1,9 0 2,5 0 2,4 0 0,5 0 1,1 0 0,5 0 0 0 5,5 18, 8 0 ,6 20 ,5 0 7 7,9 10, 6 0 23, 3 0,4 0 22, 2 5, 5 0 0 72

Приложение 7. Метод линейного программирования Приложение 7.1. Дополнительные матрицы №1 и №2 База База Клиент №1 Клиент №2 Клиент №3 Клиент №4 Клиент №5 Клиент №6 Клиент №7 Клиент №8 Клиент №9 Клиент №10 Клиент №11 Клиент №12 Клиент №13 Клиент №14 Клиент №23 Клиент №1 Клиент №2 Клиент №3 Клиент №4 Клиент №5 Клиент №6 Клиент №7 Клиент №8 Клиент №9 Клиент №10 Клиент №11 Клиент №12 Клиент №13 Клиент №14 Клиент №23 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 11 12 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 Сумма по строкам 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 73

Приложение 7.2. Основная матрица выбора перемещений для кластера №1 Расстояние Клиент База Клиент №1 Клиент №2 Клиент №3 Клиент №4 Клиент №5 Клиент №6 Клиент №7 Клиент №8 Клиент №9 Клиент №10 Клиент №11 Клиент №12 Клиент №13 Клиент №14 Клиент №23 15 0 6 2 9 База 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 3, 7 23 23 10 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 9, 2 14 5 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 3, 7 11 11 12 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 5 1,2 5 3 7 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 9 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1, 5 1 8 13 1 0 11 12 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2, 1 4 2 2,7 2 7 16 0 13 1 4 23 Сумма по строкам 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ЦФ = 109,2 Сумма Последовательность по посещения столбцам 1 6 1 9 1 23 1 10 1 14 1 11 1 12 1 5 1 3 1 1 1 8 1 13 1 4 1 2 1 7 1 0 74

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв