Маршрутизация транспортных средств

Среди задач маршрутизации транспортных средств при перевозке различных грузов одной из наиболее трудных для решения считается задача VRPTW (Vehicle Routing Problem with Time Windows) — задача маршрутизации транспортных средств с временными окнами. Временным окном здесь называют временной интервал, в который нужно выполнить заказ на перевозку. В задаче заданы:

· — число узлов-потребителей продукта ( -й узел-потребитель отождествляется с -м заказом);

· — число узлов-источников продукта;

· — число серверов (транспортных средств);

· — общее число узлов;

· — исходное расположение потребителей, источников и серверов в узлах транспортной сети;

· — матрица расстояний между узлами;

· и — нижняя и верхняя границы временного окна для выполнения -го заказа;

· — число типов продукта.

Кроме того, для узлов-потребителей и узлов-источников заданы объемы соответственно заказанного и имеющегося продукта каждого типа, для серверов — максимальный объем перевозимого продукта, скорость движения, цена за единицу расстояния пробега, штрафы за нарушение временных ограничений (выход за пределы временных окон), причем штрафы зависят от цены единицы продукта каждого типа и от степени нарушения ограничений.

Требуется найти график движения транспортных средств для выполнения всех заказов с минимальными затратами.

Каждая эвристика при использовании HCM включает правила для выбора заказа (узла-потребителя), узла-источника продукта и транспортного средства (не исключено, что для выполнения конкретного заказа привлекается более чем по одному источнику и/или серверу).

Для выбора узла-потребителя можно использовать следующие правила:

· ) предпочтение отдается узлу с максимальным суммарным объемом заказанного продукта;

· ) выбирается потребитель с максимальной ценой заказанного продукта;

· ) выбирается потребитель с минимальной верхней границей временного окна.

В правилах выбора узла-источника продукта предпочтение может отдаваться источнику:

· ) с минимальным расстоянием до выбранного в первой части узла-потребителя;

· ) с минимальной суммой расстояний до узла-потребителя и до ближайшего узла, в котором имеется свободный сервер;

· ) с минимальной величиной , где и — расстояния соответственно до узла-потребителяи и до ближайшего узла, в котором имеется свободный сервер, — суммарный объем заказанного продукта, — суммарный объем продукта в источнике.

Эвристика дополняется правилом, в котором выбирается сервер:

· ) с минимальным расстоянием до узла-потребителя;

· ) с минимальным временем освобождения от предыдущего обслуживания;

· ) с минимальным временем выполнения маршрута.