Modeling Quartiles and Variance of Optimal Traveling Salesman Tour Lengths

Abstract

Traveling Salesman Problem (TSP) plays an important role in research and has many applications in the field of transportation and logistics. Most studies focus on developing algorithms to find the shortest path while some studies explore the average length of the shortest paths. However, the quartiles and variance of the shortest paths have not been studied so far. The quartiles and variance of the shortest paths are important because they can give information about the travel/delivery time reliability and the best and worst travel/delivery time scenario, when the tour can be regarded as TSP. This study performs experiments to find the shortest path connecting n customers, which are generated randomly in a specified service area, using genetic algorithm. The service areas considered include equilateral triangle, rectangle with ratio of length and width ranging from 1 to 8, regular hexagon, and circle. The number of customers considered range from 10 to 100 with an interval of 10. In each experiment, the customers are generated randomly for 500 times. The first, second and third quartiles as well as the variance of the 500 shortest paths have been recorded. Subsequently, regression models have been developed to estimate quartiles and variance using number of customers and parameters of service area. R squares of the developed models are all above 0.96, indicating very good fit. The constructed models can be used to estimate the travel time variance and reliability.