ORツールは一貫して非常に最適な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の場合

を、いくつかの明白な最適化がまだ存在している（ここで、1のみ2点を交換する必要があります。

そして200のためにそれは恐ろしいです：

私は上記のコードは、実際にいくつかのLNSをし、または単に最もfirst_solution_strategyオプションは決定論的な初期化を提案し、特に以来、初期値を返すかどうか迷っています。

上記のTSPソルバは、タブーサーチやシミュレーテッドアニーリングなどが確率的であっても、同じデータに対して常に一貫した解を返します。そして、なぜ200ポイントのソリューションが悪いのですか？

SearchParametersでいくつかのオプションを使用しました。特に、local_search_operatorsの 'use _...'フィールドを有効にしました。これは効果がなく、同じ非常に最適ではない解が返されました。

Answer 1

私は問題が距離測定であると思う:)。距離をスケールアップし、整数にキャスト（丸め）するために使用されたor-toolsのCコードサンプルのkScalingFactorを思い出すことができます：or-toolsは、距離が整数であると予測します。

もちろん、標準的なガウスランダム座標間の距離は、通常、0〜多分2の間にあるため、整数にマッピングするとほとんどのポイントペアは同じ距離になります。

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

は、その後の結果は多くの意味をなす：

が、私は単純に乗算し、整数にキャストして、それを固定（念のSWIGは整数として浮動小数点数をインタプリタはありませんされるように）

10点：

20点：

個の

200ポイント：