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

Question

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

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

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, особенно включив поля "использовать _..." в local_search_operators, Это не имело никакого эффекта, те же самые неоптимальные решения были возвращены.

Answer 1

Я думаю, что проблема с мерой расстояния:). Я могу вспомнить kScalingFactor в примерах C-кода из or-tools, который использовался для увеличения расстояний, а затем округлил (путем приведения) их к целым числам: or-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 баллов: