A general question about routing problem: I am working on waste collection problems and I am having some trouble with some routing problems (the truck has to pass by every bin). So far I have tried a few things:

• GRASS traveling Salesman solver (in QGIS and GRASS directly)

• GVSig traveling salesman but not with better results.

• GrassHopper (https://www.graphhopper.com/)

TSP in GRASS seems to work fine is you have few points and relatively large distances between points. But because I have a large (100-300 points in close proximity) the path created is not realistic, mostly due to U-Turn problems (the shortest path between 3 points might include the equivalent of U-Turn in the middle of the street which on in reality is not possible). Did anybody solve this kind of problem, preferably with opensource tools (I know that ArcGIS have this kind of capabilities and I am trying to see if I can get there with it, but I generally prefer opensource)

Since these results are not optimum I end up using the graph road plugin (by the way is there a way to export a newly created path to an already existing file to create a full route, like it is possible in road graph with the network tools in QGIS 3?) but it is really time consuming.

  • graphhopper is by far the most capable option in your list; how did that work out? I'd suggest OSRM; the 'continue_straight_at_waypoints' option should fullfill your requirement. it uses complex tag based profiles, though, and is tailored (but not limited to) OSM data. note that the TSP is one of the big bad boys of computing problems (NP hard), and no implementation is meant for handling hundreds of points; the returned soluton has a way less chance of being close to optimal... – ThingumaBob Sep 7 at 18:02
  • I think you may be better off with a Chinese Postman solution rather than a Travelling Sales Person, I don't know if any of the above have algorithms for it though, – Ian Turton Sep 8 at 9:39

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.