|
|
Seminar for Optimization Laboratory
October 30, 2015 11:00–12:00, Ekaterinburg, Sofyi Kovalevskoi st., 16
|
 |
|
 |
|
|
|
Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem
M. Yu. Khachaiab
a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg
|
| Number of views: |
| This page: | 262 |
|
Abstract:
We consider the classic setting of Capacitated Vehicle Routing Problem (CVRP): single product, single depot, demands of all customers are identical. This problem is known to be strongly NP-hard even for Euclidean spaces of fixed dimension. Being intractable, it can be well approximated. For instance, in the Euclidean plane, the problem (along with some of its modifications) admits polynomial time approximation schemes (PTAS). We propose polynomial time approximation scheme for the case of $R^3.$
|
|
Contact us: