PROBABILITY DISTRIBUTION OF THE LENGTH OF THE SHORTEST TOUR BETWEEN A FEW RANDOM POINTS: A SIMULATION STUDY

摘要

Inspired by an application in the field of on-demand public transportation, we perform a Monte Carlo simulation study on the probability distribution of the length of Traveling-Salesman-Problem (TSP) tours between small numbers of random locations. We consider a fixed convex region, where we generate a fixed number of random locations from a known probability distribution and find the corresponding euclidean TSP tour for them. We simulate this process extensively and perform both quantitative and qualitative analyses of the resulting experimental distribution for the TSP tour length. We show that, under certain assumptions on the shape of the region and the probability distribution of locations, the length of the TSP tour is well-approximated by a normal distribution, even for as few as five locations. Furthermore, we propose experimental models for estimating the mean and standard deviation of the tour length.