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.)
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)
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.
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.
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.
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.
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;
À 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;
Duh
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.
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
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.
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.
Puis on appuie sur "play" et on a le résultat:
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.
À venir:
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