ПОЛИНОМИАЛЬНАЯ ПРИБЛИЖЕННАЯ СХЕМА ДЛЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ С ОГРАНИЧЕНИЯМИ НА ГРУЗОПОДЪЕМНОСТЬ И ВРЕМЕННЫЕ ПРОМЕЖУТКИ ОБСЛУЖИВАНИЯ

Результат исследований: Вклад в журналСтатья

Аннотация

Задача маршрутизации транспорта с ограничениями на грузоподъемность и временные промежутки обслуживания (CVRPTW) является широко известной NP-трудной задачей комбинаторной оптимизации. В настоящей работе представлено дальнейшее развитие подхода, представленного впервые в работе М. Хаймовича и А. Ринной Кана. Предложенный алгоритм для произвольного за время находит -приближенное решение задачи CVRPTW на евклидовой плоскости, где - верхняя оценка грузоподъемности транспортных средств, - число промежутков обслуживания (временных окон) и - трудоемкость поиска -приближенного решения вспомогательной постановки метрической задачи коммивояжера. Тем самым, алгоритм является полиномиальной приближенной схемой (PTAS) для постановки задачи CVRPTW, в которой , и эффективной полиномиальной схемой (EPTAS) при произвольных фиксированных значения и .
Переведенное названиеPolynomial time approximation scheme for the capacitated vehicle routing problem with time windows
Язык оригиналаРусский
Страницы (с-по)233-246
Число страниц14
ЖурналТруды института математики и механики УрО РАН
Том24
Номер выпуска3
DOI
СостояниеОпубликовано - 2018

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

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

ГРНТИ

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

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

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

Цитировать