OpenStreetMap Forum

SunCobalt

Member

From: Eislingen

Registered: 2010-01-09

Posts: 3,810

Re: Java-Bibliotheken für Routing gesucht

Was ist also Radrouting?

Kommt drauf an ob legal oder, wie Du schreibst, Einbahnstraßen ignoriert werden. Der Rest ist eine Frage des Malus/Bonus Systems. Wobei da nicht nur Wege (u.A. Primary und Steps hast Du in Deiner Aufzählung vergessen) oder Eigenschaften von Ways (bspw cobblestone) sondern auch Nodes (bspw cycle barrier) berücksichtigt werden müssen.
aighes ist hier einer der Experten dafür. Falls er nicht mitliest, schreib ihn mal an

---

Thomas

EvanE

Member

Registered: 2009-11-30

Posts: 5,716

Re: Java-Bibliotheken für Routing gesucht

Aber würde mich doch jetzt glatt mal interessieren, was ein sinnvolles Rad-Routing überhaupt ist.
Annahme: Man ignoriert, motorways und trunks. Nimmt an, dass man secondaries und tertiaries befahren kann. Residentials sowieso. Geht davon aus, dass Fahrradfahrer für gewöhnlich notfalls auch Einbahnstraßen ignorieren, von Abbiegevorschriften ganz zu schweigen... evtl. notfalls auch den Fußweg nehmen oder auf Schotterpisten fahren, jedoch Matschwege (Grade5) doch lieber Wanderern mit Gummistiefeln überlassen .... hmmm.... ????
Was ist also Radrouting?

Es gibt nicht ein Radrouting sondern viele, je nach den Bedürfnissen der unterschiedlichen Radfahrergruppen.

Beim Garmin Oregon z.B. gibt es Cycling, Tour_Cycling und Mountain_Biking.
Beim Mio Cyclo 300 gibt es Stadtrad, RennRad und Mountainbike.

Nach meiner Meinung gibt es mindestens vier Nutzertypen.
  -  Stadtrad: Liebt es gemütlich und sicher, kein sportlicher Ehrgeiz.
     Bevorzugt Radwege und Seitenstraßen.
  -  Rennrad: Liebt es schnell zu fahren, oft auch mit sportlichen Ehrgeiz.
     Bevorzugt glatte Straßen und Wege.
  -  Mountainbike: Nimmt auch mal gerne kleine schwierige Wege.
     Wirtschafts- und Waldwege sind kein Problem.
  -  Tourenfahrer: Fährt gerne Strecken abseits der großen Straßen.
     Feld- und Waldwege (grade=1/2, zum Teil grade=3) sind kein Problem.
     Ein Mittelding zwischen Rennrad (Strecke) und MTB (muss nicht alles glatt sein).

Es gibt natürlich nicht "den" MTBler, da gibt es viele Abstufungen, vom Tourenfahrer, der auch mal schwierige Wege fahren will, bis zum Downhill-Freak.

Edbert (EvanE)

pimapper

Member

From: Pinneberg

Registered: 2008-07-18

Posts: 53

Re: Java-Bibliotheken für Routing gesucht

Kernfrage: Macht es da eigentlich noch Sinn über "Routing" zu diskutieren?
Ich meine, ein Routing soll mir ja helfen, den schnellsten oder kürzesten Weg von A nach B zu finden.
Ob es geeignet ist, möglichst viele Umwege zu fahren, damit bestimmte Matschpisten möglichst dreimal umrundet werden und danach zur nächstgelegenen Dusche zu routen...
Ich denke, dass es sinnvoll ist, ein Fahrrad als Verkehrsmittel zu betrachten. Nicht unbedingt als Sportgerät.

mmd

Member

Registered: 2010-11-06

Posts: 2,150

Re: Java-Bibliotheken für Routing gesucht

.

Last edited by mmd (2012-10-19 19:16:17)

ikonor

Member

Registered: 2010-11-08

Posts: 637

Website

Re: Java-Bibliotheken für Routing gesucht

Wie sieht's mit Höhenmetern aus? Bisher habe ich noch keinen guten Router gefunden, bei dem ich Start-/Endpunkt sowie einen gewünschten Bereich an Höhenmetern (min/max) definieren kann und dann automatisch passende Routen vorgeschlagen werden. OSRM bspw.

Der einzige Router, den ich kenne, der Rundkurse vorschlägt, ist http://www.komoot.de/

Beim MTB-Profil gibt es eine "Alpin"-Einstellung, weiß aber nicht, ob das jetzt Höhenmeter meint oder nur Pfade bevorzugt. Ich komme mit Komoot allerdings nicht so klar, liefert mir zu viele Vorschläge mit Rückweg auf gleicher Strecke und ist mir zu sehr auf abklappern von POIs fixiert.

Eine Alternative ist die Suche bei einem Tourenportal, z.B. http://www.gpsies.com/trackList.do mit u.a. Länge von/bis und Gesamtanstieg von/bis.

Gruß,
Norbert

ikonor

Member

Registered: 2010-11-08

Posts: 637

Website

Re: Java-Bibliotheken für Routing gesucht

Kernfrage: Macht es da eigentlich noch Sinn über "Routing" zu diskutieren?

Ja, zumindest ein Teil der Anforderungen ist bestimmt auch mit einem normalen Routing-Algo zu lösen. Wir können es von mir aus aber auch "softwaregestützte Freizeit-Tourenplanung" nennen.

Ich meine, ein Routing soll mir ja helfen, den schnellsten oder kürzesten Weg von A nach B zu finden.

Mir nicht. Mir soll es helfen, den ruhigsten und schönsten Weg von A über B, C und D wieder zurück nach A zu finden. Umwege nehme ich in Kauf. Die Zwischenpunkte setze ich im einfachen Fall so lange selbst, bis das Ergebnis passt. Zwischen den Punkten ist es jeweils wieder A nach B Routing mit Gewichtung zusätzlich zur Länge/Geschwindigkeit. Und je passender das Routing, desto weniger Zwischenpunkte muss ich setzen, um die Route zu korrigieren.

Ich denke, dass es sinnvoll ist, ein Fahrrad als Verkehrsmittel zu betrachten. Nicht unbedingt als Sportgerät.

Da machst Du es Dir als Entwickler halt einfach, blendest damit aber die Zielgruppe der Outdoor-Navis aus.

Ich gebe zu, es ist nicht einfach zu definieren, was z.B. "ruhig" und "schön" ist und jeder hat da andere Vorstellungen. Deshalb wäre für mich ein guter Rad/Freizeit-Router vor allem eines: konfigurierbar. Zum Beispiel wie bei Routino oder den verschiedenen Garmin-Karten.

Gruß,
Norbert

EvanE

Member

Registered: 2009-11-30

Posts: 5,716

Re: Java-Bibliotheken für Routing gesucht

Kernfrage: Macht es da eigentlich noch Sinn über "Routing" zu diskutieren?
Ich meine, ein Routing soll mir ja helfen, den schnellsten oder kürzesten Weg von A nach B zu finden.
Ob es geeignet ist, möglichst viele Umwege zu fahren, damit bestimmte Matschpisten möglichst dreimal umrundet werden und danach zur nächstgelegenen Dusche zu routen...
Ich denke, dass es sinnvoll ist, ein Fahrrad als Verkehrsmittel zu betrachten. Nicht unbedingt als Sportgerät.

Ja es macht Sinn, auch Routing für den Freizeit-Bereich vorzusehen.
Schließlich ist das beim Radfahren und Wandern oft der Hauptzweck. Beim Auto mag das anders sein, aber schon die Motorradfahrer wünschen sich auch die Berücksichtigung/Bevorzugung von 'schönen' Strecken.

Beim Radfahren sind die Wünsche je nach Ausprägung (Stadt, Tour, MTB, Rennrad) sehr unterschiedlich. Und in der Freizeit sind Rundtouren durchaus gewünscht. Schließlich will man oft am Ende seiner Tour wieder zurück nach Hause. Und was die Höhenmeter und die Steilheit angeht sind die Wünsche durchaus verschieden. Der Eine will möglichst wenige und wenn dann sanfte Anstiege (z.B. Familien-Ausflug), während das für den Anderen gerade die sportliche Herausforderung ist (z.B. Rennrad, MTB).

Edbert (EvanE)

pimapper

Member

From: Pinneberg

Registered: 2008-07-18

Posts: 53

Re: Java-Bibliotheken für Routing gesucht

Weichen wir jetzt nicht ein wenig vom eigentlichen Thema Java-Bibliothek für Routing gesucht ab?

Natürlich kann ein normaler Router die Kosten aufgrund von Straßenbeschaffenheiten bewerten und entsprechend die "schönsten" Strecken wählen, wenn diese z.B. nicht länger als z.B. Faktor 1.5 der kürzesten Strecke sind. Das sollte eigentlich jeder Router können.
Ist nur eine Frage der Bewertung der Weg-Typen.

Die meisten der obigen Fragestellungen sind Sonderlocken.
z.B. Aneinanderkettungen von Teil-Routen, manuelle Eingriffsmöglichkeiten oder eben Rundreiseprobleme (TSP).

EvanE

Member

Registered: 2009-11-30

Posts: 5,716

Re: Java-Bibliotheken für Routing gesucht

Die meisten der obigen Fragestellungen sind Sonderlocken.
z.B. Aneinanderkettungen von Teil-Routen, manuelle Eingriffsmöglichkeiten oder eben Rundreiseprobleme (TSP).

Nun ja, es gibt einfach die Frage ein Ausgangs-/Endpunkt und eine Rundstrecke mit xx km oder yy Stunden usw. Das Mio-Cyclo hat so eine Funktion (SurpriseMe Modus) implementiert. Das hat nun wenig mit dem Traveling Salesman Problem (Optimierung der Reihenfolge vorgegebener Anlaufpunkte) zu tun. Hier ist nur ein Punkt festgelegt.

Edbert (EvanE)

ikonor

Member

Registered: 2010-11-08

Posts: 637

Website

Re: Java-Bibliotheken für Routing gesucht

Weichen wir jetzt nicht ein wenig vom eigentlichen Thema Java-Bibliothek für Routing gesucht ab?

Ich will das jetzt auch nicht weiter vertiefen. Ich wollte nur die Gelegenheit nutzen - wenn schon mal zwei Autoren da sind - und Werbung für ein Anwendungsgebiet machen, das im Gegensatz zur Autonavigation noch nicht so gut abgedeckt ist.

Und um zurück zum Thema zu kommen:

@TrafficJam: seit ihr mit GeoTools noch klargekommen oder habt ihr was anderes verwendet?

Gruß,
Norbert

karussell

Member

Registered: 2012-07-26

Posts: 104

Re: Java-Bibliotheken für Routing gesucht

> Weichen wir jetzt nicht ein wenig vom eigentlichen Thema Java-Bibliothek für Routing gesucht ab?

Nö, oder ? Was heißt denn Routing? Nur kürzesten/schnell Wege?

Ich denke, es sind eher "beste" Wege und da ist multi-attribute halt das allgemeinste und (noch) kompliziertere ... allerdings sobald mehr als 2 (oder 3) punkte involviert sind tritt der traveling salesman auf, was dann für mich ne andere problemstellung als routing wäre...

aber danke allen für den input !

so ne fahrradgeschichte, am besten kombiniert mit DB, wäre cool und ist durch nen trick auch praktisch möglich. mal schauen was die nächsten monate so bringen.

---

graphhopper.com route planning for your software

EvanE

Member

Registered: 2009-11-30

Posts: 5,716

Re: Java-Bibliotheken für Routing gesucht

...
Ich denke, es sind eher "beste" Wege und da ist multi-attribute halt das allgemeinste und (noch) kompliziertere ... allerdings sobald mehr als 2 (oder 3) punkte involviert sind tritt der traveling salesman auf, was dann für mich ne andere problemstellung als routing wäre...
...

Ich glaube du verwechselt da zwei Dinge:
  -  Traveling Salesman (T-S) hat als Aufgabenstellung:
      Ich will x Punkte anfahren, suche mir die günstigste Reihenfolge
      mit der insgesamt optimalen (nach den vorgegebenen Kritereien)
      Route heraus. (Oft auch mit Rückkehr zum Startpunkt)
  -  'Normales' Routing hat als Aufgabenstellung:
      Ich will von A nach E mit den Zwischenpunkten B, C und D.

Der Unterschied ist bei T-S ist die Reihenfolge der Punkte variabel (und zu optimieren), während beim normalen Routing die Reihenfolge der Zwischenpunkte vorgegeben ist. Sofern der Abstand (Luftlinie) zwischen zwei aufeinanderfolgenden Punkten geringer ist als der Abstand zwischen den Endpunkten, dürfte dies das Routing sogar erleichtern, da kürzere Teilstrecken zu berechnen sind.

Selbst bei Rundstrecken dürfte sich die Berechnung vereinfachen, da die Unterteilug in mehrere Teilstrecken die Komplexität reduziert.

Edbert (EvanE)

karussell

Member

Registered: 2012-07-26

Posts: 104

Re: Java-Bibliotheken für Routing gesucht

> Ich glaube du verwechselt da zwei Dinge:

nee, meinte ich so. nur hatte ich es so verstanden dass man bei bestimmten POI vorbei will und die reihenfolge eben nicht fest steht. egal ...

---

graphhopper.com route planning for your software

EvanE

Member

Registered: 2009-11-30

Posts: 5,716

Re: Java-Bibliotheken für Routing gesucht

> Ich glaube du verwechselt da zwei Dinge:

nee, meinte ich so. nur hatte ich es so verstanden dass man bei bestimmten POI vorbei will und die reihenfolge eben nicht fest steht. egal ...

Aus meiner Erfahrung mit Outdoor-Navis kenne ich nur die Variante mit der festgelegten Reihenfolge. Ob es PKW-Navis gibt, die auch die Reihenfolge optimieren können (dann wirklich das Travelling Salesman Problem), entzieht sich meiner Kenntnis.

Edit: Wir meinte beide schon das Richtige. Nur in der Frage der Reihenfolge hatten wir unterschiedliche Voraussetzungen und kamen daher zu anderen Schlußfolgerungen.

Edbert (EvanE)

Last edited by EvanE (2012-08-26 13:35:08)