OR-tools последовательно возвращает очень неоптимальное решение TSP

Question

Производя некоторые случайные гауссовские координаты, я заметил, что TSP-solver возвращает ужасные решения, однако он снова и снова возвращает одно и то же ужасное решение снова и снова для одного и того же входа.

Учитывая этот код:

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') 

К примеру, за 10 очков я получаю хорошее решение:

За 20 Это хуже, некоторые очевидные оптимизации все еще существуют (где один только необходимо будет заменить две точки.

И 200 это ужасно:

мне интересно, действительно ли код выше на самом деле некоторые LNS или просто возвращаю начальное значение, тем более, что большинство first_solution_strategy вариантов предполагают детерминированные инициализации.

Почему TSP-решатель выше возвращает согласованные решения для одних и тех же данных, несмотря на то, что табу-поиск и имитационный отжиг и такие являются стохастическими. И почему решение с 200 точками так плохо?

Я играл с несколькими опциями в SearchParameters, особенно с использованием полей «use _...» в local_search_operators. Это не повлияло, были возвращены те же самые очень оптимальные решения.

Answer 1

Я думаю, что проблема заключается в дистанционном измерении :). Я могу вспомнить kScalingFactor в C-образных образцах от или-tools, которые использовались для масштабирования расстояний, а затем округлять (путем их литья) до целых чисел: или-tools ожидает, что расстояния будут целыми числами.

Курс, конечно, расстояния между стандартными гауссовскими случайными координатами обычно лежат между 0 и, возможно, 2, поэтому большинство пар точек имеют одинаковые расстояния при сопоставлении целых чисел: мусор, мусор.

Я установил его простое умножение и литье до целых чисел (просто чтобы быть уверенный SWIG не переводчик поплавков в виде целых чисел):

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

Тогда результаты делают гораздо больше смысла:

10 баллов:

20 баллов:

200 баллов: