DOI

Задача маршрутизации транспорта с ограничением на грузоподъемность (Capacitated Vehicle Routing Problem, CVRP) - одна из классических маршрутных экстремальных комбинаторных задач, обладающих большим числом приложений в области исследования операций. Оставаясь NP-трудной в сильном смысле как в общем случае, так и на евклидовой плоскости, задача CVRP допускает квазиполиномиальные и даже полиномиальные приближенные схемы (QPTAS и PTAS) в евклидовых пространствах фиксированной размерности. В то же время метрическая постановка задачи APX-полна даже в случае произвольной фиксированной грузоподъемности . В данной работе показывается, что классический алгоритм М. Хаймовича и А. Ринноя Кана реализует полиномиальную приближенную схему PTAS и эффективную полиномиальную приближенную схему (EPTAS) в произвольном метрическом пространстве фиксированной размерности при и произвольной постоянной грузоподъемности соответственно.
Переведенное названиеHaimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension
Язык оригиналаРусский
Страницы (с-по)235-248
Число страниц14
ЖурналТруды института математики и механики УрО РАН
Том25
Номер выпуска4
DOI
СостояниеОпубликовано - 2019

    Предметные области ASJC Scopus

  • Applied Mathematics
  • Mathematics(all)
  • Computer Science Applications
  • Computational Mechanics

    Области исследований

  • Capacitated Vehicle Routing Problem (CVRP), Doubling dimension, Metric space, Polynomial-Time Approximation Scheme (PTAS)

    Предметные области WoS

  • Математика, Прикладная

    Уровень публикации

  • Перечень ВАК

    ГРНТИ

  • 27.00.00 МАТЕМАТИКА

ID: 11465228