Questions tagged [travelling-salesman]

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
50 views

Unreachable Nodes in Grass GIS Travelling Salesman Routine

I am writing a Grass routine to find the best route using our road network to a series of points. These points are based on property polygons but I have used SQL to get nearest the point on the ...
user avatar
  • 73
2 votes
0 answers
106 views

Drawing the most efficient path between multiple points

I am trying to find the most efficient path between multiple points on a map. A bit of background to help understand what I need. I am making a printed map that has LEDs poked through from behind and ...
user avatar
  • 53
0 votes
0 answers
26 views

Drawing equal paths from geographic points?

I have 10'000 geographic points (POS), 10 salesmen, and one starting point. To avoid discrimination between salesmen, everyone should travel the same distance and the same number of points of sale. ...
user avatar
  • 101
4 votes
1 answer
895 views

Creating map of travelling salesperson problem solution with pgrouting?

I have created the "ways" (=edges) and "ways_vertices_pgr" (=nodes) tables from OSM road data with osm2pgrouting in PostGIS. I work with this data in QGIS. Given a set of ids from the "...
user avatar
  • 560
1 vote
0 answers
168 views

Optimizing polygon ordering

Does anyone know of any GIS tool that reorders polygons so that the path through all polygons is minimized, i.e. it solves the travelling salesman problem? Here's an example of just how poorly ...
user avatar
3 votes
0 answers
1k views

Travelling Salesman in QGIS using GRASS

I would like to use the travelling salesman algorithm in the GRASS plugin in QGIS. I have a points layer (3 points) and a road layer. I have connected the 2 together using v.net and I am given this: ...
user avatar
2 votes
0 answers
140 views

traveling salesman without u-turn v.net.salesman grass

I want to compute a traveling salesman path with GRASS GIS 7.2.1 which avoids u-turns. I made a network with v.net connect. I made a turntable using this network. I updated layer 3 of the turntable ...
user avatar
1 vote
2 answers
688 views

pgrouting tsp (travelling salesman problem) performance

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 ...
user avatar
  • 291
1 vote
1 answer
228 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 ...
user avatar
  • 113
4 votes
1 answer
522 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, ...
user avatar
  • 1,130
1 vote
1 answer
356 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 ...
user avatar
  • 5,541
0 votes
2 answers
558 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 ...
user avatar
0 votes
1 answer
351 views

Using osm2po to solve Travelling Salesman Problem [closed]

I've got a Travelling Salesman Problem (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 ...
user avatar
  • 1,068
1 vote
1 answer
2k 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 problem),...
user avatar
  • 1,033
1 vote
1 answer
805 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 ...
user avatar
2 votes
1 answer
599 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 ...
user avatar
  • 1,504
1 vote
1 answer
200 views

Math related sum distance problem with TSP content

I hava an interesting problem related with GIS / MATH / TSP. If I calculate the distance between A and B on a x/y-style coordinate system it is obvious to use the following formula: sqrt((Ax-Bx)^2+(...
user avatar
  • 1,447