Проект

Общее

Профиль

Обзор

Задачи маршрутизации транспорта (Vehicle Routing Problems, VRP)

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

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

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

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

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

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

Разновидности VRP

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

  1. Capacitated VRP (CVRP): каждое транспортное средство имеет ограниченную грузоподъемность.
  2. VRP with Time Windows (VRPTW) или (TCVRP): каждый заказчик должен быть обслужен в определенное «временное окно».
  3. Multiple Depot VRP (MDVRP): используются несколько депо для обслуживания клиентов.
  4. VRP with Pick-Ups and Delivering (VRPPD): клиенты могут возвращать некоторые товары в депо.
  5. VRP with Backhauls (VRPB): аналогично предыдущей, но возврат начинается только после доставки всех товаров из депо.
  6. Split Delivery VRP (SDVRP): каждый клиент может обслуживаться одновременно несколькими машинами.
  7. Periodic VRP (PVRP): доставка может осуществляться в течение нескольких дней.
  8. Stochastic VRP (SVRP): некоторые компоненты задачи (количество и запросы клиентов, длина пути) могут иметь случайное поведение.
  9. VRP with Satellite Facilities (VRPSF): существует возможность дозагрузки автомобиля на маршруте.

Задачи

открыто закрыто Всего
Ошибка 0 0 0
Разработка 2 0 2
Поддержка 0 0 0

Просмотреть все задачи