New heuristic for the traveling salesman problem

[alex-cornejo]

Issue
JGrapht contains implementations of some heuristic algorithms for the traveling salesman problem (TSP), like nearest-neighbor and nearest-insertion. However, there are many other heuristic algorithms that may be useful to include in JGrapht for the TSP. Such is the case of the furthest-insertion heuristic. This heuristic provides an approximation factor of log n and according to some references listed below, this one provides good practical results compared with other heuristics like nearest-insertion and cheapest-insertion.

Proposal
Currently, I am working on an academic research project as part of my postgraduate studies and I am using JGrapht. I am considering using the furthest-insertion algorithm, so I am working on an implementation of this heuristic and it would be nice to include it as part of the catalog of TSP heuristics in JGrapht.

I believe I can use some ideas of the heuristics algorithms for the TSP that are already implemented in JGrapht. What do you think about it?
For more details about the furthest-insertion and other heuristics please check the references.

References
W. J. Cook, In Pursuit of the Traveling Salesman. New Jersey: Princeton
University Press, 1 ed., 2012.

D. Rosenkrantz, R. Stearns, and P. II, \An analysis of several heuristics for the
traveling salesman problem," SIAM J. Comput., vol. 6, pp. 563{581, 09 1977.

[jkinable]

We welcome new code contributions :). Just a few pointers: an algorithmic contribution should be backed by a scientific paper/book, i.e. not a home-brew solution. Moreover, if we already have some algorithm for the particular problem, in this case TSP, it would be really helpful if you could show that the new code contribution improves upon the existing code, e.g. the new algorithm can be faster, or can be better in certain use cases. Note that the references you are referring to are quite old. This might not necessarily be bad, but we prefer to have state-of-the-art algorithms.

[alex-cornejo]

We welcome new code contributions :). Just a few pointers: an algorithmic contribution should be backed by a scientific paper/book, i.e. not a home-brew solution. Moreover, if we already have some algorithm for the particular problem, in this case TSP, it would be really helpful if you could show that the new code contribution improves upon the existing code, e.g. the new algorithm can be faster, or can be better in certain use cases. Note that the references you are referring to are quite old. This might not necessarily be bad, but we prefer to have state-of-the-art algorithms.

Thanks so much for the answer.
The farthest-insertion heuristic belongs to a category of insertion constructive heuristics and it was initially proposed in (Rosenkrantz et al,. 1977). So, it is not quite recent. Despite this, through experimentation the farthest-insertion heuristic has proven to work fine for the TSP compared with other heuristics like nearest-neighbor and nearest-insertion (both of them implemented in JGrapht). Besides, recent textbooks like (Skiena, 2020) refer to this algorithm as one of the best among the category of insertion heuristics.

I did a little bit of homework and compared the implementation of the farthest-insertion (FI) with other heuristics implemented in JGrapht for the TSP like:

1. nearest-neighbor (NN)
2. nearest-insertion (NI)
3. greedy-heuristic (GH)

I tried with a couple of instances of 1000 and 2000 vertices generated in a 2D Euclidean space with a uniform random distribution. Regarding running times, the FI was faster than NI and slower than NN and GH. Regarding the quality of solutions, FI computed better tours than the others.

References

Skiena, S.-S. (2020). The Algorithm Design Manual (3rd ed.). Springer International Publishing.

[alex-cornejo]

Update

Hi guys, I have been working on the implementation of the farthest-insertion heuristic for the jgrapht library.

In fact, by checking implementations of other algorithms implemented in jgrapht, I took some ideas and I think I was able to improve considerably the performance of the farthest-insertion algorithm.

I performed experimentation and comparison with other algorithms implemented in jgrapht for the TSP. I used a couple of instances of 1000 and 2000 vertices generated in a 2D Euclidean space with a uniform random distribution. The following table shows the results.

Instance with 1000 vertices.

algorithm	Fitness	Time (s)
farthest-insertion	127,792	0.12
nearest-neighbor	148,372	0.743
nearest-insertion	148,741	4.951
greedy-heuristic	132,830	0.33
christofides	130,193	0.587

Instance with 2000 vertices.

algorithm	Fitness	Time (s)
farthest-insertion	181,203	0.194
nearest-neighbor	200,054	4.326
nearest-insertion	214,150	27.056
greedy-heuristic	184,574	1.069
christofides	183,799	2.198

The fitness column shows the length of the tour found of each algorithm. We can see that, at least for these instances, the farthest-insertion outperforms the other algorithms in terms of quality solutions and running time.