Skip to main content

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
36 views

V.Net.Salesman Unreachable Nodes at Intersections

I'm designing a network that has a layer of locations and a layer of street segments. I need to design a route to connect these locations along the street segments using the shortest route possible. ...
Michael Dinh's user avatar
0 votes
0 answers
39 views

Nearest Neighbour on route vs Shortest Path

I have a line layer “Cables” which represents my network, and this is formatted correctly so all lines are in the correct direction. I have a node layer “nodes” that sit directly on top of the lines. ...
30136353's user avatar
-1 votes
1 answer
85 views

Route design for Travelling Salesperson [closed]

I need a GIS-based solution that helps to identify the sales route of a salesperson. In a given situation, I have 500k POS/point of sales throughout the country. To server those 500k POS there are 100 ...
Devils Dream's user avatar
  • 3,189
0 votes
0 answers
144 views

QGIS: ORS Tools giving consistent error when trying to change "Traveling Salesman [optional]" to anything except blank

I am having trouble with the ORS Tools plugin. In regards to the errors themselves, they are as follows: Traceback (most recent call last): File "/Users/User/Library/Application Support/QGIS/...
CarloseNew's user avatar
0 votes
0 answers
104 views

Traveling salesman problem with start node and end node

I am having some trouble with finding an easy way to find the most optimum (shortest) route between four or so points without returning to the original one while following the path shown (red lines). ...
CarloseNew's user avatar
1 vote
0 answers
41 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 ...
postgis-user's user avatar
0 votes
0 answers
51 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 ...
Daniel's user avatar
  • 1
2 votes
2 answers
466 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, ...
BA247's user avatar
  • 21
2 votes
0 answers
70 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? ...
postgis-user's user avatar
3 votes
0 answers
243 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 ...
IceBear123's user avatar
1 vote
1 answer
76 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 ...
c ran's user avatar
  • 11
2 votes
3 answers
480 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 ...
ANDY AGUIRRE's user avatar
1 vote
0 answers
131 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 ...
César Arquero Cabral's user avatar
8 votes
2 answers
2k 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.
Wawr's user avatar
  • 89
1 vote
0 answers
312 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 ...
Lee Hachadoorian's user avatar
2 votes
0 answers
392 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 ...
Matt's user avatar
  • 53
0 votes
0 answers
41 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. ...
Nizar's user avatar
  • 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 "...
lueho's user avatar
  • 580
1 vote
0 answers
216 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 ...
Michael Peters's user avatar
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: ...
Roxanne Lloyd's user avatar
2 votes
0 answers
183 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 ...
jonathan's user avatar
1 vote
2 answers
827 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 ...
Chris's user avatar
  • 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 ...
Hariharan Murali's user avatar
1 vote
1 answer
249 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 ...
gilito's user avatar
  • 113
4 votes
1 answer
551 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, ...
Zia's user avatar
  • 1,158
1 vote
1 answer
493 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 ...
SS_Rebelious's user avatar
  • 5,621
0 votes
2 answers
614 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 ...
René Fournier's user avatar
0 votes
1 answer
435 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 ...
hoge6b01's user avatar
  • 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),...
Pablo Pardo's user avatar
  • 1,073
1 vote
1 answer
855 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 ...
rocknrollnerd's user avatar
2 votes
1 answer
645 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 ...
fgcarto's user avatar
  • 1,524
1 vote
1 answer
208 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+(...
Styp's user avatar
  • 1,473