Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems
James R. Evans, Richard Hall · American Journal of Mathematical and Management Sciences · 1984
SYNOPTIC ABSTRACTThe use of assignment ranking techniques for solving the traveling salesman problem is considered in a probabilistic framework. The principal focus of the paper is on the assumptions required for a valid mathematical analysis. For the asymmetric case, we show that the assumptions are violated when clustering of cites is present; for the symmetric problem, we show that a valid analysis can be made when 2-city subtours are eliminated. Prior probabilistic results developed by Panayiotopoulos for asymmetric problems are extended to the symmetric case.