Математические методы маршрутизации доставки светлых нефтепродуктов на АЗС

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

Ключевые слова: светлые нефтепродукты, грузовые перевозки, математические методы, имитационное моделирование, маршрутизация перевозок.

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

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

Доставка нефтепродуктов автомобильным транспортом на АЗС является задачей мелкопартионной доставки грузов с ограничениями и условиями, учитывающими специфику транспортной работы в данной отрасли. На сегодняшний день распределение транспорта на выполнение плана перевозок часто основывается на интуиции и опыте работников, участвующих в оперативном управлении доставкой. Большим недостатком этого является практически полное отсутствие альтернативных вариантов работы системы доставки нефтепродуктов на АЗС.

Внедрение математических методов для решения задачи доставки нефтепродуктов на АЗС позволяет повысить экономическую эффективность работы транспортного предприятия. Рассмотрим существующие на сегодняшний день математические методы решения задачи мелкопартионной доставки грузов.

Основными методами решения задачи маршрутизации для мелкопартионных перевозок:

– динамическое программирование;

– целочисленное линейное программирование;

– методы локальной оптимизации;

– методы случайного поиска;

– эвристические методы:

– имитационное моделирование.

Рассмотрим наиболее известные методы точного решения задачи маршрутизации.

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

1. Методы динамического программирования. Методы динамического программирования для решения задач мелкопартионных перевозок грузов впервые применили Р.Беллман, М. Хелд и Р. Карп [1].

Процесс вычислений разбивается на n + 1 стадий, где n — общее количество пунктов доставки. На каждой стадии рассматривается пункт, номер которого равен номеру стадии. Для каждой дуги, выходящей из этого пункта, подсчитывается функция состояния, и из всех оценок выбирается та, которая имеет минимальное значение. Соответствующая выбранной дуге комбинация пунктов проверяется на выполнение условий:

– в каждый пункт входит только одна дуга;

– из каждого пункта выходит только одна дуга;

– в полученном фрагменте маршрута доставки груза нет подциклов.

2. Методы целочисленного программирования впервые применили С. Миллер, А. Таккер и Р. Землин [2].

Метод основывается на том, что в задачах возникает система линейных ограничений в пространстве целочисленных переменных, используя которые строится оптимальная схема маршрутизации.

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

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

В противном случае среди не просмотренных элементов разбиения выбирается множество, являющееся в определенном смысле перспективным. Оно подвергается ветвлению. Новые подмножества анализируются до тех пор, пока не будут просмотрены все элементы разбиения [3].

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

4. Эвристический методКларка — Райта(метод «функции выгоды») [4] заключается в преобразовании начальной системы маршрутов таким образом, чтобы каждое отдельное преобразование давало наибольшее улучшение. Г. Кларком и Дж. Райтом в качестве показателя улучшения маршрутов предложена экономия пробега. Изначально составляется система из n радиальных маршрутов, которая удовлетворяет условиям задачи развозки, но содержит много мелких маршрутов. Эта система преобразовывается, постепенно объединяя маршруты (превращая радиальные маршруты в кольцевые). Маршруты объединяются с учетом значений функции выгоды, стремясь к наибольшему сокращению длины маршрутов.
5. Методы случайного поиска. Потребность в нефтепродуктах на АЗС постоянно изменяется, тем не менее система доставки постоянно стабилизировать свою работу. Потребность АЗС в нефтепродуктах рассматривается как стохастическая величина, проводится статистическая обработка массива данных, из которого выявляются определенные закономерности. Среди всего массива АЗС выделяются микрорайоны обслуживания.

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

6. Методы локальной оптимизации (Метод имитации отжига) строит последовательность планов оптимизационной задачи, начиная с начального плана x₀ и на t-й итерации (итерации нумеруются с нуля) переходит от плана x_t к плану x_t+1. На каждой из итераций метод действует следующим образом. Сначала для плана x_t строится так называемая окрестность, задающая множество “соседних” к x_t планов и для каждого из соседних планов — вероятность его выбора. Затем, с учетом вероятностей выбора, из окрестности случайным образом выбирается план x_new. Пусть f(x) — стоимость плана x. Если f(x_new) < f(x_t), то в качестве x_t+1 выбирается план x_new. Иначе x_t+1 задается по правилу:

Здесь p_t — вероятность перехода к худшему решению на t-й итерации — некоторая функция от t, x_new и x_t [5].

Процесс построения последовательности планов задачи завершается после выполнения T итераций. В качестве результата работы алгоритма выбирается план, имеющий наименьшую стоимость среди всех построенных x_t (который гарантированно не хуже x_T).

7. Имитационное моделирование. Наиболее перспективным методом решения задач маршрутизации перевозок нефтепродуктов является имитационное моделирование. Применение метода имитационного моделирования для решения данной задачи обусловлено возможностью учета сложной структуры маршрутов и временных окон погрузки и разгрузки; динамического изменения потребностей нефтепродуктов на АЗС, и соответственно возможности изменения маршрутов доставки; возможности применения специализированного программного обеспечения, позволяющего исследовать процесс функционирования системы доставки нефтепродуктов в динамике и наиболее оперативно принимать управленческие решения.

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

Литература:

1. Беллман, Р. Применение динамического программирования к задаче о коммивояжере [Текст] / Р. Беллман // Кибернетический сборник. — 1964. — Вып. 9. — С. 219–222.
2. Miller, C. E. Integer programming formulation of travelling salesman problems [Text] / C. E. Miller, A. W. Tucker, R. A. Zemlin // J. Assoc. Comput. Mach. — 1960. — No. 4. — P. 326–329.
3. Методы неявного подбора // Институт математики им. С. Л. Соболева. URL: http://math.nsc.ru/LBRT/k4/or/or_part4.pdf (дата обращения: 2.05.2018).
4. Clark, G. Sheduling of vehicles from a central depot to a number of delivery points [Text] / G. Clark, J. Wright // Operational Research Quarterly. — 1964. — Vol. 12, no. 4. — P. 568–581.
5. Ипатов А. В. Модифицированный метод имитации отжига в задаче маршрутизации транспорта // Тр. ИММ УрО РАН. — 2011. — № 17 № 4. — С. 121–125.