Modélisation mathématique et optimisation du FRTSP

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). 

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}.

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).