
Summary: We consider the capacitated traveling salesman problem with pickups and deliveries. This problem is characterized by a set of \(n\) pickup points and a set of \(n\) delivery points. A single product is available at the pickup points which must be brought to the delivery points. A vehicle of limited capacity is available to perform this task. The problem is to determine the tour the vehicle should follow so that the total distance traveled is minimized, each load at a pickup point is picked up, each delivery point receives its shipment and the vehicle capacity is not violated. We present two polynomial-time approximation algorithms for this problem and analyze their worst-case bounds.
worst-case bounds, polynomial-time approximation algorithms, Operations research and management science, capacitated traveling salesman problem
worst-case bounds, polynomial-time approximation algorithms, Operations research and management science, capacitated traveling salesman 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). | 50 | |
| 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. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
