Problème

Projeter des variantes RefLignes construites au lieu de référence, sur une infra à la voie, en combinant des variantes tirées d'Agathe (pour les cas où on ne trouve pas de variante bout en bout.)

Modélisation

Problème de flot à coût minimum dans un graphe. On construit un graphe orienté, avec un noeud par pr-voie et un (ou plusieurs) arc entre deux noeuds s'il existe un itinéraire entre ces pr-voies. On peut mettre un coût sur chaque arc, correspondant à la longueur de l'itinéraire, (ou autre chose)

flowchart LR A1 --> B1 A1 --> B2 A1 --> B3 B2 --> C2 C1 --> D1 B2 --> C3 B3 --> C3 C2 --> D1 D1 --> E1 D1 --> E2

On ajoute une source, liée à tous les pr-voies du premier PR de la variante qu'on souhaite projeter, et un puit, lié à tous les pr-voies du dernier PR de la variante qu'on souhaite projeter.

flowchart LR S([S]) -.-> A1 A1 --> B1 A1 --> B2 A1 --> B3 B2 --> C2 C1 --> D1 B2 --> C3 B3 --> C3 C2 --> D1 D1 --> E1 D1 --> E2 E1 -.-> P([P]) E2 -.-> P

On va obliger une unité de flot à sortir de la source et une unité à rentrer dans le puit. L'optimiseur va nous trouver (s'il existe) le meilleur chemin entre la source et le puit.

Variables

Il y aura une variable par arc, qui vaudra 1 si cet arc est emprunté, 0 sinon. Ci-dessous, on les note <o>_<d>, ou <o> et <d> correspondent respectivement au noeud origine et destination de l'arc.

Fonction objectif

On souhaite minimiser le coût total, coût obtenu en multipliant le coût d'emprunt d'un arc par la valeur de la variable qui représente l'emprunt de cet arc.

Contraintes

Quantité de flot

Il faudra qu'exactement une unité parte de la source. La somme des variables représentant les arcs sortants de la source = 1. Même principe, à l'inverse, pour le puits.

Dans l'exemple ci-dessus, ça donne:

s_a1 = 1;
e1_p + e2_p = 1;

Conservation du flot

À chaque noeud, il faudra que le nombre d'unités entrantes = le nombre d'unités sortantes. Si un arc qui mène vers un noeud est epmrunté, un arc qui sort de ce noeud devra être emprunté.

Par exemple: a1_b2 = b2_c2 + b2_c3;

Nombres entiers

Duh

Imposition de passage par certains PR

Dans le graphe qu'on a vu jusqu'à maintenant, la seule solution possible passe par tous les PR.

Si on rajoutait un lien direct C3 -> E2, on pourrait trouver une solution qui ne passe pas par D.

flowchart LR S([S]) -.-> A1 A1 --> B1 A1 --> B2 A1 --> B3 C1 --> D1 B2 --> C2 B2 --> C3 B3 --> C3 C2 --> D1 C3 --> E2 D1 --> E1 D1 --> E2 E1 -.-> P([P]) E2 -.-> P

Dans un tel cas, si on souhaite imposer des points intermédiaires, on peut imposer une quantité de flot entrant ou sortant à certains PR.

Par exemple: c1_d1 + c2_d1 = 1

Implémentation Excel

Voir ce classeur

C'est super pour faire un POC rapide. Mais la dernière fois que j'ai vérifié, on était limité à 100 variables dans le solveur gratuit Excel. On atteint assez vite ce nombre avec de gros graphes.

Implémentation lp_solve

C'est l'occasion d'enfin tester lp_solve http://lpsolve.sourceforge.net/5.5/

La documentation est assez bien faite. On arrive relativement facilement à écrire manuellement un modèle qui fonctionne (au format .lp):

/* Objective function */
min: 1 * a1_b1 + 1 * a1_b2 + 1 * a1_b3 + 1 * b2_c2 + 1 * b2_c3 + 1 * b3_c3 + 1 * c1_d1 + 1 * c2_d1 + 3 * d1_e1 + 2 * d1_e2 + 0 * s_a1 + 0 * s_a2 + 0 * s_a3 + 0 * e1_p + 0 * e2_p;

/* Constraints */
s_a1 = a1_b1 + a1_b2 + a1_b3;
a1_b1 = 0;
a1_b2 = b2_c2 + b2_c3;
a1_b3 = b3_c3;
0 = c1_d1;
b2_c2 = c2_d1;
b2_c3 + b3_c3 = 0;
c1_d1 + c2_d1 = d1_e1 + d1_e2;
d1_e1 = e1_p;
d1_e2 = e2_p;
s_a1 = 1;
e1_p + e2_p = 1;

/* Integer definitions */
int a1_b1, a1_b2, a1_b3, b2_c2, b2_c3, b3_c3, c1_d1, c2_d1, d1_e1, d1_e2, s_a1, s_a2, s_a3, e1_p, e2_p;

L'IDE qui est l'option la plus facile à trouver dans les downloads est assez pratique. On écrit un modèle dans l'onglet source. arborescence

Puis on appuie sur "play" et on a le résultat: arborescence

On peut convertir notre modèle en d'autres formats: ça pourrait être pratique pour le tester avec d'autres solveurs.

Il faut chercher un peu plus pour trouver le download qui contient l'exécutable en mode CLI : https://sourceforge.net/projects/lpsolve/files/lpsolve/5.5.2.9/lp_solve_5.5.2.9_exe_win64.zip/download

Il contient, entre autres, un lp_solve.exe

On lui passe un nom de fichier .lp, éventuellement un nom de fichier où envoyer la sortie:

.\lp_solve.exe .\exemple.lp > output.txt

Et on obtient un fichier contenant le résultat:

Value of objective function: 5.00000000

Actual values of the variables:
a1_b1                           0
a1_b2                           1
a1_b3                           0
b2_c2                           1
b2_c3                           0
b3_c3                           0
c1_d1                           0
c2_d1                           1
d1_e1                           0
d1_e2                           1
s_a1                            1
s_a2                            0
s_a3                            0
e1_p                            0
e2_p                            1

On peut ajouter des paramètres -S1 à -S7 pour avoir plus ou moins de détails dans la sortie (valeurs des contraintes avec -S3 par exemple).

.\lp_solve.exe .\exemple.lp -S3 > output.txt

Il ne semble pas y avoir d'autres formats de sortie plus "faciles" à parser.

Implémentation Node.js

À venir:

Modélisation alternative

Un simple plus court chemin avec Djikstra pourrait aussi suffir.

J'ai l'impression que le modèle par flot à cout minimum est plus puissant:

Il me semble aussi qu'il permet plus facilement qu'un Djikstra d'ajouter d'autres types de contraintes ou de coûts