I'm very new to Python and try to use Google's Optimization (or-)tools for solving the Travelling Salesman Problem (TSP):
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.
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?