Постановка исследовательской проблемы

В выпускной квалификационной работе задача маршрутизации транспорта с временными окнами и ограничением на грузоподъемность транспортных средств рассматривается на примере пермской торговой фирмы ООО «Фабрика еды». Компания занимается оптовой торговлей скоропортящейся продукцией: мясопродуктами, курицей, а также полуфабрикатами. В июне 2015 года в фирме появился второй водитель, который также как и первый, отвечает за развоз продукции к покупателям. Фактическим адресом фирмы является ул. Академика Курчатова 9, что находится в 12 минутах езды до центра города Пермь и, следовательно, накладывает определенные сложности на быстроту доставки продукции контрагентам. Прием заявок осуществляется офисом, который находится по вышеупомянутому адресу, за день до отгрузки (доставки). В заявке покупателей указывается желаемое время отгрузки с 11:00 до 20:00 (время работы водителя). Обозначаемый в заявке временной интервал должен быть не меньше 30 минут (для того, чтобы водитель успел доставить продукцию в отдаленные районы). Цех предприятия начинает работу с 6:00 утра каждый день, для того чтобы максимально удовлетворить все текущие заявки покупателей. Среднее количество контрагентов, ожидающих поставку в случайный день, представлено на графике:

Рис. 1. Среднее количество покупателей на одного водителя

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

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

Данный процесс развоза продукции для одного водителя можно смоделировать в виде задачи коммивояжера, представленной системой ограничений (1) — (6). Итак, в один из дней работы исследуемой фирмы имеется N покупателей. Водитель, выезжает один раз в начале рабочего дня с предприятия в 11:00 (предварительно загрузив продукцию). Он доставляет заказы всем контрагентам (соответственно, побывав у каждого один раз) и возвращается после максимального удовлетворения всех заявок на предприятие (не обязательно в 20:00). В задаче будет находиться наименьшее время, а не расстояние, поскольку у водителя основной целью является успеть во временные окна как можно к большому числу покупателей (увеличение или уменьшение расстояния на несколько километров не приведет к существенным потерям для фирмы, по сравнению с возвратом продукции). Если водитель возвращается в фирму раньше окончания рабочего дня, он может заниматься, например, доставкой продукции от поставщиков. Таким образом, задача водителя заключается в определении последовательности объезда покупателей, которая будет минимизировать его путь, а также удовлетворять временному интервалу, установленному каждым покупателем (Lorini, 2011). Заметим, что в исследовании для нас представляет интерес не только задача коммивояжера, но, в большей степени, задача маршрутизации транспорта (6) — (11). Вторая является обобщением первой задачи. В работе используется модифицированная постановка ЗМТ — задача маршрутизации транспорта с временными интервалами и ограничением на грузоподъемность транспортных средств:

Переменные задачи: — бинарная неотрицательная переменная, принимающая значение 1, если водитель под номером k едет от покупателя i к контрагенту j, и значение 0 в остальных случаях; - показывает фактическое время прибытия водителей к покупателям; - неотрицательная переменная, предотвращающая распадение гамильтонова цикла на подциклы. Отметим, что две последние переменные не зависят от номера водителя (k), поскольку данные переменные непосредственно связаны с покупателями, а не с водителями фирмы (например, в задаче не задается какой именно водитель приедет к пятому покупателю в 12:00, а учитывается сам факт приезда одного из водителей в конкретное время). ЗМТ с временными окнами и грузоподъемностью автомобилей — (6) — (11), (15) — (17) является обобщением КЗК (1) — (6) и ЗМТ (6) — (11), и именно поэтому будет подробно рассмотрена ниже. (7) — целевая функция задачи — означает, что суммарное время водителей через всех покупателей должно быть наименьшим. (15) — обозначает, что суммарный спрос на продукцию (в кг) не должен превышать максимальную грузоподъемность каждого транспортного средства. (8) и (9) показывают, что оба водителя после отгрузки продукции покидают каждого покупателя только один раз и приезжают к другому контрагенту для поставки только один раз. Поскольку, решением задачи коммивояжера являются замкнутые маршруты водителей, так называемые гамильтоновы циклы, ограничение (10) означает невозможность распадения данного цикла на подциклы (объезд всего нескольких покупателей из всей заявки). Ограничение (11) указывает на то, что переменные задачи являются бинарными и неотрицательными, а (6) означает, принадлежность переменных к множеству вещественных чисел. Большой интерес в данной постановке представляют два последних ограничения. В повседневной деятельности, предприятие заключает договоры поставки с новыми контрагентами, которые склонны к оппортунистическому поведению, а именно к сокращению желаемого времени доставки продукции (которое прописано в контракте) в новых ежедневных заявках. Торговому предприятию зачастую приходится подстраиваться под своих покупателей для того, чтобы их сохранить, а следовательно, встает необходимость удовлетворения заявок контрагентов именно в желаемое для них время, что ведет к модификации традиционной логистической задачи ЗМТ (Moon, et al., 2012). С математической точки зрения, в задачу маршрутизации транспорта необходимо добавить ряд дополнительных предпосылок, основной из которых будет ограничение на временные интервалы, в которые покупатели ожидают доставку товара.

Важным свойством задачи маршрутизации транспорта с временными интервалами и ограничением на грузоподъемность транспортных средств является то, что минимальные по времени маршруты начинаются из ООО «Фабрика еды» в 11:00, в дальнейшем проходя через все вершины (покупателей) только один раз, в течение соответствующих временных интервалов и заканчиваются в точке начала маршрута. Исходя из этого, каждому покупателюв дневной заявке будет поставлено в соответствие «жесткое» временное окно, где границы интервала будут обозначать начало ожидаемого времени поставки и его окончание соответственно. Временные интервалы покупателей должны устанавливаться во время работы водителей, которое обозначим — [0, ]. Отметим, что как опытному, так и новому водителю, необходимо определенное время для того, чтобы обслужить i-го покупателя. В модифицированной задаче, у каждого ребра весом будет являться время проезда от одного покупателя к другому (). Таким образом, в задачу (6) — (11), наряду с ограничением на грузоподъемность, добавятся два новых ограничения (16) и (17). (16) — задает временные окна у каждого покупателя, в которые водителю необходимо отгрузить продукцию. Ограничение (17) показывает временную взаимосвязь между последовательными покупателями в маршруте. Рассмотрим двух контрагентов к которым водитель приезжает напрямую (). Очевидно, что время приезда к покупателю j будет больше либо равно сумме времени приезда к покупателю i, времени разгрузки у контрагента i, а также времени проезда от i к j:. Однако такое ограничение справедливо только для тех пар клиентов i и j, которых хотя бы один из водителей посещает последовательно. Поэтому описываемое ограничение (17) становится нелинейным, что накладывает определенные сложности в выборе алгоритма решения данной логистической проблемы. Таким образом, решив детерминированную задачу (6) — (11), (15) — (17), фирма достигнет своей логистической цели — успеть вовремя ко всем покупателям в их временные интервалы, получив минимальные по времени маршруты водителей.

В работе, помимо описываемой детерминированной задачи, затрагивается стохастическая постановка ЗМТ, в которой целевая функция направлена на минимизацию риска возникновения потерь продукции. Предположим, что решив задачу (6) — (11), (15) — (17), водитель приезжает к пятому покупателю в 11:58, а правая граница временного окна — 12:00. Очевидно, что в случае, например, затора на дороге или задержки у предыдущего покупателя, водитель не успеет доставить продукцию в желаемый интервал отгрузки. Для фирмы более осмысленной представляется задача минимизации математического ожидания потерь, связанных с доставкой продукции позже указанного срока:

(18).

где: — вероятность недоставки продукции i-му покупателю;

— выручка от i-го контрагента.

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

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

В исследовании подразумевается, что вероятность непринятия продукции i-ым покупателем при принимает значение 0,2. Данное значение было получено на основе статистического анализа неотгруженных заказов.

Таким образом, ограничение (18) можно представить в виде:

(18.1).

где: k и c — параметры линейной убывающей функции.

После изменения функционала задачи, возникает стохастическая постановка — (6), (8) — (11), (15) — (17), (18.1), решение которой, с экономической точки зрения, позволит снизить риск недоставки продукции путем наиболее раннего приезда водителей к покупателям. Очевидно, что описываемая модификация ЗМТ с временными окнами и грузоподъемностью автомобилей неединственная. Данную задачу можно преобразовать под любые особенности бизнеса, например, введя ограничения на случайный размер заказа или на обслуживание одного покупателя несколькими транспортными средствами. Оказалось, что исследуемая компания не ставит цель наиболее раннего приезда ко всем контрагентам (есть покупатели с временными окнами длинной в 6 часов и фирме без разницы: приедет водитель за 2 или за 3 часа до конца интервала). В ходе анализа расходных накладных и личных интервью с водителями ООО «Фабрика еды» было установлено, что минимальная разность (позволяющая максимально снизить риск недоставки) между правой границей временного окна у каждого покупателя и приездом водителя должна составлять 10 минут, что приведет к трансформации линейной убывающей функции в кусочно-линейную невозрастающую:

Рис. 3. Вероятность недоставки продукции ООО «Фабрика еды»

Подчеркнем, что временного резерва (параметра надежности доставки продукции) в 10 минут у каждого покупателя более чем достаточно водителям для разгрузки продукции. С математической точки зрения это означает, что вероятность недоставки продукции при резерве времени больше или равном 10 минутам будет равна нулю:

(19).

Таким образом, в выпускной квалификационной работе будет анализироваться детерминированная ЗМТ (6) — (11), (15) — (17), решение которой (кратчайшие по времени маршруты для двух водителей, удовлетворяющие всем временным окнам покупателей) путем изменения параметра надежности (временного резерва) будет приближено к решению стохастической задачи. Оптимальные по времени маршруты водителей будут удовлетворять специфике реального бизнеса и минимизировать транспортные расходы компании при математическом ожидании риска недоставки продукции равном нулю. Отметим, что, несмотря на относительную простоту постановки задачи (6) — (11), (15) — (17), решать ее достаточно сложно, поскольку необходимо не только сформировать определенный набор данных с учетом различных характеристик предприятия, но и подобрать для них алгоритмы нахождения оптимального решения (Rodriguez, Ruiz, 2012).