Задачи маршрутизации транспорта (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): существует возможность дозагрузки автомобиля на маршруте.