RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Тр. ИММ УрО РАН, 2018, том 24, номер 3, страницы 233–246 (Mi timm1565)  

Полиномиальная приближенная схема для задачи маршрутизации транспортных средств с ограничениями на грузоподъемность и временные промежутки обслуживания

М. Ю. Хачайabc, Ю. Ю. Огородниковab

a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
c Омский государственный технический университет

Аннотация: Задача маршрутизации транспорта с ограничениями на грузоподъемность и временные промежутки обслуживания (CVRPTW) является широко известной NP-трудной задачей комбинаторной оптимизации. В настоящей работе представлено дальнейшее развитие подхода, представленного впервые в работе М. Хаймовича и А. Ринной Кана. Предложенный алгоритм для произвольного $\varepsilon>0$ за время $\mathrm {TIME}(\mathrm {TSP},\rho,n)+O(n^2)+ O( e^{O(q (\frac{q}{\varepsilon})^3(p\rho)^2 \log (p\rho))})$ находит $(1+\varepsilon)$-приближенное решение задачи CVRPTW на евклидовой плоскости, где $q$ - верхняя оценка грузоподъемности транспортных средств, $p$ - число промежутков обслуживания (временных окон) и $\mathrm {TIME}(\mathrm {TSP},\rho,n)$ - трудоемкость поиска $\rho$-приближенного решения вспомогательной постановки метрической задачи коммивояжера. Тем самым, алгоритм является полиномиальной приближенной схемой (PTAS) для постановки задачи CVRPTW, в которой $p^3q^4=O(\log n)$, и эффективной полиномиальной схемой (EPTAS) при произвольных фиксированных значения $p$ и $q$.

Ключевые слова: задача маршрутизации транспорта с ограничением на грузоподъемность, временные окна, эффективная полиномиально приближенная схема.

Финансовая поддержка Номер гранта
Российский научный фонд 14-11-00109
Работа первого автора выполнена при поддержке РНФ (проект 14-11-00109).


DOI: https://doi.org/10.21538/0134-4889-2018-24-3-233-246

Полный текст: PDF файл (456 kB)
Первая страница: PDF файл
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.16 + 519.85
MSC: 90C27, 90C59, 90B06
Поступила в редакцию: 29.05.2018

Образец цитирования: М. Ю. Хачай, Ю. Ю. Огородников, “Полиномиальная приближенная схема для задачи маршрутизации транспортных средств с ограничениями на грузоподъемность и временные промежутки обслуживания”, Тр. ИММ УрО РАН, 24, № 3, 2018, 233–246

Цитирование в формате AMSBIB
\RBibitem{KhaOgo18}
\by М.~Ю.~Хачай, Ю.~Ю.~Огородников
\paper Полиномиальная приближенная схема для задачи маршрутизации транспортных средств с ограничениями на грузоподъемность и временные промежутки обслуживания
\serial Тр. ИММ УрО РАН
\yr 2018
\vol 24
\issue 3
\pages 233--246
\mathnet{http://mi.mathnet.ru/timm1565}
\crossref{https://doi.org/10.21538/0134-4889-2018-24-3-233-246}
\elib{http://elibrary.ru/item.asp?id=35511290}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timm1565
  • http://mi.mathnet.ru/rus/timm/v24/i3/p233

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Труды Института математики и механики УрО РАН
    Просмотров:
    Эта страница:34
    Литература:3
    Первая стр.:4

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019