1 Formulation du Problème 1.1 Notations Pour bien modéliser le problème, on int

1 Formulation du Problème 1.1 Notations Pour bien modéliser le problème, on introduit un ensemble de notation mathématique suivant: B: l'ensemble des bus du réseau indexé par b N b: l'ensemble des n÷uds visité par b Ab: l'ensemble des arcs parcouru par b NIb: l'ensemble des n÷uds intermédiaires de b AIb: l'ensemble des inter-arcs de b ob: l'ensemble des dépôts origines de b db: l'ensemble des dépots destinations de b 1.2 Description du réseau Pour chaque bus b donné, le réseau est décrit sous forme de graphe com- posé d'un ensemble N b des n÷uds visité par le bus b et d'un ensemble Ab des arcs parcouru par ce dernier. L'ensemble des graphes du réseau est donné par Gb = N b, Ab 1.2.1 L'ensemble des n÷uds du réseau Dans notre cas d'étude, l'ensemble des n÷uds du réseau sera dé ni comme suit:  Des N÷uds sources qui représentent les n÷uds dépôts (soit′origine ou la destination) . Ils sont représentés ici par les dépôts de Ouakam et de Thiaroye .  Des N÷uds intermédiaires qui sont les lieux de passage des bus pen- dant une période de la sortie du bus de son dépôt d'origine jusqu'à son entrée dans son dépôt de destination. NB: le même dépôt peut représenter le dépôt d'origine et de destination d'un bus donné 1.2.2 L'ensemble des arcs du réseau On considère le couple (i, j) comme étant l'ensemble des arcs du réseau. Chaque bus du réseau a un dépôt d'origine et destination. Ainsi on a:  Des Arcs de début ou de n: on dit que (i, j) est un arc de début (respectivement de n) si i (respectivement j) est un dépôt. On évite les trajets entre dépôt i.e i et j soient tous des dépôts en même temps.  Des Inter-arcs: ceux sont les arcs formés par les n÷uds intermédiaires 1 i.e i et j sont tous diérents des dépôts. 1.3 Variables Plusieurs variables sont associées à notre problème et représentent les dé- cisions à prendre. Les variables de décision Xb i,j sont des variables binaire pour aecter le choix des bus aux diérents arcs du réseau. Elles sont dé nies comme suit: Xb i,j =  1 si le bus b couvre l′arc (i, j) ∈Ab 0 sinon. Pour exprimer les contraintes du problème, on dé nit les variables intermé- diaires suivantes : Une variable entier qui nous permettra de déterminer ex- actement les heures de départ de chaque bus aux diérents n÷uds i ∈N b.On la note par Hb i . Une variable binaire Y b dé nie par Y b =  1 si le bus b est utilis dans la solution 0 sinon. *Paramètre: On note par tb i,j le temps mis par le bus b pour parcourir l'arc (i, j) et db i,j la distance parcourut par b sur l'arc (i, j). Lorsqu'un bus b ∈B de la otte est utilisé durant une période, on lui associe un coût xe CDb d'utilisation du bus, un coût kilométrique c'est- à-dire, le coût d'utilisation des arcs du réseau par les bus CKb et un coût horaire CHb Pour chaque heure de départ, on dé nit un intervalle de temps à ne pas dépasser c'est-à-dire Hb i ∈  eb i, lb i  et ceci est valable au niveau de chaque n÷ud mais pas forcement pour les dépôts. 1.4 Fonction objectif L'objectif de notre problème en premier lieu est de minimiser le coût xe d'utilisation des bus ensuite de minimiser le coût d'utilisation des arcs du réseau par les bus et en dernier lieu de minimiser les temps d'attente des bus aux niveaux des arrêts et terminus. Nous appelons F la fonction objectif associé au problème avec X l'ensemble 2 des variables du problème: F(X) = min X b∈B CDb∗Y b+ X b∈B X (i,j)∈Ab CKb∗Xb i,j∗db i,j+ X b∈B X (i,j)∈AIb CHb∗Hb i ∗tb i,j (1) 1.5 Contraintes On dé nit:  Deux contraintes qui obligent chaque bus à commencer ses courses à son dépôt d'origine et de les nir à son dépôt de destination : ∀b ∈B : X j∈Nb⧸(ob,j)∈Ab Xb ob,j = 1 (2) ∀b ∈B : X i∈Nb⧸(i,db)∈Ab Xb i,db = 1 (3)  Une contrainte qui indique que l'heure de départ au n÷ud j (ou l'heure d'arrivée si j = db) doit être supérieure ou égale à l'heure de départ du service au noeud i (ou l'heure départ au dépôt si i = ob) plus le temps de parcourt de l'arc (i, j) : ∀b ∈B, ∀(i, j) ∈Ab : Hb j −(Hb i + tb i,j) ≥0 (4)  Une contrainte qui assure le respect de la fenêtre temporelle pour les heures de début de service: ∀b ∈B, ∀i ∈NIb : eb i ≤Hb i ≤lb i (5)  Et en n trois contraintes qui exige le domaine de variabilité des variables de ux: ∀b ∈B, ∀(i, j) ∈Ab, Xb i,j ∈{0, 1} (6) ∀b ∈B, Y b ∈{0, 1} (7) ∀b ∈B, ∀i ∈Ab, Hb i ∈N (8) 3 Alors le problème sera donc soumis à ces six contraintes suivantes: ∀b ∈B : X j∈Nb⧸(ob,j)∈Ab Xb ob,j = 1 (2) ∀b ∈B : X i∈Nb⧸(i,db)∈Ab Xb i,db = 1 (3) ∀b ∈B, ∀(i, j) ∈Ab : Hb j −(Hb i −T b i,j) ≥0 (4) ∀b ∈B, ∀i ∈NIb : eb i ≤Hb i ≤lb i (5) ∀b ∈B, ∀(i, j) ∈Ab, Xb i,j ∈{0, 1} (6) ∀b ∈B, Y b ∈{0, 1} (7) ∀b ∈B, ∀i ∈Ab, Hb i ∈N (8) 4 uploads/Ingenierie_Lourd/ graphic-age.pdf

Tags
Ingénierie l'ensemble réseau n÷uds dépôt variables
Documents similaires
  • 80
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager