Назад в библиотеку

Анализ современного состояния исследований в области задач маршрутизации с ограничением по грузоподъёмности с двумерным размещением груза внутри

Автор: Р.А Кашапов, А.Ф. Валеева

Источник: https://ugatu.su/media/winterSchoolSeminar/article/2022-09-15/Statya_Kashapov_R.A._MO-420.docx

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

Ключевые слова: Задача маршрутизации, эвристические методы, метаэвристика, двумерное размещение груза

Введение

Задача маршрутизации транспортных средств с ограничением по грузоподъёмности (CVRP) в общем виде является одной из главных задач логистики, целью которой является определение оптимальных маршрутов для перевозки грузов. Задача маршрутизации с двумерным размещением груза внутри (2L-CVRP) является подвидом классической задачи CVRP с учётом размещения двумерных предметов (груза) в кузове транспортного средства и объединяет задачи CVRP и задачу двумерной упаковки (Two-Dimensional Bin Packing Problem), которая заключается в минимизации занятой грузом части кузова транспортного средства. Такие задачи являются целочисленными и NP-трудными. Выбор оптимальных методов решения, алгоритмов для данных задач будет способствовать совершенствованию логистической системы любого предприятия, что положительно повлияет на минимизацию затрат и получение максимальной прибыли. В данной работе на основе научных публикаций проведен анализ существующих методов решения задачи маршрутизации с учётом грузоподъёмности с двумерным размещением груза внутри (2L-CVRP).

Современное состояние проблемы

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

Например, в статье [1] рассматриваются способы решения различных задач маршрутизации, алгоритмы для решения классифицированы по частоте использования. Самые используемые — эвристические и метаэвристические методы, так как точные алгоритмы не всегда дают решение за приемлемое время при большем объеме входных данных.

В статье [2] предлагается нестандартный подход к решению задачи. Предполагается использование эвристического алгоритма решения задачи маршрутизации транспорта с учётом грузоподъёмности. Алгоритм сотоит из двух фаз: кластеризации вершин на группы и вычисления маршрутов отдельно по группам.

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

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

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

Так, авторами [5] делается акцент на нагрузку осей грузовика и оси прицепа при решении задачи маршрутизации с учётом грузоподъёмности. Предлагается добавлять дополнительное условие в математическую модель задачи для учёта нагрузки на оси.

В статье [6] делается акцент на решении задачи 2L-CVRP с дополнительным условием, где транспортные средства находятся в нескольких депо 2L-MDCVRP. Предлагается использовать алгоритм квантового роя частиц QPSO и эвристический эволюционный алгоритм локального поиска. Метод роя частиц является эффективным подходом для решения CVRP, что продемонстрировал численный эксперимент.

В [7] предлагается скомбинировать два метода для решения задачи маршрутизации с двумерным размещением груза внутри 2L-CVRP. Представлен алгоритм, решающий задачу маршрутизации с помощью алгоритма ближайших соседей, а задачу двумерной упаковки с помощью какого-либо эвристического метода.

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

В статье [9] предлагается оптимизировать решение классических задач, в частности 2L-CVRP. Представлен подход, который учитывает нагрузку на ось грузовика с прицепом и без него, показана необходимость проверки ограничения веса оси после каждого размещения груза внутри транспортного средства. Показано, что без учёта веса оси в задачах данного типа возникает перегрузка по крайней мере одной оси. Рекомендуется учитывать этот факт при решении задач данного типа

В [10] рассмотрена оптимизационная задача доставки однородного груза из некоторого пункта производства в пункты потребления транспортным средством ограниченной вместимости с возможностью неоднократного посещения каждого пункта, проведена формализация поставленной задачи, для её решения предлагается использовать жадный алгоритм

Авторы статьи [11] предлагают учитывать при решении задач данного класса зависимость стоимости транспортировки от загрузки транспортного средства и качества дороги. Для решения задачи наряду с точным алгоритмом используется модификация эвристического алгоритма Кларка-Райта

В работе [12] предлагается комплексный метод решения задачи маршрутизации, сочетающий известный алгоритм FF – первый подходящий, оригинальный алгоритм FFR – первый подходящий с переупорядочиванием, оценивать полученное решение предлагается с помощью нижних оценок С. Мартелло и П. Тота для контроля оптимальности решения. Численный эксперимент показал эффективность данного подхода при умеренной размерности задачи.

Заключение

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

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

  1. Дмитрий Трофимов Задача маршрутизации транспорта. Дискретная математика: Алгоритмы URL: https://www.lobanov-logist.ru/library/all_articles/55059/
  2. Ю.Л Костюк М.С. Пожидаев СБАЛАНСИРОВАННАЯ ЭВРИСТИКА ДЛЯ РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА С УЧЕТОМ ГРУЗОПОДЪЕМНОСТИ Вестник Томского Государственного универститета, 2010 URL: https://cyberleninka.ru/article/n/sbalansirovannaya-evristika-dlya-resheniya-zadachi-marshrutizatsii-transporta-s-uchetom-gruzopodemnosti/viewer
  3. Валеева А. Ф. Валеев Р. С. Гончарова Ю. А.Задачи маршрутизации при транспортировке: обзор моделей, методов, алгоритмов Часть 1. Уфимский государственный технический университет (Уфа, Россия) Август 2019 URL: http://lscm.ru/images/PDF/4-2019/%D0%92%D0%B0%D0%BB%D0%B5%D0%B5%D0%B2%D0%B0-04-2019.pdf
  4. Lilian Caroline Xavier Candido Luzia Vidal de Souza Mathematical Model and Simulated Annealing Algorithm for the Two-Dimensional Loading Heterogeneous Fixed Fleet Vehicle Routing Problem Federal University of Parana, Curitiba, Brazil Received 17 June 2021; Accepted 17 December 2021; Published 28 January 2022 URL: https://downloads.hindawi.com/journals/mpe/2022/6012105.pdf
  5. Hanne Pollaris Kris Braekers An Caris Gerrit K. Janssens THE CAPACITATED VEHICLE ROUTING PROBLEM WITH LOADING CONSTRAINTS Hasselt University, Agoralaan – Gebouw D, BE-3590 Diepenbeek Reseach Foundation Flanders (FWO), Egmontstraat 5, BE-1000 Brussels URL: http://www.msc-les.org/proceedings/hms/2013/HMS2013_7.pdf
  6. Zhu X.N. Yan R. Zhang. Q A PROMOTED HYBRID HEURISTIC ALGORITHM FOR TWO-DIMENSIONAL MULTI-DEPOTS VEHICLE ROUTING PROBLEM School of Economics and Management Beijing Information Science & Technology University, Beijing 100192, China. URL: http://www.ijsimm.com/Full_Papers/Fulltext2015/text14-3_499-510.pdf
  7. The Jin Ai S.S. Wigati Combination of neares neighbor and heuristics algorithms for sequential two-dimensional loading capacitated vehicle routing problem Department of Industrial Engineering, Universitas Atma Jaya Yogyakarta, JI. Babarsari No. 44 Yogyakarta 55281, Indonesia 19-Jul-2019 03:05PM (UTC+0700) URL: http://e-journal.uajy.ac.id/19211/12/Turnitin%2017.pdf
  8. Nai K. Yu Wen Jiang Rong Hu Bin Qian Ling Wang Learning Whale Optimization Algorithm for Open Vehicle Routing Problem with Loading Constraints Faculty of Mechanical and Electrical Engineering, Kunming University of Science and Technology, Kunming 650500, China 2 Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China 3 Yunnan Key Laboratory of Artificial Intelligence, Kunming University of Science and Technology, Kunming 650500, China 4 Department of Automation, Tsinghua University, Beijing 100084, China Received 28 July 2021; Revised 30 November 2021; Accepted 6 December 2021; Published 26 December 2021 URL: https://downloads.hindawi.com/journals/ddns/2021/8016356.pdf
  9. Corinna Krebs Jan Fabian Ehmke Axle Weights in combined Vehicle Routing and Container Loading Problems Department of Management Science, Otto von Guericke University Magdeburg, Universit€atsplatz 2, 39106, Magdeburg, Germany Business Analytics Group, University of Vienna, Kolingasse 14-16, 1090, Vienna, Austria URL: https://www.sciencedirect.com/science/article/pii/S2192437621000157
  10. Е. М. Бронштейн Р. М. Гиндуллин ОБ ОДНОМ КЛАССЕ ЗАДАЧ МАШРУТИЗАЦИИ Математическое моделировани: методы, алгоритмы, технологии, Уфа, Россия URL:https://cyberleninka.ru/article/n/ob-odnom-klasse-zadach-marshrutizatsii/viewer
  11. Е.М. Бронштейн П.А Зелёв ОБ ОПТИМАЛЬНОЙ ДОСТАВКЕ ГРУЗОВ ТРАНСПОРТНЫМ СРЕДСТВОМ С УЧЕТОМ ЗАВИСИМОСТИ СТОИМОСТИ ПЕРЕВОЗОК ОТ ЗАГРУЗКИ ТРАНСПОРТНЫХ СРЕДСТВ ПО НЕСКОЛЬКИМ ЦИКЛИЧЕСКИМ МАРШРУТАМ Информ. и её примен., 2014, том 8, выпуск 4, 53–57 URL:http://www.mathnet.ru/links/9e8b57668b82f4c7f060efd032f3fe17/ia343.pdf
  12. Ю.В Бугаев Л.А Коробова С.В Гудков Методы оптимизации развозки грузов потребителям несколькими транспортными средствами Вестник ВГУИТ, Воронежский государственный университет инженерных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия URL: https://cyberleninka.ru/article/n/metody-optimizatsii-razvozki-gruzov-potrebitelyam-neskolkimi-transportnymi-sredstvami/viewer