1

I have no problems using Dijkstra or A* functions, but when I try to run TSP, I really don't know where to start.

What I'm, trying is to get the 'best route' to link four points (typical TSP problem), but I do not know how to implement this. According the documentation:

SELECT seq, id1, id2, round(cost::numeric, 2) AS cost
FROM pgr_tsp('SELECT id, x, y FROM vertex_table ORDER BY id', 6, 5);

My questions are:

  1. What means "cost::numeric" and specially "::"? I have seen it before, but still don't know what it is.
  2. Should I have another table with the points with x and y fields? Because if tsp refers to a "vertex table" that I supose will be the point table, where is the edge table (e.g streets) that I queried with Dijkstra?
  3. And what means that 5 and 6?

Sorry if this a strange question, but I'm trying to run this function but I can't do it, and I don't find any documentation but the official docs, (that I don't understand).

3

With pgRouting 2.0 there are two different TSP functions, see: http://docs.pgrouting.org/2.0/en/src/tsp/doc/index.html#pgr-tsp

The first one has as first argument a SQL statement (that's the one you are using), the second one requires a distance matrix.

The advantage of the distance matrix is, that it's up to you, how exact you want to calculate the distances. The first function only calculates the euclidean distances.

So in your case you select first all points you want to visit as the first argument, where you must know for each point its id and coordinates: SELECT id, x, y FROM vertex_table.

The second argument is the start point ID, which must be also part of your "SELECT" before, and the third argument is optional. It's the ID of the last point to visit.

So in your example you first select all points with id, x and y attributes (must also return ID 5 and 6), the first point to visit must be ID 5 and the last point to visit is point 6.

cost::numeric that you cast the cost attribute to be of type numeric.

| improve this answer | |
  • Ok I understand, but then, what would be the best way to query for a route according a streets table? Would it be this the distance matrix? – Pablo Pardo Dec 22 '13 at 15:50
  • What is best depends on your needs: if you think that Euclidean is sufficient or if computing a distance matrix takes too much time, then it's better to use the first function. – dkastl Dec 22 '13 at 16:59
  • Maybe i'm not expressing well. What I would want to know is how could I obtain the route, not for the euclidean distance, but for the distance accross a street layer. Should I get a distance matrix for this aim? Thanks again, and sorry for my ignorance. – Pablo Pardo Dec 22 '13 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.