A statistical approach to the traveling salesman problem |
| |
Authors: | WJ Kovacs DT Goodin |
| |
Institution: | GA Technologies Inc., P.O. Box 81608, San Diego, CA 92138, U.S.A. |
| |
Abstract: | A statistical approach is shown to be adaptable to the N-city traveling salesman problem by considering route distances to be random variables which are continuous and normally distributed. A solution to the shortest route distance and path can be approximated by utilizing a Monte Carlo simulation to obtain a representative sample of possible journeys. The approach involves recursive statistical inference which is used to select next-city visits leading to the most probable minimum route path. A statistical selection of the minimum route path is computationally efficient and computer run time increases in proportion to the square of the number of cities as opposed to an (N - 1)! increase for a deterministic approach. The accuracy of the statistical approach is directly proportional to the number of Monte Carlo simulations. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|