Discussion :

[hutak]

je travaille sur un problem d'optimisation qui vise a établir un planing de passage des trains sur chaque gare du réseau..alors svp si quelqu'un peut proposer quelque chose(idée,heuristique,algo...) pour m'aider,ça serait la bienvenue.merci d'avance

[ToTo13]

Bonjour,

c'est un problème de calendrier/Emploi du temps, ...
Donc un problème NP-complet que l'on ne peut résoudre de manière exhaustive.
Fais un recherche sur le forum et avec les mots clefs que je viens de te donner.

[benDelphic]

Du scheduling c 'est pas ce qu' il y a de facile !!!
si on savait un peut plus sur le problème ( les contraintes ), on pourrai peut etre t aider car pour quelques instances le scheduling peut être vu comme un problème d 'affectation , ou du BinPacking .... etc

[hutak]

mon principal problem c'est de saturer le réseau,en tout ya 7 contraintes mais celle qui pose probleme c'est les contrainte de sécurité(tmps entre deux trains,évitement de colision)car on a 3 neuds de croisement..

[ToTo13]

Bonjour,

donc je confirme ce que j'ai dit.
C'est un problème de calendrier sur lequel il te faudra interdire des zones.

[benDelphic]

As tu essayé de modéliser mathématiquement ? peut etre que c'est plus simple en programme mathématique en nombre entier ... si tu tien au graphe .. ton réseau ne sera pas que le réseau ferroviaire mais les contraintes temporelles apparaitrons sous formes de sommets, arcs ou arêtes imaginaires...

[hutak]

j'ai modéliser mathematiquement et j'ai obtenu un programme lineaire en variable bivalente {0,1} mais vu la taille du probleme l'éxécution d'une méthode éxacte est impossible vu le trés grand nombre de variables.donc la résolution va se faire avec une méthode approchée(heuristique ou méta-heuristique)le bleme c'est ke je réussis pa a trouver cette heuristiq

[pseudocode]

Dans ce genre de cas, essaye l'approche inverse : chercher toutes les configurations qui violent les contraintes. Les configurations restantes sont des candidats possibles, dont on pourra rechercher le "meilleur" élément.

[benDelphic]

Bivalent ? Tu es sur ? as tu inclus les contraintes temporelles ? moi je le voit plutôt en problème mixtes ( affectation+ temps sur les nœuds ) ce qui serte ne réduit pas sa difficulté . pour ce qui est des algorithmes je pense qu'une séparation et évaluation ( brunch and bound ) ferait l'affaire.