# Shortest way between numerous POIs - "Travelling -Salesman problem"

Mathias Dittrich shared this idea ago
Gathering feedback

Is it possible to let Locus compute the shortest way between given POIs?

For example, if i go caching in the forest and want to visit 4 caches, I often don't know what is the shortest way between them. That's known as the travelling salesman problem: http://en.wikipedia.org/wiki/Travelling_salesman_problem

It would be great, if I could select a number of POIs ans Locus solve the problem, which way is the beste, and not only search for the way from one POI to the next.

I fear that this will not be possbile, because Locus is getting the route from an extern server?

Cheers

## Replies (5)

1

It's correct that Locus gets route from online services, anyway as I know, some services already offer solution on this complicated task, so it should be even easier.

Feel free to vote Locusers :).

1

But in Osmand it is possible since years to order the viapoints between the start and endpoint automaticly.(https://help.locusmap.eu/topic/not-able-to-set-a-shape-point-in-the-route-planner) I have found this thread because I had trouble with my shapepoints in the routeplanner. Before this thread I found threads how to change the order between via and shape points.

The best way would be now for the problem, export the points to osmand, sort them there and export them back to Locus.

1

Any solution in sight?

Will go on a hike tomorrow and have no idea, what's the best way :D

1

Good day Mathias,

unfortunately, this idea is currently not planned.

1

For geocaching along a road I use BestRoute Pro.. There is also a free version to tryout

1

"Traveling Salesman" is a NP-complete problem (for the optimal solution), i.e. shows an exponentially growing runtime re. number of points to visit. And with maps it is not the number of points to VISIT, but the number of way crossings (nodes in the graph) that count. Even in a forest this number can become huge. So, in general, this massive number crunching is not a feature for which a Smartphone is best equipped.

However, there are reasonable routing algorithms that deliver reasonable (not optimal) results. Even for Smartphones. BRouter is one example.

You may try to motivate https://github.com/abrensch/brouter to extend his current feature.

He already offers "via" points. But currently they are ordered, so you have to have the idea what is the best sequence, which is what you want resolved by an App.

For BRouter it would "only" need an additional checkbox called "optimize via order" (which is the trivial change on the UI) - and all the heavy lifting under the hood :-)

I have seen the author on a youtube video, and my gut tells he seems to be the right guy for such.

1

Erst ein mal auf Deutsch. Ich versuche gerade eine Fahrradreise in Wales zu planen. Deswegen habe ich Locus auf dem PC zum laufen gebracht. Ich will/muss ca. 50 Punkte verbinden und stehe vor einem ähnlichen Problem. Ich dachte zu erst mit dem Routenplanner von Locus müsse das sehr einfach sein. Gestern war ich so entnervt, sodass ich mal Osmand ausprobiert habe.

Entweder ist das neu oder ich habe diese Möglichkeit bisher noch nicht richtig ausgelotet. Ich konnte mir dir 50 Punkte sortieren lassen und danach die Reihenfolge verändern, wenn das Ergebnis nicht passt.

Jetzt aber die Abers:

1. Du musst die Punkte händisch in die Route eingeben. Also auf den Punkt tippen und sagen, das soll ein Zwischenziel werden.
2. Es werden die Luftlinien zwischen den Punkten verwendet und nicht die gefahrenen Strecken.
3. Du legst den Start und Endpunkt fest und dann wird die beste Reihenfolge festgelegt
4. Ob es wirklich die beste Reihenfolge berechnet wird, sei dahingestellt. Ich war über das Tempo verwundert der Berechnung verwundert. Die Osmandentwickler neigen dazu Näherungslösungen zu verwenden, anstatt das Problem rechenintensiv exakt zu lösen.

Yesterday I tried to connect 50 POIs in Locus, it was so pissed of, so I gave Osmand a chance. Osmand calculated in some seconds the best order of the points. And if I was not happy about the result, I was able to change the order of the point by drag and drop.

In Locus you have the option to insert via-points automaticly, but this option is faulty like I have shown in https://help.locusmap.eu/topic/not-able-to-set-a-shape-point-in-the-route-planner#comment-67788

In Osmand you are also able to see the distance to a via point, in Locus it is a torture to figure out the distance to a via point.

So it could be Osmand is the better solutuin for you.