Arxiv/Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension 2021 2106.15034 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{arxivlink|arxiv/Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension 2021 2…») |
StasFomin (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
− | {{arxivlink|arxiv/Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension 2021 2106.15034| | + | {{arxivlink|arxiv/Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension 2021 2106.15034|2= |
В этой статье мы представляем схемы аппроксимации для емкостного транспортного средства. Задача маршрутизации (CVRP) на нескольких классах графов. В CVRP, представленный Данциг и Рамзер (1959), нам дан график ''G=(V,E)'' с метрическими краями затраты, депо ''r∈V'', и автомобиль ограниченной вместимости Q. | В этой статье мы представляем схемы аппроксимации для емкостного транспортного средства. Задача маршрутизации (CVRP) на нескольких классах графов. В CVRP, представленный Данциг и Рамзер (1959), нам дан график ''G=(V,E)'' с метрическими краями затраты, депо ''r∈V'', и автомобиль ограниченной вместимости Q. | ||
Текущая версия на 20:44, 9 декабря 2021
«Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension 2021 2106.15034»скачать
Цель состоит в том, чтобы найти минимальную стоимость туров для автомобиля, который возвращается в депо, каждое посещение не более Q узлы, так что они покрывают все узлы. Это обобщает классический TSP и был тщательно изучен. В более общие настройки, каждый узел v имеет спрос d v и общий спрос каждого тур должен быть не более Q.
Либо спрос каждого узла должен обслуживаться один тур (неразделимый) или может обслуживаться несколькими турами (разделенный). В самый известный алгоритм аппроксимации общих графиков имеет соотношение α + 2 (1-ϵ) (для нерасщепляемого) и α + 1 - ϵ (для splittable) для некоторых фиксированных ϵ > 1/3000, где а это наилучшее приближение для TSP.
Даже для деревьев наилучшее приближение соотношение 4 / 3 Беккера (2018), и вопрос о существовании схема аппроксимации для этого простого класса графов.
Дас и Матье (2015) представили схему аппроксимации со временем п журнал O\log^{(1/ϵ)п} за Евклидова плоскость R^2. Никакой другой схемы аппроксимации не известно ни для одного другой класс метрик (без дополнительных ограничений на Q).
В этой статье мы добиться значительного прогресса в решении этой классической проблемы, представив Квазиполиномиальные схемы аппроксимации времени (QPTAS) для графов ограниченного Treewidth, графики ограниченных размеров автомагистралей и графики ограниченного удвоения габаритные размеры.
Для сравнения наш результат представляет собой схему аппроксимации для Евклидов самолет со временем выполнения n O(\log^{10}{n/ϵ^9}).…»