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
1 vote
0 answers
17 views

Calculate isochrones in R within a personal network

I just need to calculate the isochrones in R from an starting point within a personal network. This network is a sf linestring with an id attribute and a speed value. There are not any other ...
user avatar
3 votes
1 answer
266 views

Building the shortest route through all points in QGIS

How to build the shortest route through all selected points, starting from a given point? Which plugin to use? There is a point layer and a linear layer for all routes between points.
user avatar
  • 39
0 votes
0 answers
19 views

QGIS v.net.salesman generates error when restricted to selected features

I'm using the GRASS v.net.salesman in QGIS to find the shortest route between some American colleges on the road network. The network layer comes from Natural Earth Data, specifically ...
user avatar
1 vote
0 answers
43 views

Traveling salesperson in PyQGIS

I actually found several related questions but it seems my specific needs are not answered. I have a set of polygons that I need to hit all of them with some path (no roads, just as the crow flies). ...
user avatar
  • 362
0 votes
0 answers
58 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
  • 83
2 votes
0 answers
132 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
29 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
960 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
177 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 problem 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
145 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
692 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
3 votes
1 answer
1k views

Creating input node file for v.net.salesman in GRASS

I have imported the line vector layer and point vector layer (12 points) to GRASS using v.in.ogr. Now I want to use v.in.salesman to find the shortest path between these 12 points, but I couldn't ...
user avatar
1 vote
1 answer
233 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
524 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,140
1 vote
1 answer
363 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
568 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
356 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
806 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
605 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
201 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