1

I currently use a web API to solve TSP tasks. However my provider limits the query to a maximum of 150 stops. I therefore consider to host my own routing service based on OSM data and pgrouting. My top priority is performance and I was wondering if anybody has experience with the performance of the pgr_tsp function? I don't care about exact stats or system specs. All I want is a ballpark figure in order to see if pgrouting is an option at all.

E.g. Can I calculate TSP for 1000+ stops and is this a matter of seconds or hours?

Improve this question
9
  • To give you an idea (not pgrouting based but our RW Net 4 software): With 1000 stops we recommend appr. 50 sec of calculation to get a decent solution. With multiple threads or if you accept a not so good solution, it can be faster. In any case you will also need a cost-matrix between the 1000 stops and here calculation time depend a lot upon distance between stops and level of details in the network. – Uffe Kousgaard Jan 30 '16 at 9:51
  • @UffeKousgaard Thanks for the reply. Calculating the actual network distance matrix for 1000 stops (i.e. ~1.000.000 routes), seems impractical. I read that using euclidean distance is often sufficient to get a near optimal solution. How do you get your distance matrix? Do you actually calculate all shortest paths? – Chris Jan 30 '16 at 10:15
  • Yes, using euclidean distance is a joke IMHO, if you are going to use the result for anything serious. Calculations are done as 1000 one-to-many, rather than 1,000,000 one-to-one. – Uffe Kousgaard Jan 30 '16 at 10:43
  • Real cities has oneway streets, rivers, railways and many other obstacles, which prevent straight lines when moving from one stop to another. – Uffe Kousgaard Jan 30 '16 at 10:50
  • @UffeKousgaard Yes, I read that in the postgreSQL pgrouting docs and that's how they implemented their tsp algorithms default behaviour. However, I also realized that it does not really work for small areas. I.e. stops are distributed on a street level rather than spread across multiple cities. The euclidean only seems to work well for long distance TSP. I assume this is because the street network becomes sufficiently dense when you zoom out and the euclidean distance converges with the actual driving distance. – Chris Jan 30 '16 at 10:59
1

Complementing, previous answer.. montevideo-release-v4 is the latest branch. There is a lot of clean up that needs to be done as everything we coded is still there even if its not used.

Improve this answer
0

The authors of "Fast data-oriented microaggregation algorithm for large numerical datasets" [1] proposed a TSP solution for millions of cities in Euclidean space. Their solution is fast enough for your application and is based on Clark-Wright heuristic.

[1] http://www.sciencedirect.com/science/article/pii/S0950705114001956

Improve this answer

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.