Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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 = {v0, v1, ..., vn} — множество вершин (v0 — депо, v1..n — потребители)

· E — множество ребер {(vi, vj) | ij}

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

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

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

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

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

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

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

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

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

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

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

FVRP = ∑C(Ri), i = 1..m

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

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


Поделиться:

Дата добавления: 2015-02-10; просмотров: 232; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты