Polynomial time approximation scheme for the capacitated vehicle routing problem with time windows

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Задача маршрутизации транспорта с ограничениями на грузоподъемность и временные промежутки обслуживания (CVRPTW) является широко известной NP-трудной задачей комбинаторной оптимизации. В настоящей работе представлено дальнейшее развитие подхода, представленного впервые в работе М. Хаймовича и А. Ринной Кана. Предложенный алгоритм для произвольного за время находит -приближенное решение задачи CVRPTW на евклидовой плоскости, где - верхняя оценка грузоподъемности транспортных средств, - число промежутков обслуживания (временных окон) и - трудоемкость поиска -приближенного решения вспомогательной постановки метрической задачи коммивояжера. Тем самым, алгоритм является полиномиальной приближенной схемой (PTAS) для постановки задачи CVRPTW, в которой , и эффективной полиномиальной схемой (EPTAS) при произвольных фиксированных значения и .
Translated title of the contributionPolynomial time approximation scheme for the capacitated vehicle routing problem with time windows
Original languageRussian
Pages (from-to)233-246
Number of pages14
JournalТруды института математики и механики УрО РАН
Volume24
Issue number3
DOIs
Publication statusPublished - 2018

Keywords

  • capacitated vehicle routing problem
  • time windows
  • efficient polynomial time approximation scheme

WoS ResearchAreas Categories

  • Mathematics, Applied

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Cite this

@article{3300e06c02094477a87f2683ad6bde0e,
title = "ПОЛИНОМИАЛЬНАЯ ПРИБЛИЖЕННАЯ СХЕМА ДЛЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ С ОГРАНИЧЕНИЯМИ НА ГРУЗОПОДЪЕМНОСТЬ И ВРЕМЕННЫЕ ПРОМЕЖУТКИ ОБСЛУЖИВАНИЯ",
abstract = "Задача маршрутизации транспорта с ограничениями на грузоподъемность и временные промежутки обслуживания (CVRPTW) является широко известной NP-трудной задачей комбинаторной оптимизации. В настоящей работе представлено дальнейшее развитие подхода, представленного впервые в работе М. Хаймовича и А. Ринной Кана. Предложенный алгоритм для произвольного за время находит -приближенное решение задачи CVRPTW на евклидовой плоскости, где - верхняя оценка грузоподъемности транспортных средств, - число промежутков обслуживания (временных окон) и - трудоемкость поиска -приближенного решения вспомогательной постановки метрической задачи коммивояжера. Тем самым, алгоритм является полиномиальной приближенной схемой (PTAS) для постановки задачи CVRPTW, в которой , и эффективной полиномиальной схемой (EPTAS) при произвольных фиксированных значения и .",
keywords = "capacitated vehicle routing problem, time windows, efficient polynomial time approximation scheme",
author = "Khachai, {Mikhail Yur'evich} and Ogorodnikov, {Yurii Yur'evich}",
year = "2018",
doi = "10.21538/0134-4889-2018-24-3-233-246",
language = "Русский",
volume = "24",
pages = "233--246",
journal = "Труды института математики и механики УрО РАН",
issn = "0134-4889",
publisher = "Институт математики и механики им. Н.Н. Красовского УрО РАН",
number = "3",

}

TY - JOUR

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

AU - Khachai, Mikhail Yur'evich

AU - Ogorodnikov, Yurii Yur'evich

PY - 2018

Y1 - 2018

N2 - Задача маршрутизации транспорта с ограничениями на грузоподъемность и временные промежутки обслуживания (CVRPTW) является широко известной NP-трудной задачей комбинаторной оптимизации. В настоящей работе представлено дальнейшее развитие подхода, представленного впервые в работе М. Хаймовича и А. Ринной Кана. Предложенный алгоритм для произвольного за время находит -приближенное решение задачи CVRPTW на евклидовой плоскости, где - верхняя оценка грузоподъемности транспортных средств, - число промежутков обслуживания (временных окон) и - трудоемкость поиска -приближенного решения вспомогательной постановки метрической задачи коммивояжера. Тем самым, алгоритм является полиномиальной приближенной схемой (PTAS) для постановки задачи CVRPTW, в которой , и эффективной полиномиальной схемой (EPTAS) при произвольных фиксированных значения и .

AB - Задача маршрутизации транспорта с ограничениями на грузоподъемность и временные промежутки обслуживания (CVRPTW) является широко известной NP-трудной задачей комбинаторной оптимизации. В настоящей работе представлено дальнейшее развитие подхода, представленного впервые в работе М. Хаймовича и А. Ринной Кана. Предложенный алгоритм для произвольного за время находит -приближенное решение задачи CVRPTW на евклидовой плоскости, где - верхняя оценка грузоподъемности транспортных средств, - число промежутков обслуживания (временных окон) и - трудоемкость поиска -приближенного решения вспомогательной постановки метрической задачи коммивояжера. Тем самым, алгоритм является полиномиальной приближенной схемой (PTAS) для постановки задачи CVRPTW, в которой , и эффективной полиномиальной схемой (EPTAS) при произвольных фиксированных значения и .

KW - capacitated vehicle routing problem

KW - time windows

KW - efficient polynomial time approximation scheme

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000451634900021

UR - https://elibrary.ru/item.asp?id=35511290

U2 - 10.21538/0134-4889-2018-24-3-233-246

DO - 10.21538/0134-4889-2018-24-3-233-246

M3 - Статья

VL - 24

SP - 233

EP - 246

JO - Труды института математики и механики УрО РАН

JF - Труды института математики и механики УрО РАН

SN - 0134-4889

IS - 3

ER -