Маршрутизация с ограничением по грузоподъемности (Capacitated VRP, CVRP)

В задачах этого типа вводится дополнительное ограничение: объем грузов на каждом маршруте R_i не должен превышать заданной величины Q (одинаковый для всех машин).

Цель: Минимизировать парк машин, необходимых для выполнения задания, а также общее время выполнения задачи.

2. Маршрутизация с ограничением по времени (VRP with Time Windows, VRPTW)

Данная задача подобна VRP с основным дополнительным условием: для выполнения запроса каждого клиента v_i существует известный промежуток времени, определенный как интервал [e_i,l_i] — намеченный горизонт (scheduling horizon).

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

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

Ограничения: по сравнению с VRP, в задачах данного типа добавляются следующие условия:

· решение неприемлемо, если клиент обслуживается после верхней временной границы;

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

· как вариант, опоздание не влияет на пригодность решения, но добавляет некоторое штрафное значение к целевой функции.

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