OR-tools consistently returns very sub-optimal TSP solution
<p>Generating some random Gaussian coordinates, I noticed the TSP-solver returns horrible solutions, however it also returns the same horrible solution over and over again for the same input.</p>

<p>Given this code:</p>

<pre><code>import numpy
import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

import matplotlib
%matplotlib inline
from matplotlib import pyplot, pylab
pylab.rcParams['figure.figsize'] = 20, 10


n_points = 200

orders = numpy.random.randn(n_points, 2)
coordinates = orders.tolist()

class Distance:
    def __init__(self, coords):
        self.coords = coords

    def distance(self, x, y):
        return math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2)

    def __call__(self, x, y):
        return self.distance(self.coords[x], self.coords[y])

distance = Distance(coordinates)

search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_ARC)

search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.TABU_SEARCH


routing = pywrapcp.RoutingModel(len(coordinates), 1)
routing.SetArcCostEvaluatorOfAllVehicles(distance)   

routing.SetDepot(0)
solver = routing.solver()
routing.CloseModel() # the documentation is a bit unclear on whether this is needed

assignment = routing.SolveWithParameters(search_parameters)

nodes = []
index = routing.Start(0)
while not routing.IsEnd(index):
    nodes.append(routing.IndexToNode(index))
    index = assignment.Value(routing.NextVar(index))

nodes.append(0)
for (a, b) in zip(nodes, nodes[1:]):
    a, b = coordinates[a], coordinates[b]
    pyplot.plot([a[0], b[0]], [a[1], b[1]], 'r' )
</code></pre>

<p>For example, for 10 points I get a nice solution:</p>

<p><a href="http://i.stack.imgur.com/uvfj6.png" rel="nofollow"><img src="http://i.stack.imgur.com/uvfj6.png" alt="enter image description here"></a></p>

<p>For 20 It's worse, some obvious optimizations still exist (where one only would need to swap two points.</p>

<p><a href="http://i.stack.imgur.com/E1x6b.png" rel="nofollow"><img src="http://i.stack.imgur.com/E1x6b.png" alt="enter image description here"></a></p>

<p>And for 200 it's horrible:</p>

<p><a href="http://i.stack.imgur.com/Reu6h.png" rel="nofollow"><img src="http://i.stack.imgur.com/Reu6h.png" alt="enter image description here"></a></p>

<p>I'm wondering whether the code above actually does some LNS, or just returns the initial value, especially since most <code>first_solution_strategy</code> options suggest deterministic initialization.</p>

<p>Why does the TSP-solver above return consistent solutions for the same data, even though tabu-search and simulated annealing and such are stochastic. And, why is the 200-point solution so bad?</p>

<p>I played with several options in SearchParameters, especially enabling 'use_...' fields in <code>local_search_operators</code>. This had no effect, the same very sub-optimal solutions were returned.</p>

<p>I think the problem is with the distance-measure :). I can remember a <code>kScalingFactor</code> in the C-code samples from or-tools, which was used to scale up distances, and then round (by casting) them to integers: or-tools expects distances to be integers.</p>

<p>Or course, distances between standard Gaussian random coordinates typically lie between 0 and maybe 2, hence most point pairs have the same distances when mapped to integers: garbage in, garbage out.</p>

<p>I fixed it by simply multiplying and casting to integers (just to be sure swig won't interpreter the floats as integers):</p>



<pre class="lang-py prettyprint-override"><code># ...
def distance(self, x, y):
    return int(10000 * math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2))
# ...
</code></pre>

<p>Then the results make a lot more sense:</p>

<p>10 points:</p>

<p><a href="http://i.stack.imgur.com/9A41r.png" rel="nofollow"><img src="http://i.stack.imgur.com/9A41r.png" alt="10 points"></a></p>

<p>20 points:</p>

<p><a href="http://i.stack.imgur.com/fmm5m.png" rel="nofollow"><img src="http://i.stack.imgur.com/fmm5m.png" alt="20 points"></a></p>

<p>200 points:</p>

<p><a href="http://i.stack.imgur.com/43Ky3.png" rel="nofollow"><img src="http://i.stack.imgur.com/43Ky3.png" alt="200 points"></a></p>

python or-tools