Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
1answer
75 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 "...
1
vote
0answers
98 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 ...
0
votes
0answers
26 views

Doing travelling salesperson using polygons in ArcGIS Pro?

I have a layer of tessellating polygons and a layer with roads. I want to find what 5km path using the roads will cover the most polygons. I looked at using the travelling salesman approach but this ...
3
votes
0answers
332 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: ...
2
votes
0answers
68 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 ...
1
vote
2answers
487 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 ...
1
vote
1answer
174 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 ...
4
votes
1answer
445 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
233 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 see ...
0
votes
2answers
401 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
242 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 Extension-...
1
vote
1answer
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),...
1
vote
1answer
730 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 ...
2
votes
1answer
519 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 ...