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.
Original language | English (US) |
---|---|
Pages (from-to) | 360-371 |
Number of pages | 12 |
Journal | Lecture Notes in Computer Science |
Volume | 3608 |
DOIs | |
State | Published - 2005 |
Event | 9th International Workshop on Algorithms and Data Structures, WADS 2005 - Waterloo, Canada Duration: Aug 15 2005 → Aug 17 2005 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science