user56574 - 1 month ago 14x

Python 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`

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

definit(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

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?

Source (Stackoverflow)

Comments