9
$\begingroup$

I am working on a political campaign where dozens of volunteers will be conducting door-knocking promotions over the next few weeks. Given a list with names, addresses and long/lat coordinates, what algorithms can be used to create an optimized walk list.

$\endgroup$
  • 3
    $\begingroup$ Cross posting seems in poor form. Why is this tagged SQL? $\endgroup$ – Air Jun 26 '14 at 15:34
  • $\begingroup$ Solve the (approximate) travelling salesman problem (TSP)... $\endgroup$ – Debasis Jun 26 '14 at 16:08
  • $\begingroup$ Beyond lat-long, what's the geography like? A gridded city? An almost tree-shaped suburb with smaller roads into cul-de-sacs? Has a MASSIVE influence. $\endgroup$ – Spacedman Jul 1 '14 at 13:24
6
$\begingroup$

As Steve Kallestad has said, this is a TSP problem, and there are wonderful free solvers to find approximate solutions.

It may be too much work for what you are looking for, but you may try use one of those solvers in combination with the Google Maps API, to find real walking distances beetwen your coordinates: https://developers.google.com/maps/documentation/directions/#DirectionsRequests

(I have never used this API, so I don't know how easy or effective it would be)

$\endgroup$
4
$\begingroup$

People see something closely related to the Travelling Salesman Problem and think that it can't be solved.

A good deal of work has been done on this topic and not all of it indicates that a solution is not available. Depending on the parameters and the desired solution, you may be able to find something that will work.

You may want to give a look at the OpenOpt python library.

Another resource to look at would be the TSP Solver and Generator.

If you are using R, there is a TSP package available.

Actually implementing a solution to your problem is a little too much to cover here, but this should provide a good starting point. Within these packages and at the documentation within the links that I provided for you, you will find that there are a fairly wide variety of algorithmic strategies available. You have a small geographic region and a small set of "salespeople", so the computational power needed to calculate a strategy within a reasonable time frame should be available on your desktop.

In practical terms, you don't need to find the absolutely most optimal strategy. You just need a very good one. Pick a TSP package that looks the least overwhelming and give it a go.

$\endgroup$
  • $\begingroup$ I agree with Steve K that the key to tackling this is to aim for approximately optimal or just good route strategies. Many times the difference between "best" and "good enough" isn't much. $\endgroup$ – MrMeritology Jun 30 '14 at 3:55
  • $\begingroup$ Of course the optimum can be found, it might just take longer than the age of the universe to iterate over all the possibilities. Your answer fails to mention this. $\endgroup$ – Spacedman Jul 1 '14 at 13:23
2
$\begingroup$

As @SpacedMan has noted in a comment, the street layout will have a massive influence on the optimization of the walk list. You have included only "latitude and longitude" in your question's title; but solving that problem does not lead to a "walk list", but to a "as-the-crow-flies list".

Looking at your street layout as a graph, with edge weights describing distances, and trying to find the shortest traversal between all required addresses, will lead you to think of your problem as a "Shortest path problem". Dijkstra's algorithm is the best known solution (there are others); in its naive implementation it converges in O(n2), which may be acceptable if your lists of addresses are moderate in size. Otherwise, look for optimized versions in the above links.

As for libraries and resources to start tackling the problem, since you do not specify languages or platforms, let me point to the compilation of routing solvers in the Open Street Maps wiki and in general their frameworks and libraries page.

$\endgroup$
1
$\begingroup$

Here's a crazy idea: talk to the volunteers who know the neighborhoods and who have done door-to-door work before. Get their advice and ideas. They will probably have insights that no algorithm will produce, and those modifications will be valuable to any computer-generated route list. One example: Avoiding crossing heavily traveled streets with slow lights or no lights. Another example: pairs of volunteers working on opposite sides of the same street will feel safer than a volunteer working that street alone.

$\endgroup$

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.