Pathfinding avec notion d'horaires

Fermé
deedllit Messages postés 5 Date d'inscription mercredi 11 avril 2007 Statut Membre Dernière intervention 13 avril 2007 - 11 avril 2007 à 16:54
deedllit Messages postés 5 Date d'inscription mercredi 11 avril 2007 Statut Membre Dernière intervention 13 avril 2007 - 13 avril 2007 à 21:40
Bonjour,

Je cherche à crée une sorte d'algo de "pathfinding" avec une notion d'horiare et de lignes.

Le but est de crée un système pour trouver des correspondances.
Par exemple le bus qui va de A à C en passant par D fait 2h, départ 06h00, 07h00, ....

Le bus qui va de A à B fait 40 min
Départ 06h00, 08h00....

Le bus qui va de B à C fait 20 min
Départ 06h30, 07h00, ...

En gros si on pars à 6h il est plus rentable de passer par A ... B ca on fait
06h00 -> 06h40
on attend celui de 07h00
07h00 -> 07h20

Par contre si on rate son bus il est préférable de prendre celui qui passe par à 7h en passant par D.

Une idée d'un algo de cette ordre?
J'avoue avoir essayer à taton mais dès qu'il y a bcp de connections... c'est pas super....

Je suis ouvert à vos idées :)

Merci
Deed

3 réponses

blux Messages postés 26845 Date d'inscription dimanche 26 août 2001 Statut Modérateur Dernière intervention 7 mai 2025 3 338
11 avril 2007 à 16:59
Salut,

tu vas mourir !

https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce
ou le problème du sac à dos...

Ca, c'est juste un début, on n'a pas encore la notion d'horaires (contraintes en plus)...
0
deedllit Messages postés 5 Date d'inscription mercredi 11 avril 2007 Statut Membre Dernière intervention 13 avril 2007 1
12 avril 2007 à 13:08
Oauis le voyageur de commerce et le problème du sac à dos je l'ai deja fait plein de fois :)

J'avais même développer un voyageur de commerce, basé sur le système du plus proche voisin avec un notion d'anticroissement ^^ pour le projet dans un cours de R & D. Ca marchait pas mal...

Faire les pacours il n'y aucun problème ^^ enfin pas trop
la ou je peine justement c'est pour les contraintes sur les horaires.... encore la c'est facile c'est à l'heure mais imaginons qu'on combine ca avec des avions, train... des jours fériés... des bus qui fonctionne que le dimanche, ....

C'est surtout sur que j'aimerais avoir une idée. :)

Deed
0
blux Messages postés 26845 Date d'inscription dimanche 26 août 2001 Statut Modérateur Dernière intervention 7 mai 2025 3 338
12 avril 2007 à 13:49
Système Expert ? IA ?
0
deedllit Messages postés 5 Date d'inscription mercredi 11 avril 2007 Statut Membre Dernière intervention 13 avril 2007 1
13 avril 2007 à 21:40
Système Expert oauis je suis d'accord mais j'ai aucune exp. comment faire ca.

Tu connais un site sympa qui explique ca ?

Mais c'est quand meme un truc de fous, ou quand il y a bcp de contraintes t'es plus vraiement sur de la réaction. J'essai de le faire pour le Net donc.... je me demande également comment le faire assez rapidement... et en quel langage.

J'aimerais bien monté ca sur un serveur Lotus Notes mais le script c'est pas super rapide. A travers une API C.

Merci
A+

Deed
0