Travelling salesperson in pgRouting without starting point

I'm a beginner with PostGIS and it's the first time I try pgRouting.

I work for a regional transit agency and I'm trying to develop a mean to evaluate the easiness or difficulty to offer a bus service for the population of a certain area.

"Traditionally", classic dispersion statistics where used, like the average nearest neighbor. In theory, it would be easier to offer a good service to a more dense population. But in reality, the road network have a great deal of importance. You can have a quite dense population, but on each side of a river or train track and if the nearest crossing is miles away, you will need to travel a lot longer to be able to pick up the maximum of persons.

We call it the "Pacman index" :) On the left, the theoric bus would pick up 6.7 persons/km. On the right, 5.3 p/km. The two populations have a average nearest neighbor of 1 km.

Once we have the results, we'll compare them to our knowledge of the area and the service already offered (and see if a relatively "easy" area have many buses or if someone, somewhere is doing wonders to serve a difficult area). That's our theory and now we'd like to test it.

I have a set of locations (every intersection within a city that could be a bus stop) and I am trying to find the shortest path between them. Looks like a classic TSP problem.

My problem is that I really don't care about the starting point and it can pass twice on the same path too, as long as the result is the shortest path to "pass by" all locations.

Network Analyst can do it, but it takes forever (my test dataset only have 2 dozen points, but my final one will have 1000+).

With pgRouting, I have to assign a starting point and an end point (if I don't specify an end point, it's doing a loop and I don't want that.

From the documentation, I've found this

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

It there a way to do this with pgRouting?

Any help would be appreciated.

1 Answer

This is know as TSPM, ie TSP with multiple visits. We currently do not support this directly in pgRouting 2.0, but I have seen some pages that discuss converting generalized TSP (GTSP) problems into symmetric TSP problems that are supported in pgRouting. You can read more about TSPM with:

https://www.google.com/#q=tspm+"multiple+visits"

• You mean that even with the sample data from pgRouting website (docs.pgrouting.org/dev/doc/src/developer/sampledata.html), it would be impossible to do a TSP analysis because it would be impossible to do it without passing twice at the same place (you can't reach point 1 and 13, starting from 5, without passing at least twice by edges 1 and 14 and vertex 2 and 10)? Commented Aug 2, 2013 at 17:30
• This is just normal TSP, the fact that a route between A and B passes through C, doesn't change it. Commented Aug 2, 2013 at 19:13
• The sample data network is not used for the TSP examples. We just solve a distance matrix which oblivious to the underlying network. Once you have optimized the order of the nodes, then you can extra the routes between them and those routes may retrace certain paths. If you think of two triangles that connect at a vertex like the symbol '8' and there is a city at that vertex, and it is a gateway between the upper and lower cities, we can not solve this case with the current solver. To solve this case we need to support TSPM and I plan to look into that for a future release. Commented Aug 3, 2013 at 18:36