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.
27
questions
1
vote
0
answers
35
views
Discrepancy in Routing Results Between pgr_TSP Versions (3.1.2 vs. 3.2.1) [closed]
I've been working with the pgr_TSP function in the pgrouting library, and I noticed a change in its behavior between versions 3.1.2 and 3.2.1. Specifically, it seems that in 3.2.1, the algorithm was ...
- 93
0
votes
0
answers
45
views
Turn point data into line while keeping order in ArcGIS Pro
I have a point dataset (ArcGIS Pro) with around 700 points (Some points are in the same place), and I need to do a route that starts at any point and goes thru all the points, without going back to ...
- 1
2
votes
2
answers
211
views
Why Travelling Salesman Problem plugin is not working in QGIS 3?
I would like to use the TSP plugin in QGIS. In my current version of QGIS 3.30, it shows an error saying that this plugin was developed for versions 2.14 - 2.99. I tried several versions (e.g., 2.14, ...
- 21
2
votes
0
answers
60
views
Calling pgr_TSP() function from existing cost matrix table
I am trying to call pgr_TSP() function like below using my existing table which has source_id, target_id and cost details but I am not able to get the result?
What should be the syntax for same?
...
- 93
3
votes
0
answers
204
views
Travelling salesman but doesn’t have to be most efficient route just trace the roads. (Python and QGIS)
I’ve got a project; for one part of this project I intend to draw a route over a shapefile, it contains 9000 nodes.
What I’ve tried:
Generating routes on a map layer in QGIS by following the lines of ...
- 59
1
vote
1
answer
69
views
how to find Shortest line for a bunch of points(Hamiltonian path) using pgrouting v3.3
it looks like tsp problem. but just as this link describes, I don't want to go back after visiting the last node, so using pgr_tsp returns the wrong answer for me. does pgrouting have any function to ...
- 11
2
votes
3
answers
292
views
V.NET.SALESMAN problem filling in dialog box parameters
I have a problem with the process of the algorithm "V.NET.SALESMAN" that surely is simple but I can't do it. I have read Grass’ documentation and similar posts here in Stack Exchange but in ...
- 85
1
vote
0
answers
109
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 ...
- 3,429
7
votes
1
answer
1k
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.
- 79
1
vote
0
answers
239
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 ...
- 4,605
2
votes
0
answers
315
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 ...
- 53
0
votes
0
answers
40
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.
...
- 101
4
votes
1
answer
1k
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 "...
- 560
1
vote
0
answers
212
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 ...
3
votes
0
answers
2k
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:
...
2
votes
0
answers
161
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 ...
- 21
1
vote
2
answers
787
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 ...
- 291
4
votes
2
answers
2k
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 ...
1
vote
1
answer
246
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 ...
- 113
4
votes
1
answer
544
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,148
1
vote
1
answer
427
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 ...
- 5,601
0
votes
2
answers
607
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
1
answer
414
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 ...
- 1,118
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),...
- 1,063
1
vote
1
answer
834
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 ...
- 113
2
votes
1
answer
636
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 ...
- 1,524
1
vote
1
answer
207
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+(...
- 1,473