| RUS ENG |
| Полная версия |
|
|
|
| СЕМИНАРЫ |
|
Семинар отдела математического программирования
|
|||
|
|
|||
|
Полиномиальная приближенная схема для евклидовой задачи маршрутизации с одним складом и ограниченной грузоподъемностью М. Ю. Хачайab a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург |
|||
|
Аннотация: Рассматривается классическая постановка задачи маршрутизации транспорта с органиченной грузоподъемностью (CVRP), обладающая стандартными свойствами: однородные продукция и спрос, единственный склад, Известно, что эта задача остается NP-трудной даже будучи сформулированной в евклидовом пространстве фиксированной размерности. Несмотря на труднорешаемость, в этом частном случае задача мжет быть эффективно аппроксимирована. Например, на плоскости задача (и некоторые ее модификации) обладают полиномиальными приближенными схемами (PTAS). В работе строится PTAS для трехмерного пространства. |
|||