Проекты за года
Аннотация
Задача маршрутизации транспорта с ограничениями на грузоподъемность и временные промежутки обслуживания (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 МАТЕМАТИКА
Уровень публикации
- Перечень ВАК
Fingerprint
Подробные сведения о темах исследования «ПОЛИНОМИАЛЬНАЯ ПРИБЛИЖЕННАЯ СХЕМА ДЛЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ С ОГРАНИЧЕНИЯМИ НА ГРУЗОПОДЪЕМНОСТЬ И ВРЕМЕННЫЕ ПРОМЕЖУТКИ ОБСЛУЖИВАНИЯ». Вместе они формируют уникальный семантический отпечаток (fingerprint).Проекты
- 1 Активно
-
Научная лаборатория «Лаборатория оптимального раскроя промышленных материалов и оптимальных маршрутных технологий»
Петунин, А. А., Ченцов, П. А., Ченцов, А. Г., Сесекин, А. Н., Верхотуров, М. А., Картак, В. М., Fisher, A., Scheithauer, G., Мясогутов, М., Панюкова, Т. А., Кошелева, М. С., Полищук, Е. Г., Шипачёва, Е. Н., Репницкий, В. Б., Захарова, Г. Б., Полевов, А. В., Кротов, В. И., Галкин, И. С., Березин, И. М., Чернухин, В. И., Таваева, А. Ф., Фатехрад, М., Асанбеков, К., Панюков, А. В., Котел, Н. С., Уколов, С. С., Миронов, К. В., Салий, Я. В., Попов, В. Ю., Хачай, М. Ю., Иванко, Е. Е. & Савчук, А.
12/12/2013 → …
Проект: Исследование › Научная лаборатория