RUS  ENG
Полная версия
СЕМИНАРЫ

Семинар отдела математического программирования
26 октября 2018 г. 11:00, г. Екатеринбург, Институт математики и механики им. Н. Н. Красовского УрО РАН, ул. Софьи Ковалевской 16, актовый зал


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


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


© МИАН, 2024