Search code examples
c++google-mapsnpor-tools

What approximate TSP algorithm does Google OR-Tools use?

I came across Google OR-Tools which computes the TSP with reasonable approximations as discussed in this link. I am curious to know what specfic algorithm this tool uses for TSP. Does it have any specific optimizations (to the code) that make it perform well? (There are several approximate algorithms for the TSP, I am just curious to know if it uses a mix of multiple algorithms or which specific algorithm it uses).

Solution

  • See comment here:

    https://github.com/google/or-tools/issues/920#issuecomment-435880431

    it links to:

    https://www.researchgate.net/publication/226021015_A_Constraint_Programming_Toolkit_for_Local_Search

    which is a good starting point to understand the technology used.