Методы оптимизации развозки грузов потребителям несколькими транспортными средствами

Бесплатный доступ

Грузовой транспорт является одной из наиболее важных отраслей народного хозяйства. Увеличение эффективности работы логистической компании обеспечивается точной организации поставок, а также своевременной доставкой груза в пункты маршрута. Именно поэтому возникает потребность в оптимизации развозки грузов. Задача развозки - это транспортная задача по доставке негабаритных грузов из распределительного центра множеству получателей, расположенных в районе действия транспортной компании. Она является обобщением известной задачи коммивояжера, от которой отличается условием ограниченности грузоподъемности применяемого транспортного средства и, как следствие, необходимостью неоднократного возвращения на базу для пополнения перевозимого груза. В данной статье предлагается дополнить традиционную формулировку задачи требованием распределить клиентов по нескольким одновременно работающим транспортным средствам (ТС), чтобы максимальное время выполнения заказа было минимально. Тем самым учитываются не только интересы исполнителя развозки, но и клиентов. Решение задачи состоит из двух этапов. На первом каким-либо известным способом определяются рациональные кольцевые маршруты для каждого ТС, минимизирующие общий пробег. По результатам этапа рассчитывается время прохождения каждого маршрута. На втором этапе решается задача сокращения максимальное время прохождения маршрутов за счет использования нескольких ТС, производящих развозку в одно время. Для этого необходимо оптимально распределить ТС по индивидуальным маршрутам. Предлагается для решения этой задачи воспользоваться алгоритмом решения известной задачи «Упаковка предметов в контейнеры». Данная задача относится к классу NPтрудных задач в сильном смысле и не имеет точного алгоритма решения для произвольных исходных данных. В данной работе предлагается комплексный метод решения, сочетающий известный алгоритм «First fitted (FF)» - «первый подходящий», оригинальный алгоритм «First fitted with reordering (FFR)» - «первый подходящий с переупорядочением», а также нижние оценки С. Мартелло и П. Тота для контроля оптимальности полученного решения. Тестовые расчеты показали эффективность данного подхода при умеренной размерности задачи.

Еще

Математические методы, экономика, задача развозки, оптимальный маршрут, упаковка в контейнеры

Короткий адрес: https://readera.org/140257361

IDR: 140257361   |   DOI: 10.20914/2310-1202-2021-1-466-472

Список литературы Методы оптимизации развозки грузов потребителям несколькими транспортными средствами

  • Zhou L., Baldacci R., Vigo D., Wang X. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution //European Journal of Operational Research. 2018. V. 265. № 2. P. 765-778. doi: 10.1016/j.ejor.2017.08.011
  • Kampf R., Hlatka M., Savin G. Proposal for optimizing specific distribution routes by means of the specific method of operational analysis // Communications-Scientific letters of the University of Zilina. 2017. V. 19. №. 2. P. 133-138.
  • Parhusip S.F. Composite Algorithm Based on Clarke-Wright and Local Search for the Traveling Salesman Problem // Proceedings of the 2019 5th International Conference on Industrial and Business Engineering. 2019. P. 87-90.
  • Иванова A.A., Черноморова Т.С. Об алгоритме решения задачи развозки и его реализации //Бюллетень науки и практики. 2017 № 4. С. 107-114
  • Доценко С.И. Задача распределения расходов при развозке по кольцевому маршруту как кооперативная игра //Информатика. 2017. № 1. С. 12-19.
  • Просов С.И., Кузьменко Е.А. Декомпозиция задачи маршрутизации по эвристикам метода Кларка-Райта. // Мир транспорта. 2018. 16(3). С. 190-199.
  • Бугаев К).В., Коробова Л.А., Зеленова Е.Е. Планирование грузовых перевозок модифицированным методом Кларка-Райта // В сборнике: Виртуальное моделирование, прототипирование и промышленный дизайн. Материалы III Международной научно-практической конференции. 2016. С. 179-182.
  • Бугаев К).В., Коробова Л.А., Гудков С.В. Решение задачи развозки негабаритных грузов несколькими транспортными средствами // Математические методы в технике и технологиях: сб. тр. междунар. науч. конф. СПб.: Изд-во Политехн. ун-та, 2021. С. 55-60.
  • Коновалова Т.В., Супрун О.С. К вопросу выбора критерия оптимизации маршрута при доставке грузов автомобильным транспортом // Электронный сетевой политематический журнал" Научные труды КубГТУ". 2017. №. 11. С. 143-150.
  • Подшивалова КС., Подшивалов С.Ф. Исследование метода ветвей и границ при решении задачи развозки грузов по кольцевому маршруту // Проблемы качества и эксплуатации автотранспортных средств. 2017. С. 276-281.
  • Christensen H.I. et al. Approximation and online algorithms for multidimensional bin packing: A survey // Computer Science Review. 2017. V. 24. P. 63-79. doi: 10.1016/j.cosrev.2016.12.001
  • Delorme M., Iori M., Martello S. Bin packing and cutting stock problems: Mathematical models and exact algorithms //European Journal of Operational Research. 2016. V. 255. №. 1. P. 1-20. doi: 10.1016/j.ejor.2016.04.030
  • Boyar J., Larsen K.S., Kamali S., Lopez-Ortiz A. Online bin packing with advice // Algorithmica. 2016. V. № 1. P. 507-527. doi: 10.1007/s00453-014-9955-8
  • Dosa G., Epstein L. The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints //Journal of Computer and System Sciences. 2018. V. 96. P. 33-49. doi: 10.1016/j.jcss.2018.03.004
  • Asta S., Ozcan E., Parkes A.J. CHAMP: Creating heuristics via many parameters for online bin packing // Expert Systems with Applications. 2016. V. 63. P. 208-221. doi: 10.1016/j.eswa.2016.07.005
  • Чепикова A.B., Коробова Л.А., Бугаев Ю.В. Задача трехмерной упаковки элементов // Аллея науки. 2018. Т. 1. № 9 (25). С. 433-436. URL: https://www.elibraiy.ru/download/elibrary_36430946_56294686.pdf
  • Фуремс Е.М. Обратная задача об упаковке в контейнеры при наличии качественных критериев - постановка и обзор применяемых методов // Искусственный интеллект и принятие решений. 2016. № 3. С. 31-43.
  • Орлов Б.Ю. Построение алгоритма последовательности перестановок в исследованиях и работе оборудования маслодобывающих предприятий // Научные исследования и современное образование. 2017. С. 183-185.
  • Шабля К).В., Кручинин Д.В., Репкин А.С. Сравнение подходов к разработке алгоритмов комбинаторной генерации на примере множеств перестановок и сочетаний // Прикладная математика и информатика: современные исследования в области естественных и технических наук. 2019. С. 75-80.
  • Титенко Е.А., Крипачев А.В., Марухленко АЛ. Коммутационная схема параллельных парных перестановок для специализированного продукционного устройства // Известия Южного федерального университета. Технические науки. 2018. №. 8 (202).
Еще
Статья научная