R extensions are a kind of plug-in that can be installed into IBM SPSS Statistics to implement an algorithm according to users’ requirements. We announce a new R extension that can address travelling salesperson problems.
The travelling salesperson problem (TSP) is a well known and important optimization problem. The goal is to find the shortest route between each location in a given list and then returns to the starting location. For example, we know the distance between five cities in China: Beijing, Shanghai, Guangzhou, Chengdu and Hefei.
Below is the active dataset which we created in IBM SPSS Statistics 24 to represent the example of travelling salesperson problem.
In IBM SPSS Statistics 24, we click Analyze > Travelling Salesperson Problem. Choose the five cities to utilize the travelling salesperson problem algorithm. Firstly, select five cities to the “Nodes” and set the “Starting Node” city.
Secondly, choose the “Cost Type” which means your data set type. In the symmetric case, the cost type matrix between n cities are stored with elements dij where i, j = 1 . . . n and the diagonal elements dii are zero. In the matrix, the cost type is equal for all pairs of cities dij = dji, which means the spatial distance of Beijing to Shanghai is equal to Shanghai to Beijing.
In the asymmetric case, the cost type is not equal for all pairs of cities dij ≠ dji. Problems of this kind arise when we do not deal with spatial distances between cities. For example, the price for the plane ticket between two cities may be different, which can be used for the asymmetric case.
Finally, set the “Method” you require. There are 7 methods can be chose for the user.
• Nearest neighbour algorithm. The algorithm starts with a tour containing a randomly chosen city and then always adds the nearest not yet visited city in the tour.
• Repetitive nearest neighbour algorithm. Repeat the nearest neighbour algorithm with each city as the starting point and then return the best tour found.
• Nearest insertion. The city k is chosen in each step as the city which is nearest to a city on the tour.
• Farthest insertion. The city k is chosen in each step as the city which is farthest from any of the cities on the tour.
• Cheapest insertion. The city k is chosen in each step such that the cost of inserting the new city is minimal.
• Arbitrary insertion. The city k is chosen randomly from all cities not yet on the tour.
• 2-Opt heuristics. The idea is to define a neighbourhood structure on the set of all admissible tours.
We get the result of travelling salesperson problem algorithm in the IBM SPSS Statistics 24 output file. The shortest path is from Chengdu to Guangzhou, Hefei, Shanghai, Beijing, and then back to Chengdu. In addition, we get the total distance for the route, in this case 6781km.
#extensions#SPSSStatistics