Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Семинар отдела математического программирования
30 октября 2015 г. 11:00–12:00, г. Екатеринбург, ул. Софьи Ковалевской, 16, Институт математики и механики им. Н.Н. Красовского, актовый зал, 3 этаж
 


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

М. Ю. Хачайab

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

Количество просмотров:
Эта страница:243

Аннотация: Рассматривается классическая постановка задачи маршрутизации транспорта с органиченной грузоподъемностью (CVRP), обладающая стандартными свойствами: однородные продукция и спрос, единственный склад, Известно, что эта задача остается NP-трудной даже будучи сформулированной в евклидовом пространстве фиксированной размерности. Несмотря на труднорешаемость, в этом частном случае задача мжет быть эффективно аппроксимирована. Например, на плоскости задача (и некоторые ее модификации) обладают полиномиальными приближенными схемами (PTAS). В работе строится PTAS для трехмерного пространства.
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024