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

, (20)

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

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

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

(21)

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

t - момент времени.

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

, (22)

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

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

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

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

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

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

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

, (23)

где: - неотрицательная разность между тестируемым и ранее полученным решением;

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

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

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

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

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

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

3 минуты. Несмотря на быстроту получения маршрута, он включал

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

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

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

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

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

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

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

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

Заметим, что увеличение произошло из-за изменившейся последовательности покупателей и их количества (у водителя № 1 стало на 3 покупателя больше по сравнению с локальной оптимизацией). Таким образом, фирме сначала необходимо попытаться оптимизировать маршрут одного из водителей (если второй маршрут оптимален) и только потом переходить к глобальной оптимизации, если первый вариант покажет свою несостоятельность. Решение детерминированной задачи без временных резервов алгоритмом поиска с запретами позволит изначально разделить покупателей на две группы между водителями, следовательно, возможна как локальная так и глобальная оптимизация задачи.

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

маршрутизация грузоподъемность доставка транспортный

Таблица 3

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

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

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

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

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

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

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

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

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

Таблица 5

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

В работе проводится анализ основных научных статей по теме. Выяснено, что первое упоминание о КЗК (TSP) появилось в трудах

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№ 2, с. 78-90.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

pp. 342-354.

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

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

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

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

pp. 345-358.

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