Extracted From

GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR

TRAVELING SALESMAN PROBLEM* Thesis by SEUNG HO LEE

C. Satellite list

As another efficient data structure … Osterman and Rego [16] designed the satellite list. Figure 2 describes the basic concept of the satellite list structure and its Swap operation. The satellite list maintains two linked lists which indicate the clockwise and counterclockwise orientations of the tour. For example, suppose that 1-2-3-4-5-6-7 is a path of the TSP tour. Therefore the two linked lists indicating both orientations of the tour are the paths 1-2-3-4-5-6-7 (clockwise) and 7-6-5-4-3-2-1 (counterclockwise) as described in the first illustration of Figure 2. In the illustration, the two nodes connected with a dashed line indicate the same city and they are called complement satellites to each other. Suppose further Swap(1, 2, 7, 6) is performed; the edges {2, 7}, {1, 6} substitute the edges (1, 2), (6, 7). This operation is a 180 degree flip of the linked lists as described in the second and third illustrations of Figure 2. The last illustration represents the reconstruction of the new tour path. In the C implementation, we can perform this Swap operation by changing the pointers of four linked list nodes (clockwise 1, clockwise 6, counterclockwise 2, counterclockwise 7) in a constant time.

Osterman and Rego [16] designed a special array structure combining those two linked lists. This satellite list array is the one dimensional array with length of 2n, where n is the total number of cities. In the array, each of the evenly indexed element has the previous city’s index. In this way, the satellite list array can be initially constructed representing both orientations of the TSP tour. The ith element in the array indicates the index of the next or the previous city from the city i/2. If i mod 2 is 0, then the element represents the next city. Otherwise it denotes the index of previous city from the city i/2. For example, the 4th element in the satellite list array will be the next city’s index of the city 2, and the 5th element will be the previous city’s index of the city 2. Those 4th and 5th elements are the complement satellites which have the neighbor information of city 2. Under this convention, the tour 0-1-2-3-4 can be constructed to the satellite list array 2-9-4-1-6-3-8-5-0-7. In order to change the tour to the new tour 0-3-2-1-4, the edges (0,1), (3,4) should be removed and the edges {0,3}, {1,4} should be added. The concept of the Swap operation in the satellite list array is as follows. The satellite list array contains two tour representations of both orientations, which are (a) 0-1-2-3-4 and (b) 4-3-2-1-0. If we use the separated two linked list representation, the Swap operation will be the exchange of pointers. That is exchanging the pointer of 0 in tour (a) and the pointer of 4 in tour (b), and the pointer of 3 in (a) and the pointer of 1 in (b).

Then the new two linked list will be (a) 0-3-2-1-4 and (b) 4-1-2-3-0. Similarly, in the satellite list array structure, the exchanges between array elements make the same tour reconstruction. Those are the swap between the even element of city 0 and the odd element of city 4, and the swap between the odd element of city 1 and the even element of city 3.

Figure 3 demonstrates the above satellite list array Swap operation. After the swap operation, we can see that not all the even elements represent the next city’s index. We should follow each element index to track the tour without knowing the orientation. By this reason, the satellite list is limited to the symmetric TSP. Because of its symmetric design, the satellite list performs this operation easily in constant time, O(1)

.

[16] C. Osterman and C. Rego, The satellite list and new data structures for symmetric

traveling salesman problems, Tech. Report HCES-06-03, Hearin Center for Enterprise Science, School of Business Administration, University of Mississippi, University, MS, 2003.