
doi: 10.1007/11534273_32
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.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
