VRM (Vehicle routing model) - модель маршрутизации транспорта

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

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

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

Задачи VRP лежат на пересечении двух хорошо изученных задач.

· Задача коммивояжера (Traveling Salesman Problem, TSP): если грузоподъемность Скаждого транспортного средства принимается бесконечной (точнее, достаточной), то задача VRP сводится к множественной задаче коммивояжера (Multiple Traveling Salesman Problem, MTSP) путем добавления к исходному графу k-1 (где k — количество маршрутов) копий нулевой вершины и ее ребер (между этими копиями ребра отсутствуют).

· Задача об упаковке рюкзака (Bin Packing Problem, BPP): решение данной задачи, по сути, эквивалентно решению задачи VRP при условии, что все расстояния принимаются равными нулю (таким образом, эффективность всех подходящих решений будет одинакова).

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

Классический вариант задачи маршрутизации

Маршрутизация транспорта относится к комбинаторным задачам, которые можно представить в виде графа G(V, E):

· V = {v₀, v₁, ..., v_n} — множество вершин (v₀ — депо, v_1..n — потребители)

· E — множество ребер {(v_i, v_j) | i ≠ j}

· C — матрица неотрицательных расстояний (стоимости пути) c_ij между потребителями

· m — количество машин

· R_i — маршрут i-й машины (i=1..m)

· C(R_i) — стоимость маршрута R_i

· q_i - объем груза, поставляемый i-му потребителю

С каждой вершиной V_i ассоциировано некоторое количество товаров, которые должны быть доставлены соответствующему потребителю. Задача маршрутизации состоит в определении такого множества маршрутов m с минимальной общей стоимостью, чтобы каждая вершина множества V была посещена только одним автомобилем только один раз. Кроме того, все маршруты должны начинаться и заканчиваться в депо (v₀).

Решением задачи является:

· разбиение множества V на подмножества (маршруты);

· задание порядка обхода на каждом подмножестве (перестановка вершин маршрута).

Решение является приемлемым (feasible), если все маршруты удовлетворяют дополнительным ограничениям задачи.

Целевой функцией является стоимость решения задачи:

F_VRP = ∑C(R_i), i = 1..m

где C(R_i) — сумма длин ребер маршрута R_i.

В классическом варианте требуется найти приемлемое решение с минимальной стоимостью.