How can I get a good route for many way-points?

I need an app that can search for me all the various places for different keywords like "beauty salon" and "web design" (the keywords are chosen by the user) in a specific region (e.g. my city) and then give me an optimum route for the "beauty salon" ∪ "web design" places in function of accessibility (the app has to know the public transport routes).

Is there any app that can do this for Android? It would spare me from making a lot of calculations. There are around 700 places in my city. Imagine doing an optimum route for all of them. If there isn't, then I got you a very good idea, for a possibly viral app.

I can't start making such an app, because I don't have time. I have to sell. That's it. So, there must be another solution. Did someone got into the same situation as mine?

PS: It's not like I don't know HOW to do it, it's the fact that I don't have time.

Programmatically you can do it by following a backtracking model. For every optimum route calculated, the app shall send the data to a server so the next time you won't be obliged to recalculate. For the server, you'll use a a search engine, so everyone can access a previous route. Afterwards, you can gradually implement stop lights, traffic. Gradually because you don't want to overstress the CPU at first.

• The problem you describe is known as the "Travelling Salesman Problem (TSP)" in computer science. Unluckily for you, this problem is NP-hard, which basically means that there is no algorithm known to solve it without trying all possible solutions and since the solutions space get's exponential bigger with every place you add, there are many solutions. To sum app: Even if there is an app that would calculate a route it either wouldn't be the optimal route or it would take extremely long to calculate it.
– Flow
Feb 1, 2014 at 13:31
• If you edit your question so that it has a meaningful title and doesn't ask for an app, but instead describes the problem you trying to solve (e.g. "How can I get a good route for many waypoints?"), then this question will be eligible for re-opening.
– Flow
Feb 1, 2014 at 13:33
• Is it good now? By the way, there is always a compromise between quality and speed. Feb 1, 2014 at 14:11
• Huh, I just had a good thought: what if you use neural networks? This can give a speed bump. But that's implementation, therefore I'm dreaming. Feb 1, 2014 at 14:14