УДК 656.025

Вопросы оптимизации маршрутов перевозки автотранспортными средствами

Малиновский Никита Андреевич – студент магистратуры Балтийского федерального университета им. И. Канта.

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

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

Конкуренция в деловом мире сегодня очень высока, поэтому каждый бизнесмен пытается минимизировать операционные расходы, включая стоимость распределения товаров среди всех агентов. Одна из попыток снизить затраты на распространение товаров – это определение оптимального маршрута распространения. Как правило, основой для определения маршрута являются время и расстояние. Это также можно узнать с помощью приложения google-map или Waze. Просто оба эти приложения не учитывают спрос на товары у каждого агента и транспортную мощность используемого для доставки вида транспорта. Кроме того, время в пути и дорожные условия нечеткие, что означает, что значение является относительным и зависит от различных факторов, включая часы доставки, погоду и плотность движения. Следовательно, этот фактор размытия устраняется с помощью подхода нечетких множеств.

Между тем, определение оптимального маршрута на основе одного критерия можно решить с помощью проблемы с маршрутизацией автомобилей (Vehicle Routing Problem (VRP)). VRP можно охарактеризовать как проблему построения оптимального маршрута от дистрибьютора до дилера. VRP имеет несколько классификаций, одна из которых - проблема маршрутизации с использованием емкости для транспортных средств (CVRP), в которой каждый транспортный режим имеет ограниченную пропускную способность. Существует несколько методов заполнения CVRP, а именно точный метод и эвристический метод. Одним из эвристических методов, которые можно использовать для решения CVRP, является алгоритм Сбережения Кларка и Райта. Алгоритм Сбережения Кларка и Райта - очень популярный эвристический метод для решения задач VRP [1]. Алгоритм используется для минимизации расстояния при прохождении маршрута путем объединения двух или более маршрутов с учетом экономии расстояния, количества запросов клиентов и вместимости используемого транспортного средства. В этом исследовании применяется комбинация двух подходов к определению оптимального маршрута с несколькими целями, а именно: нечеткие множества и алгоритм экономии Кларка и Райта.

Алгоритм распределения товаров учитывает три критерия:

  1. минимальное общее расстояние;
  2. общее время в пути от склада дистрибьютора до каждого минимального агента;
  3. общее максимальное качество дороги.

Проблема маршрутизации транспортных средств (VRP) была впервые представлена Данцигом и Рамзером в исследовании под названием «Проблема диспетчеризации грузовиков» в 1959 году. В своих исследованиях Данциг и Рамзер разработали формулировку математических программ и алгоритмов подхода для решения проблемы диспетчеризации бензина. С тех пор интерес к VRP вырос от группы математиков до широкого круга исследователей и практиков из различных дисциплин. [2]

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

VRP можно определить как поиск решения, который включает в себя определение количества маршрутов, где каждый маршрут проходит транспортным видом, который начинается и заканчивается в его исходной станции, так что потребности/запросы всех клиентов удовлетворяются при одновременном удовлетворении. существующие операционные ограничения, в том числе за счет минимизации затрат на транспортировку по всему миру [2]. Каждого клиента можно обслуживать только на автомобиле. Это сделано, чтобы минимизировать затраты, учитывая вместимость транспортного средства за одну доставку.

При использовании VRP в реальном мире возникает множество факторов. Эти факторы влияют на появление вариаций VRP, таких как:

  1. Емкостная VRP (CVRP), т.е. каждое транспортное средство имеет ограниченную вместимость.
  2. VRP с временными окнами, т.е. каждому заказчику необходимо поставить в течение определенного периода.
  3. VRP с несколькими складами, то есть у дистрибьюторов есть много складов для снабжения клиентов
  4. VRP с приемом и доставкой, то есть покупатель может вернуть товары на исходный склад.
  5. Раздельная доставка VRP, то есть клиенты обслуживаются разными транспортными средствами
  6. Стохастическая VRP, которая представляет собой появление «случайных значений», таких как количество клиентов, количество запросов, время обслуживания или время в пути.
  7. Периодический VRP, то есть доставка осуществляется только в определенные дни.

Проблема с маршрутизацией на емкостном транспортном средстве

Capacitated Vehicle Routing Problem (CVRP) - одна из разновидностей проблемы VRP, где существуют дополнительные ограничения идентичной пропускной способности транспортного средства для посещения ряда потребителей согласно их соответствующим запросам. Проблема CVRP заключается в том, что общее количество запросов потребителей на маршруте не превышает возможности транспортного средства, обслуживающего маршрут, и каждый клиент посещается только один раз одним транспортным средством. Задача CVRP направлена на минимизацию общего расстояния, пройденного транспортными маршрутами, и минимизацию количества транспортных средств, используемых при распределении товаров от места доставки (депо) ряду потребителей.

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

  1. Pugacs, S. A Clustering Approach for Vehicle Routing Problem with Hard Time Windows. Master Thesis, Nova de Lisboa University. (2014).
  2. Тот П., Виго Д. Обзор проблем с маршрутизацией транспортных средств. Проблема маршрута транспорта. Филадельфия: Сиам. (2018).

Интересная статья? Поделись ей с другими:

Внимание, откроется в новом окне. PDFПечатьE-mail