Name
Abstract | ||
|---|---|---|
In the Vehicle Routing Problem (VRP), as in the Traveling Salesman Problem (TSP), we have a metric space of customer points, and we have to visits all customers. Additionally, every customer has a demand, a quantity of a commodity that has to be delivered in our vehicle from a single point called the depot. Because the vehicle capacity is bounded, we need to return to the depot each time we run out of the commodity to distribute. We describe a fully polynomial time algorithm with approximation 2.5, we also modify this algorithm for the on-line version of VRP, the randomized version has competitive ratio of 2.5 on the average, and the deterministic version has ratio 4. We also describe 2 approximation for a restricted version of the problem. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11534273_32 | WADS |
Keywords | Field | DocType |
randomized version,customer point,vehicle routing problem,competitive ratio,deterministic version,restricted version,polynomial time algorithm,salesman problem,vehicle capacity,on-line version,traveling salesman problem,metric space | Approximation algorithm,Combinatorics,Mathematical optimization,Vehicle routing problem,Steiner tree problem,Computer science,Travelling salesman problem,Time complexity,Deterministic system (philosophy),Competitive analysis,Bounded function | Conference |
Volume | ISSN | ISBN |
3608 | 0302-9743 | 3-540-28101-0 |
Citations | PageRank | References |
2 | 0.37 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Piotr Berman | 1 | 32 | 3.31 |
| Surajit K. Das | 2 | 2 | 0.37 |