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

Доклад будет посвящён описанию двух полиномиально приближённых схем для задачи маршрутизации транспорта с ограничениями на грузоподъёмность и временные промежутки обслуживания (CVRPTW), широко известной NP-трудной задачи комбинаторной оптимизации. Обе схемы являются развитием подхода, впервые предложенного в работе М.Хаймовича и А.Ринной-Кана для случая задачи маршрутизации транспорта с ограничениями лишь на грузоподъёмность (CVRP). В докладе будет показано, что классические результаты, полученные данными авторами, могут быть обобщены и на случай CVRPTW. Кроме того, в докладе будет рассмотрена модификация схемы М. Хаймовича и А.Ринной-Кана, в результате чего была получена полиномиальная приближённая схема с более лучшей трудоёмкостью по сравнению с оригинальным результатом.