The paper describes a new algorithm to produce r-optimal tours for the travelling salesman problem. This algorithm is faster than the original r-optimal method, and computation times increase much less rapidly with problem size. The new algorithm makes it possible to solve large-scale travelling salesman problems and examples are given for problems varying in size from 100 to 500 cities. The paper also discusses r-optimality in terms of multistage 2-optimality.
No takes yet. Share an insight, caveat, or question.
Christofides et al. (1972) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: