Given a region in a city, I'd like to make a list of all the street addresses it contains in an order which is reasonably efficient for a person to traverse on foot. Ideally, I'd like the solution to use free software. An optimized set of lists for multiple people to traverse simultaneously would be even better. Does this already exist?


This is the travelling salesman problem, although I'm not sure that you care about returning to the same place as you began. The TSP is NP-Hard: for even a small number of destinations to be visited, there is an incredibly large number of possibilities for an algorithm to consider before it can tell you what the optimal path is. I haven't tried with every street address in a city, but I imagine it would take a long time to come to something resembling a good answer. I would reduce the number of possible solutions by reducing your destinations to street segments, rather than addresses.

A free and open source implementation exists in pgRouting: pgr_tsp

Unfortunately I'm not sure about the multiple people aspect, but if you have districts or obvious geographic barriers that are hard to pass on foot (e.g. a train line or a motorway), then you could try get one solution per 'district'. This has the additional benefit of reducing the solution space further (this may not be a benefit if accuracy is more important than having a fast algorithm).

  • Definitely better to cut down to smaller 'zones' and then you can run multiple at a time. Networking in Esri can be a benefit as a lot of the maths are already pre-done but still there's a lot of possibilities, halving the active area will speed it up by much more than double, halving that again by more than 4 times. When I did a similar problem as a one-off for charity collection I broke the canvassing area into 64 units and then it took only a few minutes per collection area (walker), then further refined where the traversed distance was more than a person could walk in a day. – Michael Stimson Jul 20 '15 at 4:50
  • 1
    Actually this is the harder Chinese Postman Problem - en.wikipedia.org/wiki/Route_inspection_problem – Ian Turton Jul 20 '15 at 8:28
  • Ah, thanks, I thought it didn't seem to fit the bill of the TSP exactly. Do you know if there's any implementation of it in open source (GIS) software? – alphabetasoup Jul 20 '15 at 8:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.