METHODOLOGY

 

  

Figure: IGA Procedure (http://gaslab.cs.unr.edu/)

(a) Display city coords

(b) User decomposes the TSP

(c) Run GA on each cluster to get sub-tours

(d) Connect sub-tours to get a global tour

Using the IGA to attack TSPs follows four steps.

Step 1: Plot and display city locations on the interface as shown in Figure 1 (a). This provides the user with ability to identify and exploit any structure in the distribution of cities. Although we could use one of several clustering methods to decompose the problem, humans are very good at finding patterns in visual data - we simply exploit this property.

Step 2: Separate the data into clusters Figure 1 (b). The clusters are separated manually by choosing a cluster id and then using the mouse to select groups of points (cities) on the interface to belong to the chosen cluster. The current version allows all cities inside a mouse drawn rectangle to be assigned to a cluster. Cities can also be added and deleted from clusters.

Step 3: Run the genetic algorithm on each cluster. Note that this can be done in parallel with one GA assigned to each cluster. We can run each GA on a different machine or do further parallelization. Our Java implementation creates a separate thread for each cluster while the C implementation simply starts separate processes. At the end of this step we get tours for each cluster of cities as shown in Figure 1 (c).

Step 4: Connect these sub-tours to get a complete tour. We currently allow two ways of reconnecting sub-tours.

1.

Manual: The user can choose to delete and add edges to open subtours and to combine adjacent open subtours. The current sum of the lengths of all edges (total tour length) is always displayed so that the user can experiment with the subtours. In this scheme, the whole process is based completely on the user's visual judgment. That is, we try to decrease the total tour length by replacing long edges with short edges.

2.

Semi-Automatic: The user draws a rectangle that includes appropriate (in the user's judgment) cities in two adjacent clusters and the interface does an exhaustive search among chosen city edges to find edges to delete and add such that the combined tour length is minimized. The total tour length will also be updated. This scheme relieves the user from the tedium of experimenting with fine adjustments - you only need to specify a promising area for reconnection.