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.
TSP1

Below is the active dataset which we created in IBM SPSS Statistics 24 to represent the example of travelling salesperson problem.
TSP2

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.
TSP3

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.
TSP4

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.
TSP5

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.
TSP6

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.
TSP7

2 comments on"New R Extension for IBM SPSS Statistics: Travelling Salesperson Problem"

  1. AlexFleischer July 21, 2016

    Hi,
    aside the 7 methods you provide, you could also use Integer Programming or Constraint Programming within CPLEX

    See https://www.ibm.com/developerworks/community/forums/html/topic?id=5efb1db1-c642-4877-af60-b330f959a534

    regards

    • Linear, quadratic, and integer programming is available in SPSS Statistics with the STATS LP extension command.

Join The Discussion

Your email address will not be published. Required fields are marked *