Arxiv/Improved Approximations for CVRP with Unsplittable Demands 2021 2111.08138 — различия между версиями

«Improved Approximations for CVRP with Unsplittable Demands 2021 2111.08138»^{скачать}

«В этой статье мы представляем улучшенные алгоритмы аппроксимации для (неразделимой) задачи о маршрутизации емкостных транспортных средств (CVRP) в общих показателях.

В CVRP, введенном Данцигом и Рамзером (1959), нам дается набор точек (клиентов) V вместе с депо r в метрическом пространстве, причем каждый v∈V имеет спрос dv>0, и транспортное средство ограниченного вместимость Q.

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

Мы представляем два алгоритма аппроксимации для нерасщепляемого CVRP: комбинаторное (α + 1,75) -приближение, где α — коэффициент аппроксимации для задачи коммивояжера, и алгоритм аппроксимации, основанный на округлении LP с гарантией приближения α + ln (2) + δ ≈3.194 + δ за время nO (1 / δ). Оба приближения могут быть дополнительно улучшены на небольшую величину в сочетании с недавней работой Blauth, Traub и Vygen (2021), которые получили (α + 2⋅ (1 − ϵ)) — приближение для нерасщепляемого CVRP для некоторой константы ϵ в зависимости от на α (ϵ> 1/3000 при α = 1,5).…»