Математические методы маршрутизации доставки светлых нефтепродуктов на АЗС | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 27 июля, печатный экземпляр отправим 31 июля.

Опубликовать статью в журнале

Автор:

Рубрика: Технические науки

Опубликовано в Молодой учёный №18 (204) май 2018 г.

Дата публикации: 05.05.2018

Статья просмотрена: 122 раза

Библиографическое описание:

Кодиленко А. С. Математические методы маршрутизации доставки светлых нефтепродуктов на АЗС // Молодой ученый. — 2018. — №18. — С. 69-71. — URL https://moluch.ru/archive/204/50068/ (дата обращения: 16.07.2019).



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

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

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

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

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

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

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

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

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

– метод «ветвей и границ»;

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

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

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

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

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

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

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

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

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

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

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

Если на данной стадии все дуги нарушают эти условия, то производится возврат на одну стадию назад и принятая на этой стадии дуга игнорируется и выбирается следующая по оценке дуга. Если условия не нарушены хотя бы для одной дуги, то производится переход на одну стадию вперед. Вычисления заканчиваются, когда достигнута n + 1 стадия.

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература:

  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.
Основные термины (генерируются автоматически): имитационное моделирование, АЗС, случайный поиск, локальная оптимизация, динамическое программирование, мелкопартионная доставка грузов, точное решение задачи маршрутизации, план, автомобильный транспорт, допустимое решение.


Похожие статьи

Решение транспортных задач с помощью линейного...

Доставка нефтепродуктов автомобильным транспортом на АЗС является задачей мелкопартионной доставки грузов с ограничениями и условиями.

Динамическая адаптация эвристического алгоритма для задачи...

Решение транспортных задач с помощью линейного программирования.

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

Организация автомобильных перевозок мелких партий груза на...

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

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

В этом поможет решение задач по минимизации нулевых пробегов

Применение бионических принципов в проектировании...

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

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

Организация автомобильных перевозок мелких партий груза на...

Организация решения задач динамического программирования

Динамическое программирование в решении задачи...

Для решения задачи стохастического программирования при планировании плана производства.

Решение транспортной задачи с помощью программного...

Решением классической задачи транспортной маршрутизации является множество.

Динамическая адаптация эвристического алгоритма для задачи...

Решение транспортных задач с применением программирования...

Компьютерная модель для лабораторной работы...

Основными методами решения задачи маршрутизации для мелкопартионных перевозок: – динамическое программирование; – целочисленное линейное программирование; – метод «ветвей и границ»; – методы локальной оптимизации.

Анализ существующих методов решения транспортной...

Основными методами решения задач в логистике являются

При использовании этого метода необходимо иметь допустимый опорный план.

Актуальные проблемы транспорта и энергетики: пути их инновационного решения, 2016.

Факторы выбора имитационного моделирования, как...

Математический аппарат, применяемый в имитационном моделировании практически нечем неограничен [2]. В основе данного моделирования транспортных систем, лежит

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

Похожие статьи

Решение транспортных задач с помощью линейного...

Доставка нефтепродуктов автомобильным транспортом на АЗС является задачей мелкопартионной доставки грузов с ограничениями и условиями.

Динамическая адаптация эвристического алгоритма для задачи...

Решение транспортных задач с помощью линейного программирования.

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

Организация автомобильных перевозок мелких партий груза на...

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

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

В этом поможет решение задач по минимизации нулевых пробегов

Применение бионических принципов в проектировании...

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

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

Организация автомобильных перевозок мелких партий груза на...

Организация решения задач динамического программирования

Динамическое программирование в решении задачи...

Для решения задачи стохастического программирования при планировании плана производства.

Решение транспортной задачи с помощью программного...

Решением классической задачи транспортной маршрутизации является множество.

Динамическая адаптация эвристического алгоритма для задачи...

Решение транспортных задач с применением программирования...

Компьютерная модель для лабораторной работы...

Основными методами решения задачи маршрутизации для мелкопартионных перевозок: – динамическое программирование; – целочисленное линейное программирование; – метод «ветвей и границ»; – методы локальной оптимизации.

Анализ существующих методов решения транспортной...

Основными методами решения задач в логистике являются

При использовании этого метода необходимо иметь допустимый опорный план.

Актуальные проблемы транспорта и энергетики: пути их инновационного решения, 2016.

Факторы выбора имитационного моделирования, как...

Математический аппарат, применяемый в имитационном моделировании практически нечем неограничен [2]. В основе данного моделирования транспортных систем, лежит

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

Задать вопрос