Modélisation mathématique et optimisation du FRTSP

Après avoir défini le problème FRTSP et étudier son comportement dynamique grâce au modèle de simulation à évènements discrets, nous allons nous intéresser dans le présent chapitre à l’optimisation de son processus décisionnel. D’abord nous étudions la nature combinatoire du FRTSP en montrant que la relaxation de plusieurs de ses contraintes le ramène au problème d’affectation généralisée. Un exemple numérique est présenté afin d’illustrer l’ensemble des contraintes et données du problème, plusieurs solutions sont également proposées pour saisir les enjeux de ce problème. Ensuite, nous nous intéressons à l’établissement du plan prédictif en formulant un PLVM pour réduire les temps d’attente des marchandises. Pour compléter cette approche, nous adapterons un algorithme de colonies de fourmis pour les instances de grande taille. Par la suite, nous proposons une approche par horizon glissant pour la replanification du FRTSP afin de prendre en compte des changements relatifs à la demande. Cette mise à jour du plan initial permet d’ajuster les décisions initiales de manière à minimiser les écarts dus au recalcul. Enfin, nous décrivons les processus de couplage simulation / optimisation, aussi bien dans le cas prédictif, que dans le cas de la replanification. 2. Un exemple numérique Avant de procéder à la formalisation mathématique du problème FRTSP, dans cette section, nous proposons un exemple numérique sur une instance réduite afin d’appréhender sa complexité. Cet exemple permet d’illustrer toutes les contraintes techniques et organisationnelles, présentées au chapitre 2. Nous allons proposer deux solutions pour cette instance afin de ressortir l’impact des différentes contraintes sur le processus d’exploitation, ainsi que les enjeux et l’intérêt d’une approche d’optimisation. Nous considérons une ligne ferroviaire composée de 4 stations de voyageurs, où il est possible de procéder aux chargements / déchargements des marchandises. Cette ligne est parcourue par 3 trains mixtes, à intervalle de 10 minutes. Enfin, 10 commandes doivent être transportées sur cette ligne, suivant des parcours différents (i.e. les stations de départs et d’arrivées varient d’une commande à une autre). L’exemple est illustré par la Figure V.1. Les autres caractéristiques du problème sont : – Nous considérons l’instant 0, comme le moment de début de l’exploitation. – Les 𝑙𝑡 et 𝑟𝑗 sont exprimées en minutes. – Les 𝑐𝑎𝑝𝑡 et 𝑄𝑗 sont exprimés en nombre de colis standards. – La distance entre deux stations successives est exprimée en durée de parcours (comme indiqué dans la Figure V.1, elle est égale à 5 min). – Comme conséquences directes de la conception de ce système de transport, aucune commande ne peut être déchargée dans la station 1 (les trains sont vides au départ). Aussi, aucune commande ne peut être chargée dans la station 4 (c’est le terminus pour les trains). Figure V.1 : Une illustration d’une instance numérique du FRTSP Nous proposons deux plans différents de transport des commandes, élaborés en appliquant des règles décisionnelles aléatoires. Ceci nous permettra de constater l’impact de toutes les contraintes sur l’activité de transport de marchandises, ainsi que l’importance du schéma décisionnel adopté. Le Tableau V.1 et le Tableau V.2 présentent ces deux plans. Les notations et formules suivantes sont utilisées : – Commandes disponibles pour le transport dans la station, lors du passage du train : 𝐶𝐷𝑖𝑠𝑝 – Commandes déchargées du train : 𝐶𝐷𝑐ℎ𝑔 – Commandes chargées dans le train : 𝐶𝑐ℎ𝑔 – Date d’arrivée à la station (min, secondes) : 𝐴𝑟𝑟𝑠 = { 𝑙𝑡 𝑠𝑖 𝑠 = 1 𝐷𝑒𝑝𝑠−1 + 5 𝑠𝑖𝑛𝑜𝑛 – Temps d’attente dans la station (secondes) : 𝑇𝑐ℎ𝑔 = 𝑚𝑎𝑥(∑ 𝑡𝑒𝑚𝑝𝑠 𝑑𝑒 𝑑é𝑐ℎ𝑎𝑟𝑔𝑒𝑚𝑒𝑛𝑡 + ∑ 𝑡𝑒𝑚𝑝𝑠 𝑑𝑒 𝑐ℎ𝑎𝑟𝑔𝑒𝑚𝑒𝑛𝑡, 𝑤𝑎𝑖𝑡𝑚𝑖𝑛) – Nombre de colis à l’intérieur du train : 𝑁𝑏𝑟𝐶𝑠 = { 𝑐𝑜𝑙𝑖𝑠 𝑐ℎ𝑎𝑟𝑔é𝑠 𝑠𝑖 𝑠 = 1 𝑁𝑏𝑟𝐶𝑠−1 − 𝑐𝑜𝑙𝑖𝑠 𝑑é𝑐ℎ𝑎𝑟𝑔é𝑠 + 𝑐𝑜𝑙𝑖𝑠 𝑐ℎ𝑎𝑟𝑔é𝑠 𝑠𝑖𝑛𝑜𝑛 – Date de départ de la station (min, secondes) : 𝐷𝑒𝑝𝑠 = 𝐴𝑟𝑟𝑠 + 𝑇𝑐ℎ𝑔 Le premier plan de transport se résume comme suit : – Train 1 : commandes transportées {2 ; 3 ; 4}. – Train 2 : commandes transportées {1 ; 8 ; 7 ; 6}. – Train 3 : commandes transportées {5 ; 9 ; 10}. Le temps d’attente moyen de chaque commande dans sa station de départ, avant son transport par un train, est égal à : 7 min. Les différentes contraintes ayant impacté l’élaboration de ce plan de transport, se présentent comme suit : j=1 ( ) File d’attente des trains t=1 ( ) t=2 ( ) t=3 ( ) j=2 ( 4) j=8 ( 2) 5min 5min 5min Temps d’attente : secondes secondes Temps de chargement d’1 colis : secondes j=3 ( ) j=4 ( 3) j=5 ( 4) j=9 ( 4) j=6 ( ) j=7 ( 4) j=10 ( 4) File d’attente des commandes – station 1 File d’attente des commandes – station 2 File d’attente des commandes – station 3 CHAPITRE V : Modélisation mathématique et optimisation du FRTSP 130 – La commande 1 n’a pas été chargée dans le train 1 à la station 1, parce que son chargement aurait nécessité une durée d’arrêt totale égale à 70 secondes (> 𝑤𝑎𝑖𝑡𝑚𝑎𝑥). – La commande 5 n’a pas été chargée dans le train 1 à la station 2, parce que son chargement aurait nécessité une durée d’arrêt totale égale à 70 secondes (> 𝑤𝑎𝑖𝑡𝑚𝑎𝑥). Aussi, la capacité du train a été atteinte (𝑐𝑎𝑝1 = 10). – Les commandes 6 et 7 n’ont pas été chargée dans le train 1, parce que le déchargement des commandes 3 et 4 a nécessité 60 secondes (= 𝑤𝑎𝑖𝑡𝑚𝑎𝑥). – La commande 5 n’a pas été chargée dans le train 2, bien que le temps d’attente fût suffisant dans la station 2. Cette décision, a permis le transport des commandes 6 et 7 par le train 2. En effet, le chargement de la commande 5 aurait requis 10 secondes d’attente supplémentaires dans la station 4, nécessaires à son déchargement.

Complexité du problème FRTSP

Nous avons présenté dans le chapitre 3, le problème d’affectation généralisée et mentionné sa complexité. En ce qui concerne le FRTSP, il est possible de le réduire à un problème d’affectation généralisée, en considérant un cas particulier que l’on représente dans la Figure V.2). La réduction du FRTSP peut être décrite comme suit : – La ligne est réduite à 2 stations seulement. – Toutes les commandes sont disponibles à l’instant 0, dans la première station, qui sera la seule station de départ. Ces commandes sont transportées vers l’autre station, qui sera l’unique station d’arrivée : ∀j ∈ J { rj = 0 depj = 1 arrj = 2 – Chaque commande j doit être transportée par un seul train. – Le planning de circulation des trains est connu à l’avance. Les trains sont mis en circulation à partir de la station 1 à intervalle régulier. – Les trains peuvent charger et transporter plusieurs commandes simultanément. Cependant, ils sont limités par une capacité maximum en nombre de colis standard. – Le temps de chargement d’un colis est négligeable. Ainsi, le temps d’attente des trains dans la station 1 est indépendant du nombre de colis chargés. – Le moment auquel un train t charge la commande j à la station 1, est égal dans ce cas au temps d’attente de cette commande dans sa station de départ (étant donné que 𝑟𝑗 = 0). Ainsi, le temps d’attente de la commande j sera directement égal à : 𝑥𝑗𝑡 ∗ 𝑙𝑡 (avec 𝑥𝑗𝑡 = 1 si la commande j est affectée au train t, 0 sinon)