How to input data in Google or-tools's TSP (Travelling Salesman Prob..)?

Question

I'm very new to Python and try to use Google's Optimization (or-)tools for solving the Travelling Salesman Problem (TSP):

https://github.com/google/or-tools/blob/1b98e19ec2b202e253d605cae2cf664abb4ae2e6/examples/python/tsp.py

I can run it and get a nice output for the random input numbers of the example, but I cannot find any way on how to input data myself. All I want to do is input a file/list with x/y coordinates. On the site

https://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/tsp/tsp.html

they show how the input file should/can look like, but how do I implement and run that with the tsp.py file? It seems that, in the example, a random input is created through

class RandomMatrix(object): """Random matrix."""

def init(self, size): """Initialize random matrix."""

rand = random.Random()
rand.seed(FLAGS.tsp_random_seed)
distance_max = 100
self.matrix = {}
for from_node in xrange(size):
  self.matrix[from_node] = {}
  for to_node in xrange(size):
    if from_node == to_node:
      self.matrix[from_node][to_node] = 0
    else:
      self.matrix[from_node][to_node] = rand.randrange(distance_max)

def Distance(self, from_node, to_node): return self.matrix[from_node][to_node]

Unfortunately, I don't even understand in what format it is created, which would be the first step to create an input myself. Later on in the code, the previously created input is used as:

matrix = RandomMatrix(FLAGS.tsp_size)
matrix_callback = matrix.Distance
if FLAGS.tsp_use_random_matrix:
  routing.SetArcCostEvaluatorOfAllVehicles(matrix_callback)
else:
  routing.SetArcCostEvaluatorOfAllVehicles(Distance)

I assume that this part distinguishes between a random input (which is the standard case) and a manual input, which is what I need.

Answer 1

It seems that Matrix is a "2-D array" that is indexed by its from_node and to_node. The nodes are numbered 0,1,..., up to number of nodes - 1.

What is stored in the matrix is the pair-wise distance between the nodes. For example, if you have three nodes, then you can set your matrix be something like: [ [0, 3, 5], [3, 0, 7], [5, 7, 0] ], which represents a "triangle" map with edge lengths 3, 5, and 7.

Does this make sense to you?