A lexisearch algorithm for traveling salesman problem

摘要

A data-guided lexisearch algorithm for the traveling salesmannproblem (TSP) is presented along with an illustrative example. Thenalgorithm is a modification of the lexisearch approach to TSP asnproposed by S.N.N. Pandit (1962). By utilizing the information providednby appropriate statistics computed from the cost data of the TSP, thennodes of the network cities are renamed and an alphabet table is definednfor the search algorithm developed for the TSP, It is shown that evennthis minor preprocessing of the data before a standard algorithm wasnapplied improves the computational efficiency substantially