Application : itinéraire multiple étape qui choisi le trajet le plus optimal

Bonjour à tous,

Je cherche une application où je lui indique un point de départ, point d’arrivée tout en rajoutant des étapes.
L’ordre des étapes est choisi en fonction de ce qui est le plus optimal en matière de KM/durée…
(édit : comme dit @cquest, c’est le fameux « problème du voyageur de commerce »)

Je cherche principalement pour le vélo mais ça m’intéresse aussi pour la voiture.

ça peut être une application web du moment qu’il est possible d’exporter la trace sous format GPX. Et même je préfère que ce soit une application WEB pour pouvoir l’utiliser depuis le PC pour ensuite exporter.

Je vous remercie par avance du partage si vous en connaissez.
Bon week-end

BRouter est celui que j’utilise:
https://brouter.de/brouter-web/#map=12/46.3501/-0.5006/cyclosm

différents profils peuvent etre appliqués (voiture, vélo de route, rando, et même « fluvial » pour moi qui navigue…) et avec des alternatives proposés.

Pour le paramètre « optimal » c’est un peu propre a soit, mais BRouter je trouve te donne pas mal d’alternatives a toit après de choisir celle qui te conviendrait le mieux.

1 Like

Merci @PierreV. Je connaissais de nom BRouter. Je viens de tester et c’est assez puissant. Actuellement, j’utilise Géovélo.

ça remplit pas totalement ce que je cherche. L’ordre des étapes on est obligé d’optimiser soi-même.

Ce que je trouve beaucoup moins pratique par rapport à Géovélo ou Google Maps, c’est le fait de ne pas pouvoir inverser l’ordre des étapes une fois que ça a été positionné. (Ou alors j’ai pas trouvé).

ah j’avais pas compris que tu souhait donner des points mais pas leur « ordre »…

pour l’inversion tu as le logo:
image
ou la touche R

En faite c’est pas inverser le sens de tout le trajet que je souhaite. Je souhaite juste modifier l’ordre de certaines étapes.

Sur Géovélo, il suffit de bouger les étapes dans la liste comme Google Maps

1 Like

J’utilise simplement OSMAnd. J’ai aussi entendu beaucoup de bien de Komoot.

C’est le fameux « problème du voyageur de commerce », non ?

1 Like

Je ne connaissais pas, c’est tout à fait ça. J’identifie des antennes sur RNCMobile par exemple et j’ai besoin de savoir quel itinéraire est le plus optimal.
Idem quand je dois me rendre sur place pour de multiple identifications OSM sur le terrain/prendre des photos.
ex : références des PMZ, bornes incendies…

Valhalla fait ça, OSRM et graphopper aussi à ce qu’il me semble

https://valhalla.github.io/demos/optimized_route/

La doc de l’API est là: valhalla-docs/optimized/api-reference.md at master · valhalla/valhalla-docs · GitHub

La doc de l’API est là: valhalla-docs/optimized/api-reference.md at master · valhalla/valhalla-docs · GitHub

Je ne sais pas sur quelle URL tester. j’ai tester avec https://valhalla.openstreetmap.de/

ça fonctionne pas
https://valhalla.openstreetmap.de/optimized_route?json=%7B%22locations%22:%5B%7B%22lat%22:40.042072,%22lon%22:-76.306572%7D,%7B%22lat%22:39.992115,%22lon%22:-76.781559%7D,%7B%22lat%22:39.984519,%22lon%22:-76.6956%7D,%7B%22lat%22:39.996586,%22lon%22:-76.769028%7D,%7B%22lat%22:39.984322,%22lon%22:-76.706672%7D%5D,%22costing%22:%22auto%22,%22directions_options%22:%7B%22units%22:%22kilometers%22%7D%7D

Cet outil est aussi pas mal : OpenRouteService route planner - directions, isochrones and places mais je ne sais pas s’il fait ce que tu cherches.

Bonsoir ou bonjour, il y a in moment j’avais visionné un tuto YouTube décrivant comment « remplacer » le routage d’Osmand par BRouter … il me semble que c’était dans une série de tutos. Je ne me souviens plus, mais la manip’ était relativement complexe mais bien expliquée. Kenav’henta.

Hello !

C’est possible avec Geovelo:
Une fois le départ/arrivé séléctionné, tu peux faire clique droit sur carte a la position du point de passage souhaité puis « Définir comme point de passage » et le point va etre ordonné corectement selon l’algo du voyageur de commerce en théorie ! Y a plus qu’a répéter pour chaque point de passage !

2 Likes

Les différents calculateurs d’itinéraires ont des fonctions plus ou moins bonnes pour ce problème d’ordonnancement. OpenRouteService le fait en intégrant la librairie VROOM, qui peut gèrer aussi plusieurs véhicules et plein d’autres contraintes.

Voir la démo du projet :

http://map.vroom-project.org/

Disclaimer : je suis le dev principal de VROOM :wink:

3 Likes

VROOM interressant mais malheureusement ne fournit pas de solutions pour recuperer soit l’itinéraire soit l’ordonancement du parcours comme le permet OSRM et plante lamentablement quand on clique sur « store » :frowning: mais rapide. Peut être quand le projet sera plus abouti …
Pour info osmand permet egalement de realiser le TSP (travelling salesman problem) et ce avec des options interressantes (bouclage notamment) et est pour le moment le seul réel TSP hors ligne gratuit que j’ai trouvé.

OsmAnd permet l’ajout de plusieurs étapes et on peut en changer l’ordre très simplement dans la liste.
L’export GPX de l’itinéraire est également possible.



@CapitaineMoustache Est-ce que l’ordre peut-être choisis au plus optimal (problème du voyageur de commerce) ?

oui ! comme dit plus haut, sachant que tous les algorithmes de TSP implémentés dans les applications aujourd’hui sont des algorithmes heuristiques (non parfaits)

mais ce que cherche Cayenne c’est que l’optimisation/inversion des étapes soient faites automatiquement, et pas un « forcage » de l’utilisateur

2 Likes

un exemple de calcul de TSP avec Osmand sur cette video :

à partir de la minute 3:27 (mettre les commentaires pour avoir plus d’infos)