3

I'm totally new to QGIS but I really like it and would like to solve something more elaborated. I found a lot of threads and tutorials about how to solve the traveling salesman problem with QGIS but my 'problem' is a bit different.

I don't want to set a start and endpoint (at least no endpoint) but have multiple polygons and the goals is to 'visit' all of them. In fact the polygons are the districts of a city and I want to know which path to take to visit all of them while taking the shortest route. I also have a shapefile with the streets of course.

Maybe there are already solutions for this out there and I just didn't use the right wording in my search queries.

  • Can the polygons (districts) be represented by points, e.g. by their centroids? – Mesa Mar 18 '18 at 10:14
  • @Mesa Unfortunately not. Sometimes it may be best to just 'take one step' into a polygon and leave it again or walk along the border. – obs Mar 18 '18 at 10:36
  • One approach would be to create the intersections between the districts' borders and the road network and use these points as possible destinations. After this, you can formulate your problem as a special case of TSP: not all destinations must be visited, but at least one of each group (=one at each district). So to speak "traveling salesman with optional/alternative destinations". I guess this goes far beyond QGIS' (limited) abilities for network analyses. – Mesa Mar 18 '18 at 11:14
  • @Mesa yes, this approach seems reasonable. Do you have any idea what other software would be capable of doing this? ArcGIS maybe? – obs Mar 18 '18 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.