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