Given a list of cities and the distances between each pair of cities, finds shortest possible route that visits each city exactly once and returns to the origin city.

learn more… | top users | synonyms (1)

0
votes
0answers
20 views

From Yunnan to Tibet? [migrated]

We want to travel in from Hong Kong through south China into Tibet. We are hoping to go through Guangdong to Guangxi, Yunnan or Guizhou to Sichuan to Tibet. But we are struggling to find a tour ...
0
votes
0answers
8 views

Traversal Path through points [duplicate]

I need to develop an algorithm to plot a traversing path through few hundred location/points (geo-coded). I am looking into Dijkstra's algorithm but evaluating distance for every pair of points seems ...
1
vote
1answer
46 views

How to calculate the shortest path to pass on 7.000 UTM points?

Anyone can give me an advice how to calculate the shortest path with a lot of UTM points? In total I have 7000 points, but it can be grouping 100 or 500. I have knowledges about Java and Python for ...
1
vote
1answer
139 views

Solving “Traveling Purchaser Problem”

Till now, I was using PostGIS-pgrouting pgr_tsp function to solve Travelling Salesman Problems. This function can give us the best possible route depending upon the cost parameter when the starting, ...
1
vote
1answer
57 views

How to assess quality of the TSP algorithm?

I'm trying to develop my own algorithm for solving Travelling Salesman Problem (TSP) I tested it (in its current state) on the "att48" instance of the TSPLIB and got following results: As we can ...
0
votes
2answers
134 views

pgRouting pgr_tsp() not returning results when used with SQL parameter

I’m trying to solve the travelling salesman problem with locations pulled from a database, e.g.: mydb=# SELECT id::integer, location_lng::float AS x, location_lat::float AS y FROM addresses where ...
0
votes
1answer
133 views

How to use osm2po to solve TSP

I've got a TSP to solve. I created a routable street graph using osm2po and imported the result to PostGIS. On my PG db I installed the pgrouting extension (over PGAdmin3 GUI --> right click ...
1
vote
1answer
563 views

Can anyone explain me the TSP pgRouting function?

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 ...
1
vote
1answer
302 views

pgRouting TSP: is it possible to apply to the roads network?

I want to solve a TSP problem on a set of points from a road network (given N points, find the shortest possible route to visit them all). It seems that pgrouting pgr_tsp function doesn't take into ...
1
vote
1answer
275 views

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 ...