Discussion :

[gb-ch]

Bonjour,

J'aimerais développer un script en PHP qui permette à l'utilisateur de saisir une ville de départ et une ville d'orgine. Puis, le script calcul la "route" (itinéraire) et donne quelques étapes (villes) intermédiaires.

Je cherche des idées, expériences, méthodes, algorithmes, etc. J'ai charché un peu mais sans succès. À priori, je me dis qu'il faut stocker dans une table chaque "villes-villes" chaque relation "1 à 1" entre une ville (étape) et l'autre. Un travail initial immense de saisie. Chaque étape (ville) serait donc reliée à une autre et le script tracerait la "route".

Est-ce plus compliqué que cela? Des idées, morceaux de codes ou logiques?

Pour info, l'itinéraire ne doit pas être "déssiné" comme sur mappy.fr ou viamichelin.fr mais simplement donné textuellement.

Exemple:
input: Rome-Londres
output: Rome-Milan-Genève-Paris-Londres

(niveau de "granularité" assez grossier

Merci pour votre aide!

[Mr N.]

Cadeau (quoique) :
http://fr.wikipedia.org/wiki/Recherche_opérationnelle
http://fr.wikipedia.org/wiki/Théorie_des_graphes
http://fr.wikipedia.org/wiki/Problème_du_voyageur_de_commerce
...
Prévoit une boîte d'aspirine ^^

[gb-ch]

Merci Mr N.!

En effet, je crois que l'aspirine va être nécessaire... ;-)

As-tu (ou qqn) d'autre déjà confonté à ce genre de problème? Je ne dois pas (en tout cas pas initialement) aboutir à une solution très évoluée mais à une détermination d'itinéraire de base.

Merci d'avance pour votre aide!

[Mr N.]

Non, à part en cours et ça m'a suffit. J'espère ne pas avoir à tomber sur un projet comme ça... ch'uis pas fou

[gb-ch]

OK, merci bcp quand même, je crois aussi que l'Algorithme de Dijkstra http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra peut être utile à ceux qui se confrontent à ce même problème.

Toutefois, je suis étonné que, bien que complexe ce problème "banal" n'ait pas produit plus de codes libres ou disponibles dans une communauté comme celle de PHP...

[Mr N.]

Pourquoi faire ? on implémente pas un algorithme pour le plaisir. C'est en fonction d'un but, d'un besoin particulier. Et surement que ceux qui font du php, ne font pas des applications qui requiert la Théorie des graphes.

Surtout que dans ton cas, il va falloire construire ton graphe, c'est à dire toutes les villes avec les routes et les distances... Là je reconnais qu'une telle base de données open source serait sympa.

[arh_il]

Bonjour,
j'ai le meme probleme en langage java, et j'utilise une base de donnée d'une liste de villes avec leur latitudes et leur longitude
je vous prie de m'aider ,comment on construit le graphe ou il faut juste utilisé dijkstra directement?merci

[Finidrigoler]

excusez moi, si le but c'est simplement de se torturer l'esprit, auquel cas, je serais hors sujet, mais sinon..


gb-ch, en gros, tu veux un webservice de cartographie.


http://www.maporama.com/home/fr/prod...b_services.asp
( celui ne semble pas permettre le point par point )


http://ws.viamichelin.com/wswebsite/...eyFeatures.jsp

( RouteCalculation )

Pour info, l'itinéraire ne doit pas être "déssiné" comme sur mappy.fr ou viamichelin.fr mais simplement donné textuellement.

car ça serait ici que tu te tromperais,
j'ai deja utilisé viamichelin,
et il ( le webservice )
renvoie bel et bien chaque "ville de passage" dans ton trajet, et ce au format texte


regarde la documentation.

[gloubi]

Avec de la chance, j'ai encore un dijikstra, un bell et un floyd en C/C++ (VC++6) que j'avais codé lors de mes études...
Si tu veux, je peux essayer de te les retrouver

[Are-no]

J'ai essayé de fair le même genre de truc mais en plus simple, juste donner les distance de ville à ville.

Voir www.paysdebray.eu rubrique etablissement

J'ai récuperé les coordonées GPS des villes qui m'interessé (plus de 200) et après c'est que du calcule.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
$distance = 6366 * acos(cos(deg2rad($lat_a)) * cos(deg2rad($lat_b)) * cos(deg2rad($long_b)-deg2rad($long_a))+sin(deg2rad($lat_a)) * sin(deg2rad($lat_b)));

Et ça me donne une distance en Km (les long et lat doivent être en degré decimaux)

De là tu peut avoir toute des distances de ville à ville.

Ma table contiens aussi le nombre d'habitant, à partir de là tu peut faire une selection de ville "importante" (qui sont souvent relié pas des grands axes routier) et faire un algorithme qui par exemple l'oblige à calculé la distance mais en passant par d'autre ville suivant leur impotance.