VRP (задача маршрутизации транспорта)

VRP – класс задач комбинаторной оптимизации о построении оптимального набора маршрутов для парка транспортных средств, обслуживающих множество клиентов из одного или нескольких депо при минимуме суммарных издержек (пробега, времени, числа машин). Формально введена Данцигом и Рамсером в 1959 году как «задача диспетчеризации грузовиков» и является обобщением задачи коммивояжёра; относится к NP-трудным, поэтому на практике решается эвристиками и метаэвристиками. Базовые вариации учитывают грузоподъёмность (CVRP) и временные окна доставки (VRPTW).