Реферат по теме выпускной работы

Содержание

Введение

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

Оптимизировать можно практически любой элемент транспортно-логистической системы, поэтому, спектр работ в рамках данного направления очень широкий. [1]

Далее приведен не полный перечень возможных оптимизаций:

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

1. Актуальность темы

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

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

2. Цель и задачи исследования, планируемые результаты

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

Основные задачи исследования:

  1. формализация задач поставок с расширенным функционалом, за счет различных групп требований;
  2. проанализировать существующие методы решения подобных задач;
  3. разработать либо усовершенствовать существующие методы решения задачи и адаптировать их к условиям задачи;
  4. реализация разработки в виде алгоритма на программном языке;
  5. анализ результатов с проведением оценки сложности алгоритма.

Объект исследования: модели и методы решения комбинаторных оптимизационных задач на графах, связанных с поставками в торговой сети.

Предмет исследования: быстродействие и функциональность итогового программного продукта.

3. Обзор исследований и разработок

Количество работ по темам изучаемой области растет как в национальных, так и зарубежных журналах и интернет-ресурсах.

3.1 Обзор зарубежных источников

В зависимости от условий содержания и сложного графика работы клиентов могут возникать дополнительные проблемы. Так в своей работе Метод расшифровки с применением алгоритма роевого интеллекта для решения проблемы маршрутизации в логистике транспортных средств холодной цепи [2] Сяолей Лян, вместе с соавторами, рассмотрел алгоритм роевого интеллекта для оптимизации распределения транспортных средств в логистике холодной цепи. Так же, в статье был описан авторский подход к определению последовательности обслуживания клиентов с последующей оценкой его производительности.

В зависимости от загруженности транспортных условий возникает необходимость в особых подходах к дистрибуции товаров. В своей статье Оптимизация городской логистической транспортной системы со смешанными пассажирами и грузами [3] Рено Массон и его соавторы разработали модель, в которой транспортировка груза совмещается с перевозкой пассажиров на автобусах с заданным маршрутом. Авторы рассмотрели возможные проблемы и разработали решения для них. Следует отметить, что в статье рассмотрены чисто детерминированные данные.

3.2 Обзор национальных источников

Во время изучения национальных источников найдено множество статей, направленных на уменьшение затрат за счет разработки моделей и методов решающих определенные транспортные задачи. Так, например, Костюк Ю.Л. и Пожидаев М.С. в своей статье Сбалансированная эвристика для решения задачи маршрутизации транспорта с учетом грузоподъемности [4] предложили эвристический алгоритм для решения задачи маршрутизации транспорта. Борханов И.Ф. и Фазылов Б.Р. модифицировали метод Литтла, который решал задачу коммивояжера, для более сложной задачи о развозке, предоставив результаты в работе Метод Литтла со штрафами для решения задачи о развозке [5].

3.3 Обзор локальных источников

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

В статье Разработка программного обеспечения для формирования оптимальных маршрутов быстрой доставки товаров [6] Макогон С.А. и Ситникова О.Д. рассмотрели задачу построения оптимального маршрута быстрой доставки товаров. Так же они представили разработанное программное обеспечение, предназначенное для формирования оптимальных маршрутов с обеспечением быстрой доставки товаров.

Александрова О.А. вместе со своим научным руководителем Секириным А.И. описала предложенный ею алгоритм и провела адекватность эволюционной модели. В статье Оптимизация грузовых перевозок с использованием генетических алгоритмов, на основе программной реализации, ими были проведены экспериментальные исследования с целью выявления рациональных значений параметров генетического алгоритма и оценки эффективности оптимизации грузовых перевозок [7].

Бражник А.В., научным руководителем которого также был Секирин А.И., проанализировал особенности задачи о транспортировке груза, а также, привел ее математическую постановку. В своей статье Анализ эффективности методов решения задачи о транспортировке груза [8] он провел подробное сравнение генетических и муравьиных алгоритмов по качественным и временным характеристикам.

4. Проблема решения NP-полных задач

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

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

Задачи, которые по своим моделям являются комбинаторными, оптимизационными или смешанного типа с элементами комбинаторики в основном являются NP-полными. Класс NP-полных задач обладает следующими свойствами [9]:

  • никакую NP-полную задачу нельзя решить никаким полиномиальным алгоритмом, несмотря на настойчивые усилия многих блестящих исследователей;
  • если бы удалось построить полиномиальный алгоритм для какой-нибудь NP-полной задачи, то это бы означало полиномиальную разрешимость каждой NP-полной задачи.

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

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

5. Известные методы решения NP-полных задач

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

Для сокращения времени, необходимого для нахождения оптимального решения в задачах целочисленного программирования, в 1960 году Аилсой Ленд и Элисон Дойг предложили метод ветвей и границ [10]. Это общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, в особенности, дискретной и комбинаторной оптимизации. Метод является развитием метода полного перебора, в отличие от последнего — с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных, хотя, в худшем случае, его сложность равна сложности полного перебора. При большой размерности задачи решение так же займет слишком много времени.

Дж. Литтл, К. Мурти, Д. Суини, К. Кэрол адаптировали метод ветвей и границ для решения задачи коммивояжёра в 1963 году [11]. Данный алгоритм используется для поиска оптимального гамильтонова контура в графе.

Илья scidev в статье Решение задачи коммивояжера алгоритмом Литтла с визуализацией на плоскости [12] представил график сравнения метода ветвей и границ с полным перебором и среднее время работы реализованного им алгоритма на различном количестве городов (рисунок 1). Тестировалось на матрицах для случайно сгенерированных точек.

Сравнение полного перебора с методом ветвей и границ
Рисунок 1 — Сравнение полного перебора (синий) с методом ветвей и границ (оранжевый)


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

Время работы алгоритма
Рисунок 2 — Время работы алгоритма
(синим изображено лучшее время, оранжевым – среднее, а серым худшее)


Как видно по рисунку 2, уже на 30 точках алгоритм может работать около 180 секунд, а с ростом количества точек время работы будет увеличиваться экспоненциально. Для получения решения за приемлемое время, обычно, можно использовать эвристические алгоритмы. Они включают практические методы, не являющиеся гарантированно точными или оптимальными, но достаточными для решения поставленной задачи [13]. К таким алгоритмам относятся, например, муравьиные, которые представляют собой вероятностную жадную эвристику, где вероятности устанавливаются исходя из информации о качестве решения, полученной из предыдущих решений [14]. Также следует отметить алгоритмы роевого интеллекта, основанные на коллективном поведении децентрализованной самоорганизующейся системы. Они рассматриваются в теории искусственного интеллекта как оптимизационный метод. Термин был введён Херардо Бени и Ван Цзином в 1989 году, в контексте системы клеточных роботов [15].

Одним из самых популярных методов [18], несмотря на давность разработки, является метод Кларка-Райта, разработанный двумя британскими учеными Г. Кларком и Дж.В. Райтом [16]. Его суть заключается в пошаговом переходе к оптимальной схеме развозки с кольцевыми маршрутами. На рисунке 3 показаны две схемы доставки.

Схемы доставки
Рисунок 3 — Схемы доставки
(Анимация: 6 кадров, 6 кб)

На схеме доставки грузов по радиальным маршрутам в пункты T1 и T2 суммарный пробег автотранспорта равен:


LA = d01 + d10 + d02 + d20
 (1)

На схеме доставки грузов по кольцевому маршруту в пункты T1 и T2 пробег автотранспорта составляет:


LB = d01 + d12 + d20
 (2)

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


S12 = LA − LB = d10 + d02 − d12
 (3)


В статье Разработка ПО оптимизации логистики поставок продукции [17] мною был реализован алгоритм Кларка-Райта с некоторыми оптимизациями и протестирован на различных размерах входных данных. Исходя из полученных данных, была построена следующая диаграмма, на которой изображен рост времени работы алгоритма от количества точек:

Увеличение времени работы алгоритма от количества точек
Рисунок 4 – Увеличение времени работы алгоритма от количества точек

Заключение

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

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

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

Список источников

  1. Оптимизация логистики – [Электронный ресурс]. – Режим доступа: https://morproekt.ru/articles/materialy-po-tekhnologii/optimizatsiya-logistiki
  2. A Decoding Method for Applying Swarm Intelligence Optimization Algorithm to Solve the Cold Chain Vehicle Logistics Routing Problem / Xiaolei Liang, Yuan Sun, Mengdang Tian, Wenfeng Zhou // IOP Conference Series: Earth and Environmental Science, 2018
  3. Renaud Masson, Anna Trentini, Fabien Lehuédé, Nicolas Malhéné, Olivier Péton / Optimization of a city logistics transportation system with mixed passengers and goods / EURO Journal on Transportation and Logistics, Springer, 2017, 6 (1), pp.81-109.
  4. Ю.Л. Костюк, М.С. Пожидаев / Сбалансированная эвристика для решения задачи маршрутизации транспорта с учетом грузоподъемности / Вестник Томского государственного университета, Управление, вычислительная техника и информатика, 2010
  5. И.Ф. Борханов, В.Р. Фазылов / Метод Литтла со штрафами для решения задачи о развозке. / Учебные записки Казанского государственного университета, Физико-математические науки, 2008
  6. Макогон С.А. Разработка программного обеспечения для формирования оптимальных маршрутов быстрой доставки товаров / Макогон С.А., Ситникова О.Д. // VI Международная научно-техническая конференция «Информатика, управляющие системы, математическое и компьютерное моделирование — 2017» / Информатика и кибернетика. — 2017. — № 2(4). — С. 63–70.
  7. Александрова О.А. Оптимизация грузовых перевозок с использованием генетических алгоритмов / О.А. Александрова, А.И. Секирин // Информатика и компьютерные технологии — 2009 №5, — Донецк: ДонНТУ, с. 237–244.
  8. Бражник А.В. Анализ эффективности методов решения задачи о транспортировке груза / Бражник А.В., Секирин А.И., Валуева О.С. // X Международная научно-техническая конференция «Информатика, управляющие системы, математическое и компьютерное моделирование — 2019» — 2019. — С. 57-61.
  9. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  10. A.H. Land and A.G. Doig. An automatic method of solving discrete programming problems, С. 497–520.
  11. Костевич Л.С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л.С. Костевич. — Мн.: Новое знание, 2003. ил., стр. 150
  12. Решение задачи коммивояжера алгоритмом Литтла с визуализацией на плоскости — [Электронный ресурс]. — Режим доступа: https://habr.com/ru/post/332208/
  13. С. Гудман. Введение в разработку и анализ алгоритмов / С. Гудман, С. Хидетниеми. — М. : Мир, 1981
  14. Макконелл Дж. Основы современных алгоритмов: учебное пособие / Дж. Макконелл; пер. с англ. С.К. Ландо. — [3-е изд.]. — М.: Техносфера, 2004. — 368 c.
  15. Beni G., Wang J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26-30 (1989)
  16. Clarke G. Scheduling of vehicles from a central depot to a number of delivery points / G. Clarke, J.W. Wright // Journal of Operations Research Society. — 1964. — Vol.12, № 4. — pp. 568–581.
  17. Хубеджев Д.П. Разработка ПО оптимизации логистики поставок продукции / Д.П. Хубеджев, О.Д. Ситникова // II Международная научно-практическая конференции «Программная инженерия: методы и технологии разработки информационно-вычислительных систем – 2018» / Программная инженерия. — 2018. — № 1(4). — С. 123-126.
  18. Л.Н. Шилин. Эвристический алгоритм как средство оптимизации транспортных потоков предприятия / Л.Н. Шилин, А.А. Навроцкий, Р.В. Козарь // Пятая Международная научно-практическая конференция «BIG DATA and Advanced Analytics. BIG DATA и анализ высокого уровня» — 2019.