Implement multi-fragment heuristics for the traveling salesman problem

Question

I would like to implement the multi-fragment heuristics algorithm for finding a solution to the traveling salesman problem.

The algorithm is described here as follows:

This seriation method re-organises the $D$ matrix by iteratively placing the smallest distances in matrix $D$ in the $n-1$ cells contiguous to the diagonal.

This is a greedy approach, with $n-1$ steps.

At each step, rows $i$ and columns $j$ in $D$ are moved so that the smallest distance is placed in a not yet allocated cell. The smallest distance is not chosen freely. It is constrained by the necessity to keep the already allocated cells in place.

...

This heuristic do not guarantee to find an optimal solution but give quickly a "reasonable good" solution. This solution could be improved by a local search heuristic.

According to the mentioned article, this algorithm was mentioned in a 1992 paper "Fast Algorithms for Geometric Traveling Salesman Problems" by "Bentley", but I couldn't find it on the internet. Moreover, there are almost no other information regarding this algorithm online, except from the usual definition like:

The multi fragment algorithm works as follows:

1. Consider a distance matrix (such as the type at the back of a road atlas of Britain), containing all the distances between all cities on the tour.

2. Find the shortest distance and link these two cities together.

3. Then, find the second shortest distance, and link these two cities.

4. Now, find the next smallest edge whose cities conform to the following criteria:

   1. Both must have an edge degree ratio <=1 (i.e. neither can already be linked to more than one other city)

   2. Adding an edge between the cities must not result in a closed tour, which does not already include all the cities on the tour.

5. Repeat until all cities end up being connected to two other cities.

I understood the algorithm according to this last article I'm linking to, but I'm not seeing the connection between this last description and the description above.

If the first description is correct, I'm actually not understanding it fully and how could I implement it in practice. For example, suppose we have this simple distance matrix $D$

$$D = \begin{pmatrix} 2& 1 &2 &3\\ 3 &2 &7 &2 \\ 3 &1 &1& 0\\6& 2& 5 &1\end{pmatrix}$$

In the first description, they mention the $n -1$ cells contiguous to the diagonal, but of course we have $2$ of this $n-1$ cells, one in the left triangular matrix (currently from the top to the bottom $3, 1, 5$) and one in the upper one ($1, 7, 0$). Is it ok to choose one arbitrarily?

Then they say:

At each step, rows $i$ and columns $j$ in $D$ are moved so that the smallest distance is placed in a not yet allocated cell. The smallest distance is not chosen freely. It is constrained by the necessity to keep the already allocated cells in place.

Of course if we move a row or a column in the matrix $D$ and if we number the nodes from $1..N$, then we need to rename the nodes according to the moves.

But actually I'm not fully understanding how these moves could proceed in practice? Any concrete example?

Furthermore, after these moves, what should we do?

I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm.

Answer 1

there are almost no other information regarding this algorithm online
[...]
I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm.

I invite you to read my paper "An Empirical Study of the Multi-fragment Tour Construction Algorithm for the Travelling Salesman Problem" appeared in the Proceedings of the 16th International Conference on Hybrid Intelligent Systems (HIS 2016) pp 278-287. DOI: 10.1007/978-3-319-52941-7_28.

You'll find a pseudo-code of the algorithm, which is similar to the "usual definition". It's explained with some examples of a small instance. The paper also presents briefly other tour construction methods and gives experimental results for the Multi-Fragment algorithm and a comparative study to show the effectiveness of this method.

If the first description is correct, I'm actually not understanding it fully and how could I implement it in practice.

It's correct but maybe a little bit hard to explain. The main idea is to move columns and rows following the criteria such that we can read the constructed tour from the $n−1$ cells contiguous to the diagonal {D[1][0],D[2][1],... D[n][n-1]}.

In the first description, they mention the n−1 cells contiguous to the diagonal, but of course we have 2 of this n−1 cells, one in the left triangular matrix (currently from the top to the bottom 3,1,5) and one in the upper one (1,7,0). Is it ok to choose one arbitrarily?

The distances matrix in the Traveling Salesman Problem (TSP) is symmetric $(D[i][j]=D[j][i])$, we may consider only the upper/lower triangular portion of the matrix $D$.
There is another variant of the TSP which is the Asymmetric TSP.