Студопедия

КАТЕГОРИИ:

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



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




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

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

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

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

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

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

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

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

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

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

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


Дата добавления: 2015-02-10; просмотров: 25; Нарушение авторских прав





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